Artificial Intelligence

Knowledge Reasoning And Planning

Automated Planning

Module 2's search algorithms treated actions as opaque — "move to state B" without any structured understanding of what changes when that action happens. Automa

JrCodex·8 min read

Jr Codex AI Notes

Level: Advanced Prerequisites: Chapter 4 Time to complete: ~30 minutes

Table of Contents

  1. Planning vs Plain Search
  2. The STRIPS Representation
  3. A Worked STRIPS Example: The Blocks World
  4. Planning as State-Space Search
  5. Forward vs Backward Planning
  6. Planning Graphs (Conceptual Overview)
  7. Why Planning Matters Beyond Toy Blocks
  8. Summary & Next Steps

Module 2's search algorithms treated actions as opaque — "move to state B" without any structured understanding of what changes when that action happens. Automated planning uses the first-order, predicate-based representation from Chapter 3 to describe actions in terms of their preconditions and effects, enabling much smarter, more general problem-solving.

Plain Search (Module 2)                Planning (this chapter)
─────────────────────────────         ─────────────────────────────
  Actions are OPAQUE — the search        Actions have STRUCTURED
  algorithm just knows "this action        preconditions (what must
  leads to that state"                       be true to use it) and
                                               EFFECTS (what becomes
  Must hand-write a NEW state space            true/false afterward)
  representation for every different
  problem                                    The SAME planning algorithm
                                               works across VERY different
                                               domains, since actions are
                                               described in a common language
─────────────────────────────────────────

2. The STRIPS Representation

STRIPS (STanford Research Institute Problem Solver) is the classic, still-influential way to represent planning actions — each action is defined by its preconditions and effects, expressed as first-order predicates (Chapter 3).

STRIPS Action Schema
─────────────────────────────────────────
  Action:        Move(block, from, to)
  Precondition:    Clear(block) ∧ Clear(to) ∧ On(block, from)
  Effect:            On(block, to) ∧ Clear(from) ∧
                        ¬On(block, from) ∧ ¬Clear(to)
─────────────────────────────────────────

class StripsAction:
    def __init__(self, name, preconditions, add_effects, delete_effects):
        self.name = name
        self.preconditions = preconditions      # set of predicates that must ALL be true
        self.add_effects = add_effects            # predicates that become TRUE
        self.delete_effects = delete_effects         # predicates that become FALSE
 
    def is_applicable(self, state):
        """Can this action run, given the current state (a set of true predicates)?"""
        return self.preconditions.issubset(state)
 
    def apply(self, state):
        """Return the NEW state after applying this action."""
        if not self.is_applicable(state):
            raise ValueError(f"Preconditions not met for {self.name}")
        new_state = (state - self.delete_effects) | self.add_effects
        return new_state

This is a direct generalization of Module 2's transition model — instead of a hand-coded, problem-specific function, an action's effect is computed generically: remove whatever it deletes, add whatever it produces.

3. A Worked STRIPS Example: The Blocks World

The classic planning textbook example: stacking blocks on a table, using a robot arm.

# World: three blocks (A, B, C) and a Table. Initially: A on Table, B on A, C on Table.
initial_state = {
    "On(B,A)", "On(A,Table)", "On(C,Table)",
    "Clear(B)", "Clear(C)", "ArmEmpty",
}
 
goal_state = {"On(A,B)", "On(B,C)"}      # build a stack: A on B on C
 
def make_move_action(block, from_loc, to_loc):
    return StripsAction(
        name=f"Move({block},{from_loc},{to_loc})",
        preconditions={f"Clear({block})", f"Clear({to_loc})", f"On({block},{from_loc})", "ArmEmpty"},
        add_effects={f"On({block},{to_loc})", f"Clear({from_loc})"},
        delete_effects={f"On({block},{from_loc})", f"Clear({to_loc})"},
    )
 
# Example: moving C onto B, assuming preconditions are met
move_c_to_b = make_move_action("C", "Table", "B")
print(move_c_to_b.is_applicable(initial_state))      # False — B is NOT Clear yet (C is on Table, but B has nothing on it... check preconditions)
Working Through the Plan by Hand
─────────────────────────────────────────
  Initial: B on A, C on Table, A on Table. Goal: A on B on C.

  Step 1: Move(B, A, Table)   — B is Clear, Table is always "Clear" (simplification)
            → New state: A on Table, B on Table, C on Table, A Clear, B Clear, C Clear

  Step 2: Move(B, Table, C)     — B Clear, C Clear, B on Table
            → New state: B on C, A on Table (Clear), C not Clear

  Step 3: Move(A, Table, B)       — A Clear, B Clear (top of stack), A on Table
            → New state: A on B on C  ✓ GOAL REACHED
─────────────────────────────────────────

This step-by-step derivation is exactly what a planning algorithm (Section 4) automates — finding this specific 3-step sequence without a human working it out by hand.

The most direct way to solve a STRIPS planning problem: treat it as a search problem (Module 2, Chapter 1!) where states are sets of true predicates, and actions are STRIPS actions.

from collections import deque
 
