Classical Planning and PDDL

Chapter 11 — Automated Planning Book: Artificial Intelligence: A Modern Approach (Russell & Norvig, 4th ed) Pages: 373–408

What is Planning?

Planning is the task of finding a sequence of actions to achieve a goal from an initial state.

Differences from classical search (Ch.3): - Explicit action representation: actions described by preconditions and effects (not black-box successors) - Expressive goal language: goals are logical sentences, not a specific target state - Open-world assumption: planning deals with incomplete state descriptions

Key insight: representing actions symbolically allows planners to decompose the problem rather than just searching blindly.

STRIPS (Stanford Research Institute Problem Solver, 1971)

The foundational planning formalism.

An action schema in STRIPS:

Action(Fly(p, from, to)):
  PRECOND:  Plane(p) ∧ Airport(from) ∧ Airport(to) ∧ At(p, from)
  EFFECT:   ¬At(p, from) ∧ At(p, to)

Preconditions: positive literals that must hold before the action
Effects: literals added/removed from the state (add list + delete list)
State: a set of positive ground literals (closed-world assumption)

STRIPS Assumption

Only explicitly listed effects change — everything else stays the same (solves the frame problem by convention)
States are complete — unmentioned fluents are false

PDDL (Planning Domain Definition Language)

PDDL extends STRIPS with: - Types (typed objects) - Conditional effects: when P: E - Quantified effects: forall (x) E(x) - Numeric fluents and durations (PDDL 2.1+) - Temporal and probabilistic extensions

PDDL Structure

;; Domain definition
(define (domain airport)
  (:predicates (Plane ?p) (Airport ?a) (At ?obj ?loc))
  (:action fly
    :parameters (?p ?from ?to)
    :precondition (and (Plane ?p) (Airport ?from) (Airport ?to) (At ?p ?from))
    :effect (and (not (At ?p ?from)) (At ?p ?to))))

;; Problem definition
(define (problem fly-to-paris)
  (:domain airport)
  (:objects plane1 JFK CDG - object)
  (:init (Plane plane1) (Airport JFK) (Airport CDG) (At plane1 JFK))
  (:goal (At plane1 CDG)))

State, Goal, and Action in the Planning Problem

Initial state I: a conjunction of ground atoms.

Goal G: a conjunction of ground/universally-quantified atoms to be made true.

Action schema: universally quantified; instantiated by binding variables to objects.

Solution: a sequence of ground action instances (a plan) such that:

apply(aₙ, apply(aₙ₋₁, ... apply(a₁, I))) ⊨ G

Complexity

Classical planning (STRIPS) is: - Satisficing (find any plan): PSPACE-complete - Optimal (find shortest plan): PSPACE-complete / sometimes harder

In practice, modern planners solve problems with thousands of actions using heuristic search.

The Blocks World

Classic planning benchmark: - Objects: blocks A, B, C on a table or stacked - Actions: Pick-Up, Put-Down, Stack, Unstack - Goals: achieve specific stack configurations

Sussman Anomaly: goal On(A,B) ∧ On(B,C) from On(C,A) ∧ OnTable(B) cannot be solved by working on each subgoal independently — they interact. Illustrated the need for interleaved planning.

Relevance to DynamICCL

PDDL’s action schema model maps to NCCL operations:

Action(SwitchAlgorithm(node, from_algo, to_algo)):
  PRECOND: CurrentAlgo(node, from_algo) ∧ SupportedAlgo(node, to_algo)
  EFFECT: ¬CurrentAlgo(node, from_algo) ∧ CurrentAlgo(node, to_algo)

Planning formalizes NCCL configuration management — finding a sequence of parameter changes to achieve a target throughput state.