Automated planning and scheduling

• 1. Introduction

  ›

  Automated planning and scheduling is a branch of artificial intelligence that asks a deceptively simple question: given what the world looks like right now, and given what you want it to look like, what do you do next? The field concerns the discovery and execution of strategies or action sequences, typically by intelligent agents, autonomous robots, and unmanned vehicles. But the solutions to these problems are not simple. They must be found and optimized across multidimensional space, where the number of possibilities can grow exponentially. What happens when an agent cannot fully see the world around it? What if its actions do not always produce the results it expects? And how does a system plan for a future it cannot entirely predict? Those are the questions this field was built to answer.

• 2. The Classical Problem

  ›

  The simplest version of any planning problem starts with four ingredients: a unique known initial state, actions that happen instantaneously without duration, actions that are entirely deterministic, and a single agent. This is what researchers call the Classical Planning Problem, and its elegance is that it removes all uncertainty. Because the starting state is known without any ambiguity, and every action produces an exact and predictable outcome, any sequence of actions can be forecasted precisely before a single step is taken. Plans can be expressed as straightforward sequences because there is no branching, no uncertainty, and no need to prepare alternative responses. The agent never needs to ask "what if?"; it simply executes. Algorithms for solving classical planning problems include forward chaining state space search, backward chaining search using constraints, and partial-order planning, sometimes enhanced with heuristics. Two of the most influential languages for expressing these problems are STRIPS and PDDL, both grounded in state variables, where each possible state of the world is an assignment of values to those variables, and actions define how those values shift. The catch is that a set of state variables generates a state space that grows exponentially in size, a challenge researchers call the curse of dimensionality and the combinatorial explosion.

• 3. When the World Is Uncertain

  ›

  Michael L. Littman demonstrated in 1998 that when actions can branch, the planning problem becomes EXPTIME-complete, meaning that even verifying a solution can demand exponential time. That finding frames the core challenge of planning under uncertainty: as the world becomes less predictable, the problem becomes structurally harder. One major variant is contingent planning, where the environment is observable through sensors that can be faulty. A plan in this setting is no longer a sequence of steps but a decision tree, because each step represents a set of possible states rather than a single perfectly known one. A common illustration: if it rains, the agent takes the umbrella; if it does not, it may leave it behind. The agent is watching the world and reacting. A related variant, conformant planning, removes even that partial window onto the world. The agent holds beliefs about the real state of things but cannot confirm them through any sensing action. Haslum and Jonsson showed that conformant planning is EXPSPACE-complete, and becomes 2EXPTIME-complete when both the initial situation is uncertain and action outcomes are nondeterministic. Contingent planning also gives rise to a specific class called FOND problems, for fully-observable and non-deterministic, where if the goal is specified in LTLf, linear time logic on finite trace, the problem is always EXPTIME-complete, and 2EXPTIME-complete if specified with LDLf.

• 4. Conditional and Hierarchical Plans

  ›

  Deterministic planning first appeared with the STRIPS planning system, a hierarchical planner in which action names are ordered in a sequence. Hierarchical planning can be compared to an automatically generated behavior tree, but a standard behavior tree carries a limitation: it contains action commands without loops or conditional statements, making it less expressive than a computer program. Conditional planning addresses that gap by introducing a notation similar to control flow found in programming languages like Pascal. A conditional plan can react to sensor signals the planner did not know in advance, generating two prepared choices before execution begins: if an object is detected, execute action A; if the object is absent, execute action B. An early example of a conditional planner is Warplan-C, introduced in the mid-1970s. One practical benefit of this approach is the ability to handle partial plans. An agent does not need to map out every step from start to finish but can divide the problem into chunks, reducing the state space and making more complex problems tractable. Closely related to conditional planning is the framework of hierarchical task networks, where a set of tasks is given and each task can either be realized by a primitive action or decomposed into subtasks. State variables are not strictly required in this framework, though in more realistic applications they help simplify the description of task networks.

• 5. Time, Probability, and Preference

  ›

  Temporal planning extends the classical framework by allowing actions to have duration and to overlap in time. Because multiple actions can now be running concurrently, the definition of a state must expand to include the current absolute time and how far along each active action has progressed. When time is expressed in rational or real numbers rather than integers, the state space can become infinite, a complication absent from classical planning. Temporal planning connects closely to scheduling problems when uncertainty is involved, and can also be understood through the framework of timed automata. One specific scheduling construct here is the Simple Temporal Network with Uncertainty, known as STNU, which involves controllable actions, uncertain events, and temporal constraints; Dynamic Controllability for such problems requires reacting to uncertain events in real time to guarantee all constraints are met. Probabilistic planning takes a different route by working with Markov decision processes, or MDPs, which combine nondeterministic actions with known probabilities, full observability, and a reward function to maximize rather than a fixed goal state. When full observability is replaced by partial observability, the framework becomes a partially observable Markov decision process, a POMDP. Both can be solved with iterative methods such as value iteration and policy iteration when the state space is small enough. Preference-based planning adds another dimension: instead of only meeting a goal or maximizing a numerical reward, the agent must also satisfy user-specified preferences that may not carry any precise numerical value, distinguishing this approach from MDP-style reward maximization.

• 6. Domain Models and Real Machines

  ›

  Domain-independent planners accept two kinds of input: a domain model describing the set of possible actions in a given environment, and a specific problem defined by its initial state and goal. The phrase domain-independent highlights their flexibility, since a single planner can be applied to block-stacking, logistics, workflow management, and robot task planning without modification. A route planner, by contrast, is a typical example of a domain-specific planner, built for one kind of problem only. Creating a domain model is difficult, time-consuming, and prone to error, which has driven the development of action model learning, a family of methods for automatically deriving full or partial domain models from observations rather than hand-coding them. Planning also connects to other computational frameworks: the classical planning problem can be reduced to the propositional satisfiability problem, an approach called satplan, and can also be reduced to model checking, since both involve traversing state spaces. In dynamically unknown environments, planning often cannot be done offline and instead must be revised in real time using techniques from dynamic programming, reinforcement learning, and combinatorial optimization. One of the most visible real-world deployments of planning technology is the Hubble Space Telescope, which relies on a short-term scheduling system called SPSS and a long-term planning system called Spike to manage its complex observation schedule.