Motivation
A list of desirable action effects is not yet a plan. Every action must find its preconditions true when it executes, and later actions must preserve facts needed by subsequent ones. A planner therefore has to reason both about producing facts and about protecting them. Choosing the same useful actions in a different order can change success into failure.
There are two natural search spaces. State-space search commits to one complete state after each action. Plan-space search instead refines a set of action occurrences and ordering constraints, postponing choices that do not yet matter. The latter can represent several legal execution orders at once, but its causal commitments must be checked carefully. A partial order does not automatically mean that its actions are safe to execute simultaneously.
We retain deterministic finite positive-precondition STRIPS from the earlier unit, then supply two complete algorithms with explicit hypotheses. Breadth-first state search is complete over the finite state graph. A bounded partial-order refinement algorithm is complete for plans using at most a specified number of actions.
Definitions
Definition 6.1.1
(STRIPS planning problem and state transition)
Let be a finite set of propositional facts, the initial state, the positive goal, and a finite set of ground actions. An action has positive preconditions, disjoint add and delete lists, and deterministic successor when its preconditions hold. Every action costs one in the shortest-length result below. There are at most possible states, including ones unreachable from .
Definition 6.1.2
(Action occurrences and partial-order plans)
An action occurrence is a particular step, not just an action name. The same ground action may occur several times in a plan. A partial-order plan has finitely many occurrences, a strict acyclic precedence relation, and two special steps: Start adds exactly and has no preconditions; Finish has preconditions and no effects. Start precedes Finish and every ordinary step; every ordinary step precedes Finish. A linearization is a total ordering extending the precedence constraints.
Definition 6.1.3
(Causal links, threats and open conditions)
A causal link claims that step establishes precondition of step and that the fact survives in between. It requires , , and . A step deleting threatens the link unless the ordering already forces or . These exclusions put a potential deleter outside the protected interval. An open condition is a precondition occurrence not yet assigned a supporting link. We exclude ; an action cannot establish its own precondition by its later effect.
Definition 6.1.4
(Complete protected plan)
A complete protected plan has no open conditions, every causal link is protected from all threats, and its ordering is acyclic. This definition gives a verifiable certificate. It may contain redundant actions or links; minimality is a separate property. It concerns sequential linearizations under the chosen action semantics, not physical concurrency, durations or resource capacity.
Theorem/Proposition
Theorem 6.1.5
(Complete shortest-length search in a finite state graph)
Breadth-first search from , generating every applicable ground action and recording each reached state only once when enqueued, terminates on the finite state graph. It returns a shortest action-count plan if a goal state is reachable, and reports failure otherwise. Correct state keys must retain every fact affecting action applicability and effects.
Theorem 6.1.6
(Protected plans and bounded refinement completeness)
Every linearization of a complete protected plan is an executable plan achieving . For each finite action bound , the exhaustive refinement procedure below terminates and finds such a plan exactly when some executable plan of at most ordinary actions achieves . Completeness requires trying every action assignment, supporter and consistent threat resolution; a single greedy refinement path does not suffice.
Proof sketch or proof idea
Proof
(Breadth-first order and shortest paths)
For breadth-first search, initialize the queue with , mark it visited, and store no predecessor. Repeatedly remove the oldest state, test the goal, and for each applicable action compute its successor. Enqueue a successor only if unvisited, marking it immediately and recording the state-action predecessor. When a goal is removed, follow predecessors backwards to reconstruct the sequence. If the queue empties, return failure.
Induction on graph distance shows all states at distance are removed before states first discovered at distance . Every reachable state appears: for a shortest path to an allegedly missing state, its predecessor would already be generated and its last action would generate it. Thus a goal first removed has minimum distance. At most states enter the queue. With finite action lists and finite state operations, termination follows. Ignoring unreachable states can save work but is not a change to the completeness argument.
Proof
(Soundness of a protected plan)
For partial-order soundness, take any linearization and use induction over its steps. Every precondition of the next step has a supporting link from some earlier . Start makes its supported initial facts true, while an ordinary supporter makes its add effects true when executed. Any other step deleting is ordered before or after , so none can erase it between support and use. Therefore still holds just before . All preconditions hold, so is applicable. At Finish the same argument gives every goal fact.
Proof X-ray
A causal link proves persistence over an interval
The supporting action proves that a fact becomes true at one point. Threat protection proves that no intervening action destroys it before use. Both are required. The soundness argument does not require a global statement that every fact remains true forever; it protects only the particular intervals needed by the plan.
Here is a deliberately exhaustive bounded refinement procedure. For every , create labeled ordinary occurrences and enumerate all assignments of ground actions to them. Begin with the required Start/Finish order constraints. Put every ordinary precondition and every Finish goal on the open-condition agenda. Choose an open condition and branch over all distinct occurrences , including Start, that add . Insert and the causal link; discard a branch if ordering becomes cyclic. Remove that open condition. For any threat to a link , branch on adding or , again discarding cycles. Continue until all open conditions and threats have been resolved, or all branches fail.
Proof
(Termination and completeness of bounded refinement)
There are finitely many action assignments and precondition occurrences. Each support choice permanently removes one open condition, and each threat resolution adds a previously unforced ordering relation. There are finitely many pairs of steps; no relation is later removed. Hence each branch is finite and the branching factor is finite. Exhaustive search terminates. A topological ordering of a successful branch gives an executable sequence by soundness.
For completeness, suppose a valid sequence of actions exists. One enumerated assignment uses exactly these occurrences. For every precondition use, choose the latest earlier action adding the required fact, or Start if the fact persisted from the initial state. Validity ensures such a supporter exists and no intervening step deletes the fact; a re-adding action would itself be a later supporter. Choose each threat's before-or-after resolution consistently with this witness sequence. Every selected ordering relation holds in the witness, so no cycle arises. That branch supports all preconditions and protects all links, and therefore succeeds. The bound is essential: failure for rules out plans of length at most three, not all longer plans.
Worked examples
Worked example 6.1.7
(A shortest plan can require destroying a goal first)
Let the initial state be , meaning a cake is available, and let the goal be , meaning cake available and cake eaten. Eat requires , adds , and deletes . Bake has no precondition and adds . Breadth-first search sees that the empty plan and either one-action plan fail. Eat then Bake gives then and succeeds in two actions. Bake then Eat fails because the final available-cake fact is deleted. A currently true goal may need to be temporarily lost.
Worked example 6.1.8
(Threat resolution determines the useful ordering)
For the cake problem, support Eat's from Start, Finish's from Eat, and Finish's from Bake. Eat threatens the link Bake Finish. Ordering Finish before Eat is impossible because all ordinary steps precede Finish. The remaining resolution is Eat before Bake. The resulting partial order yields the successful sequence. Trying to support Finish's directly from Start instead leaves Eat threatening a link whose two resolutions both conflict with Start/Finish constraints, so that branch fails correctly.
Concept lensCombinatorial
A plan as a set of linear extensions
A protected plan describes a whole set of action sequences: its executable orders are exactly the total orders extending the precedence relation, the linear extensions of the partial order. In the cake plan the constraint Eat before Bake leaves one sequence. With ordinary steps and no constraints among them there are sequences, and a protected plan makes all of them valid. Each added causal or threat constraint removes some of that flexibility.
Worked example 6.1.9
(Independent subgoals need no arbitrary order)
Initially facts are and . Action A requires and adds ; action B requires and adds ; neither deletes anything. The goal is . Links Start to A for , Start to B for , and A/B to Finish for their goal facts form a protected plan without ordering A against B. Both A,B and B,A are valid linearizations. This does not by itself authorize simultaneous execution on one physical machine: an unmodeled shared resource could forbid overlap even though both sequential orders are legal.
Common mistakes
Counterexample mode
Useful actions can invalidate each other's preconditions
Initially . A requires , adds , and deletes ; B requires and adds . Goal needs both. The link Start B is threatened by A, forcing B before A, since A cannot precede Start. Choosing A then B fails at B's precondition. A set of action names is therefore insufficient to certify a plan.
Common mistake
(Treating the delete list as the whole story)
The frame problem has a local answer in this model: all facts outside the delete list persist. That answer relies on the action description containing every relevant change. If unlocking a device also disables an alarm through an indirect mechanism, and the alarm matters to future actions, the effect must be represented or derived under an explicitly extended semantics. A planner is not a physical-law discovery procedure.
Common mistake
(Checking threats against direct edges only)
Partial orders must be closed conceptually under transitivity when checking threats. If the constraints imply through several steps, the threat is already resolved even without a direct edge. Conversely, a cycle hidden in several indirect constraints is just as invalid as a two-step cycle. A reachability test or topological check is needed, rather than examining only the newly inserted edge's endpoints.
Common mistake
(Reading completeness as a guarantee about the real task)
These completeness theorems assume all relevant actions are grounded and generated. A planner restricted to an incomplete action library can fail despite a real-world solution. Positive goals and deterministic effects also exclude many practical problems involving information gathering, uncertainty, time and resources. Those omissions are model boundaries, not minor implementation details.
Summary
Breadth-first state search gives a complete finite baseline and shortest action-count plans. Causal links express who establishes each needed fact, while threat resolution protects that fact until use. Exhaustive bounded refinement is complete because it contains a branch consistent with any valid witness sequence within its bound. Order, persistence and model adequacy each require an explicit argument.
Exercises
Exercise 6.1.10
(In the cake example, list all states reachable from and show that breadth-first search can store states rather than every action history without losing completeness.)
Core
Solution(3)
- 1
List the reachable states
Bake at changes nothing and Eat gives . From , Bake reaches and Eat is inapplicable. From , Eat returns to and Bake changes nothing. The reachable states are , and .
- 2
Argue that the state is enough
Key step
Any continuation from two histories that end at the same state is identical as a planning possibility, because applicability and effects depend only on the state.
Because: The state contains all applicability and effect information.
- 3
Keep the first history
Keeping the first breadth-first history to each state preserves a shortest route to that state, so discarding later histories loses neither completeness nor shortest length.
Exercise 6.1.11
(For the common-mistake example, give every causal link in a successful protected plan and one legal linearization. Identify the threat and its only consistent resolution.)
Core
Solution(3)
- 1
List the causal links
Use Start B, Start A, A Finish and B Finish.
- 2
Find the threat and its resolution
Key step
A deletes and so threatens the link Start B. The resolution A before Start is impossible, since Start precedes every step, leaving B before A. The deletion at A does not threaten its own incoming link, because its precondition is tested before its effects.
Because: A deletes , which B needs from Start.
- 3
State a linearization
The legal sequence B, A achieves both and .
Exercise 6.1.12
(Suppose is a link and a distinct deleting step has constraints . Show why neither ordinary threat-resolution branch can succeed. What new support might repair the plan after changing its causal links?)
SynthesisProof
Solution(3)
- 1
Try the first resolution
The resolution would have to be added to the existing constraint .
- 2
Try the second resolution
Key step
The resolution would have to be added to the existing constraint . Each of the two resolutions creates a cycle of two constraints, so both branches are discarded.
- 3
Consider a repair
∎If an action can re-add between and , replacing the link by may repair support, provided the preconditions of are supported and all new threats are resolved. This is a different refinement branch with a different supporter, not permission to ignore the original threat.
Exercise 6.1.13
(If a bounded refinement run exhausts all branches at , what has it proved? Explain how increasing bounds gives a semidecision procedure in general, and why finite state search gives a stronger terminating decision procedure under this unit's hypotheses.)
Synthesis
Solution(3)
- 1
State what the failure proves
It rules out plans with zero, one or two ordinary actions, assuming exhaustive generation and correct checks. It does not rule out longer plans.
- 2
Describe the semidecision procedure
Trying increasing finite bounds eventually finds any finite plan if one exists, but this alone supplies no stopping rule when none exists.
- 3
Compare with finite state search
Breadth-first search exhausts a finite state graph and can certify failure. In fact any reachable goal has a simple state path of at most actions, so that bound would also suffice for a finite exhaustive bounded procedure, though usually at enormous cost.
Because: Under the finite propositional hypotheses the state graph is finite.