Hubbry Logo
Automated planning and schedulingAutomated planning and schedulingMain
Open search
Automated planning and scheduling
Community hub
Automated planning and scheduling
logo
7 pages, 0 posts
0 subscribers
Be the first to start a discussion here.
Be the first to start a discussion here.
Automated planning and scheduling
Automated planning and scheduling
Automated planning and scheduling
View on Wikipedia
from Wikipedia
Part of a series on
Artificial intelligence (AI)
Major goals
Approaches
Applications
Philosophy
History
Controversies
Glossary

Automated planning and scheduling, sometimes denoted as simply AI planning,[1] is a branch of artificial intelligence that concerns the realization of strategies or action sequences, typically for execution by intelligent agents, autonomous robots and unmanned vehicles. Unlike classical control and classification problems, the solutions are complex and must be discovered and optimized in multidimensional space. Planning is also related to decision theory.

In known environments with available models, planning can be done offline. Solutions can be found and evaluated prior to execution. In dynamically unknown environments, the strategy often needs to be revised online. Models and policies must be adapted. Solutions usually resort to iterative trial and error processes commonly seen in artificial intelligence. These include dynamic programming, reinforcement learning and combinatorial optimization. Languages used to describe planning and scheduling are often called action languages.

Overview

[edit]
Further information: State space search

Given a description of the possible initial states of the world, a description of the desired goals, and a description of a set of possible actions, the planning problem is to synthesize a plan that is guaranteed (when applied to any of the initial states) to generate a state which contains the desired goals (such a state is called a goal state).

The difficulty of planning is dependent on the simplifying assumptions employed. Several classes of planning problems can be identified depending on the properties the problems have in several dimensions.

  • Are the actions deterministic or non-deterministic? For nondeterministic actions, are the associated probabilities available?
  • Are the state variables discrete or continuous? If they are discrete, do they have only a finite number of possible values?
  • Can the current state be observed unambiguously? There can be full observability and partial observability.
  • How many initial states are there, finite or arbitrarily many?
  • Do actions have a duration?
  • Can several actions be taken concurrently, or is only one action possible at a time?
  • Is the objective of a plan to reach a designated goal state, or to maximize a reward function?
  • Is there only one agent or are there several agents? Are the agents cooperative or selfish? Do all of the agents construct their own plans separately, or are the plans constructed centrally for all agents?

The simplest possible planning problem, known as the Classical Planning Problem, is determined by:

  • a unique known initial state,
  • durationless actions,
  • deterministic actions,
  • which can be taken only one at a time,
  • and a single agent.

Since the initial state is known unambiguously, and all actions are deterministic, the state of the world after any sequence of actions can be accurately predicted, and the question of observability is irrelevant for classical planning.

Further, plans can be defined as sequences of actions, because it is always known in advance which actions will be needed.

With nondeterministic actions or other events outside the control of the agent, the possible executions form a tree, and plans have to determine the appropriate actions for every node of the tree.

Discrete-time Markov decision processes (MDP) are planning problems with:

  • durationless actions,
  • nondeterministic actions with probabilities,
  • full observability,
  • maximization of a reward function,
  • and a single agent.

When full observability is replaced by partial observability, planning corresponds to a partially observable Markov decision process (POMDP).

If there are more than one agent, we have multi-agent planning, which is closely related to game theory.

Domain independent planning

[edit]

In AI planning, planners typically input a domain model (a description of a set of possible actions which model the domain) as well as the specific problem to be solved specified by the initial state and goal, in contrast to those in which there is no input domain specified. Such planners are called "domain independent" to emphasize the fact that they can solve planning problems from a wide range of domains. Typical examples of domains are block-stacking, logistics, workflow management, and robot task planning. Hence a single domain-independent planner can be used to solve planning problems in all these various domains. On the other hand, a route planner is typical of a domain-specific planner.

Planning domain modelling languages

[edit]

The most commonly used languages for representing planning domains and specific planning problems, such as STRIPS and PDDL for Classical Planning, are based on state variables. Each possible state of the world is an assignment of values to the state variables, and actions determine how the values of the state variables change when that action is taken. Since a set of state variables induce a state space that has a size that is exponential in the set, planning, similarly to many other computational problems, suffers from the curse of dimensionality and the combinatorial explosion.

An alternative language for describing planning problems is that of hierarchical task networks, in which a set of tasks is given, and each task can be either realized by a primitive action or decomposed into a set of other tasks. This does not necessarily involve state variables, although in more realistic applications state variables simplify the description of task networks.

Algorithms for planning

[edit]

Classical planning

[edit]
See also: Sussman anomaly

Action model learning

[edit]

Creating domain models is difficult, takes a lot of time, and can easily lead to mistakes. To help with this, several methods have been developed to automatically learn full or partial domain models from given observations. [2] [3] [4]

Reduction to other problems

[edit]

Temporal planning

[edit]

Temporal planning can be solved with methods similar to classical planning. The main difference is, because of the possibility of several, temporally overlapping actions with a duration being taken concurrently, that the definition of a state has to include information about the current absolute time and how far the execution of each active action has proceeded. Further, in planning with rational or real time, the state space may be infinite, unlike in classical planning or planning with integer time. Temporal planning is closely related to scheduling problems when uncertainty is involved and can also be understood in terms of timed automata. The Simple Temporal Network with Uncertainty (STNU) is a scheduling problem which involves controllable actions, uncertain events and temporal constraints. Dynamic Controllability for such problems is a type of scheduling which requires a temporal planning strategy to activate controllable actions reactively as uncertain events are observed so that all constraints are guaranteed to be satisfied. [5]

Probabilistic planning

[edit]
Main articles: Markov decision process and Partially observable Markov decision process

Probabilistic planning can be solved with iterative methods such as value iteration and policy iteration, when the state space is sufficiently small. With partial observability, probabilistic planning is similarly solved with iterative methods, but using a representation of the value functions defined for the space of beliefs instead of states.

Preference-based planning

[edit]
Main article: Preference-based planning

In preference-based planning, the objective is not only to produce a plan but also to satisfy user-specified preferences. A difference to the more common reward-based planning, for example corresponding to MDPs, preferences don't necessarily have a precise numerical value.

Conditional planning

[edit]

Deterministic planning was introduced with the STRIPS planning system, which is a hierarchical planner. Action names are ordered in a sequence and this is a plan for the robot. Hierarchical planning can be compared with an automatic generated behavior tree.[6] The disadvantage is, that a normal behavior tree is not so expressive like a computer program. That means, the notation of a behavior graph contains action commands, but no loops or if-then-statements. Conditional planning overcomes the bottleneck and introduces an elaborated notation which is similar to a control flow, known from other programming languages like Pascal. It is very similar to program synthesis, which means a planner generates sourcecode which can be executed by an interpreter.[7]

An early example of a conditional planner is “Warplan-C” which was introduced in the mid 1970s.[8] What is the difference between a normal sequence and a complicated plan, which contains if-then-statements? It has to do with uncertainty at runtime of a plan. The idea is that a plan can react to sensor signals which are unknown for the planner. The planner generates two choices in advance. For example, if an object was detected, then action A is executed, if an object is missing, then action B is executed.[9] A major advantage of conditional planning is the ability to handle partial plans.[10] An agent is not forced to plan everything from start to finish but can divide the problem into chunks. This helps to reduce the state space and solves much more complex problems.

Contingency planning

[edit]

We speak of "contingent planning" when the environment is observable through sensors, which can be faulty. It is thus a situation where the planning agent acts under incomplete information. For a contingent planning problem, a plan is no longer a sequence of actions but a decision tree because each step of the plan is represented by a set of states rather than a single perfectly observable state, as in the case of classical planning.[11] The selected actions depend on the state of the system. For example, if it rains, the agent chooses to take the umbrella, and if it doesn't, they may choose not to take it.

Michael L. Littman showed in 1998 that with branching actions, the planning problem becomes EXPTIME-complete.[12][13] A particular case of contiguous planning is represented by FOND problems - for "fully-observable and non-deterministic". If the goal is specified in LTLf (linear time logic on finite trace) then the problem is always EXPTIME-complete[14] and 2EXPTIME-complete if the goal is specified with LDLf.

Conformant planning

[edit]

