STRIPS Representation

In STRIPS, the world is represented using first-order logic atoms. A planning problem consists of three components: an initial state I (a set of ground atoms true at the start), a goal state G (a set of atoms that must be true in the final state), and a set of operators (actions).

from dataclasses import dataclass
from frozenset import frozenset as fset

@dataclass
class STRIPSOperator:
    name: str
    preconditions: frozenset   # atoms that must be TRUE before action
    add_effects: frozenset     # atoms that become TRUE after action
    delete_effects: frozenset  # atoms that become FALSE after action

def apply(state: frozenset, op: STRIPSOperator) -> frozenset | None:
    """Apply STRIPS operator to state. Returns None if preconditions not met."""
    if not op.preconditions.issubset(state):
        return None  # preconditions not satisfied
    # New state = (state - delete_effects) + add_effects
    return (state - op.delete_effects) | op.add_effects

# Blocks World example: Move block A from B to Table
move_A_from_B_to_Table = STRIPSOperator(
    name="Move(A, B, Table)",
    preconditions=frozenset({"On(A,B)", "Clear(A)", "Clear(Table)"}),
    add_effects=frozenset({"On(A,Table)", "Clear(B)"}),
    delete_effects=frozenset({"On(A,B)", "Clear(Table)"}),
)

initial_state = frozenset({"On(A,B)", "On(B,Table)", "Clear(A)", "Clear(Table)"})
next_state = apply(initial_state, move_A_from_B_to_Table)
# Result: {"On(A,Table)", "On(B,Table)", "Clear(A)", "Clear(B)", "Clear(Table)"}

Closed-World Assumption (CWA): STRIPS uses CWA: any atom not explicitly in the state is assumed FALSE. This simplifies state representation but is a strong assumption — it means the agent has perfect and complete knowledge of the world. Real-world planning often requires open-world assumptions (unknown ≠ false).

State-Space Search for Planning

Planning can be cast as a search problem in two directions. Forward search (progression planning) starts from the initial state and applies operators forward until a state satisfying G is reached. Backward search (regression planning) starts from the goal and works backwards — asking 'which states could have led here?' — until the initial state is reached or subsumed.

Effective planning heuristics are designed using relaxed problems — most commonly the delete-relaxation, which ignores all delete effects of operators. This makes the planning problem monotone (atoms only added, never removed) and allows efficient exact solution via a polynomial-time algorithm, producing the admissible heuristic h⁺.

h^+(s) = \text{cost of optimal plan in relaxed problem (no deletes)}

The Planning Graph and GraphPlan

A planning graph is a leveled graph structure: proposition levels (P₀, P₁, …) alternate with action levels (A₀, A₁, …). P₀ contains the initial state's atoms. Aᵢ contains all actions applicable in some state consistent with Pᵢ. Pᵢ₊₁ contains all atoms in the add-effects of actions in Aᵢ, plus all atoms carried forward. Mutex (mutual exclusion) relations track pairs of actions/propositions that cannot both be true simultaneously.

Mutex conditions: Two actions at the same level are mutex if: (1) Inconsistent effects: one deletes a precondition or add-effect of the other. (2) Interference: one deletes a precondition of the other. (3) Competing needs: they have mutually exclusive preconditions. Two propositions are mutex if all ways to achieve them are mutex. GATE may ask to identify mutexes in a small planning graph.

The planning graph level at which all goal atoms first appear simultaneously (non-mutex) gives a lower bound on plan length. GraphPlan extracts a valid plan from the graph by backward chaining from the goal level, or proves no plan exists of that length.

Complexity of Planning

Classical planning is computationally hard in general. Key complexity results that GATE may reference:

PSPACE vs NP: Planning in general is PSPACE-complete — harder than NP under standard complexity assumptions. This means no polynomial-time algorithm exists unless P = PSPACE. In practice, domain-specific heuristics and structure exploitation (delete relaxation, landmark analysis) make planners effective on real-world instances despite worst-case hardness.

