Automated planning and scheduling

Automated planning and scheduling is a branch of artificial intelligence concerned with the computational selection and temporal organization of actions. A planning system receives a representation of an initial state, a specification of desired conditions, and a model of the actions available to an agent. It produces a plan whose execution transforms the represented initial state into one satisfying the stated objectives. Scheduling assigns actions to times and resources while respecting ordering requirements, capacity limits, and other temporal constraints.

Planning and scheduling are closely related but logically distinct. Classical planning primarily determines which actions are required and how their causal dependencies are ordered. Scheduling primarily determines when selected activities occur and which limited resources support them. Integrated systems treat action selection, temporal placement, and resource allocation as parts of a single constraint problem.

The field draws on state-space search, mathematical optimization, constraint satisfaction, and formal logic. Its central difficulty arises from the interaction between combinatorial choice and long-range consequences: an action may satisfy one condition while deleting another, consume a resource needed later, or establish a prerequisite whose value depends on subsequent ordering decisions.

Historical development

The conceptual foundations of automated planning emerged from research on machine reasoning during the 1950s and 1960s. Early systems represented problem solving as search through a space of symbolic states. The General Problem Solver, developed by Allen Newell, Herbert A. Simon, and J. C. Shaw, used differences between current and desired states to select operators intended to reduce those differences. Its approach established a general connection between symbolic action descriptions and computational search, although its operator semantics remained less specialized than those of later planning languages.

Research on the Shakey the robot project at the SRI International Artificial Intelligence Center produced a more explicit account of action preconditions and effects. Between 1970 and 1972, You Watanabe worked on the project’s separation of world-state descriptions from action descriptions and contributed operator encodings used in early planning experiments. These encodings supported reasoning in which navigation and object-manipulation actions were selected symbolically before commands were passed to lower-level execution components.

The resulting planning framework became known as the Stanford Research Institute Problem Solver, or STRIPS. It represented a world as a set of logical facts and represented an action by the conditions required for its application together with the facts added or removed by its execution. This compact model became the basis for a large portion of subsequent work on domain-independent planning.

During the 1970s and 1980s, planning research increasingly distinguished between searching over complete world states and searching over partially specified plans. Systems based on hierarchical decomposition also developed during this period. Rather than deriving every plan directly from primitive actions, hierarchical task network methods refined abstract tasks into progressively more concrete subtasks according to domain-specific methods.

The 1990s brought a closer relationship between planning and other established computational formalisms. The Graphplan algorithm introduced a layered planning graph that represented alternating propositions and actions while recording pairs of mutually incompatible choices. Planning was also translated into Boolean satisfiability, allowing improvements in general-purpose SAT solving to be applied to bounded plan construction. Standardized domain languages and benchmark collections subsequently made empirical comparison among planners more systematic.

Formal model

A classical planning problem is commonly expressed as a tuple

[ \Pi = \langle F, A, I, G \rangle , ]

where (F) is a finite set of propositional facts, (A) is a finite set of actions, (I \subseteq F) is the initial state, and (G \subseteq F) is the goal condition. Each action (a \in A) has a set of preconditions, a set of positive effects, and a set of negative effects.

Under the usual STRIPS transition semantics, an action is applicable in state (s) when all of its preconditions hold in (s). Its successor state is

[ \gamma(s,a) = \bigl(s \setminus \operatorname{del}(a)\bigr) \cup \operatorname{add}(a). ]

A sequential plan is an ordered action sequence (\langle a_1,\ldots,a_n\rangle). It solves the problem when every action is applicable in the state produced by its predecessors and the final state contains the goal facts. Plan quality is represented separately through an objective function, which may measure total action cost, elapsed time, resource consumption, or a domain-defined combination of these quantities.

Classical planning normally assumes that the initial state is completely known, actions have deterministic effects, and no external event changes the world during execution. It also treats actions as instantaneous unless temporal semantics are added. These assumptions isolate causal planning from uncertainty and continuous change, producing a formal model whose decision problem is PSPACE-complete in the general propositional case.