Conformant planning is when the agent is uncertain about the state of the system, and it cannot make any observations. The agent then has beliefs about the real world, but cannot verify them with sensing actions, for instance. These problems are solved by techniques similar to those of classical planning,[15][16] but where the state space is exponential in the size of the problem, because of the uncertainty about the current state. A solution for a conformant planning problem is a sequence of actions. Haslum and Jonsson have demonstrated that the problem of conformant planning is EXPSPACE-complete,[17] and 2EXPTIME-complete when the initial situation is uncertain, and there is non-determinism in the actions outcomes.[13]

Deployment of planning systems

[edit]

See also

[edit]
Lists

References

[edit]

Further reading

[edit]
[edit]
Revisions and contributorsEdit on WikipediaRead on Wikipedia

Automated planning and scheduling

View on Grokipedia
from Grokipedia
Automated planning and scheduling is a subfield of artificial intelligence focused on the automated generation of action sequences, or plans, that enable intelligent agents to achieve predefined goals while optimizing resources, timing, and constraints. This process involves modeling problems in domains such as state transitions, temporal relations, and resource allocation, often using formal representations like the Planning Domain Definition Language (PDDL) to specify actions, preconditions, effects, and objectives. The field encompasses both planning, which derives high-level strategies or action orders to transform an initial state into a goal state, and scheduling, which assigns specific times and resources to those actions while respecting constraints like deadlines, capacities, and conflicts. Early developments centered on classical planning under restrictive assumptions—such as deterministic, fully observable, and static environments—using techniques like state-space search, plan-space planning (e.g., partial-order planners like UCPOP), and planning graphs (e.g., GraphPlan). Over time, advancements have addressed more realistic scenarios, including probabilistic planning, hierarchical task networks (HTNs) for domain-configurable systems (e.g., SHOP2), and integrated temporal planning that combines action sequencing with . Key applications span diverse domains, including aerospace operations (e.g., NASA's Mars Rovers using automated planners for autonomous activity generation in 2003), for task execution, , and for automation. The International Conference on Automated Planning and Scheduling (ICAPS), held annually since 1991, serves as the premier venue for advancing theoretical foundations, algorithms, and practical tools in the field. Challenges persist in scaling to complex, real-world problems, often NP-hard, driving ongoing research into heuristic search, integration, and explainable methods.

Introduction

Definition and Scope

Automated planning and scheduling is a subfield of focused on the computational generation of action sequences and resource allocations to transition from an initial state to a desired state within a given environment. Automated planning specifically involves synthesizing a course of action by selecting and ordering high-level actions that achieve objectives, often through over possible outcomes and interactions. In contrast, automated scheduling entails assigning temporal slots and limited resources—such as time, personnel, or materials—to predefined tasks or actions while optimizing for constraints like deadlines or availability. Together, these processes enable intelligent agents or systems to operate autonomously in dynamic settings, distinguishing them from mere reactive control by emphasizing proactive formulation. The scope of automated planning and scheduling encompasses domain-independent methods applicable to diverse real-world problems, including , , , emergency response, and space operations. These techniques model environments abstractly using state representations and action effects, allowing across scenarios without reliance on problem-specific coding, unlike traditional search problems that operate on low-level state manipulations. For instance, in , simple path planning might compute trajectories between points, whereas full mission planning coordinates multiple actions like , , and environmental to complete complex tasks. This broad applicability supports efficiency in resource-constrained systems, from optimizing supply chains in to sequencing operations in assembly lines. Key objectives in automated planning and scheduling include ensuring completeness (guaranteeing a solution if one exists), optimality (selecting the most efficient plan by criteria like cost or duration), and computational (solving problems within practical time and space limits). These goals address challenges in high-dimensional state spaces, where planning prioritizes action viability and goal attainment, while scheduling focuses on feasible temporal and resource distributions to minimize conflicts or delays. By integrating these elements, the field advances autonomous decision-making, adapting to uncertainties and supporting human-AI collaboration in complex domains.

Historical Development

The field of automated planning and scheduling traces its origins to the early days of , particularly with the development of the STRIPS (Stanford Research Institute Problem Solver) system in 1971, which introduced a foundational framework for situation calculus-based planning using theorem proving and means-ends analysis to generate sequences of operators transforming an initial world model to a goal state. STRIPS, created by Richard Fikes and Nils Nilsson at , marked a pivotal shift toward about actions and their effects, laying the groundwork for domain-independent planning by separating action descriptions from specific problem instances. During the 1980s and 1990s, the field evolved with the rise of domain-independent planners, exemplified by UCPOP (Universal Causal Partial Order Planner) in 1992, a sound and complete partial-order planner for the Action Description Language (ADL) that extended earlier non-linear planning approaches to handle complex dependencies more efficiently. This period saw increased focus on partial-order planning techniques, influenced by key figures such as Austin Tate, whose earlier work on the Nonlin planner in the late 1970s laid the foundations for hierarchical partial-order planning, and whose subsequent work on the O-Plan system in the 1980s advanced hierarchical and resource-aware planning for real-world applications. Standardization efforts culminated in 1998 with the introduction of the Planning Domain Definition Language (PDDL) by Drew McDermott, Malik Ghallab, and colleagues, designed as a neutral syntax for specifying planning problems to enable the first International Planning Competition (IPC), fostering comparability across planners. The 2000s brought further advancements through the biennial IPC, which began in 1998 and drove algorithmic improvements by benchmarking planners on standardized PDDL domains, with the competition's third edition in 2002 highlighting progress in expressive modeling. A major milestone was the 2003 extension to PDDL 2.1 by Maria Fox and Derek Long, which incorporated durative actions and temporal constraints to support metric-temporal planning, enabling the modeling of time-dependent and resource-limited scenarios. Key contributors like Malik Ghallab and Dana Nau further shaped the field; Ghallab co-authored PDDL and emphasized integrated planning-acting systems, while Nau developed the SHOP (Simple Hierarchical Ordered Planner) series in the late 1990s, advancing hierarchical task network (HTN) methods for practical decomposition. In the 2010s and 2020s, automated planning integrated with machine learning, particularly post-2015, as seen in approaches like ML-Plan (2018), which used hierarchical planning to automate machine learning pipeline configuration, and subsequent works leveraging neural networks for heuristic guidance and learning from failed plans to enhance solver efficiency. Recent advances emphasize hybrid systems combining symbolic planning with learning for real-time applications, as highlighted in the International Conference on Automated Planning and Scheduling (ICAPS), with the 2024 event in Banff focusing on AI-robotics integration through workshops on learning-enhanced planning for autonomous systems, and the 2025 conference in Melbourne continuing this trend with sessions on fused AI planning for robotic decision-making.

Fundamentals

Planning versus Scheduling

Automated planning and scheduling are distinct yet complementary processes in systems designed to achieve complex objectives. Planning primarily involves the generation of a sequence of actions that logically transform an initial world state into a desired state, emphasizing the selection and ordering of actions based on their effects and preconditions, while initially abstracting away from temporal and details. This core focus on logical transitions allows planners to explore high-level decision spaces, such as determining what actions to take in domains like or , without committing to execution timelines. In contrast, scheduling centers on the optimization of action execution by assigning specific durations, start times, and resources to the planned sequence, subject to constraints like limited machine availability, worker shifts, or precedence relations. Scheduling treats actions as fixed tasks post-planning and aims to minimize inefficiencies, such as idle times or overloads, often formulating the problem as a resource-constrained optimization. For instance, while planning might outline the steps to assemble a product, scheduling would allocate those steps to available factory resources over a finite horizon to ensure feasibility. The interplay between planning and scheduling is evident in integrated frameworks like Advanced Planning and Scheduling (APS) systems, particularly in manufacturing, where planning provides a feasible action outline that scheduling refines into a timed, resource-aware executable plan to handle dynamic uncertainties. This separation enables modular development—planning for long-term feasibility and scheduling for short-term optimization—but integrated approaches, such as interleaved planning and scheduling, combine them to address real-world problems requiring both action choice and temporal allocation simultaneously. Success metrics further highlight the distinction: planning evaluates outcomes by measures like total plan length or cumulative action cost, whereas scheduling prioritizes indicators such as makespan (the time from start to completion of all tasks) or total lateness (deviation from due dates). Domain-independent planning approaches often exploit this dichotomy by first generating abstract plans before applying scheduling refinements.

Domain-Independent Planning

Domain-independent planning constitutes a core in where algorithms generate plans for diverse problem domains without embedding domain-specific knowledge directly into the solver. These planners operate on abstract, general models of actions, states, and goals provided as input, enabling them to address a wide array of tasks through standardized representations rather than custom-coded logic. This generality distinguishes the approach from earlier, more rigid systems and underpins much of modern automated planning research. The key advantages of domain-independent planning lie in its reusability and broad applicability, allowing a single planner to tackle varied scenarios—such as optimizing or designing strategies in complex games—by merely adjusting the input model. This eliminates the need for reprogramming the core for each new application, fostering rapid adaptation and reducing the expertise required for deployment across fields like and . Moreover, it promotes community-wide , accelerating advancements through shared benchmarks and tools. Despite these benefits, domain-independent planning grapples with inherent challenges, foremost among them the tension between expressive problem modeling and computational tractability. Classical planning tasks in this paradigm, exemplified by propositional STRIPS problems, are PSPACE-complete, implying that determining the existence of a plan can demand resources exponential in the input size, even for seemingly simple domains. This complexity stems from the exhaustive exploration of potentially enormous state spaces without tailored guidance, often necessitating heuristic approximations to achieve practical performance. Evaluation of domain-independent planners relies heavily on empirical competitions like the International Planning Competition (IPC), which began in 1998 and periodically tests systems on standardized suites of diverse domains to measure coverage, speed, and solution quality. Unlike domain-dependent planners, which leverage handcrafted rules for superior efficiency in targeted scenarios, domain-independent methods prioritize versatility at the cost of raw performance, making them ideal for exploratory or evolving applications but less suited for highly optimized, fixed-domain needs.

Core Concepts

Automated planning and scheduling revolves around the fundamental problem of finding a sequence of actions that transforms an initial state of the into a desired state. The state space consists of all possible configurations of the , where each state represents a complete description of relevant facts or properties at a given point. The initial state specifies the starting configuration, the state defines the target configuration to achieve, and intermediate states are those reached during the execution of actions en route to the . Actions, also known as operators, are the basic building blocks that enable changes in the state space. Each action is defined by preconditions, which are conditions that must hold true in the current state for the action to be applicable; effects, which describe the changes resulting from the action, typically partitioned into add lists (new facts made true) and delete lists (facts made false); and optionally, costs to quantify the expense of executing the action. In classical planning, actions are assumed to have deterministic effects, meaning that applying a valid action always produces a predictable new state without . Transitions between states occur when an applicable action is executed, updating the state according to the action's effects. This process is formally modeled in frameworks such as the STRIPS notation, which uses precondition-effect pairs to represent state changes, or situation calculus, a first-order logic formalism where situations denote world states and actions transform one situation into a successor situation via the "do" function. A plan is a valid sequence of actions (or, in more general cases, a policy mapping states to actions) that, when executed from the initial state, reaches a goal state without violating preconditions along the way. Key assumptions underpin these core concepts in basic planning models. Deterministic effects ensure that outcomes are fully predictable given the action and state. Additionally, the is typically adopted, positing that all relevant facts are explicitly known in the state description—if a fact is not stated, it is false—contrasting with assumptions where unknown facts might be true. A representative example is the domain, where the task involves stacking blocks on a table using a . States are described by predicates such as on(blockA, blockB) (block A is on block B), ontable(blockC) (block C is on the table), and clear(blockD) (nothing is on block D). Actions include pickup(blockX), which requires handempty, clear(blockX), and ontable(blockX) as preconditions, adding holding(blockX) and deleting the others; and stack(blockX, blockY), which requires holding(blockX) and clear(blockY), adding on(blockX, blockY) and clear(blockX) while deleting holding(blockX) and clear(blockY). A might be to achieve on(blockA, blockB) and on(blockB, blockC), leading to a plan sequence like unstacking interfering blocks, moving them aside, and restacking to form the tower.

Modeling Languages

Planning Domain Definition Language (PDDL)

The (PDDL) is a standardized, declarative language designed for specifying planning domains and problems in planning, enabling domain-independent planners to generate solutions without requiring custom implementations for each task. Introduced in 1998 for the First Planning Systems (AIPS) competition, PDDL separates the description of the world model (domain) from specific instances (problems), promoting reusability and comparability across planners. This structure facilitates the encoding of classical planning tasks using predicate logic, where states are represented as sets of logical propositions, and actions modify these states according to defined rules. PDDL's core structure consists of two primary files: a domain file defining the general model and a problem file instantiating it for a specific scenario. The domain file, enclosed in (define (domain <name>) ...), includes requirements (e.g., :strips for basic action models), types for object classification (e.g., (:types truck package location)), constants, predicates, and actions. Predicates are atomic formulas like (on ?x - block ?y - block), where ?x and ?y are variables typed as blocks, representing relationships in the state. Actions are specified with parameters, preconditions, and effects; for instance, an action might be (:action move :parameters (?x - block ?y - block ?z - block) :precondition (and (on ?x ?z) (on ?y ?z) (clear ?x)) :effect (and (on ?x ?y) (clear ?z) (not (on ?x ?z)) (not (clear ?y)))), ensuring preconditions hold before applying additive and deletive effects to the state. The problem file, (define (problem <name> (:domain <domain-name>)), declares objects (e.g., (truck1 - truck)), the initial state as a conjunction of grounded predicates, and goals as desired state conditions. PDDL has evolved through versions, starting with 1.2 in 1998, which supports basic STRIPS-style with added features like typing, equality, and conditional effects inspired by Action Description Language (ADL). Subsequent levels include PDDL 2.1 (2003), introducing durative actions and numeric fluents for temporal and resource modeling; PDDL 2.2 (2004), adding derived predicates computed from other state variables; PDDL 3.0 (2005), incorporating preferences for expressing soft constraints; and PDDL 3.1 (2008), further extending with features such as finite domain variables. These versions maintain backward compatibility while expanding expressiveness. PDDL serves as the input format for the International Planning Competition (IPC), where planners are benchmarked on standardized domains, ensuring consistent evaluation. Tools like VAL provide validation by simulating plan execution against PDDL specifications, checking for correctness and detecting errors in models or solutions. A limitation of PDDL is its lack of native support for learning domain models from data, as it is a static declarative language requiring manual specification; domain acquisition typically relies on external machine learning techniques. For example, the Logistics domain models transportation tasks with types such as truck, package, and location; predicates like (at ?p - package ?l - location) and (in ?p - package ?t - truck); and actions such as loading a package into a truck at a location, with preconditions ensuring the package and truck are co-located, and effects updating their positions. Extensions to PDDL exist for temporal planning, but core versions focus on discrete, non-temporal actions.

Extensions and Alternative Languages

Extensions to the Planning Domain Definition Language (PDDL) have been developed to address limitations in modeling temporal and continuous aspects of planning problems. PDDL 2.1 introduced durative actions, which allow actions to have durations and conditions/effects that occur at the start, over the interval, or at the end of the action, enabling the representation of temporal domains such as scheduling tasks with time constraints. This extension supports leveled semantics, with Level 3 incorporating numeric fluents for modeling resources like fuel or energy that change continuously or incrementally during actions. Building on PDDL 2.1, PDDL+ extends the language to handle continuous time-dependent effects and hybrid systems, incorporating processes that model ongoing changes (e.g., linear or piecewise constant numeric variations) alongside discrete events and durative actions. This makes PDDL+ suitable for domains involving continuous dynamics, such as robotic control or chemical process planning, where state variables evolve over real-valued time. Temporal PDDL variants, often based on PDDL 2.1, facilitate scheduling by specifying temporal constraints on action execution and resource usage. For instance, PDDL 2.2, used in the 4th International Planning Competition, enhanced support for numeric fluents in problems, allowing planners to optimize metrics like total cost or in domains with quantitative constraints. Alternative languages have emerged to support specialized planning paradigms beyond core PDDL capabilities. PPDDL (Probabilistic PDDL) extends PDDL for probabilistic by incorporating nondeterministic action effects and probabilistic goals, used in the probabilistic tracks of the 4th and 5th International Planning Competitions. ANML (Action Notation Modeling Language), an XML-based language, emphasizes hierarchical task decomposition and timeline-based representations, providing greater expressiveness for concurrent actions and temporal constraints compared to PDDL's simpler action-centric model. ANML's timeline structure allows specifying multiple concurrent activities on resources, trading off PDDL's modeling simplicity and broad planner support for enhanced concurrency handling in complex domains like spacecraft operations. Domain-specific frameworks like ROSPlan integrate PDDL with the (ROS) for applications, enabling seamless and execution in real-time environments such as autonomous or manipulation tasks. PDDL remains the dominant in automated , as evidenced by its use in all tracks of the International Planning Competitions since 1998 and widespread adoption in academic and industrial tools. Alternatives like ANML and PPDDL find use in niche areas, such as multi-agent systems requiring hierarchical coordination or modeling.

Planning Algorithms

Classical Planning

Classical planning represents a foundational in automated planning, characterized by its deterministic and fully observable nature. In this framework, the world is modeled as a of discrete states, where actions produce instantaneous transitions without duration or concurrency. Key assumptions include full , meaning the planner has complete knowledge of the current state; deterministic effects, ensuring each action yields a unique successor state; and a static environment, where no changes occur except those caused by the agent's actions. These restrictions simplify the problem to finding a sequence of actions that transforms an initial state into one satisfying a specified , abstracting away real-world complexities like uncertainty or time. The classical planning problem is formally defined as a consisting of an initial state II, a set of actions AA, and a goal condition GG. Each action a∈Aa \in A is specified by preconditions (logical formulas that must hold for applicability) and effects (additions and deletions to the state). The objective is to find a π=⟨a1,a2,…,an⟩\pi = \langle a_1, a_2, \dots, a_n \rangle such that applying the sequence π\pi to II results in a state where GG holds, typically represented as a conjunction of positive literals. This formulation traces back to early systems like STRIPS, emphasizing propositional logic for state representation to enable efficient reasoning. Solution approaches in classical planning primarily involve search strategies over state, plan, or graph spaces. Forward search, or progression planning, explores from the initial state by applying applicable actions to generate successor states until the goal is reached, benefiting from early pruning of irrelevant paths. Backward search, or regression planning, starts from the goal and works in reverse, identifying preconditions that must hold to achieve subgoals, which is advantageous when goals are simpler to specify than full state expansions. operates in plan space, beginning with an incomplete plan and refining it by adding causal links and resolving threats, allowing for flexible, least-commitment sequences that avoid unnecessary . These methods form the basis for more advanced techniques but are computationally intensive due to the problem's inherent hardness. The of classical planning is well-established: deciding plan existence is in general for propositional STRIPS domains, reflecting the exponential state space explosion, while simpler cases without delete effects (e.g., monotonic planning) are NP-complete. This hardness underscores the need for domain-specific optimizations, yet practical solvers leverage these bounds effectively on benchmark problems. The International Planning Competition (IPC), with its classical tracks running since 1998, has served as a key benchmark suite, evaluating planners on diverse domains like and to track progress in scalability and solution quality. Over successive IPC events, classical track problems have grown in size, with recent editions featuring hundreds of instances to assess coverage and metrics such as and runtime.

Heuristic Search Techniques

Heuristic search techniques form a cornerstone of solving classical planning problems by guiding the exploration of the state space toward goal states more efficiently than uninformed methods. In classical , where actions have uniform unit costs and the environment is deterministic and fully , these techniques rely on functions that estimate the distance from a given state to the . A key approach involves delete relaxation, which simplifies the planning task by ignoring the delete effects of actions—those that remove preconditions or add negative effects—allowing for the computation of lower-bound estimates on the true plan cost. This relaxation enables the construction of relaxed planning graphs (RPGs), layered structures that propagate achievable propositions and actions without deletions, providing a basis for deriving admissible heuristics. Prominent delete relaxation heuristics include h_max and h_add, both computed efficiently in polynomial time from RPGs. The h_max heuristic estimates the cost to achieve each goal proposition independently by taking the maximum over the costs of unsatisfied goals, assuming no interactions between them; it is admissible because it underestimates the true cost by ignoring positive interactions. In contrast, h_add, the additive heuristic, sums the individual minimum costs to achieve each unsatisfied goal proposition, also ignoring delete effects but overestimating due to not accounting for actions that achieve multiple goals simultaneously. For a state ss and goal set GG, the additive heuristic is formally defined as hadd(s)=∑g∈G∖smin⁡{c(a)∣a achieves g in the relaxed task},h_{\text{add}}(s) = \sum_{g \in G \setminus s} \min \{ c(a) \mid a \text{ achieves } g \text{ in the relaxed task} \}, where c(a)c(a) is the cost of action aa, typically 1 in unit-cost settings; this formulation overestimates the relaxed plan length since it overcounts costs for shared actions and disregards inter-goal dependencies, making h_add inadmissible. While h_max is often more informative for guiding search due to its focus on the hardest subgoals, h_add provides a looser estimate but can be faster to compute in some contexts. These heuristics were foundational in planners like HSP, demonstrating significant speedups over earlier methods like Graphplan. Heuristic search algorithms integrate these estimates into best-first strategies to ensure completeness and, under certain conditions, optimality. The A* algorithm, adapted for , uses the f(n)=g(n)+h(n)f(n) = g(n) + h(n), where g(n)g(n) is the path cost from the initial state to node nn, and expands nodes in order of increasing ff; with an (where h(n)≤h∗(n)h(n) \leq h^*(n), the true optimal cost), A* guarantees an optimal solution upon reaching the goal. To address memory demands in large state spaces, Iterative Deepening A* (IDA*) employs a depth-bounded search with increasing cost thresholds based on ff-values, effectively trading space for time while preserving optimality if the heuristic is admissible. Consistency, a stronger property where h(n)≤c(n,n′)+h(n′)h(n) \leq c(n, n') + h(n') for every successor n′n' of nn and edge cost cc, ensures A* and IDA* avoid re-expansions, further promoting optimality; h_max is consistent in unit-cost classical . Practical implementations often combine heuristics with greedy or local search for efficiency. Enforced Hill-Climbing (EHC), introduced in the FF planner, performs a greedy best-first search that "enforces" progress by selecting the lowest-heuristic successor at each step, only if stuck; it uses the FF-heuristic, an extension of h_add and h_max that incorporates relaxed extraction to better capture action dependencies, yielding much faster than pure A* in scenarios. The planner builds on this by employing FF-heuristic-guided EHC for initial finding, followed by iterative cost-optimal searches using A* with a landmark-based pseudo-heuristic, achieving strong performance in international planning competitions. These strategies prioritize speed over optimality in the first phase, reserving exhaustive search for refinement. Post-2000 advancements have enhanced accuracy through abstractions like pattern databases (PDBs) and analysis. PDBs precompute exact costs for abstracted subproblems—subsets of propositions treated independently—storing them in lookup tables; the overall is the sum or max of PDB values for disjoint patterns covering the goals, providing admissible estimates that scale with memory allocation and outperform simple relaxations in optimal . heuristics, meanwhile, identify propositions that must be achieved in every (landmarks) along with ordering constraints, deriving a counting that penalizes states based on unsatisfied landmarks and their precedence; this approach, integrated into systems like , improves guidance for cost-sensitive search by capturing necessary structure without full abstraction. These methods have significantly boosted solver performance, with techniques enabling anytime that refines solutions progressively.

Temporal Planning

Temporal planning extends classical planning frameworks to incorporate explicit representations of time, allowing actions to have durations and enabling the modeling of temporal constraints between events. This approach is essential for domains where timing is critical, such as and , where actions may overlap and must satisfy conditions over intervals rather than instantaneously. In temporal planning, actions are typically modeled as durative, spanning a period from initiation to completion, with effects and preconditions specified at precise points within that duration. A key innovation in temporal planning is the use of durative actions, which include conditions and effects categorized as occurring "at start" (upon initiation), "over all" (holding invariantly throughout the open interval of the action), or "at end" (upon completion). Temporal constraints further refine these models by specifying relationships such as overall durations (e.g., fixed or variable lengths) or conditions within specific intervals, ensuring between concurrent actions. These features were formalized in the PDDL 2.1 temporal profile, which integrates durative actions with the to support reasoning while maintaining compatibility with classical planning elements. Optimization objectives often focus on metrics like minimization, defined as the total time from plan start to goal achievement, to produce efficient schedules. To solve temporal planning problems, specialized planners employ techniques such as combined with constraint propagation. For instance, the POPF planner uses forward-chaining partial-order search to generate temporally flexible plans, maintaining consistency through Simple Temporal Networks (STNs), which represent time-point constraints as difference constraints solvable via shortest-path algorithms like Bellman-Ford. Similarly, OPTIC extends this approach to handle preferences and time-dependent costs, also relying on STNs to enforce temporal consistency during heuristic-guided search. These solvers address the heightened complexity of temporal planning, which is EXPSPACE-complete for concurrent actions with due to the exponential state space introduced by overlapping durations and continuous timing. A representative application of temporal planning is satellite scheduling, where durative actions model observation tasks constrained by narrow visibility windows over ground targets. In such domains, planners must sequence maneuvers and data collections to maximize coverage while respecting orbital dynamics and temporal windows, often minimizing to optimize mission timelines. For example, systems using PDDL-based temporal planning have been applied to generate nominal operations schedules for Earth-observing satellites, ensuring actions like and align precisely within fleeting opportunity intervals.

Probabilistic Planning

Probabilistic planning addresses decision-making in environments where action outcomes are uncertain, extending classical by incorporating probabilistic transitions and rewards to model non-deterministic effects. In contrast to deterministic classical , which assumes guaranteed outcomes, probabilistic planning seeks policies that maximize expected utility over possible future states. The core models are Markov Decision Processes (MDPs) and Partially Observable Markov Decision Processes (POMDPs). An MDP is defined as a (S,A,P,R,γ)(S, A, P, R, \gamma), where SS is the set of states, AA is the set of actions, P(s′∣s,a)P(s'|s,a) denotes the transition probabilities to next states s′s' given state ss and action aa, R(s,a)R(s,a) is the reward function, and γ∈[0,1)\gamma \in [0,1) is the discount factor. POMDPs extend MDPs by adding partial observability, introducing an observation set OO and observation probabilities Z(o∣s′,a)Z(o|s',a) that map next states and actions to observations oo, requiring the agent to maintain a belief state over possible worlds. Solutions to these models typically involve computing an optimal policy π:S→A\pi: S \to A (for MDPs) or π:B→A\pi: B \to A (for POMDPs, where BB is the belief space) that maximizes the expected discounted reward. For finite-horizon or discounted infinite-horizon MDPs, dynamic programming methods like value iteration and policy iteration are standard, solving the Bellman optimality equation: V∗(s)=max⁡a[R(s,a)+γ∑s′P(s′∣s,a)V∗(s′)],V^*(s) = \max_a \left[ R(s,a) + \gamma \sum_{s'} P(s'|s,a) V^*(s') \right], where V∗(s)V^*(s) is the optimal value function for state ss. Value iteration iteratively updates value estimates until convergence, while policy iteration alternates between policy evaluation and improvement. POMDP solutions are computationally harder (PSPACE-complete in general), often using dynamic programming over the belief simplex or approximation techniques due to the continuous belief space. Key planners for probabilistic domains include the Model-Based Planner (MBP), which generates policies for non-deterministic domains—a special case of probabilistic planning where outcomes are fully nondeterministic—using conformant planning techniques based on to ensure goal achievement with certainty in the worst case. Probabilistic-FF (PFF) extends the heuristic forward-search of the classical FF planner to non-observable probabilistic settings, using weighted model counting for to guide search toward high-probability plans. For large state spaces, approximations like Real-Time Dynamic Programming (RTDP) provide efficient online planning by focusing updates along simulated trajectories from the initial state, converging to optimal policies under mild assumptions like acyclic state graphs. RTDP, introduced by Barto et al., improves over full value iteration by leveraging heuristic guidance and real-time adaptation. Performance in probabilistic planning is evaluated using metrics such as expected utility (discounted cumulative reward) or probability of success (likelihood of reaching a state). A representative example is robotic navigation with sensor noise, modeled as a POMDP where the robot's position is partially observable due to noisy readings, and actions like "move forward" have probabilistic outcomes (e.g., slipping on terrain); the optimal balances to update beliefs with exploitation to reach the goal, maximizing expected reward.

Advanced Planning Paradigms

Preference-Based Planning

Preference-based planning extends traditional automated by incorporating user-specified preferences to generate plans that not only achieve hard goals but also optimize for desirable qualities, such as or user satisfaction. These preferences are modeled as soft constraints or goals that can be partially satisfied, allowing planners to rank plans based on how well they align with user desires beyond mere feasibility. This approach addresses limitations in classical , where all valid plans are treated equally, by enabling the selection of higher-quality outcomes in domains like and . In modeling preferences, PDDL 3.0 introduces soft goals and constraints, expressed using modal operators like :preferences to define desirable conditions that contribute to plan quality without being mandatory. Preferences can be qualitative, such as lexicographic ordering where higher-priority preferences must be fully satisfied before considering lower ones, or quantitative, involving weighted sums that aggregate satisfaction scores across multiple criteria. Qualitative models prioritize hierarchical user intents, while quantitative approaches allow fine-grained trade-offs through numerical utilities. Algorithms for preference-based planning often extend satisficing planners, such as LPG, by integrating preference semantics during search to favor plans that maximize preference satisfaction. In cases with conflicting criteria, these methods compute Pareto-optimal plans, forming a set of non-dominated solutions where no plan improves one preference without degrading another. Plan quality is typically measured as the sum of satisfied preferences minus penalties for violations, providing a scalar metric for ranking. Applications include personalized robotics, where preferences ensure safety takes precedence over speed in navigation tasks, adapting plans to individual user needs like accessibility. For instance, in travel planning, a system might generate itineraries preferring scenic routes over direct paths to enhance enjoyment, balancing time constraints with qualitative desires for aesthetics.

Conditional and Conformant Planning

Conformant planning is a paradigm in automated planning that addresses uncertainty in the initial state and nondeterministic action effects without the availability of sensing actions during execution. In this setting, the planner must generate a single, linear sequence of actions—known as a conformant plan—that guarantees achievement of the goal from every possible initial world state consistent with the partial knowledge. Belief states, representing sets of possible worlds, are used to model the agent's knowledge, and planning proceeds by searching in the space of these belief states. This approach draws on Kripke structures to represent epistemic uncertainty, where possible worlds are interconnected based on indistinguishability. Seminal work formalized conformant planning and introduced symbolic model checking techniques to verify and generate such plans efficiently, leveraging binary decision diagrams for state explosion mitigation. The of conformant planning exceeds that of classical planning, which is ; conformant planning is EXPSPACE-complete in the general propositional case. Solvers like Conformant-FF employ forward search in belief space, adapting techniques from classical planners such as FF while incorporating CNF-based reasoning to handle . A classic example is a mail delivery task where the robot's initial position and the mail's location are unknown, but the plan—such as systematically visiting all possible locations—must succeed regardless of the actual starting configuration. Conditional planning, or contingent planning, builds on conformant planning by incorporating sensing actions that resolve through s during execution. The resulting plans are branching structures, often represented as trees or directed acyclic graphs with contingencies based on possible outcomes, allowing adaptation to revealed information. Extensions to the Graphplan algorithm enabled efficient extraction of conditional plans by modeling conditional effects in the planning graph. The complexity of conditional planning is 2-EXPTIME-complete, reflecting the added challenge of branching over sequences. For instance, in a robot repair scenario, the agent senses the type of fault (e.g., via diagnostic probes) and selects repair actions accordingly, branching the plan to cover different fault possibilities. These paradigms focus on execution uncertainty arising from incomplete initial information or nondeterministic effects, distinct from preference-based planning which optimizes for qualitative criteria. While related to probabilistic planning, conformant and conditional approaches treat uncertainty nondeterministically without assigning probabilities to transitions.

Learning-Based Planning

Learning-based planning integrates techniques into automated planning and scheduling to acquire action models, generate plans, or optimize trajectories dynamically, addressing the limitations of hand-crafted domain models required in classical planning approaches. This enables systems to learn from such as execution traces, demonstrations, or interactions, facilitating to new environments without exhaustive manual specification. Key motivations include improving scalability in complex domains and handling where traditional symbolic models fall short. Action model learning focuses on inducing preconditions, effects, and invariants from observed plan traces using methods like (ILP), which generalizes logical rules from examples while incorporating background knowledge. For instance, the AMAN system (Action-Model Acquisition from Noisy plan traces) employs graphical models to learn STRIPS-like action models from incomplete or erroneous traces, achieving high accuracy even with noise levels up to 20% in benchmarks like blocks-world domains. These techniques relax the full-observability assumptions of classical planning by inferring models that explain observed state transitions, often outperforming manual modeling in time efficiency for real-world applications. Neural approaches leverage (DRL) to solve Markov decision processes (MDPs) underlying problems, with AlphaGo-style methods combining policy and value neural networks with (MCTS) for long-horizon decision-making. In contexts, such as tactical games or , these yield sample-efficient policies by training, as extended in hybrid frameworks for continuous state spaces. Post-2020 neuro-symbolic planners integrate neural networks for and with symbolic reasoning for interpretability and , as surveyed in works emphasizing hybrid architectures for tasks like . Techniques like imitation learning from demonstrations use behavioral cloning or inverse RL to extract policies from trajectories, while employs gradient-based methods to minimize costs in continuous spaces, ensuring feasibility under dynamics constraints. Recent advances include (LLM)-augmented planning, where models like generate PDDL domains from descriptions, enabling planning in unstructured text-based environments. Systems such as those in "On the prospects of incorporating s in automated planning and scheduling" categorize LLM roles in model generation, plan synthesis, and verification, boosting accessibility for non-expert users. However, challenges persist in sample efficiency, particularly in sparse-reward settings where DRL requires millions of interactions to converge. An illustrative example is learning robot manipulation from unconstrained web videos, where systems like those processing WWW footage infer action plans by tracking object interactions, achieving 68% accuracy in generating manipulation commands from household cooking videos.

Applications and Deployment

Industrial and Robotic Applications

In , automated planning and scheduling systems like SAP Advanced Planning and Optimization (APO) enable efficient production scheduling by optimizing , proposals, and detailed sequencing to minimize lead times and improve on-time delivery rates. The Production Planning and Detailed Scheduling (PP/DS) module within SAP APO uses constraint-based optimization to handle complex production environments, integrating with constraints for real-time adjustments. Integration of AI into these systems has further enhanced outcomes, with capabilities reducing machine downtime by 30-50% and extending equipment life by 20-40%, as reported in industry analyses. In , automated planning has been pivotal for autonomous operations in challenging environments, exemplified by NASA's Remote Agent experiment on the spacecraft in 1999, which demonstrated goal-directed planning, execution, and fault recovery using model-based reasoning to manage onboard activities without ground intervention. More recently, frameworks like ROSPlan integrate task planning directly into the (ROS), facilitating autonomous navigation and multi-robot coordination by translating high-level goals into executable action sequences, often incorporating probabilistic elements for uncertainty handling in dynamic settings. Logistics applications leverage automated planning for warehouse optimization and inventory management, as seen in Amazon's multi-echelon planning system, which uses optimization algorithms to balance levels across fulfillment centers, incorporate , and account for delivery constraints to enable efficient . Case studies highlight domain-specific adaptations, such as the use of (PDDL) for scheduling modular construction projects, where planners generate sequences for assembly lines and resource allocation to accelerate off-site fabrication timelines, as explored in recent manufacturing automation research. In healthcare, robot-aided rehabilitation employs automated planning to personalize sessions, selecting and sequencing exercises based on progress and constraints, with systems optimizing session duration and intensity to maximize recovery outcomes. These applications underscore the scalability of automated planning in dynamic environments, where online replanning mechanisms allow systems to adapt to disruptions like equipment failures or changing priorities without full recomputation, enabling robust performance in manufacturing lines and robotic fleets.

Integration with Other AI Systems

Automated planning and scheduling systems often integrate with machine learning (ML) components to enable adaptive and efficient decision-making in dynamic environments. One prominent approach involves online replanning, where learned models from reinforcement learning (RL) guide the replanning process in anytime planners. For instance, the DARLING framework synthesizes automated planning with RL by using planning to constrain the exploration space of the RL agent's Markov Decision Process (MDP), allowing dynamic replanning when unmodeled states are encountered; this is achieved through Answer Set Programming to merge new plans with existing policies, significantly reducing the action space in example domains. Similarly, deep RL policies can be integrated with sampling-based motion planning for high-level behavior selection in automated driving, enabling cyclic replanning that predicts future traffic scenes via built-in simulators and outperforms single-shot methods in multi-agent maneuvers. These integrations leverage RL's ability to learn from experience while maintaining planning's guarantee of rationality, as surveyed in works combining the two paradigms for robust robotic decision-making. Perception integration enhances by addressing partial observability, particularly through Partially Observable Markov Decision Processes (POMDPs) that incorporate for state estimation. In POMDP solvers, belief states are updated using observation models from vision sensors, refining estimates of the environment; for example, in robotics domains like FieldVision-RockSample, vision-like observations (e.g., 32-128 possible outcomes) update beliefs probabilistically to estimate rock states across grids. In autonomous driving, Transformer-based models predict online belief states from multimodal perception data, including inputs, to support efficient POMDP under uncertainty. This allows planners to handle noisy or incomplete visual data, such as from cameras, by propagating belief updates via functions like τ(b, a, z), where z represents visual observations. Hybrid approaches with optimization techniques, such as , extend planning capabilities for complex scheduling tasks. By combining mixed integer linear programming (MILP) via solvers like CPLEX with CP, logic-based allocates tasks to facilities (using MILP) and schedules them under resource constraints (using CP's cumulative scheduling), achieving significant speedups over standalone methods in task scheduling problems. These hybrids interface planning's symbolic reasoning with CPLEX's numerical optimization, enabling scalable solutions for minimization in parallel task environments. A key example of such integrations appears in autonomous vehicles, where employs hierarchical model-based generative adversarial imitation learning (MGAIL) for planning, augmented with perception to process sensor data like and cameras for environmental understanding. Trained on over 100,000 miles of real-world trajectories in , this system generalizes to novel routes via a hierarchical model, approaching expert performance in closed-loop evaluations with simulated agents. Frameworks like Hierarchical Task Networks (HTNs) further facilitate these synergies by decomposing high-level plans into primitive actions, linking them to low-level control via execution structures such as Behavior Trees; in dynamic multi-agent settings, HTNs coordinate group strategies while Behavior Trees handle reactive decisions like path selection, minimizing replanning overhead.

