Planning

The Planning Problem

Background — Search algorithms (like A*) define states as black boxes. Logic algorithms (like Resolution) are fully expressive but often too slow to find action sequences efficiently. Planning sits in the middle.

Planning: The task of coming up with a sequence of actions that will achieve a goal.¹1. If you are just finding a path on a map, use Search. If you are coordinating a fleet of autonomous rovers on Mars, you need Planning.

• We open up the “black box” of states and actions using a factored representation, allowing the solver to extract heuristics directly from the problem definition.

PDDL Representation

PDDL (Planning Domain Definition Language) is the standard syntax for expressing planning problems.

• States: Conjunctions of positive, ground literals (e.g., At(Plane1, JFK) ^ Cargo(C1)).
  • Closed-World Assumption: Any literal not mentioned is assumed to be false.
• Goals: A partially specified state. A state satisfies the goal if it contains all the goal literals.
• Actions: Defined by an Action Schema consisting of:
  • Preconditions: What must be true to execute the action.
  • Effects: What becomes true (ADD list) and what becomes false (DELETE list) after the action.²2. Explicitly listing what changes (the effects) neatly sidesteps the “Frame Problem”—the impossible task of listing all the things in the world that do not change when an action occurs.

Action(Load(c, p, a),
  PRECOND: Cargo(c) \land Plane(p) \land Airport(a) \land At(c, a) \land At(p, a)
  EFFECT: \neg At(c, a) \land In(c, p))

Planning as Search

Since we have states, actions, and goals, we can just use standard search algorithms!

Forward (Progression) State-Space Search

Search from the initial state toward the goal.

• Actions are applicable if their preconditions are satisfied in the current state.
• Problem: The branching factor is massive because it explores many irrelevant actions.

Backward (Regression) State-Space Search

Search from the goal state backwards to the initial state.

• Only consider actions that achieve at least one literal in the goal (and don’t undo another).
• Replaces the current goal with the preconditions of the chosen action.
• Much lower branching factor, but computing state descriptions is tricky.³3. Regression search works on sets of states (subgoals) rather than complete specific states.

Partial-Order Planning (POP)

State-space search forces us to strictly order actions, even if they are independent (e.g., putting on your left shoe and right shoe). Partial-Order Planning searches through the space of plans rather than states.

• It adds actions and ordering constraints (Action A must happen before Action B) only when necessary.
• Result: A flexible plan that represents the “principle of least commitment”.⁴4. Partial-Order Planning is excellent for multi-agent execution because independent branches of the plan can be executed simultaneously by different robots.

Heuristics for Planning

Because the state representation is standardized, we can automatically generate heuristics without the user providing them.

1. Ignore Preconditions: Drop all preconditions from actions. The cost to goal is just the number of unsatisfied goal literals. (Often too optimistic).
2. Ignore Delete Lists: Assume actions only add facts and never delete them. This guarantees no action undoes progress. The length of the plan in this relaxed problem is an excellent, admissible heuristic.⁵5. The “Ignore Delete Lists” heuristic is incredibly famous in AI planning research and forms the backbone of modern fast-forward (FF) planners.
3. State Abstraction: Group multiple objects together or drop certain predicates entirely to create a smaller, easily solved abstract problem.