Automated planning

Constructing a sequence of actions whose successive applications transform a specified initial state into one satisfying a goal. The formal model must specify action preconditions, state changes and the meaning of facts absent from a state. STRIPS represents changes by add and delete lists; planning state invariants explain which physical properties the action definitions preserve.

In deterministic classical planning, a finite sequence of actions applicable successively from the initial state and ending in a state satisfying the goal. A STRIPS plan must respect every action's precondition set and both add and delete effects. A numerical bound on a possible plan's cost does not itself specify the action sequence.

Automated planning with several possible successors for an action and no specified probabilities for choosing between them. A plan must say how to act after observed outcomes. A strong plan guarantees eventual success for every possible outcome history; a favorable outcome on just one branch does not establish that guarantee.

A plan or policy that reaches a goal after finitely many steps under every permitted outcome sequence. In a finite state space with finite outcome sets, a terminating finitely branching plan tree has bounded depth. Strong planning winning-set iteration constructs exactly the states from which such finite guaranteed-success plans exist. A repeated state cannot be accepted merely because repeated attempts might eventually succeed: without a fairness or probability assumption, an unfavorable outcome can recur forever.

For a finite nondeterministic planning problem with goal set $G$, initialize $W_0=G$ and putA state in $W_t$ has a strong plan reaching $G$ within $t$ steps. The proof is mathematical induction: an action witnessing admission to $W_{t+1}$ has only successors with plans of depth at most $t$. Conversely, the first action of any guaranteed plan of depth $t+1$ has every successor in $W_t$, again by mathematical induction. Since $W_t$ only grows inside a finite state space, the iteration stabilizes after at most the number of states many strict expansions. Recording a witnessing action at first admission gives a policy whose rank decreases at every nonterminal step.

Automated planning whose result may branch on information revealed during execution. In partially observable search, an AND-OR search chooses an action at each OR node and requires a continuation for each possible observation at its AND branches. A contingent plan can therefore be a conditional tree or a policy on belief states, rather than one fixed action sequence.

Automated planning with a completely specified initial state, deterministic actions and a goal condition. A finite STRIPS model is a common representation. A plan is an action sequence applicable from the initial state, ending in a goal state. Unknown facts about the initial world require an epistemic representation such as a belief state, rather than silently interpreting every unlisted fact as false.

Two subgoals interact when actions needed for one can establish, obstruct or delete facts needed for the other. A plan for each subgoal separately need not combine into a plan for their conjunction. Preparing the world before committing to a subgoal, revising an earlier subplan or temporarily undoing an achieved fact can all be necessary. Goal-by-goal planning may therefore be incomplete.

The Sussman anomaly is a blocks world example in which independently constructing the obvious subplans for two stacking goals gives destructive goal interaction in planning. Clearing a block in advance allows a short joint plan, while prematurely achieving either isolated goal can block the other. It demonstrates the inadequacy of restricted goal-by-goal planning, rather than a prohibition on every possible ordering of final goal achievements. Preparatory actions can make such an ordering succeed. For a concrete instance, start with $C$ on $A$ and $A,B$ on the table, and require $A$ on $B$ and $B$ on $C$. Moving $C$ to the table, then $B$ onto $C$, then $A$ onto $B$ succeeds. The first move is preparation that an isolated shortest subplan for the second stacking goal would omit.

A restricted goal-by-goal planning procedure chooses one subgoal, constructs a subplan for it without preparation motivated by other pending subgoals, then moves on while treating the earlier goal as protected. Destructive goal interaction in planning can defeat either ordering. Merely requiring the final plan to be a concatenation of subplans is a weaker condition: a subplan may already contain preparatory work useful to a later goal. A claimed impossibility must specify the stronger restriction rather than infer it from concatenation alone.

The blocks world is a classical planning model of movable blocks arranged in stacks on an unlimited table. Each block has one support, each block supports at most one other block, and the support relation has no directed cycle. A clear block can move onto another clear block or onto the table. In a direct-transfer STRIPS representation, an action includes the entire pickup-and-placement operation; a separate holding or empty-hand planning fluent is unnecessary unless the action model explicitly splits those operations.

The table has unlimited capacity, so its availability must not be deleted when a block is placed there. Planning state invariants connect the predicate describing a clear block to the absence of any block directly above it. Goal interaction in planning makes this small model useful for testing automated planning methods.

For a positive conjunctive goal $G$, an action with $\mathrm{Del}(a)\cap G=\varnothing$ can serve as the final step. Before it executes, the remaining goals and its preconditions must hold, giving the displayed regressed set. For precondition-free STRIPS planning, only deletion of already supplied requirements remains.

A condition specifying when a fact remains unchanged by an action. In STRIPS, facts outside the add and delete lists persist. A successor-state axiom combines these persistence conditions with all action effects that can change the fact.

A logical equivalence characterizing exactly when a planning fluent is true after one step. Here ${\mathrm{Add}}_F$ and ${\mathrm{Delete}}_F$ are disjunctions of selected actions with the respective effects, under a suitable action-conflict policy. The persistence term excludes spontaneous changes and captures the relevant frame axiom. An implication from add effects alone would not constrain all other state changes.

An approach to automated planning that constructs a Boolean satisfiability problem for a bounded planning horizon, solves it and decodes a satisfying assignment into a plan. A typical encoding has time-indexed action occurrences and planning fluents, initial and goal clauses, action precondition axioms, state-transition constraints and action exclusion axioms. Sequential and parallel encodings have different notions of a step.

Henry Kautz and Bart Selman introduced planning as satisfiability in their 1992 paper.^[ref]

A sequential SATPlan encoding has a complete initial assignment of planning fluents, final goal constraints, action precondition axioms, successor-state axioms and action exclusion axioms allowing at most one action per layer. Zero selected actions is an idle step: the successor-state axioms preserve all facts. This encodes an upper bound on plan length rather than forcing exactly $T$ physical actions.

For soundness, read selected ground actions in layer order. The initial assignment is the real initial state. By mathematical induction, each selected action has its preconditions in the current state and the successor-state axioms give precisely its add/delete update; an empty layer leaves that state unchanged. The final goal constraint therefore proves that the decoded plan succeeds. Conversely, take any plan of length at most $T$, assign its actual state trajectory to the fluent variables, select its actions in successive layers and pad with idle layers. All encoding components hold. Complete initial negations and persistence conditions are essential: omitting either can introduce unsupported facts and spurious plans.

A condition forbidding a conflicting pair of action occurrences in one layer. A serial SATPlan encoding excludes every distinct pair; parallel encodings exclude the pairs disallowed by their concurrency semantics. Excluding two simultaneous pickups can enforce a one-hand resource restriction even if both individual precondition sets hold.

A clause or formula ensuring a selected action occurrence has all of its preconditions satisfied at the current time. It is one part of a plan encoding; action effects, persistence, initial conditions and goals require additional constraints.

The number of action layers allowed in a bounded automated planning encoding. Sequential layers permit at most one physical action, while a parallel semantics may permit several compatible actions. A sufficiently large horizon guarantees finding a solution only for a solvable input; shorter plans require idle layers or testing the successive smaller horizons.

Expand a concrete state by applying every action whose preconditions hold, and search the resulting state graph for a goal. For STRIPS, the successor is $(S\setminus \mathrm{Del}(a))\cup \mathrm{Add}(a)$. A valid expansion checks the complete precondition set, including resource markers such as an empty hand, rather than only an action's geometric destination.