Real-World Challenges in Deployment

One major challenge in deploying automated planning and scheduling systems is , particularly the state explosion problem that arises in large domains with numerous variables and actions, leading to computationally intractable search spaces. Traditional planners, such as those based on PDDL, exhibit in time and as the number of symbols increases, limiting their applicability to complex real-world scenarios like multi-robot coordination. To mitigate this, abstraction techniques, including hierarchical and state abstractions, reduce the problem size by grouping similar states or actions, enabling solutions in domains with temporal constraints; however, these methods still face real-time limits, where robot decisions often require computation under 1 second to ensure responsive behavior in dynamic environments. For instance, cloud-based introduces latency variability, hindering predictable response times essential for human-robot . Robustness to real-world uncertainties poses another significant hurdle, as planning systems must handle noise such as sensor inaccuracies or environmental changes, which can deviate outcomes from nominal plans. Actuator failures, for example, introduce probabilistic disruptions modeled as independent events that expand the state space and necessitate contingency handling in unreliable robotic actuators. Effective deployment often requires replanning mechanisms to recover from such failures, quantifying plan robustness statistically—e.g., measuring the probability of goal achievement under initial state perturbations via Bayesian estimation—to ensure executability in noisy settings like urban traffic control or robotic manipulation with the Baxter arm. In practice, plans achieving at least 90% robustness may demand tolerance margins of around 20% in conservative domains to account for execution failures. Verification of plan safety is critical for deployment in safety-sensitive applications, where ensuring that plans adhere to properties like avoiding hazardous states prevents . Integrating with verifies domain models against safety specifications by negating properties and using planners to constrain counterexamples, guaranteeing valid violations if they exist without redundant exploration. This approach, applied to domains like , augments model transitions with goal constraints to focus on post-goal safety, reducing the states evaluated compared to exhaustive checking. Such techniques have been evaluated with tools like Spin and MIPS planners on IPC benchmarks, confirming their efficacy in identifying safety lapses efficiently. Ethical concerns further complicate deployment, particularly bias in learned planners derived from , which can perpetuate disparities if training data reflects historical inequities, leading to unfair in tasks. In critical applications like healthcare, accountability demands clear delineation of responsibility for AI-generated plans, amplified by 2025 regulations emphasizing mitigation, transparency, and equitable outcomes to safeguard . For example, U.S. national guidance requires organizations to assign oversight for AI tools, including evaluation, to align with ethical standards and avoid enforcement risks from discriminatory decisions. Deployment metrics highlight these challenges, with success rates in applications around 70% for valid plans in multi-domain settings, as reported in recent evaluations of neurosymbolic frameworks at conferences like ICAPS. In robustness assessments from ICAPS-related proceedings, target success under uncertainty reaches 90% in controlled tests but drops in real-world noise, underscoring the gap between benchmarks and practical deployment.