PDDL: Modern Planning Language

PDDL (Planning Domain Definition Language) standardizes STRIPS for use in the International Planning Competition (IPC). A PDDL problem is split into a domain file (defining types, predicates, and action schemas) and a problem file (specifying objects, initial state, and goal).

;;; DOMAIN FILE: blocksworld-domain.pddl
(define (domain blocksworld)
  (:predicates
    (on ?x ?y)       ; block x is on block y
    (ontable ?x)     ; block x is on the table
    (clear ?x)       ; nothing is on top of block x
    (holding ?x))    ; robot arm is holding block x

  (:action pick-up
    :parameters (?x)
    :precondition (and (clear ?x) (ontable ?x) (handempty))
    :effect (and (not (ontable ?x)) (not (clear ?x))
                 (not (handempty)) (holding ?x)))

  (:action put-down
    :parameters (?x)
    :precondition (holding ?x)
    :effect (and (not (holding ?x)) (clear ?x)
                 (ontable ?x) (handempty)))

  (:action stack
    :parameters (?x ?y)
    :precondition (and (holding ?x) (clear ?y))
    :effect (and (not (holding ?x)) (not (clear ?y))
                 (clear ?x) (on ?x ?y) (handempty))))

;;; PROBLEM FILE: blocks-prob.pddl
(define (problem stack-A-on-B)
  (:domain blocksworld)
  (:objects A B)
  (:init (ontable A) (ontable B) (clear A) (clear B) (handempty))
  (:goal (on A B)))

Classical planning meets LLMs

Since 2023, an active research thread has tried to combine classical planners' guarantees with LLMs' flexibility. Rather than trusting an LLM to plan correctly end-to-end — which it often cannot do reliably for problems that require strict logical consistency, like blocks-world puzzles with many objects — systems such as LLM+P (Liu et al., 2023) use the LLM only as a translator: it turns a natural-language task description into a formal PDDL problem file, and hands the actual search off to a classical, sound-and-complete planner. The planner returns a guaranteed-valid plan (or proves none exists), which the LLM then translates back into natural language or executable actions.

Why the division of labor works: This plays to each system's strength: LLMs are good at open-ended language understanding but weak at exhaustive, provably-correct search; classical planners are the reverse. If you ever see an LLM confidently produce a wrong multi-step plan for a puzzle with a small but strict solution space — a blocks-world stack, a scheduling problem with hard constraints — that is exactly the gap this hybrid approach is designed to close. The LLM is pattern-matching to plausible-looking plans, not searching a state space with the guarantees a STRIPS/GraphPlan solver provides.

GATE PYQ Spotlight

GATE DA — STRIPS state transition (2-mark): Blocks World: Initial state: On(C,A), On(A,Table), On(B,Table), Clear(C), Clear(B). Goal: On(A,B). Action Unstack(C,A): Pre: {On(C,A), Clear(C)}, Add: {Clear(A), Holding(C)}, Del: {On(C,A), Clear(C)} Action Stack(A,B): Pre: {Holding(A), Clear(B)}, Add: {On(A,B), Clear(A)}, Del: {Holding(A), Clear(B)} Valid plan: (1) Unstack(C,A) → holds C, A is clear. (2) PutDown(C) → C on table. (3) PickUp(A) → holds A. (4) Stack(A,B) → A on B. ✓ Expects you to trace through STRIPS state transitions step by step and verify preconditions hold before each action.

GATE DA — Planning complexity (1-mark): What is the complexity class of the general plan-existence problem (PLANSAT) in classical STRIPS planning? (A) P (B) NP-complete (C) PSPACE-complete (D) Undecidable Answer: (C) PSPACE-complete. This is a standard result. Bounded plan existence (is there a plan of length ≤ k?) is NP-complete. Unrestricted plan existence is PSPACE-complete. Delete-free planning is in P.