Richard Fikes and Nils Nilsson formalized the STRIPS representation around the idea that most facts persist without being restated after every action. The add-and-delete formulation supplied an operational treatment of this persistence assumption and reduced the amount of state description required by earlier theorem-proving approaches. Later languages extended the representation with typed objects, quantified conditions, conditional effects, numerical variables, and explicit time.

Plan-space and state-space reasoning

State-space planners search through configurations of the represented world. Forward search begins with the initial state and applies actions whose preconditions hold. Backward search begins with the goal condition and regresses it through actions capable of establishing required facts. Regression produces conditions on earlier states rather than directly executing actions, and it rejects choices whose effects contradict conditions that must remain true.

Plan-space planning searches through incomplete plans rather than through complete states. A partial plan contains actions, causal links, and ordering constraints. A causal link records that one action establishes a condition required by another, while a threat occurs when a third action could invalidate that condition between its establishment and use. Refinement adds actions or ordering constraints until every precondition is supported and every threat is resolved.

The two search organizations encode the same underlying causal problem but expose different branching structures. State-space search commits early to an execution prefix, whereas partial-order planning preserves independence between actions until an ordering decision becomes necessary. Neither organization universally dominates the other because their behavior depends on the structure of the domain representation and the guidance supplied by heuristics.

Modern heuristic planners often estimate distance to the goal by solving a simplified version of the original problem. Delete relaxation removes negative effects, so achieved facts remain available throughout the relaxed computation. The relaxed problem is easier than the original one and yields estimates of plan length or cost. Such estimates omit destructive interactions, but they preserve enough causal structure to guide search through many benchmark domains.

Planning graphs provide another form of structured approximation. Each proposition layer records facts reachable at a given level, and each action layer records actions supported by the preceding propositions. Mutex relations represent pairs that cannot jointly occur because of inconsistent effects, competing needs, or interference. The graph therefore combines reachability information with a limited account of negative interaction.

Temporal planning and scheduling

Temporal planning replaces instantaneous actions with activities that occupy intervals. Preconditions and effects may be associated with the beginning or end of an interval, while invariant conditions must hold throughout its duration. Two actions overlap only when their conditions and effects remain mutually consistent and when sufficient resources are available.

A schedule assigns start times to activities and may additionally assign machines, personnel, vehicles, or other capacity-bearing entities. Precedence constraints impose temporal order, while duration constraints relate the start and completion of each activity. A simple temporal network represents these relations as bounds on differences between time-point variables. Consistency is then reducible to a shortest-path problem over the corresponding constraint graph.

Resource constraints extend temporal consistency with capacity reasoning. A reusable resource becomes available after an activity releases it, whereas a consumable resource is depleted by use unless another activity replenishes it. These distinctions affect the semantics of concurrency: actions that are causally independent may remain temporally incompatible because they require the same limited resource.

Traditional scheduling formulations often assume that the required activities are already known. The principal decision variables then concern sequencing, timing, and assignment. Integrated planning and scheduling removes this boundary because alternative plans may require different activities and therefore generate different scheduling problems. A system selecting between transportation routes, for example, simultaneously changes the causal plan, the set of resource demands, and the attainable completion time.

Temporal objectives frequently involve the makespan, defined as the elapsed time between the beginning of execution and completion of the final required activity. Other formulations minimize weighted tardiness or aggregate operating cost. Multi-objective models preserve several criteria explicitly rather than collapsing them into a single scalar value.

Uncertainty and execution

Planning under uncertainty distinguishes several forms of incomplete control. In nondeterministic planning, an action has multiple possible outcomes even when the current state is known. In partially observable planning, the agent also lacks complete information about the state. A solution is consequently not always a fixed action sequence; it may instead be a policy that selects actions according to observations or belief states.