Future Directions

One prominent emerging trend in automated planning and scheduling is the integration of large language models (LLMs) for natural language-based planning, enabling more intuitive domain modeling and task specification. At the International Conference on Automated Planning and Scheduling (ICAPS) 2025, workshops such as the Hierarchical Planning (HPlan) emphasized the use of generative AI, including LLMs, to automate hierarchical planning structures and generate domain representations from natural language descriptions. This approach facilitates faster prototyping of planning problems in complex environments, such as robotics and logistics, by translating high-level user intents into executable PDDL (Planning Domain Definition Language) models. Early explorations in quantum planning are demonstrating potential for exponential speedups in search and optimization tasks, particularly through hybrid quantum-classical algorithms. Post-2024 prototypes have applied to factory layout , solving constrained quadratic models for multi-criteria optimization in scalable manufacturing scenarios. Similarly, quantum-assisted path for robotic inspections has shown promise in optimizing trajectories from CAD models, reducing computational overhead in high-dimensional spaces compared to classical methods. These advancements, including quantum-accelerated distribution network , highlight initial prototypes targeting real-world scheduling problems like in grids. Sustainability-focused trends are driving the development of green scheduling techniques to minimize across industrial and computational systems. Recent frameworks optimize task scheduling in environments by aligning workloads with low-carbon periods, achieving up to 33% reductions in carbon emissions for sustainable . In automated container terminals, energy-efficient AGV () scheduling algorithms integrate battery management and route optimization to lower overall power usage while maintaining throughput. These efforts align with EU initiatives like the 2025 Energy Efficiency Directive, which mandates 1.49% annual savings through 2030 and supports projects under the program for innovative energy-minimizing technologies in and . Multi-agent decentralized planning is advancing rapidly, particularly for swarm coordination in dynamic environments like drone operations. Decentralized metaheuristic frameworks, such as MetaPlanner, enable joint spatio-temporal trajectory planning for UAV swarms, improving collision avoidance and mission efficiency in unstructured settings. Multi-agent approaches have been applied to cooperative path planning in UAV swarms, allowing real-time adaptation to obstacles and constraints in applications like . These methods support scalable, fault-tolerant coordination without central oversight, as seen in systems for autonomous drone fleets. The market for automated planning and scheduling (APS) software reflects these innovations, with projections indicating robust growth driven by AI integration and industrial adoption. According to 2025 industry reports, the global APS software market, valued at USD 1.023 billion in 2025, is expected to reach USD 2.58 billion by 2034, expanding at a (CAGR) of approximately 10.7%. This surge is fueled by demand in sectors like and , where advanced APS tools address complex, real-time optimization needs.

