Planning

A planning problem is a triple (I, G, A): an initial state I, a goal condition G, and a set of actions A. A plan is a sequence of actions [a1, a2, ..., an] such that executing them from I produces a state satisfying G.

This seems simple, but the key insight is how we represent states and actions. In propositional planning, a state is a set of Boolean facts ("the robot is in room A", "the box is on the floor"). In first-order planning, we use predicates and objects ("On(A, B)", "Clear(C)"), letting us write compact descriptions of huge state spaces.

The formal complexity of planning is brutal: classical STRIPS planning is PSPACE-complete in general. Even deciding whether a plan exists is PSPACE-complete, and finding an optimal (shortest) plan is harder still. This is why heuristics are not just nice-to-have — they are essential.

Analogy: Think of a planning problem like a puzzle box. The initial state is the scrambled puzzle, the goal is the solved picture, and the actions are the legal moves. A planner is an algorithm that finds a sequence of moves without trying every possible sequence (which would be exponential).

# Representing a planning problem in Python

from dataclasses import dataclass, field
from frozenset import frozenset  # states as frozensets of facts

@dataclass(frozen=True)
class Action:
    name: str
    preconditions: frozenset  # facts that must be true
    add_effects: frozenset    # facts made true
    del_effects: frozenset    # facts made false

def apply(state: frozenset, action: Action) -> frozenset | None:
    """Returns new state, or None if preconditions not met."""
    if not action.preconditions.issubset(state):
        return None
    return (state - action.del_effects) | action.add_effects

# Example: Blocksworld — stack block A on block B
stack_A_on_B = Action(
    name='Stack(A,B)',
    preconditions=frozenset({'Holding(A)', 'Clear(B)'}),
    add_effects=frozenset({'On(A,B)', 'Clear(A)', 'ArmEmpty'}),
    del_effects=frozenset({'Holding(A)', 'Clear(B)'})
)

STRIPS (Fikes & Nilsson, 1971) introduced the first formal action language. A STRIPS action has three components:

• Precondition: A conjunction of positive literals that must hold.
• Add list: Facts to add to the current state.
• Delete list: Facts to remove from the current state.

The closed-world assumption (CWA) is fundamental: any fact not in the current state is assumed false. This makes the semantics crisp but limits expressivity — you cannot say "I don't know if it's raining."

STRIPS is less expressive than ADL (Action Description Language), which allows:

• Negative preconditions (not Holding(x))
• Disjunctive preconditions
• Conditional effects (when P, then Q)
• Quantified effects

PDDL (Planning Domain Definition Language) is the modern standard, evolved from STRIPS/ADL. It separates a domain (what actions exist in this world) from a problem (the specific initial state and goal). This separation is critical — the same domain file describes Blocksworld for any instance; problems differ only in what blocks exist and where they start.

Here is PDDL for a classic Blocksworld pickup action:

(:action pickup
  :parameters (?b - block)
  :precondition (and (on-table ?b) (clear ?b) (arm-empty))
  :effect (and (holding ?b)
               (not (on-table ?b))
               (not (clear ?b))
               (not (arm-empty))))

The :parameters and :precondition/:effect structure is STRIPS at its core — declarative, readable, and solver-agnostic. The key insight of PDDL is that intelligence is in the planner, not the domain description — you write what the world is like, and the planner figures out how to act.

;; PDDL Domain: Blocks World (simplified)
(define (domain blocksworld)
  (:requirements :strips)
  (:predicates (on ?x ?y)
               (on-table ?x)
               (clear ?x)
               (arm-empty)
               (holding ?x))

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

  (:action unstack
    :parameters (?x ?y)
    :precondition (and (on ?x ?y) (clear ?x) (arm-empty))
    :effect (and (holding ?x)
                 (clear ?y)
                 (not (on ?x ?y))
                 (not (clear ?x))
                 (not (arm-empty)))))

The most direct approach to planning is state-space search: treat the planning problem as a graph where nodes are world states and edges are actions, then search for a path from I to any state satisfying G.