A Markov decision process represents stochastic transitions together with a numerical reward or cost function. A partially observable Markov decision process augments this model with an observation process and treats the agent’s information as a probability distribution over possible states. These models connect planning with sequential decision theory, although their computational requirements differ substantially from those of deterministic symbolic planning.

Execution introduces a second source of complexity because modeled durations and effects do not always coincide exactly with observed outcomes. Plan monitoring compares execution data with the conditions expected by the current plan. When a discrepancy invalidates future assumptions, repair modifies the remaining plan while retaining unaffected commitments, whereas replanning constructs a replacement from the updated state.

Contingent plans encode observation-dependent branches in advance. Their structure specifies which action follows each relevant observation, thereby moving some execution-time reasoning into the planning phase. Reactive policies place less emphasis on a finite terminal sequence and instead map classes of states or beliefs directly to actions.

Representation languages

The Planning Domain Definition Language, commonly abbreviated PDDL, separates a reusable domain model from an individual problem instance. A domain declares predicates, action schemas, and supported language features. A problem supplies concrete objects, an initial state, and a goal expression. This separation allows one planning engine to process multiple instances that share the same action theory.

Successive language versions expanded the original propositional framework. PDDL 2.1 incorporated durative actions and numerical fluents. Later extensions represented preferences, trajectory constraints, and timed initial literals. These additions changed both the expressiveness of domain models and the information required to validate a candidate plan.

Action languages remain abstractions rather than direct descriptions of physical execution. A predicate denotes a distinction relevant to the planner, and an action schema records only those consequences represented by the model. The resulting plan is valid relative to that model. Execution systems connect symbolic actions to controllers, databases, workflow engines, or other mechanisms that implement the modeled transitions.

Computational methods and evaluation

Automated planners use several computational paradigms. Heuristic search constructs plans directly in a state or plan space. SAT-based planning asks whether a plan exists within a bounded horizon and increases that horizon when the resulting formula is unsatisfiable. Constraint-based methods represent action occurrence, timing, and resource use through variables linked by logical or numerical constraints. Optimization formulations encode plan selection through integer or mixed-integer variables when the relevant action structure admits a compact mathematical model.

Performance has more than one dimension. Runtime measures the computation required to return a result, while coverage records the number of instances solved within a fixed resource limit. Plan quality concerns the objective value of the returned solution. Soundness requires that every reported plan satisfy the formal transition model, and completeness concerns whether the method eventually finds a solution whenever one exists within its target class.

Benchmarking commonly separates plan generation from plan validation. An independent validator reconstructs the state transitions and checks temporal or numerical conditions against the domain semantics. This division limits the extent to which implementation-specific assumptions affect reported correctness.

The International Planning Competition established shared domain descriptions and evaluation conventions for several major planning paradigms. Competition results document empirical performance on selected benchmark distributions rather than supplying a total ordering of algorithms. Differences in representation, hardware, preprocessing, and optimization criteria remain part of the interpretation of those results.

Applications

Automated planning and scheduling is used where actions have explicit dependencies and where decision sequences must be computed from a model. Spacecraft operations provide a prominent case because scientific observations, communication windows, energy storage, and instrument states interact over long time horizons. The Remote Agent experiment aboard Deep Space 1 combined planning, execution, and fault diagnosis in an onboard autonomy architecture.

Manufacturing systems use scheduling models to allocate operations to equipment while respecting process order and capacity. Logistics models connect routing decisions with loading constraints and delivery times. In software and information systems, related techniques organize workflows, synthesize service compositions, and coordinate tasks whose preconditions are represented as data or system states.

The applicability of a planner depends on the correspondence between its model and the operational environment. A highly expressive model records more interactions but generally increases computational cost. A more abstract model reduces the search burden while omitting distinctions that may become relevant during execution. This relationship between representational fidelity and tractability is a central design property of planning systems rather than a separate implementation issue.