Hierarchical, Symbolic, Language, and Multi-Agent Planning › Hierarchical, Symbolic, Language, and Multi-Agent Planning

Much of the planning machinery introduced so far in Part VII: Planning and Agency is easiest to present at the primitive-action level: torque commands, joint velocities, discrete moves, or token-level gestures. That representation becomes awkward when one task spans thousands of decisions. A robot retrieving a mug from a cabinet or negotiating a traffic merge needs feedback at the motor level, but its task planner should not enumerate every motor command. Long primitive rollouts also expose a learned world model to compounding error and states outside its training support.

The combinatorics are easy to see. If a task requires $T$ primitive timesteps and the agent has $|\mathcal{A}|$ actions at each step, a naive full tree has $|\mathcal{A}|^T$ leaves. Four moves over fifty steps already give $4^{50} \approx 1.3 \times 10^{30}$ action sequences. Heuristics, pruning, constraints, and replanning can avoid enumerating that tree. Temporal abstraction offers another lever: it can reduce the number of high-level decisions, and a carefully chosen skill library can keep the high-level branching factor manageable.

There is a second reason to avoid long primitive rollouts: model error compounds. A learned option-outcome model can replace many primitive predictions with one high-level prediction, but that helps only when its initiation states and outcomes are covered by training data or checked during execution. An option can itself traverse unfamiliar states, so hierarchy is not an automatic cure for distribution shift.

The practical move is to structure the problem. Skills can compress many primitive timesteps into one high-level choice. Symbols can discard continuous detail irrelevant to a task. Language can specify goals and constraints without requiring a user to write reward code. Models of other agents can expose strategic dependence that a single-agent transition model hides. These mechanisms change different dimensions of planning; only temporal abstraction directly shortens the decision horizon. Human-readable abstractions can also make plans easier to inspect and communicate, although learned latent skills need not be interpretable.

Abstraction is familiar elsewhere in computing. High-level programming languages let programmers express algorithms in functions and statements that compilers lower into machine instructions. Operating systems expose files and processes rather than disk sectors and page tables. Hierarchical planning applies the same separation of interfaces to decisions: a high-level controller selects a meaningful behavior while a lower-level controller handles its internal feedback.

This chapter develops four interfaces for that structure. Temporal abstraction uses options and skills. Symbolic abstraction maps task-relevant state into predicates and operators. Language grounding converts an instruction into a goal, constraint, reward, or plan sketch. Multi-agent planning represents joint actions, private information, and assumptions about other policies. They are related because each factorizes a planning problem, not because they share one compression formula.

The organizing question is therefore precise: what variable has been simplified, and what assumption makes the simplification valid? Options simplify decision time but rely on competent closed-loop skills. Predicates simplify state descriptions but rely on sound grounding and effects. Language simplifies task specification but relies on reference resolution and semantic alignment. Opponent or teammate models structure strategic uncertainty, but often enlarge rather than shrink the represented state. Each interface creates a distinct failure mode.

By the end of the chapter you will be able to:

• define an option as a temporally extended action with a policy, a termination condition, and an initiation set;
• write the semi-Markov decision process equations that make options composable with ordinary planners;
• build a symbolic abstraction from a continuous world model, including predicates, operators, and the STRIPS-style planning loop;
• condition a plan on a natural-language instruction by grounding it into a goal predicate or reward signal;
• reason about opponents and nested beliefs using the tools of game theory and recursive belief modeling;
• recognize when each abstraction fails and design evaluations that catch the failure.

We assume you have worked through Search and Belief-Space Planning, Policies Learned in Imagination, and Active Perception, Dual Control, and Exploration. This chapter reuses their state, belief, policy, and information notation while changing the structure of the decisions being planned.