Open Research Problems

One prominent open research problem in automated planning and scheduling is enhancing expressiveness by scaling to continuous and hybrid domains that extend beyond the capabilities of PDDL+. Hybrid systems, which combine discrete and continuous dynamics, suffer from state space explosion due to discrete variables alongside the challenges of modeling continuous effects like physical processes, making exact computationally intractable in real-world scenarios. Current approaches, such as those integrating with frameworks, show promise but struggle with errors and verification of hybrid trajectories, limiting their applicability to complex cyber-physical systems. Researchers emphasize the need for new modeling languages and solvers that handle unbounded continuous variables without excessive approximation, as existing PDDL+ extensions remain inefficient for large-scale hybrid problems. Explainability remains a critical frontier, particularly in generating human-understandable plans that address user expectations through techniques like contrastive explanations. In automated planning, explanations often fail to intuitively convey why a specific plan was selected over alternatives, leading to mismatches between planner outputs and intuition, especially in high-stakes domains. Contrastive methods, which restrict models to highlight differences between expected and actual plans (e.g., "why action A instead of B?"), have emerged as a promising approach, but they require iterative user interaction and scalable computation, which current frameworks do not fully support. Comprehensive surveys highlight the lack of standardized evaluation metrics for explainable AI planning (XAIP), underscoring the need for integrated systems that produce both verifiable and cognitively accessible rationales. Achieving , such as zero-shot across unseen domains via , poses significant challenges due to the domain-specific nature of traditional planners. algorithms typically overfit to training environments, failing to transfer knowledge to novel tasks without retraining, which hampers deployment in dynamic, real-world settings. techniques aim to enable rapid adaptation by learning from task distributions, but in sequential contexts like , they face issues with compositional structure and long-horizon dependencies in unseen domains. Recent workshops on in stress the open need for benchmarks and algorithms that support zero-shot transfer, integrating meta-reinforcement learning with classical to handle variability in objectives and constraints. Real-time planning at sub-millisecond latencies for high-speed represents an ambitious goal, with ongoing challenges in balancing speed, optimality, and robustness in dynamic environments. Current motion planners achieve sub-millisecond times for simple trajectories using specialized hardware, but they falter in cluttered or adversarial settings due to local minima and under time constraints. For applications requiring reactive adaptation, such as collision avoidance in unstructured spaces, planners must integrate sensing, prediction, and execution without sacrificing , yet real-time verification of plans remains computationally prohibitive. By 2025, the field aims to develop hardware-accelerated, anytime algorithms that meet these latencies while scaling to multi-agent coordination, as highlighted in studies on constraint-based real-time systems. Interdisciplinary integration, including ethics in autonomous planning and neuroscience-inspired cognitive models, is an emerging open area to ensure responsible and human-aligned . Ethical considerations in involve embedding fairness, , and value alignment into autonomous systems, but current frameworks lack mechanisms to handle moral dilemmas in multi-objective scenarios, such as in human-robot teams. Simultaneously, integrating offers potential for cognitive models that mimic human processes, like prospective simulation in the , yet bridging computational with brain-inspired architectures faces hurdles in scalability and empirical validation. Collaborative efforts between AI and advocate for hybrid models that incorporate and ethical reasoning, addressing gaps in transparency and societal impact for advanced autonomous systems.

