Classical AI Planning (STRIPS & PDDL)

STRIPS operator representation and state transition

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)"}

Delete-relaxation heuristic h⁺: admissible for forward A* planning. Computed via a layered graph (planning graph) in polynomial time. The hadd and hmax heuristics are approximations of h⁺ used in practice.

PDDL domain and problem for Blocks World — the canonical planning example

;;; 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)))

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, optimises 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.)