GATE DA — Forward vs. backward planning (1-mark): Which statement about forward vs. backward (regression) planning is TRUE? (A) Backward planning requires the goal to be fully specified (B) Forward planning cannot use heuristics (C) Backward planning explores only goal-relevant states (D) Both have the same worst-case complexity Answer: (C). Regression planning starts from the goal and works backward, only considering operators whose add-effects are relevant to the current subgoal — this focuses search on relevant states. (A) is false: goals are partial. (B) is false: forward planning uses heuristics like h⁺. (D) is false: backward may have a smaller effective search space in many domains.

Practice questions

1. What is a PDDL (Planning Domain Definition Language) file structure? (Answer: PDDL has two files: domain file defines: types, predicates (what can be true), and action schemas (preconditions + effects). Problem file defines: objects (specific instances), initial state (:init — which predicates are true), and goal state (:goal — desired predicates). Example action schema: (:action move :parameters (?robot ?from ?to) :precondition (and (at ?robot ?from) (connected ?from ?to)) :effect (and (not (at ?robot ?from)) (at ?robot ?to))). Planning: find a sequence of actions that transitions from init to goal.)
2. What is the difference between forward search (progression) and backward search (regression) in planning? (Answer: Forward (progression): start from initial state, apply actions, explore reachable states. Natural match to execution — states are explicit. BFS/A* with heuristics. Memory: can be exponential in state space. Backward (regression): start from goal, find what state must precede it (regress actions), search backward. Can focus on goal-relevant subproblems. More complex: must handle partial states (not all predicates specified). Used in planning systems for subgoal decomposition. Both are complete; forward planning with good heuristics (FF, LAMA) dominates modern planning.)
3. What is the delete relaxation heuristic and how does it guide classical planners? (Answer: Delete relaxation: compute a relaxed plan ignoring all delete effects of actions (actions only add, never remove predicates). The relaxed plan is always easier or equally hard as the real plan — admissible heuristic (never overestimates). Compute relaxed plan with polynomial-time algorithm (no need to worry about undone effects). The length (number of actions) of the relaxed plan = h^+ heuristic. Used in FF planner (one of the most successful classical planners) as its primary heuristic. Provides excellent guidance with minimal computation.)
4. What is goal regression and why is it used in backward planning? (Answer: Goal regression: given a goal G and action A with effects E, the regression of G through A is: (G - E^+) ∪ A's preconditions ∪ (G ∩ neg_effects_complement). This computes which state BEFORE action A must hold to achieve G after A. Regression checks: does A's effects contribute to G? If yes, what must be true before A for G to hold after? Backward chaining in planning = repeated goal regression from the current goal set back to the initial state.)
5. What is the difference between classical planning and probabilistic planning (MDPs)? (Answer: Classical planning: deterministic actions (each action has exactly one outcome), complete information (full state known), no costs (or uniform costs). Finds a plan — a sequence of actions guaranteed to reach the goal. MDP planning: stochastic actions (transition probabilities P(s'|s,a)), can handle partial information, optimizes expected cumulative reward. Policies (state → action mapping) rather than fixed sequences. Classical planning finds guaranteed solutions; MDP planning finds optimal expected solutions under uncertainty. When the world is deterministic and fully observable: classical planning is more efficient.)
6. What is LLM+P and what specific weakness of using an LLM as a standalone planner does it address? (Answer: LLM+P (Liu et al., 2023) uses an LLM only to translate a natural-language planning task into a formal PDDL problem file, then hands the actual search to a classical sound-and-complete planner rather than letting the LLM generate the plan itself. This addresses the fact that LLMs, asked to plan directly, are pattern-matching to plausible-sounding action sequences rather than performing exhaustive state-space search — so they can confidently produce invalid plans on problems with many interacting constraints, exactly where a classical planner's guarantees (soundness, completeness, provable non-existence) matter most.)