def plan_search(initial_state, goal_state, actions):
    """BFS over the STRIPS state space (Module 2, Chapter 2's algorithm, reused directly)."""
    frontier = deque([(initial_state, [])])
    visited = {frozenset(initial_state)}
 
    while frontier:
        state, plan = frontier.popleft()
 
        if goal_state.issubset(state):
            return plan      # SUCCESS
 
        for action in actions:
            if action.is_applicable(state):
                new_state = action.apply(state)
                if frozenset(new_state) not in visited:
                    visited.add(frozenset(new_state))
                    frontier.append((new_state, plan + [action.name]))
 
    return None      # no plan found
 
all_actions = [
    make_move_action("B", "A", "Table"),
    make_move_action("B", "Table", "C"),
    make_move_action("A", "Table", "B"),
    # (a complete solver would generate ALL possible move combinations automatically)
]
 
plan = plan_search(initial_state, goal_state, all_actions)
print(plan)      # ['Move(B,A,Table)', 'Move(B,Table,C)', 'Move(A,Table,B)']

This directly reuses Module 2, Chapter 2's BFS — the entire point of STRIPS is that once a problem is described in this standard predicate-based language, the same general search machinery from Module 2 can solve it, rather than needing bespoke code per problem.

5. Forward vs Backward Planning

Just like Chapter 4's inference strategies, planning can proceed in two directions:

Forward (Progression) Planning
─────────────────────────────────────────
  Start at the INITIAL state, apply actions FORWARD,
  searching for a state that satisfies the goal.

  (This is exactly what Section 4's plan_search does —
  it's the more intuitive direction, but can explore many
  states irrelevant to the actual goal.)
─────────────────────────────────────────

Backward (Regression) Planning
─────────────────────────────────────────
  Start at the GOAL, and work BACKWARD: "what state, plus
  which action, would PRODUCE this goal?" — directly
  mirroring Chapter 4's backward chaining, applied to actions
  instead of logical rules.

  Often more efficient when the goal is specific and the
  space of RELEVANT actions is much smaller than the space
  of states reachable from the start.
─────────────────────────────────────────

The Same Trade-off as Chapter 4's Inference Strategies
─────────────────────────────────────────
  Forward planning  ≈  Forward chaining (data-driven, explores
                          broadly from what's known)
  Backward planning   ≈  Backward chaining (goal-driven, only
                            explores what's relevant to the
                            specific question/goal)
─────────────────────────────────────────

6. Planning Graphs (Conceptual Overview)

For problems too large for straightforward forward/backward search, a planning graph provides a more efficient structure — alternating layers of possible states and possible actions, built up level by level, used by algorithms like GraphPlan.

Planning Graph Structure (Conceptual)
─────────────────────────────────────────
  Level 0 (state layer):    facts true in the initial state
       │
  Level 0 (action layer):     all actions whose preconditions
       │                        are satisfied at Level 0
       ▼
  Level 1 (state layer):        facts possibly true after ONE
       │                           action (or no action) from Level 0
       ▼
  Level 1 (action layer):          all actions applicable given
       │                             Level 1's possible facts
       ▼
       ... (continues until the goal appears as possible,
             or the graph stops changing between levels)
─────────────────────────────────────────

The key efficiency insight: a planning graph tracks mutual exclusions ("mutex" — pairs of facts or actions that can't both hold/happen at the same level) which dramatically prunes the search once an actual plan is extracted from the graph. This is a more advanced technique than this chapter covers in full implementation detail — the conceptual takeaway is that specialized planning-specific data structures can outperform treating planning as generic state-space search (Section 4) once problems grow large.

7. Why Planning Matters Beyond Toy Blocks

Real-World Applications of Automated Planning
─────────────────────────────────────────
  Robotics:          sequencing a robot arm's actions to
                       assemble a product
  Logistics:            planning delivery routes and warehouse
                          operations (loading/unloading sequences)
  Space missions:          NASA's Remote Agent used STRIPS-style
                             planning to autonomously sequence
                             spacecraft operations
  Video game AI:              NPC behavior planning (deciding a
                                 sequence of actions to achieve an
                                 in-game goal)
  Automated workflow systems:      sequencing steps in business
                                     process automation
─────────────────────────────────────────

The blocks-world example in this chapter is deliberately simple precisely because it isolates the core mechanism (preconditions, effects, search over predicate-based states) that scales up to these much more complex, real applications — the underlying STRIPS representation and search techniques remain conceptually the same.

8. Summary & Next Steps

Key Takeaways

  • Planning represents actions with structured preconditions and effects (STRIPS), rather than the opaque transitions used in Module 2's plain search — enabling the same algorithm to work across very different domains.
  • A STRIPS action's effect is computed generically: remove its delete-effects from the current state, add its add-effects — no problem-specific transition code needed.
  • Planning can be framed directly as state-space search (reusing Module 2's BFS/DFS/A*) — forward planning explores from the initial state, backward planning works from the goal, mirroring Chapter 4's inference strategies.
  • Planning graphs offer a more efficient, specialized structure for larger problems, using mutual-exclusion tracking to prune the search significantly.

Concept Check

  1. What's the key advantage of STRIPS's precondition/effect representation over Module 2's opaque transition model?
  2. How does backward planning relate to backward chaining from Chapter 4?
  3. Name two real-world domains where automated planning is genuinely applied, beyond the blocks-world toy example.

Next Chapter

→ Chapter 6: Expert Systems & Rule-Based AI

Jr Codex — 1-on-1 Personalized Coaching | Back to Module Index