References

  1. http://www.cs.umd.edu/~nau/papers/nau2007current.pdf
  2. https://ojs.aaai.org/index.php/ICAPS/issue/view/287
  3. https://www.cs.umd.edu/~nau/cmsc722/slides/chapter15.pdf
  4. https://icaps25.icaps-conference.org/
  5. https://www.sciencedirect.com/topics/computer-science/automated-planning
  6. https://ntrs.nasa.gov/api/citations/20000115877/downloads/20000115877.pdf
  7. https://arxiv.org/pdf/2305.16151
  8. https://ai.stanford.edu/~nilsson/OnlinePubs-Nils/PublishedPapers/strips.pdf
  9. https://www.sciencedirect.com/science/article/pii/0004370271900105
  10. https://homes.cs.washington.edu/~weld/papers/ucpop-kr92.pdf
  11. https://www.aiai.ed.ac.uk/project/nonlin/1976-dai-memo25-tate-nonlin.pdf
  12. https://www.cs.cmu.edu/~mmv/planning/readings/98aips-PDDL.pdf
  13. https://ojs.aaai.org/aimagazine/index.php/aimagazine/article/view/1506/1405
  14. https://jair.org/index.php/jair/specialtrack-ipc3
  15. https://planning.wiki/_citedpapers/pddl212003.pdf
  16. https://link.springer.com/article/10.1007/s10994-018-5735-z
  17. https://icaps24.icaps-conference.org/
  18. https://kmi.open.ac.uk/publications/pdf/kmi-02-4.pdf
  19. https://www.sciencedirect.com/science/article/pii/S2213846323000457
  20. https://www.ri.cmu.edu/pub_files/2007/9/scheduling-comp-ICAPSworkshp_with-acknow.pdf
  21. https://thegradient.pub/when-ai-plans-ahead/
  22. https://www.sciencedirect.com/science/article/pii/0004370294900817
  23. https://jair.org/index.php/jair/specialtrack-ipc4
  24. https://www.ijcai.org/proceedings/2019/0898.pdf
  25. https://dai.fmph.uniba.sk/~sefranek/kri/handbook/chapter22.pdf
  26. https://rodsmith.nz/wp-content/uploads/McCarthy_Hayes_1969_Some_philosophical_problems_from_the_sta.pdf
  27. https://www.cs.umd.edu/users/nau/cmsc421/planning.pdf
  28. https://cdn.aaai.org/ojs/7575/7575-13-11105-1-2-20201228.pdf
  29. https://web.engr.oregonstate.edu/~afern/classes/cs533/notes/strips-intro.pdf
  30. https://ai.dmi.unibas.ch/_files/teaching/hs21/po/exercises/pddl_intro.pdf
  31. https://planning.wiki/_citedpapers/pddl222004.pdf
  32. https://planning.wiki/_citedpapers/pddl32005.pdf
  33. https://ipc06.icaps-conference.org/deterministic/pddl.html
  34. https://ieeexplore.ieee.org/document/1374201
  35. https://hal.science/hal-03895464v1/document
  36. http://pddl4j.imag.fr/pddl_tutorial.html
  37. https://planning.wiki/_citedpapers/pddlplus2003.pdf
  38. https://ipc04.icaps-conference.org/probabilistic/proceedings/younes.pdf
  39. http://psresearch.xyz/publications/ICAPS08-ANML.pdf
  40. https://dugi-doc.udg.edu/bitstream/handle/10256/17712/ROSPlan.pdf
  41. https://www.sciencedirect.com/science/article/pii/S0004370215000144
  42. https://fai.cs.uni-saarland.de/teaching/winter18-19/planning-material/planning09-delete-relaxation-heuristics-pre-handout.pdf
  43. https://www.ida.liu.se/divisions/aiics/publications/AIPS-2000-Admissible-Heuristics-Optimal.pdf
  44. https://fai.cs.uni-saarland.de/teaching/winter18-19/planning-material/planning07-heuristic-search-pre-handout-4up.pdf
  45. https://planning.wiki/_citedpapers/planners/ff.pdf
  46. https://arxiv.org/abs/1401.3839
  47. https://www.ijcai.org/Proceedings/13/Papers/347.pdf
  48. https://aaai.org/Papers/AAAI/2008/AAAI08-155.pdf
  49. https://planning.wiki/_citedpapers/popf2010.pdf
  50. https://planning-wiki.ams3.cdn.digitaloceanspaces.com/63880ce063791987afc7dee797c7f154.pdf
  51. https://users.aalto.fi/~rintanj1/papers/Rintanen07icaps.pdf
  52. https://www.cse.iitd.ac.in/~mausam/papers/tut12a.pdf
  53. https://jair.org/index.php/jair/article/view/10523
  54. https://icaps12.icaps-conference.org/planningschool/slides-Mausam-Kolobov.pdf
  55. https://people.csail.mit.edu/lpk/papers/aij98-pomdp.pdf
  56. https://www.researchgate.net/publication/2932738_MBP_a_Model_Based_Planner
  57. https://www.sciencedirect.com/science/article/pii/000437029400011O
  58. http://cs-www.cs.yale.edu/homes/dvm/papers/pddl-ipc5.pdf
  59. https://users.cecs.anu.edu.au/~patrik/publik/ipc5-aij.pdf
  60. https://www.cs.toronto.edu/~sheila/publications/bai-mci-aim08.pdf
  61. https://www.labri.fr/perso/meghyn/papers/BieFriMci_KR06.pdf
  62. https://rakaposhi.eas.asu.edu/tuan-ijcai09.pdf
  63. https://www.jstage.jst.go.jp/article/transinf/E102.D/11/E102.D_2019EDP7052/_pdf
  64. https://jair.org/index.php/jair/article/view/10267
  65. http://www.tark.org/proceedings/tark_jun4_15/TARK2015.21.pdf
  66. https://cdn.aaai.org/ICAPS/2004/ICAPS04-041.pdf
  67. https://www.ida.liu.se/divisions/aiics/publications/ECP-1999-Some-Results-Complexity.pdf
  68. https://cdn.aaai.org/AIPS/1998/AIPS98-006.pdf
  69. https://www.sciencedirect.com/science/article/pii/S0004370206000087
  70. https://hal.science/hal-02010536/file/A_Review_of_Learning_Planning_Action_Models.pdf
  71. https://www.cambridge.org/core/journals/knowledge-engineering-review/article/review-of-learning-planning-action-models/E9156A2EBF0BCDBED23EA46B42628F10
  72. https://link.springer.com/article/10.1007/s10994-021-06089-1
  73. https://www.sciencedirect.com/science/article/pii/S0004370218304259
  74. https://arxiv.org/abs/1905.02680
  75. https://par.nsf.gov/servlets/purl/10481273
  76. https://ieeexplore.ieee.org/document/9561411/
  77. http://underactuated.mit.edu/trajopt.html
  78. https://ojs.aaai.org/index.php/ICAPS/article/view/31502
  79. https://dl.acm.org/doi/10.1609/icaps.v34i1.31503
  80. https://arxiv.org/html/2306.06192v8
  81. https://www.researchgate.net/publication/273818079_Robot_Learning_Manipulation_Action_Plans_by_Watching_Unconstrained_Videos_from_the_World_Wide_Web
  82. https://help.sap.com/docs/SAP_ADVANCED_PLANNING_AND_OPTIMIZATION%2C_ON_SAP_ERP/c95f1f0dcd9549628efa8d7d653da63e/69f3055130534338e10000000a154ce5.html
  83. https://leverx.com/solutions/sap-apo
  84. https://www.mckinsey.com/capabilities/operations/our-insights/manufacturing-analytics-unleashes-productivity-and-profitability
  85. https://www.jpl.nasa.gov/nmp/ds1/tech/autora.html
  86. https://ojs.aaai.org/index.php/ICAPS/article/view/13699
  87. https://www.amazon.science/latest-news/the-evolution-of-amazons-inventory-planning-system
  88. https://link.springer.com/article/10.1007/s10845-023-02211-3
  89. https://pmc.ncbi.nlm.nih.gov/articles/PMC12363123/
  90. https://www.sciencedirect.com/science/article/abs/pii/S0736584524000942
  91. https://link.springer.com/article/10.1007/s10514-022-10043-y
  92. https://www.ijcai.org/proceedings/2025/0956.pdf
  93. https://oaktrust.library.tamu.edu/bitstreams/603bdbe0-aa27-4f73-a748-b95328137603/download
  94. https://web.itu.edu.tr/sariel/publications/KarapinarAAAI2012.pdf
  95. https://ceur-ws.org/Vol-2655/paper19.pdf
  96. https://pmc.ncbi.nlm.nih.gov/articles/PMC12263600/
  97. https://www.parkerpoe.com/news/2025/11/new-national-guidance-lays-out-responsible-use-of
  98. https://www.alation.com/blog/ethics-of-ai-in-healthcare-privacy-bias-trust-2025/
  99. https://icaps25.icaps-conference.org/program/workshops/hplan/
  100. https://www.sciencedirect.com/science/article/pii/S0007850625000149
  101. https://www.sciopen.com/article/10.23919/IEN.2025.0009
  102. https://arxiv.org/abs/2508.05949
  103. https://www.mdpi.com/2077-1312/13/4/647
  104. https://energy.ec.europa.eu/topics/energy-efficiency/energy-efficiency-targets-directive-and-rules/energy-efficiency-targets_en
  105. https://www.sciencedirect.com/science/article/abs/pii/S0957417425034839
  106. https://www.researchgate.net/publication/396596442_Multi-Agent_Deep_Reinforcement_Learning_for_Cooperative_Path_Planning_of_UAV_Swarms
  107. https://dl.acm.org/doi/10.1145/3749566.3749592
  108. https://www.businessresearchinsights.com/market-reports/advanced-planning-and-scheduling-aps-software-market-102839
Add your contribution
Related Hubs
User Avatar
No comments yet.