An engineering masterclass on deliberate action synthesis: factored state-action representations in STRIPS and PDDL, forward progression vs. backward regression, Partial-Order Planning (POP) with causal links, Planning Graphs and the GRAPHPLAN algorithm, Hierarchical Task Networks (HTN), and mission-critical applications.
In classical search (such as A* on the Romania road network), an agent searches through an atomic state graph where states are opaque black-box labels. Automated Planning opens these black boxes: states and actions are represented with explicit internal structure (factored representations), allowing the planning algorithm to reason deliberately about preconditions, causal dependencies, and side-effects.
At(Plane1, JFK) ^ At(Cargo1, JFK)). Under the Closed-World Assumption, any literal not explicitly stated as true is assumed to be false.At(Cargo1, SFO) ^ At(Cargo2, SFO)). Any world state that satisfies all conjuncts in the goal description is an acceptable goal state.| Feature / Dimension | Standard State Search (A*, BFS, DFS) | Automated Planning (STRIPS, PDDL, Graphplan) |
|---|---|---|
| State Representation | Atomic: States are monolithic IDs with no accessible internal structure. | Factored: States are conjunctions of logical propositions and relational predicates. |
| Action Representation | Black-box transition function Result(s, a). The engine cannot inspect what an action does without running it. |
Explicit declarative Precondition and Effect lists. The engine inspects causal interactions directly. |
| Goal Specification | Opaque boolean function IsGoal(state). |
Explicit conjunction of subgoals (e.g., On(A, B) ^ On(B, C)). |
| Heuristic Derivation | Must be hand-crafted by human engineers (e.g., straight-line distance, Manhattan distance). | Domain-Independent Automatic Heuristics: Derived mechanically by dropping action delete lists or relaxing constraints! |
| Direction of Search | Strictly forward from initial state (backward search is impossible when goal test is an implicit function). | Can search forward (Progression) or backward from the goal (Regression) with equal ease! |
To standardize planning across academic and industrial systems, researchers formalized action representations, beginning with STRIPS in 1971 and evolving to the modern ISO-style standard PDDL (Planning Domain Definition Language).
Developed for the Shakey the Robot project at Stanford Research Institute. An action schema consists of:
Move(b, x, y)On(b, x) ^ Clear(b) ^ Clear(y)On(b, y) ^ Clear(x)On(b, x) ^ Clear(y)New_State = (Current_State - Delete_List) + Add_List
Introduced by Drew McDermott (1998) to support the International Planning Competitions (IPC). It decouples the general physics of the domain from a specific problem instance:
:init state, and the :goal state.;; PDDL Domain Definition for Air Cargo Transport
(define (domain air-cargo)
(:requirements :strips :typing)
(:types cargo plane airport)
(:predicates
(In ?c - cargo ?p - plane)
(At ?x - (either cargo plane) ?a - airport))
;; Action 1: Load Cargo into Plane
(:action Load
:parameters (?c - cargo ?p - plane ?a - airport)
:precondition (and (At ?c ?a) (At ?p ?a))
:effect (and (not (At ?c ?a))
(In ?c ?p)))
;; Action 2: Unload Cargo from Plane
(:action Unload
:parameters (?c - cargo ?p - plane ?a - airport)
:precondition (and (In ?c ?p) (At ?p ?a))
:effect (and (not (In ?c ?p))
(At ?c ?a)))
;; Action 3: Fly Plane between Airports
(:action Fly
:parameters (?p - plane ?from - airport ?to - airport)
:precondition (At ?p ?from)
:effect (and (not (At ?p ?from))
(At ?p ?to)))
)
The classic benchmark domain in automated planning is the Blocks World, consisting of flat square blocks on a table, manipulated by a single robotic gripper. Predicates include: On(x, y), OnTable(x), Clear(x), and Holding(x).
Initial Configuration: Goal Configuration:
[ C ] [ A ]
[ A ] [ B ] [ B ]
======== ======= ========
Table Table [ C ] on Table
Why Simple Linear Planners Fail:
- If planner tries to solve Goal 1 first ("Put A on B"):
It must unstack C from A, then place A on B.
Result: [A on B] on Table, with C on Table.
Now to solve Goal 2 ("Put B on C"):
It MUST TEAR DOWN [A on B] to pick up B! It undoes its own progress!
- Principle Demonstrated: Subgoals in planning CANNOT always be solved
independently in isolation; actions for different subgoals must be INTERLEAVED!
Planning algorithms can search directly through the space of states using standard search algorithms (like A* with domain-independent heuristics). There are two complementary search directions:
Starts at the complete Initial State and moves forward toward the goal:
Pros: Operates on completely known states; very intuitive.
Cons: Branching factor can be huge because many legal actions are completely irrelevant to the goal (e.g., driving a cargo truck in circles).
Starts at the Goal Description and searches backward toward the initial state:
A that is relevant: it must achieve at least one of the target subgoals, and its delete list must not destroy any other target subgoals.A's add list, and add all of A's preconditions as new subgoals to be satisfied.
Pros: Highly focused: only examines actions relevant to the goal.
Cons: Must manipulate sets of states (partial state descriptions) rather than concrete individual states.
What makes forward search fast in modern planners (such as Fast Forward / FF)? The ability to automatically derive admissible heuristics directly from the PDDL text:
State-space search generates totally ordered plans: a strict linear sequence of actions: Step 1, then Step 2, then Step 3.... If two subproblems are completely independent (e.g., putting on your left sock and putting on your right sock), a total-order planner is forced to make arbitrary ordering choices, multiplying the search tree needlessly.
Partial-Order Planning (POP) searches through the space of plans rather than the space of world states. It adheres strictly to the Principle of Least Commitment: never order two actions unless forced to do so to resolve a causal conflict!
Start with effects = Initial State, and dummy Finish with preconditions = Goal).A < B (meaning action A must occur at some point before action B, though not necessarily immediately before).A --[p]--> B. Meaning: action A produces effect p explicitly to satisfy the precondition p required by action B. Causal links protect p from being tampered with between A and B!
A Threat occurs when an action C has an effect that negates condition p (i.e., deletes p), and C could potentially be ordered between A and B where a causal link A --[p]--> B exists.
The Threat Conflict:
Action A ----[ produces p ]----> Action B
^
| deletes p! (Threat)
Action C
How POP Resolves the Conflict:
1. PROMOTION (Force C to happen BEFORE A):
Add ordering constraint: C < A
Result: C deletes p before A even creates it. Link A --[p]--> B is SAFE!
2. DEMOTION (Force C to happen AFTER B):
Add ordering constraint: B < C
Result: B consumes p before C deletes it. Link A --[p]--> B is SAFE!
In 1997, Avrim Blum and Merrick Furst introduced GRAPHPLAN, which fundamentally changed automated planning by constructing a polynomial-sized data structure called a Planning Graph to identify reachability and mutual exclusions before doing any search.
A Planning Graph is a directed, layered graph organized into alternating levels of proposition (state) nodes and action nodes: S0, A0, S1, A1, S2, A2...
Si, along with Persistence Actions (No-Ops) that carry each proposition unchanged from Si to Si+1.Ai.Two actions or two propositions at the same level are marked as Mutex (Mutually Exclusive) if they cannot possibly occur or hold simultaneously:
| Mutex Category | Entity Type | Formal Condition | Intuitive Example |
|---|---|---|---|
| Inconsistent Effects | Action Mutex | One action adds a literal that the other action deletes. | Load(Cargo1, Plane1, JFK) deletes At(Cargo1, JFK) while a No-Op persists At(Cargo1, JFK). |
| Interference | Action Mutex | One action deletes a precondition of the other action. | Fly(Plane1, JFK, SFO) deletes At(Plane1, JFK), which is a precondition for Load(Cargo1, Plane1, JFK). |
| Competing Needs | Action Mutex | One of the preconditions of action A is mutex with one of the preconditions of action B. | Action A requires Holding(BlockA) while Action B requires Holding(BlockB) (gripper cannot hold both). |
| Inconsistent Support | Proposition Mutex | Every possible pair of actions that can produce proposition P and proposition Q are themselves mutually exclusive. | Propositions At(Cargo1, SFO) and At(Cargo1, JFK) cannot both hold at Level S1. |
Si to extract a conflict-free set of parallel actions that achieves the goals.
Si+1 and repeat.Classical planning synthesizes plans from scratch using low-level primitive actions. In complex real-world problems (e.g., building a house or writing an operating system), humans think hierarchically. Hierarchical Task Network (HTN) Planning mirrors this by allowing agents to decompose high-level abstract tasks into structured networks of lower-level actions.
TurnLeft, Drive(5km)).TravelFrom(NY, London) or BuildRoof).An HTN Method specifies how to break down a compound task into a sub-network of smaller tasks:
Travel(NY, London)BuyTicket(JFK, LHR) → GoToAirport → Fly → ExitAirport
The planner recursively decomposes abstract tasks until the entire plan consists purely of executable primitive actions.
In May 1999, NASA's Deep Space 1 probe became the first spacecraft controlled autonomously by an onboard AI planner (Remote Agent). It detected component failures millions of miles from Earth, re-planned science observation schedules on the fly, and executed closed-loop repairs without ground intervention.
NASA's Curiosity and Perseverance rovers use automated planning systems (like MAPGEN) to synthesize daily science activity schedules, balancing battery power, thermal limits, rover mobility paths, and tight orbital communication windows with Mars orbiters.
Automated planners coordinate multi-modal container shipping networks (ports, freight trains, autonomous warehouse sorting robots), routing millions of packages daily through dynamic rerouting during port strikes, weather delays, or highway bottlenecks.
Below is a complete, standalone Python implementation of a Forward State-Space STRIPS Planner that solves the classic Blocks World Sussman Anomaly from first principles.
"""
AI Track Unit 6: Automated Planning & Acting
Forward State-Space STRIPS Planner solving the Sussman Anomaly
Author: DevAscent Engineering Team
"""
from typing import List, Set, Dict, Tuple, Optional
from collections import deque
class Action:
def __init__(self, name: str, preconds: Set[str], add_list: Set[str], del_list: Set[str]):
self.name = name
self.preconds = preconds
self.add_list = add_list
self.del_list = del_list
def is_applicable(self, state: Set[str]) -> bool:
"""Action is applicable if all preconditions are present in the current state."""
return self.preconds.issubset(state)
def apply(self, state: Set[str]) -> Set[str]:
"""STRIPS state transition: (State - Delete_List) + Add_List."""
return (state - self.del_list) | self.add_list
def __repr__(self):
return self.name
class ForwardSTRIPSPlanner:
def __init__(self, actions: List[Action]):
self.actions = actions
def solve(self, initial_state: Set[str], goal_state: Set[str]) -> Optional[List[str]]:
"""
Forward State-Space Search (Progression).
Finds a sequence of actions transforming initial_state to satisfy goal_state.
"""
if goal_state.issubset(initial_state):
return []
# Queue stores: (current_state, plan_action_names)
queue = deque([(initial_state, [])])
visited = [initial_state]
while queue:
state, plan = queue.popleft()
# Check if all goal literals are satisfied
if goal_state.issubset(state):
return plan
for action in self.actions:
if action.is_applicable(state):
next_state = action.apply(state)
if next_state not in visited:
visited.append(next_state)
queue.append((next_state, plan + [action.name]))
return None
# =====================================================================
# BLOCKS WORLD ACTIONS GENERATOR
# =====================================================================
def generate_blocks_world_actions(blocks: List[str]) -> List[Action]:
actions = []
# 1. MoveToTable(b, x): Move block b from top of block x to Table
for b in blocks:
for x in blocks:
if b != x:
name = f"MoveToTable({b}, {x})"
preconds = {f"On({b}, {x})", f"Clear({b})"}
add_list = {f"OnTable({b})", f"Clear({x})"}
del_list = {f"On({b}, {x})"}
actions.append(Action(name, preconds, add_list, del_list))
# 2. MoveFromTable(b, y): Move block b from Table to top of block y
for b in blocks:
for y in blocks:
if b != y:
name = f"MoveFromTable({b}, {y})"
preconds = {f"OnTable({b})", f"Clear({b})", f"Clear({y})"}
add_list = {f"On({b}, {y})"}
del_list = {f"OnTable({b})", f"Clear({y})"}
actions.append(Action(name, preconds, add_list, del_list))
# 3. Move(b, x, y): Move block b from block x to block y
for b in blocks:
for x in blocks:
for y in blocks:
if b != x and b != y and x != y:
name = f"Move({b}, {x}, {y})"
preconds = {f"On({b}, {x})", f"Clear({b})", f"Clear({y})"}
add_list = {f"On({b}, {y})", f"Clear({x})"}
del_list = {f"On({b}, {x})", f"Clear({y})"}
actions.append(Action(name, preconds, add_list, del_list))
return actions
# =====================================================================
# DEMONSTRATION HARNESS: SOLVING SUSSMAN ANOMALY
# =====================================================================
if __name__ == "__main__":
print("=" * 68)
print("AUTOMATED PLANNING DEMO: SOLVING THE SUSSMAN ANOMALY")
print("=" * 68)
blocks = ['A', 'B', 'C']
all_actions = generate_blocks_world_actions(blocks)
# Initial State: C on A, A on Table, B on Table, C is clear, B is clear
initial = {
"On(C, A)",
"OnTable(A)",
"OnTable(B)",
"Clear(C)",
"Clear(B)"
}
# Goal State: A on B, B on C (Tower: A on top of B, B on top of C)
goal = {
"On(A, B)",
"On(B, C)"
}
print("Initial State Literals:")
for lit in sorted(initial):
print(f" * {lit}")
print("\nGoal Description Literals:")
for lit in sorted(goal):
print(f" * {lit}")
planner = ForwardSTRIPSPlanner(all_actions)
print("\nExecuting Forward State-Space Search...")
plan = planner.solve(initial, goal)
if plan:
print(f"\nPLAN DISCOVERED SUCCESSFULLY ({len(plan)} Steps):")
for step_num, act in enumerate(plan, 1):
print(f" Step {step_num}: {act}")
else:
print("No valid plan found.")
Answer: Automated planners exploit the factored nature of PDDL representations. By mechanically altering the action schemas, the planner constructs a relaxed problem. The most common technique is the Ignore Delete Lists heuristic: the engine removes all delete lists (negative effects) from all actions. In this relaxed world, actions only accumulate capabilities and never undo progress, allowing optimal step counts to be computed in polynomial time. This relaxed solution length provides a powerful, domain-independent heuristic for guiding A* search in the real state space.
Answer: The Sussman Anomaly is a classic Blocks World problem where early linear planners failed because they attempted to satisfy subgoals independently in sequential order. When trying to achieve On(A, B) then On(B, C), satisfying the first subgoal produces a state where block A sits on B. To subsequently satisfy the second subgoal (putting B on C), the planner is forced to tear down On(A, B), destroying its own earlier progress. The Sussman Anomaly proved that subgoals are interdependent and action plans must be interleaved rather than concatenated linearly.
Answer: The Principle of Least Commitment dictates that a planner should never make an arbitrary choice (such as deciding whether action A precedes action B) unless forced to do so to resolve a specific causal conflict. By maintaining a partial order of actions constrained only by necessary causal links and ordering constraints, POP avoids the exponential combinatorial explosion that occurs when total-order planners arbitrarily order independent subtasks.
Answer: These are the three conditions that create action mutexes:
1. Inconsistent Effects: One action adds a literal that the other action explicitly deletes.
2. Interference: One action deletes a literal that is a precondition for the other action.
3. Competing Needs: A precondition of action A and a precondition of action B are marked as mutually exclusive at the preceding proposition level (e.g., both require the robot's only hand).
Answer: A planning graph grows monotonically until it reaches a level-off condition: a state where two consecutive proposition levels Si and Si+1 are identical in both their proposition sets and their mutex relationships. If the graph levels off and the goal literals still do not appear without mutexes, or if backward search fails at and beyond this level-off point, GRAPHPLAN mathematically proves that the goal can never be achieved, terminating with failure.
Answer: HTN planning represents problem solving through recursive task decomposition. Instead of searching blindly among millions of low-level motor primitives, domain experts provide hierarchical methods that specify how abstract compound tasks (e.g., AssembleGearbox) decompose into subtasks. This constrains the search space dramatically, ensures compliance with engineering safety protocols, and allows planning over horizons of thousands of actions that would stall classical first-principles planners.