Forward search (progression) starts at the initial state and applies actions forward, generating successor states. It is complete (will find a plan if one exists) and easy to implement — it's just graph search. The problem is that the state space is enormous: with n Boolean facts, there are 2^n states.

Backward search (regression) starts from the goal and works backward, asking: "which actions could have produced this goal, and what did the world need to look like before that action?" Formally, the regression of goal G through action a is:

regress(G, a) = (G \ add(a)) ∪ precond(a)

(remove effects a just added, add what a required). This is valid only when a is relevant (its add effects overlap G) and consistent (its delete effects don't conflict with G).

Backward search tends to focus on states that are relevant to the goal — it never explores parts of the state space that cannot contribute to goal achievement. For planning problems where the goal is highly specific, this is a massive win.

Both directions have tradeoffs. Forward search generates concrete states (easy to check, easy to heuristically evaluate). Backward search generates partial states (not all facts specified) — these are more compact but harder to reason about. In practice, modern planners use forward search with powerful heuristics, because heuristics are much easier to compute on concrete states.

def forward_search(initial, goal, actions):
    """BFS forward state-space search. Returns plan or None."""
    from collections import deque

    # Each entry: (current_state, plan_so_far)
    queue = deque([(frozenset(initial), [])])
    visited = {frozenset(initial)}

    while queue:
        state, plan = queue.popleft()

        # Goal test: all goal facts hold in current state
        if goal.issubset(state):
            return plan

        for action in actions:
            if action.preconditions.issubset(state):  # applicable?
                next_state = (state - action.del_effects) | action.add_effects
                if next_state not in visited:
                    visited.add(next_state)
                    queue.append((next_state, plan + [action.name]))

    return None  # no plan found

# Regression (backward) step
def regress(goal_set, action):
    """Returns the regression of goal through action, or None if not relevant."""
    if not action.add_effects & goal_set:       # action not relevant
        return None
    if action.del_effects & goal_set:            # action destroys goal — inconsistent
        return None
    return (goal_set - action.add_effects) | action.preconditions

Uninformed search over state spaces is hopeless for realistic problems — a domain with 50 facts has 2^50 ≈ 10^15 states. Heuristics guide search toward the goal, and the quality of the heuristic is the single most important factor in planner performance.

The gold standard for heuristics is admissibility: a heuristic h(s) is admissible if it never overestimates the true cost h*(s) from s to the goal. Admissible heuristics guarantee optimal plans when used with A*.

The Delete-Relaxation Heuristic (h+)

The most influential planning heuristic family is based on relaxation: solve a simpler version of the problem and use that solution cost as the heuristic. The classic relaxation is the delete relaxation: ignore all delete effects. In the relaxed problem, facts are never removed — the world is monotonically improving. This is almost always solvable optimally in polynomial time.

• h^add: Sum the cost of achieving each goal fact independently. Not admissible (double-counts shared subgoals) but fast and often effective.
• h^max: Maximum cost to achieve any single goal fact. Admissible but very weak (ignores interactions).
• h^FF (Fast-Forward heuristic): Extract a plan from the relaxed problem (a "relaxed plan") and count its length. Not admissible in general but dramatically better in practice — it's the heuristic behind the landmark Fast-Forward planner that won the 2000 International Planning Competition.

Landmark Heuristics

A landmark is a fact or action that must appear in every solution to the problem. For example, in Blocksworld, if block A ends on block B, then at some point "Holding(A)" must be true — it's a landmark. Counting unachieved landmarks gives a strong lower bound.

Pattern Database Heuristics

Precompute the exact cost for a projection of the problem (a subset of facts), then use that as a heuristic. This is analogous to the pattern databases used in 15-puzzle solving.

The key insight is that the quality of a heuristic trades off computation time for search nodes expanded. A perfect heuristic h = h* means A* expands only nodes on optimal paths — but computing h* is as hard as the original problem. The art is finding the sweet spot.

def h_add(state, goals, actions):
    """
    h^add heuristic via forward relaxed Bellman-Ford.
    cost[f] = min cost to achieve fact f from state.
    (Ignores delete effects — the 'relaxation'.)
    """
    INF = float('inf')
    cost = {f: 0 if f in state else INF for f in all_facts}

    changed = True
    while changed:
        changed = False
        for action in actions:
            # Action cost = 1 + sum of precondition costs
            pre_cost = sum(cost[p] for p in action.preconditions)
            action_cost = 1 + pre_cost
            for eff in action.add_effects:
                if action_cost < cost[eff]:
                    cost[eff] = action_cost
                    changed = True

    # h^add = sum of goal costs (not admissible — double counts)
    return sum(cost[g] for g in goals if cost[g] < INF)

def h_max(state, goals, actions):
    """h^max: admissible but weak. Max over goal costs."""
    # Same propagation, but use max instead of sum for action cost
    INF = float('inf')
    cost = {f: 0 if f in state else INF for f in all_facts}
    changed = True
    while changed:
        changed = False
        for action in actions:
            pre_cost = max((cost[p] for p in action.preconditions), default=0)
            action_cost = 1 + pre_cost
            for eff in action.add_effects:
                if action_cost < cost[eff]:
                    cost[eff] = action_cost
                    changed = True
    return max((cost[g] for g in goals), default=0)

An alternative to searching through states is searching through plans. Plan-space search maintains a partial plan — a set of actions with partial ordering constraints — and refines it by resolving flaws.

A Partial-Order Plan (POP) represents a plan as:

• A set of steps (action instances, plus special Start and Finish pseudo-actions)
• A set of ordering constraints: Ai ≺ Aj (action i before action j)
• A set of causal links: Ai →[p] Aj meaning "Ai achieves fact p for Aj"
• A set of binding constraints on variables (for first-order planning)

A POP is complete when every precondition of every step is supported by a causal link, and consistent when there are no ordering cycles.

A plan has two types of flaws:

1. Open precondition: A precondition of some step has no causal link supporting it.
2. Threat: An action Ak might delete a fact p that is protected by a causal link Ai →[p] Aj (if Ak is between Ai and Aj).

The POP algorithm (SNLP, UCPOP):

1. If no flaws, return the plan.
2. Select a flaw.
3. For open preconditions: choose an existing step or add a new step that achieves the precondition.
4. For threats: resolve by promotion (force Ak before Ai) or demotion (force Ak after Aj).
5. Recurse (backtrack on failure).

Why plan-space search? It represents the least-commitment principle: only commit to ordering when forced by dependencies. This can avoid exponential orderings of independent actions — the plan [Cook, Pack] and [Pack, Cook] are represented as a single partial-order plan when the actions are independent.

In practice, plan-space search fell out of favor for classical planning because state-space planners with strong heuristics proved faster. But plan-space ideas resurface in hierarchical task networks (HTN) and in planning with complex concurrent actions.

# Partial-order plan represented as a dataclass
from dataclasses import dataclass, field
from typing import Set, Tuple

@dataclass
class PartialOrderPlan:
    steps: Set[str]                      # action names (plus START, FINISH)
    orderings: Set[Tuple[str, str]]      # (before, after) pairs
    causal_links: Set[Tuple[str,str,str]]# (producer, fact, consumer)
    open_preconditions: Set[Tuple[str,str]] # (step, fact) needing support

def has_threat(plan: PartialOrderPlan, ak: str, link: Tuple) -> bool:
    """True if ak threatens causal link (ai, p, aj)."""
    ai, p, aj = link
    # ak threatens if: ak deletes p AND ak could be between ai and aj
    # (i.e., ai≺ak and ak≺aj is consistent with orderings)
    deletes_p = p in get_del_effects(ak)  # implementation-specific
    not_before_ai = (ak, ai) not in plan.orderings  # ak not forced before ai
    not_after_aj  = (aj, ak) not in plan.orderings  # ak not forced after aj
    return deletes_p and not_before_ai and not_after_aj

# Resolving a threat by demotion:
def demote(plan: PartialOrderPlan, ak: str, aj: str) -> PartialOrderPlan:
    """Force ak before ai — add ordering constraint."""
    # In practice, check for cycles before committing
    plan.orderings.add((ak, aj))
    return plan

Classical planning assumes all actions are primitive and equally available. Hierarchical Task Networks (HTN) add a crucial layer: tasks can be abstract (decomposed into subtasks) or primitive (directly executable actions). HTN planning mirrors how humans actually think — "make dinner" decomposes into "prepare ingredients, cook, plate", which further decomposes into primitives.

Formally, an HTN planning problem has:

• Primitive tasks: Correspond to STRIPS-like actions with preconditions and effects.
• Compound tasks: High-level tasks with no direct effects; they are refined by methods.
• Methods: Each method says "task T can be decomposed into subtasks [t1, t2, ..., tn] with ordering constraints, when precondition P holds."

The planner starts with the top-level task (e.g., AssembleCar) and recursively decomposes until only primitive tasks remain. The key search problem is which method to use at each compound task — methods may conflict or may only apply in certain states.

HTN planning is more expressive than STRIPS: HTN planning with method preconditions is undecidable in general, though practical subsets are decidable. This extra power is genuinely useful — HTN planners can encode expert knowledge about how to solve problems, not just what states are reachable. This makes them extremely effective in practice for domains like web services composition, game AI (NPC behavior trees), and manufacturing.

SHOP2 (Simple Hierarchical Ordered Planner) is a well-known HTN planner that has been successfully deployed in real applications, including the DARPA logistics domain. Its key insight: if you force total order on subtasks (ordered task decomposition), the planner is very efficient because it can check preconditions greedily.

# HTN represented as a recursive decomposition
# (Simplified ordered HTN, like SHOP2)

methods = {
    'MakeBreakfast': [
        # Method 1: full breakfast
        {'precond': {'HasEggs', 'HasBread'},
         'subtasks': ['FryEggs', 'ToastBread', 'Plate']},
        # Method 2: cereal fallback
        {'precond': {'HasCereal', 'HasMilk'},
         'subtasks': ['PourCereal', 'AddMilk', 'Plate']},
    ]
}

def htn_search(tasks, state, methods, primitives):
    """
    tasks: list of task names (ordered)
    Returns a flat primitive plan, or None.
    """
    if not tasks:
        return []  # empty plan succeeds

    first, *rest = tasks

    if first in primitives:
        action = primitives[first]
        if action.preconditions.issubset(state):
            new_state = apply(state, action)
            subplan = htn_search(rest, new_state, methods, primitives)
            if subplan is not None:
                return [first] + subplan
        return None

    # Compound task: try each method
    for method in methods[first]:
        if method['precond'].issubset(state):
            new_tasks = method['subtasks'] + rest
            result = htn_search(new_tasks, state, methods, primitives)
            if result is not None:
                return result

    return None  # no applicable method

Classical planning assumes deterministic, fully observable worlds. Reality is neither. Markov Decision Processes (MDPs) extend planning to stochastic environments where actions have uncertain outcomes.

Formally, an MDP is a tuple (S, A, T, R, γ) where:

• S — state space
• A — action space
• T(s, a, s') = P(s' | s, a) — transition probability (stochastic dynamics)
• R(s, a) — reward (positive for desirable states/transitions)
• γ ∈ [0,1) — discount factor (future rewards worth less)

The Markov property ("the future depends only on the present, not the history") is what makes MDPs tractable — it means the optimal policy π*(s) depends only on the current state, not on how you got there.

The goal is to find a policy π: S → A that maximizes expected discounted total reward E[Σ γ^t R(s_t, a_t)].

The optimal value function V*(s) satisfies the Bellman optimality equation:

V*(s) = max_a [ R(s,a) + γ · Σ_s' T(s,a,s') · V*(s') ]

This is a fixed-point equation — V* is the unique function satisfying it.

Value Iteration solves this by iterating:

V_{k+1}(s) = max_a [ R(s,a) + γ · Σ_s' T(s,a,s') · V_k(s') ]

Starting from any V_0, this converges to V* (the contraction mapping theorem guarantees this). Once you have V*, the optimal policy is:

π*(s) = argmax_a [ R(s,a) + γ · Σ_s' T(s,a,s') · V*(s') ]

Policy Iteration alternates between:

1. Policy evaluation: Solve V^π(s) = R(s,π(s)) + γ · Σ_s' T(s,π(s),s') · V^π(s') (a linear system)
2. Policy improvement: Greedily update π(s) = argmax_a [...]

Policy iteration converges in fewer iterations (each improves monotonically) but each step is more expensive. Both converge to π*.

Connection to classical planning: Classical planning is a special case of MDPs where T(s,a,s') ∈ {0, 1} (deterministic) and R(s,a) = -1 for non-goal states (minimize plan length).

import numpy as np

def value_iteration(S, A, T, R, gamma=0.95, theta=1e-6):
    """
    S: list of states (indices 0..n-1)
    A: list of actions
    T[s][a]: dict mapping s' -> P(s'|s,a)
    R[s][a]: immediate reward for (s,a)
    Returns V (value function) and pi (policy).
    """
    n = len(S)
    V = np.zeros(n)  # initialize arbitrarily

    while True:
        delta = 0
        for s in S:
            # Bellman backup
            q_values = [
                R[s][a] + gamma * sum(
                    prob * V[s_prime]
                    for s_prime, prob in T[s][a].items()
                )
                for a in A
            ]
            v_new = max(q_values)
            delta = max(delta, abs(v_new - V[s]))
            V[s] = v_new

        if delta < theta:  # converged
            break

    # Extract greedy policy
    pi = {}
    for s in S:
        pi[s] = max(A, key=lambda a:
            R[s][a] + gamma * sum(
                prob * V[s_prime]
                for s_prime, prob in T[s][a].items()
            )
        )
    return V, pi

MDPs assume the agent knows its exact state. This is often unrealistic — a robot with noisy sensors, a doctor who doesn't know the exact disease, a poker player who can't see opponents' cards. Partially Observable MDPs (POMDPs) model this uncertainty.

A POMDP adds to an MDP:

• Ω — observation space
• O(o | s', a) — probability of observing o after taking action a and landing in state s'

The agent cannot observe s directly — it only sees observations o. The key idea is the belief state b: S → [0,1] — a probability distribution over states encoding what the agent believes about the current state. The belief state is a sufficient statistic for the history of observations and actions.

Belief update (Bayesian filtering): After taking action a and observing o:

b'(s') = η · O(o|s',a) · Σ_s T(s,a,s') · b(s)

(where η is a normalizing constant).

The POMDP belief MDP is an MDP over the (continuous, infinite-dimensional) belief space — but it satisfies the Markov property, so dynamic programming applies. The value function over beliefs is a piecewise-linear convex function of the belief:

V*(b) = max over a set of α-vectors of  α · b

where each α-vector corresponds to a conditional plan.

PBVI (Point-Based Value Iteration) and SARSOP approximate the value function over a sampled set of reachable belief points — making POMDPs tractable for moderate state spaces.

Why does this matter for planning? A POMDP planner must choose actions not just to reach goals but to gather information (reduce uncertainty) when that will help future decisions. This information-gathering behavior — choosing to look at a sensor reading before acting — emerges automatically from the POMDP framework without being explicitly programmed.

POMDPs are the theoretical foundation for modern active perception, medical decision-making under uncertainty, and dialogue system design (where the "state" is the user's intent, partially revealed by their words).

# POMDP belief update and one-step value computation
import numpy as np

def belief_update(b, action, observation, T, O):
    """
    b: current belief (np.array of length |S|)
    action: index into A
    observation: index into Omega
    T[s,a,s'] = P(s'|s,a)   shape: (|S|, |A|, |S|)
    O[a,s',o] = P(o|s',a)   shape: (|A|, |S|, |Omega|)
    Returns updated belief b'
    """
    n_states = len(b)
    b_new = np.zeros(n_states)

    for s_prime in range(n_states):
        # Sum over previous states: transition * current belief
        predicted = sum(T[s, action, s_prime] * b[s] for s in range(n_states))
        # Weight by observation probability
        b_new[s_prime] = O[action, s_prime, observation] * predicted

    # Normalize
    total = b_new.sum()
    if total < 1e-12:
        raise ValueError("Impossible observation given belief and action")
    return b_new / total

def alpha_vector_value(b, alpha_vectors):
    """
    POMDP value function: V(b) = max over alpha-vectors of dot(alpha, b)
    alpha_vectors: list of np.arrays, each of length |S|
    """
    return max(np.dot(alpha, b) for alpha in alpha_vectors)

The Fast-Forward (FF) planner (Hoffmann & Nebel, 2001) is one of the most influential planners ever built. It combines:

1. Forward state-space search (hillclimbing + systematic BFS when stuck)
2. The FF heuristic (h^FF): Extract a relaxed plan from the delete-relaxed problem, count its length.

The FF heuristic works in two phases:

1. Relaxed planning graph construction: Build a layered graph alternating between fact layers and action layers. Fact layer F_0 = current state. Action layer A_i = all actions whose preconditions are in F_0 ∪ ... ∪ F_i. Fact layer F_{i+1} = all effects of actions in A_i. Crucially: never delete anything (the relaxation).
2. Relaxed plan extraction: Greedily extract an achiever for each goal at the highest layer. Propagate subgoals backward through the graph.

The resulting h^FF value is the size of the extracted relaxed plan. This is not admissible (the relaxation is too optimistic and greedy extraction can miss synergies), but empirically it is extremely accurate and rarely causes search to miss optimal or even near-optimal plans.

FF uses enforced hill-climbing (EHC): greedily follow states that decrease h^FF. When no neighbor improves h^FF (local minimum), switch to BFS from the current state until a state with lower h^FF is found (escaping plateaus). This makes FF fast and complete (though not optimal).

Modern successors include LAMA (landmark-based), FD (Fast Downward) (using causal graph decomposition and multiple heuristics), and Lama-2011 (winner of IPC 2011). Fast Downward is the dominant open-source planner today — it is used as the backbone for many research systems and has won multiple International Planning Competitions.

The lesson: the right heuristic + simple search often beats fancy algorithms with weak heuristics. The story of classical planning is largely the story of better and better heuristics.

def relaxed_planning_graph(state, goals, actions):
    """
    Build relaxed planning graph (ignoring delete effects).
    Returns (fact_layers, action_layers) until all goals appear.
    """
    fact_layers = [set(state)]
    action_layers = []
    all_facts = set(state)

    while not goals.issubset(all_facts):
        # All applicable actions given current facts
        applicable = [a for a in actions
                      if a.preconditions.issubset(all_facts)]
        action_layers.append(applicable)

        new_facts = all_facts.copy()
        for a in applicable:
            new_facts |= a.add_effects  # NEVER delete — relaxation

        if new_facts == all_facts:
            return None, None  # goals unreachable even in relaxation

        all_facts = new_facts
        fact_layers.append(all_facts.copy())

    return fact_layers, action_layers

def h_ff(state, goals, actions):
    """Count actions in the relaxed plan extracted from RPG."""
    fact_layers, action_layers = relaxed_planning_graph(state, goals, actions)
    if fact_layers is None:
        return float('inf')

    # Greedy backward extraction
    plan_actions = set()
    open_goals = set(goals)

    for layer_idx in range(len(action_layers) - 1, -1, -1):
        new_open = set()
        for goal in open_goals:
            if goal in fact_layers[layer_idx]:  # already true earlier
                continue
            # Find an action in this layer that achieves goal
            achiever = next(
                (a for a in action_layers[layer_idx] if goal in a.add_effects),
                None
            )
            if achiever:
                plan_actions.add(achiever)
                new_open |= achiever.preconditions
        open_goals = new_open

    return len(plan_actions)