Planning must track what an action destroys
A plan is more than a list of individually useful actions. Driving to a destination can make being at the starting location false; delivering an object can make carrying it false. A later action may therefore undo a condition established earlier. To reason about a whole plan, we need a precise account of preconditions, effects and facts that stay unchanged.
We use a finite propositional STRIPS model with positive preconditions and positive goals, deterministic actions and unit action costs. It is a useful core planning model, not a model of uncertain sensing, hidden facts, negative preconditions or conditional effects.
A state specifies all currently true facts
Definition 18.1.1
(States, actions and goals)
Let be a finite set of propositional facts. A state is a subset : exactly its members are true, and the other facts are false. Absence means false in this model, rather than unknown.
An action has sets , and , all subsets of , with add and delete sets disjoint. It is applicable when . Its successor is
A positive goal is a set , satisfied when . A plan is an applicable action sequence whose final state satisfies . Each action costs one, so plan cost is sequence length.
Preconditions are checked before execution and may be deleted by the action. Consuming a required resource is therefore permitted. Facts outside the add and delete sets retain their truth values. This frame convention specifies what does not change without listing every unaffected fact in every action.
Fact names alone impose no logical constraints. For example, two different location facts are not automatically exclusive in an arbitrary subset of . A domain may enforce exclusivity through its initial state and actions; such an invariant must be proved for reachable states.
A delivery domain with a return requirement
Use facts atA, atB, parcelA, carrying, delivered. The initial
state is and the goal is
. Actions are:
| Action | Preconditions | Add effects | Delete effects |
|---|---|---|---|
pickup | atA, parcelA | carrying | parcelA |
driveAB | atA | atB | atA |
driveBA | atB | atA | atB |
deliver | atB, carrying | delivered | carrying |
These symbols describe a small formal domain. No physical rule is being assumed beyond the stated facts and actions.
Worked example 18.1.2
(Delivery is not complete until the agent returns)
Execute the following four-action plan:
| Step | Action just applied | Resulting state |
|---|---|---|
| 0 | None | atA, parcelA |
| 1 | pickup | atA, carrying |
| 2 | driveAB | atB, carrying |
| 3 | deliver | atB, delivered |
| 4 | driveBA | atA, delivered |
Pickup leaves the location unchanged; driving leaves carrying unchanged; delivery leaves the location unchanged. These are consequences of the frame rule, not missing effects to be guessed.
The plan is shortest. Only deliver adds delivered; it requires carrying
and being at B. Only pickup creates carrying, and it is available at A.
At least one driveAB is needed before delivery. By the location invariant
proved next, delivery at B means atA is false. The final location goal
therefore needs a driveBA afterwards. These four distinct necessary
action types give a lower bound of four, attained above.
Proposition 18.1.3
(Location and parcel-stage invariants)
Starting from , every state reached by an applicable action sequence contains exactly one of atA, atB, and exactly one of parcelA, carrying, delivered.
Proof
(Induction on plan length)
The initial state has exactly one of atA and atB. Pickup and delivery
change neither fact. If driveAB is applicable in a state with exactly
one location, atA is true and atB false; deleting the former and
adding the latter preserves exactly one. The reverse drive is symmetric.
Induction on plan length proves the invariant for every reachable state.
Similarly, exactly one of parcelA, carrying, delivered holds:
pickup changes the first into the second, delivery changes the second
into the third, and driving changes none of them.
Proof X-ray
What the invariant depends on
The induction checks the four actions of this domain one by one, and each
check uses the full triple of the action. driveAB preserves exactly one
location because its precondition atA, together with the induction
hypothesis, forces atB to be false, and because it deletes atA while
adding atB. An extra action teleport with no precondition,
and no delete effects would break the
invariant at once: applied to it gives
. The invariant therefore
describes this action set, not arbitrary subsets of . The argument
closes because there are finitely many actions, each preserves the
property, and the initial state has it.
Regression asks what had to be true one step earlier
Forward search applies actions to states. Backward regression applies a possible last action to a target condition. The result should be a condition on the previous state, not a simulated previous complete state.
Theorem 18.1.4
(Exact regression of a positive goal)
For an action and goal set :
- If , no state can use as its last action and then satisfy .
- Otherwise define
In this no-delete-conflict case, for every state , is applicable and its successor satisfies if and only if .
Proof
(Separate goals made by the action from goals that must persist)
If some goal fact is deleted, disjoint add/delete sets ensure that it is not added back. The successor must lack it, so the action cannot be last in a plan achieving .
Now suppose no goal fact is deleted. Applicability requires exactly . Any goal in the add set is true after the action without needing to be true beforehand. A goal outside the add set is true afterwards exactly when it was true in , since it is not deleted. Thus the remaining requirement is .
Combining these two conditions gives the stated union, in both directions. The result is exact for this positive-precondition, positive-goal model. It does not silently handle negative goals or conditional effects.
The equivalence is a condition on formal states. Whether a particular state is reachable from the chosen initial state is a separate question.
Regress the complete plan, not each goal independently
Starting from the delivery goal, choose the last actions in reverse order:
| Target after the action | Proposed last action | Regressed target before it |
|---|---|---|
atA, delivered | driveBA | atB, delivered |
atB, delivered | deliver | atB, carrying |
atB, carrying | driveAB | atA, carrying |
atA, carrying | pickup | atA, parcelA |
The last regressed set is contained in . Reading the selected actions in forward order gives the four-action plan already verified. Regression subgoals need not specify every fact in the preceding state; unspecified facts are unconstrained by that target.
Trying deliver as the last action for the full goal instead gives
atA, atB, carrying. Its delete set does not directly conflict with
that goal, but its precondition atB and the persistent goal atA
create an unreachable subgoal under the proved location invariant.
Achieving atA and delivered separately is not enough to order a plan:
driving can destroy the location goal.
Worked example 18.1.5
(A regression step that leads to an unreachable subgoal)
Take the target . Two actions add one of its facts.
Through pickup, the delete set misses the target, so
The formula is exact for formal states, since that set does allow pickup and leads to a state containing the target. But it contains both locations, so the location invariant says that no reachable state satisfies it: the branch is valid yet dead.
Through driveAB, the delete set also misses the target and
. Regressing
this through pickup gives .
This branch recovers the prefix pickup, driveAB.
Counterexample mode
Dropping the delete-conflict test makes regression unsound
Take target atA, delivered and action driveAB. If one blindly applies
only the union formula, the regressed set is again atA, delivered.
The reachable state containing exactly those two facts satisfies it,
and the drive is applicable. But the successor is atB, delivered,
which fails the target because atA was deleted.
The omitted condition is therefore essential. The regression formula is not valid for an arbitrary last action without checking its delete effects.
Forward breadth-first search supplies a complete baseline
There are at most states. With finitely many actions, breadth-first search over applicable transitions is complete and finds a shortest plan under our unit-cost assumption. Mark a state seen when enqueuing it, so repeated drives and other cycles do not create endless duplicate work.
PLAN_BFS(initial, goal):
queue = [initial]
seen = {initial}
predecessor[initial] = NONE
while queue is not empty:
S = remove first state from queue
if goal is a subset of S:
return reconstruct action sequence from predecessor
for each action a:
if Pre(a) is a subset of S:
T = (S minus Del(a)) union Add(a)
if T is not in seen:
add T to seen
predecessor[T] = (S, a)
append T to queue
return NO_PLAN
Theorem 18.1.6
(Breadth-first planning is complete and optimal for unit costs)
For a finite fact set and unit action costs, PLAN_BFS terminates. It returns the empty plan exactly when the initial state satisfies the goal, returns a shortest plan whenever a plan exists, and returns NO_PLAN exactly when no plan exists.
Proof
(Queue layers are layers of plan length)
Each state is enqueued at most once, because it is marked seen on entry, and there are at most states, so the loop terminates. Every generated edge is a valid action application, so reconstruction is sound. The queue is FIFO: successors of one layer are appended after that layer's remaining states. Induction therefore makes dequeue order nondecreasing in minimum action count, and the first dequeued goal state has minimum length. If the queue empties, every reachable state has been examined, so no plan exists. A goal already true in the initial state gives the empty plan.
Finite-state completeness does not mean the search is inexpensive: the state count is exponential in .
In this domain the two invariants allow only six combinations: two
locations times three parcel stages. The displayed plan visits five; the
sixth, atB, parcelA, is reached by driving directly from the initial state.
The abstract
power-set bound is 32, while BFS first reaches the full goal at depth four.
For unequal action costs, ordinary BFS no longer proves minimum cost;
the search method must match the cost model.
Delete relaxation gives a lower bound, not another physical plan
Define the delete-relaxed version by replacing every delete set with the empty set. Its transition is , with the same positive preconditions and goals. For the fixed goal , let be the shortest original plan length and the shortest relaxed length, using if the respective goal is unreachable.
Theorem 18.1.7
(Delete relaxation never overestimates)
For every state and positive goal , , where is larger than every number. In particular, if the relaxed problem has no plan, neither has the original problem.
Proof
(Simulate the original plan in the relaxed model)
Run the same action sequence in the original and relaxed models, starting at the same state. Initially the states agree. If the original current state is contained in the relaxed one, every applicable positive precondition remains true in the relaxed state. The original successor deletes some facts and adds effects; the relaxed successor only adds those effects, so the containment is preserved.
Induction proves that an original plan is a relaxed plan of the same length. Therefore whenever an original solution exists, and the inequality extends to unreachable cases with . If even the relaxed problem is unsolvable, the original one is unsolvable.
Proof X-ray
Where positivity is used
The only invariant carried through the induction is containment: the original state is a subset of the relaxed state. Positive preconditions are monotone, so a larger state still satisfies them, and a positive goal is monotone too, so the larger final relaxed state still contains . Deleting never helps in this model; relaxing the delete sets exploits exactly that. Outside the model the step fails. Let , , goal , an action with precondition that deletes , and an action with the negative precondition " is false" that adds . The plan solves the original problem, but after relaxation is never removed, so is never applicable and .
In the delivery example, pickup, driveAB, deliver is a relaxed plan
of length three: driveAB never removes atA. Three is also necessary
because carrying, being at B and delivery need their three distinct
actions. Hence , compared with the original optimum 4.
Computing an exact relaxed optimum can itself be difficult; defining a
relaxation does not automatically make its optimal distance cheap.
Relaxed fact layers yield a simpler admissible estimate
Build growing fact sets, starting from the current state:
All action preconditions in a round use the old layer , not facts just added within that round. Define as the first index with , or if a fixed point is reached without the goal. Each strict-growth round adds at least one previously absent fact, so there are at most growth rounds. One additional non-growing round suffices to detect a fixed point if needed.
Proposition 18.1.8
(Relaxed layers give a lower bound)
For every state and positive goal ,
If the layers reach a fixed point without containing , the relaxed problem, and hence the original problem, has no plan.
Proof
(Relaxed plans stay inside the layers)
Let be a relaxed plan from and let be the relaxed state after actions. We show by induction. For , . If , the preconditions of lie in , so its add effects lie in ; since , we get . A relaxed plan of length ends with , so .
If the layers stop growing at a fixed point without , every , so no relaxed plan reaches ; then . The second inequality is the previous theorem.
A layer can add effects of several actions at once. It is not a sequential action count or an executable parallel schedule with delete conflicts.
For the example, contains atA, atB, parcelA, carrying, and
also contains delivered. The three bounds are therefore .
Both location facts in deliberately violate the original invariant:
these sets are overapproximations used for a bound, not physical reachable
states.
Worked example 18.1.9
(Estimates from the middle of the plan)
Let with the goal
. Only driveBA and deliver are
applicable, so
and . No single action adds both goal facts, and
driveBA, deliver is a relaxed plan in either order, so . In the
original model driveBA first deletes atB, making deliver inapplicable;
deliver, driveBA works, so . The bounds read : here
relaxation loses the ordering constraint but not the length, while the
layer count undercounts because one layer holds the effects of two actions.
Common mistakes
Common mistake
(A precondition is not deleted unless it is a delete effect)
Writing the successor of pickup at the initial state as carrying alone,
because atA and parcelA were "used". Only members of
are removed. The successor is
atA, carrying: atA persists by the frame rule and only parcelA is
deleted. A resource is consumed exactly when the domain lists it as a
delete effect.
Common mistake
(A relaxed layer is not a state)
Reading
as a state in which the agent can stand, then applying driveBA to it or
regressing from it. It contains both locations and two parcel stages, which
the invariant forbids for every reachable state. Layers collect the facts
that could hold after relaxed actions; their only role is the bound
.
Solved exercises
Quick check
(1. Check applicability and the frame rule)
Apply pickup to the initial delivery state. Is atA deleted because
it is a precondition? Can pickup be repeated immediately afterwards?
Solution · Solution 1
The successor is atA, carrying. Only parcelA is deleted; a precondition
does not disappear merely because it was required. atA persists by the
frame rule. Repeating pickup fails because parcelA is now false.
Preconditions are evaluated in the state before each attempted action.
Quick check
(2. Regress a target that the action destroys)
Regress the singleton target carrying through deliver. Why is the
union formula alone insufficient? Give an applicable preceding state
that would fool that incomplete rule.
Solution · Solution 2
Delivery deletes carrying, so the delete-conflict test rejects it as
a possible last action. The union formula alone would yield
atB, carrying. That state makes delivery applicable, but its successor
is atB, delivered, with carrying false. This is a direct counterexample
to omitting the conflict check.
Quick check
(3. Compute the relaxed layers and interpret their result)
List for the delivery initial state. Give the layer estimate, the shortest relaxed sequential length and the true shortest length. Does describe a reachable original state?
Solution · Solution 3
is atA, parcelA. The first layer adds carrying from pickup and
atB from driving, giving atA, atB, parcelA, carrying. The second adds
delivered, so . The relaxed sequential optimum is
3, while the original optimum is 4. is not an original reachable
state: it contains both locations and both parcelA and carrying.
Its purpose is a sound lower bound, not an execution trace.
Quick check
(4. One action can serve two goals)
Start with no facts and goal . One action has no preconditions and adds both , with no deletes. Compare the plan length with the sum of the two individual goal distances. Then replace it by two separate actions, one adding only and one adding only . Compare sequential distance with the relaxed-layer estimate.
Solution · Solution 4
With the joint action, the true and relaxed plan lengths are 1, as is the layer estimate. Each individual goal also costs 1, so their sum is 2 and overestimates: summing goal estimates can double-count a shared action and need not be admissible. With two separate actions, the sequential optimum is 2, but both effects appear in the first relaxed layer, so the layer estimate is 1. This remains a lower bound and shows why layers should not be reported as executable sequential plan lengths.