---
title: Planning and Acting in the Real World
module: Logic and Planning
moduleNumber: 3
lessonNumber: 9
order: 309
summary: >
  Classical planning's clean theory rests on four assumptions: time is
  ignored, actions are atomic, the world is deterministic and fully observable,
  and the agent is alone. This first part drops the first two. We add durations
  and resource constraints — turning a plan into a schedule, solved by the
  critical-path method and, once resources contend, by NP-hard job-shop
  scheduling — and let a planner reason at multiple levels of abstraction
  through high-level actions and their angelic reachable sets.
topics: [Logic]
sources:
  - book: AIMA
    ref: "Ch. 11 — Planning and Acting in the Real World; §11.1 Time, Schedules, and Resources"
  - book: AIMA
    ref: "§11.2 Hierarchical Planning"
---


[Classical planning](/artificial-intelligence/logic-and-planning/classical-planning)
solves a clean problem: a fully observable, deterministic, static world, acted on
by a single agent through atomic, instantaneous actions. None of those assumptions
holds in the real world. A spacecraft's thrusters fire for a
_duration_ and drain a finite pool of _fuel_; a factory has more operations than
any flat action list could hold, and only a _hierarchy_ makes it tractable; a
painting robot cannot know a can's color until it _looks_; and a delivery fleet is
many agents, not one. This lesson keeps the PDDL representation from classical
planning and extends it four times, once per broken assumption — time and
resources, hierarchy, nondeterminism, and other agents.[^intro]

## Time, schedules, and resources

Classical planning says _what_ to do and in _what order_, but never _how long_ an
action takes or _when_ it happens. An airline planner might assign planes to
flights, yet we also need departure and arrival times — that is **scheduling**.
The real world adds **resource constraints**: an airline has a fixed number of
staff, and a person on one flight cannot be on another at the same moment.

The standard strategy is **plan first, schedule later**. Split the problem into a
_planning_ phase that selects actions with some ordering constraints to meet the
goals, and a later _scheduling_ phase that adds temporal information so the plan
respects deadlines and resource limits. Any planner from the previous chapter that
emits a plan with only the minimal necessary ordering — GraphPlan, SatPlan, a
partial-order planner — can supply the planning phase.[^scheduling]

### The job-shop scheduling problem

A **job-shop scheduling problem** consists of a set of **jobs**, each a collection
of **actions** with ordering constraints among them. Each action carries a
**duration** and a set of resource requirements. A resource is either
**consumable** (bolts are used up) or **reusable** (a pilot is occupied during a
flight but free again after it); resources can even be **produced** by actions with
negative consumption, as in manufacturing or resupply. A solution assigns a start
time to every action, satisfying all temporal ordering and resource constraints.
Solutions are ranked by a cost function; for simplicity we take the cost to be the
total plan duration, called the **makespan**.

$$
% caption: The two-car assembly problem of Figure 11.1. Two jobs, each an
% $AddEngine \prec AddWheels \prec Inspect$ chain; the notation $A \prec B$ means
% $A$ must precede $B$. Resources: 1 engine hoist, 1 wheel station, 2 inspectors,
% 500 lug nuts.
\begin{tikzpicture}[>=stealth, font=\small,
  act/.style={draw, minimum width=22mm, minimum height=11mm, align=center, font=\footnotesize}]
  \definecolor{acc}{HTML}{2348F2}
  % job 1
  \node[act] (e1) at (0,1.4)   {AddEngine1\\dur 30};
  \node[act] (w1) at (3.1,1.4) {AddWheels1\\dur 30};
  \node[act] (i1) at (6.2,1.4) {Inspect1\\dur 10};
  \draw[->, acc, thick] (e1) -- (w1);
  \draw[->, acc, thick] (w1) -- (i1);
  % job 2
  \node[act] (e2) at (0,-1.4)   {AddEngine2\\dur 60};
  \node[act] (w2) at (3.1,-1.4) {AddWheels2\\dur 15};
  \node[act] (i2) at (6.2,-1.4) {Inspect2\\dur 10};
  \draw[->, acc, thick] (e2) -- (w2);
  \draw[->, acc, thick] (w2) -- (i2);
  \node[font=\footnotesize, anchor=east] at (-0.9,1.4)  {job 1:};
  \node[font=\footnotesize, anchor=east] at (-0.9,-1.4) {job 2:};
\end{tikzpicture}
$$

The example problem assembles two cars. Each job has the form
$[\mathit{AddEngine}, \mathit{AddWheels}, \mathit{Inspect}]$. The
$\mathit{AddEngine}$ actions use the single engine hoist; the $\mathit{AddWheels}$
actions consume lug nuts and use the single wheel station; each $\mathit{Inspect}$
uses one of the two inspectors. Lug nuts are consumed (used up as wheels go on);
the hoist, station, and inspectors are reusable — borrowed at the start of an
action and released at its end.

Representing inspectors as a quantity, $\mathit{Inspectors}(2)$, rather than as
named individuals $\mathit{Inspector}(I_1)$ and $\mathit{Inspector}(I_2)$, is an
instance of **aggregation**: group indistinguishable objects into a count. It does
not matter _which_ inspector inspects a car, so the distinction is wasted detail.
Aggregation is essential for reducing complexity. If a schedule needs 10 concurrent
$\mathit{Inspect}$ actions but only 9 inspectors exist, a quantity representation
detects the failure at once; with named individuals the planner would grind through
all $10!$ ways of assigning inspectors before giving up.

### The critical path method

Begin with the temporal problem alone, ignoring resources. To minimize makespan we
need the earliest start times consistent with the ordering constraints. View those
constraints as a directed graph relating the actions, and apply the **critical
path method** (CPM) to it. A **path** through the graph is a linearly ordered
sequence of actions from $\mathit{Start}$ to $\mathit{Finish}$. The **critical
path** is the path whose total duration is longest: it fixes the duration of the
whole plan, because shortening any other path does not shorten the plan, but
delaying any action _on_ the critical path delays everything.

Each action has a window in which it may run, given by an earliest start time
$\mathit{ES}$ and a latest start time $\mathit{LS}$. The **slack** is
$\mathit{LS} - \mathit{ES}$: the amount an action can be delayed without pushing out
the finish. Actions on the critical path have zero slack by definition. Together the
$\mathit{ES}$ and $\mathit{LS}$ values for all actions form a **schedule**. The
following formulas both define the two quantities and outline a dynamic-programming
algorithm to compute them, where $A \prec B$ means $A$ comes before $B$:

$$
\begin{aligned}
\mathit{ES}(\mathit{Start}) &= 0, \\
\mathit{ES}(B) &= \max_{A \,\prec\, B}\; \mathit{ES}(A) + \mathit{Duration}(A), \\
\mathit{LS}(\mathit{Finish}) &= \mathit{ES}(\mathit{Finish}), \\
\mathit{LS}(A) &= \min_{B \,\succ\, A}\; \mathit{LS}(B) - \mathit{Duration}(A).
\end{aligned}
$$

Set $\mathit{ES}(\mathit{Start}) = 0$; then, once every action immediately before
$B$ has an $\mathit{ES}$, set $\mathit{ES}(B)$ to the maximum earliest _finish_ time
of those predecessors (earliest finish is earliest start plus duration). The
$\mathit{LS}$ values are computed the same way, working backward from
$\mathit{Finish}$. The complexity is $O(Nb)$ for $N$ actions and branching factor
$b$: each of the two passes touches each action once, iterating over at most $b$
neighbors. Finding a minimum-duration schedule with no resource constraints is
therefore easy.

$$
% caption: Critical-path schedule for the two-car problem. Each box shows the
% window $[\mathit{ES}, \mathit{LS}]$ above and the duration below. The whole plan
% takes 85; the top job carries 15 of slack per action, the bottom job (bold, the
% critical path) has zero slack.
\begin{tikzpicture}[>=stealth, font=\small,
  act/.style={draw, minimum width=20mm, minimum height=13mm, align=center, font=\scriptsize},
  crit/.style={draw, line width=1pt, minimum width=20mm, minimum height=13mm, align=center, font=\scriptsize}]
  \definecolor{acc}{HTML}{2348F2}
  \node[act] (st) at (-2.6,0) {Start\\{}(0,0)};
  % top job (15 slack each)
  \node[act] (e1) at (0.4,1.7)  {AddEngine1\\{}(0,15) : 30};
  \node[act] (w1) at (3.3,1.7)  {AddWheels1\\{}(30,45) : 30};
  \node[act] (i1) at (6.2,1.7)  {Inspect1\\{}(60,75) : 10};
  % bottom job (critical, zero slack)
  \node[crit] (e2) at (0.4,-1.7) {AddEngine2\\{}(0,0) : 60};
  \node[crit] (w2) at (3.3,-1.7) {AddWheels2\\{}(60,60) : 15};
  \node[crit] (i2) at (6.2,-1.7) {Inspect2\\{}(75,75) : 10};
  \node[act] (fi) at (8.9,0) {Finish\\{}(85,85)};
  \draw[->, black] (st) -- (e1);
  \draw[->, black] (e1) -- (w1);
  \draw[->, black] (w1) -- (i1);
  \draw[->, black] (i1) -- (fi);
  \draw[->, acc, line width=1pt] (st) -- (e2);
  \draw[->, acc, line width=1pt] (e2) -- (w2);
  \draw[->, acc, line width=1pt] (w2) -- (i2);
  \draw[->, acc, line width=1pt] (i2) -- (fi);
\end{tikzpicture}
$$

For example, work the two-car problem by hand. The forward pass
sets $\mathit{ES}(\mathit{Start}) = 0$ and sweeps the chains left to right, taking
earliest finish (start plus duration) as each successor's earliest start. Job 1 runs
$\mathit{AddEngine1}$ at 0 (finish 30), $\mathit{AddWheels1}$ at 30 (finish 60),
$\mathit{Inspect1}$ at 60 (finish 70). Job 2 runs $\mathit{AddEngine2}$ at 0 (finish
60, because its duration is 60), $\mathit{AddWheels2}$ at 60 (finish 75),
$\mathit{Inspect2}$ at 75 (finish 85). $\mathit{Finish}$ waits on both inspections,
so $\mathit{ES}(\mathit{Finish}) = \max(70, 85) = 85$: the makespan.

The backward pass sets $\mathit{LS}(\mathit{Finish}) = 85$ and sweeps right to left,
taking each action's latest start as the minimum over its successors of
$\mathit{LS}(\text{successor}) - \mathit{Duration}(\text{this action})$. On job 2,
$\mathit{LS}(\mathit{Inspect2}) = 85 - 10 = 75$, $\mathit{LS}(\mathit{AddWheels2}) =
75 - 15 = 60$, $\mathit{LS}(\mathit{AddEngine2}) = 60 - 60 = 0$ — every value equals
its $\mathit{ES}$, so job 2 has zero slack and is the critical path. On job 1,
$\mathit{LS}(\mathit{Inspect1}) = 85 - 10 = 75$, so $\mathit{ES} = 60$ against
$\mathit{LS} = 75$ leaves 15 of slack; the same 15 propagates back through
$\mathit{AddWheels1}$ and $\mathit{AddEngine1}$.

$$
% caption: Forward and backward passes for the two-car problem, by action.
% Columns: duration, earliest start (ES), earliest finish (EF = ES + dur), latest
% start (LS), latest finish (LF), slack (LS $-$ ES). The four zero-slack rows of
% job 2 (bold) are the critical path; job 1 carries 15 of slack throughout.
\begin{tikzpicture}[font=\footnotesize]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  \definecolor{tintb}{HTML}{DDE3FE}
  % header row
  \fill[tintb] (0,4.6) rectangle (11.4,5.2);
  \foreach \c/\x in {action/1.55, dur/4.0, ES/5.2, EF/6.4, LS/7.6, LF/8.8, slack/10.4}
    {\node[font=\scriptsize\bfseries] at (\x,4.9) {\c};}
  % vertical separators
  \foreach \x in {3.1,4.6,5.8,7.0,8.2,9.4}
    \draw[black] (\x,-0.6) -- (\x,5.2);
  % horizontal lines
  \draw[black] (0,5.2) -- (11.4,5.2);
  \draw[black] (0,4.6) -- (11.4,4.6);
  \draw[black] (0,-0.6) -- (11.4,-0.6);
  \draw[black] (0,1.8) -- (11.4,1.8);
  % job 1 rows (slack 15)
  \foreach \name/\d/\es/\ef/\ls/\lf/\y in {%
    AddEngine1/30/0/30/15/45/4.1,
    AddWheels1/30/30/60/45/75/3.4,
    Inspect1/10/60/70/75/85/2.7}
    {\node[anchor=west] at (0.15,\y) {\name};
     \node at (4.0,\y) {\d}; \node at (5.2,\y) {\es}; \node at (6.4,\y) {\ef};
     \node at (7.6,\y) {\ls}; \node at (8.8,\y) {\lf};
     \node[black] at (10.4,\y) {15};}
  % job 2 rows (slack 0, critical)
  \foreach \name/\d/\es/\ef/\ls/\lf/\y in {%
    AddEngine2/60/0/60/0/60/1.2,
    AddWheels2/15/60/75/60/75/0.5,
    Inspect2/10/75/85/75/85/-0.2}
    {\node[anchor=west, font=\footnotesize\bfseries] at (0.15,\y) {\name};
     \node[font=\bfseries] at (4.0,\y) {\d}; \node[font=\bfseries] at (5.2,\y) {\es};
     \node[font=\bfseries] at (6.4,\y) {\ef}; \node[font=\bfseries] at (7.6,\y) {\ls};
     \node[font=\bfseries] at (8.8,\y) {\lf}; \node[red, font=\bfseries] at (10.4,\y) {0};}
\end{tikzpicture}
$$

Mathematically, critical-path problems are easy because they are a _conjunction_
of linear inequalities on the start and end times. Resource constraints spoil this.
The two $\mathit{AddEngine}$ actions both need the single engine hoist and so cannot
overlap; "cannot overlap" is a _disjunction_ of two linear inequalities, one per
possible ordering. Introducing disjunctions makes scheduling with resource
constraints **NP-hard**. The resource-respecting solution for the two cars takes
115 minutes, 30 more than the 85 of the resource-free schedule.

$$
% caption: Adding resource constraints. The two engine actions must serialize on
% the single hoist, and the wheel actions on the single station, stretching the
% makespan from 85 to 115. Bars are placed against the timeline (minutes).
\begin{tikzpicture}[>=stealth, font=\footnotesize]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{tintb}{HTML}{DDE3FE}
  \definecolor{tintg}{HTML}{ECECEC}
  % axis
  \draw[black] (0,-0.4) -- (12,-0.4);
  \foreach \t/\x in {0/0, 30/3, 60/6, 90/9, 115/11.5}
    {\draw[black] (\x,-0.35) -- (\x,-0.55); \node[anchor=north, font=\scriptsize] at (\x,-0.55) {\t};}
  % hoist row: AddEngine1 [0,30], AddEngine2 [30,90]
  \node[anchor=east, font=\scriptsize] at (-0.2,2.4) {hoist:};
  \draw[fill=tintb, draw=acc] (0,2.1) rectangle (3,2.7); \node[font=\scriptsize] at (1.5,2.4) {AddEngine1};
  \draw[fill=tintb, draw=acc] (3,2.1) rectangle (9,2.7); \node[font=\scriptsize] at (6,2.4) {AddEngine2};
  % station row: AddWheels1 [30,60], AddWheels2 [90,105]
  \node[anchor=east, font=\scriptsize] at (-0.2,1.5) {station:};
  \draw[fill=tintg, draw=black] (3,1.2) rectangle (6,1.8); \node[font=\scriptsize] at (4.5,1.5) {AddWheels1};
  \draw[fill=tintg, draw=black] (9,1.2) rectangle (10.5,1.8); \node[font=\scriptsize] at (9.75,1.5) {AW2};
  % inspector row: Inspect1 [60,70], Inspect2 [105,115]
  \node[anchor=east, font=\scriptsize] at (-0.2,0.6) {inspect:};
  \draw[fill=tintg, draw=black] (6,0.3) rectangle (7,0.9); \node[font=\scriptsize] at (6.5,0.6) {I1};
  \draw[fill=tintg, draw=black] (10.5,0.3) rectangle (11.5,0.9); \node[font=\scriptsize] at (11,0.6) {I2};
\end{tikzpicture}
$$

Optimal scheduling with resources is hard in practice as well as in theory: a 1963
challenge problem of 10 machines and 10 jobs of 100 actions each went unsolved for
23 years. One simple, popular heuristic is **minimum slack**: on each iteration,
among the unscheduled actions whose predecessors are all scheduled, pick the one
with the _least_ slack, schedule it at its earliest possible start, then update the
$\mathit{ES}$ and $\mathit{LS}$ of every affected action and repeat. It is the
scheduling cousin of the minimum-remaining-values heuristic from
[constraint satisfaction](/artificial-intelligence/search/constraint-satisfaction).
It works well in practice but is not optimal — on the two-car problem it yields a
130-minute schedule, not the 115-minute optimum.

The first minimum-slack step shows where the heuristic goes wrong. At the start, only the two
$\mathit{AddEngine}$ actions have all predecessors scheduled (their sole predecessor
is $\mathit{Start}$). From the resource-free schedule $\mathit{AddEngine1}$ has slack
15 and $\mathit{AddEngine2}$ has slack 0, so the heuristic schedules
$\mathit{AddEngine2}$ first, at time 0, on the hoist. That commits the hoist for
$[0, 60]$. Now $\mathit{AddEngine1}$ becomes eligible, but the hoist is busy until 60,
so its earliest feasible start moves from 0 to 60; the update recomputes every
downstream $\mathit{ES}$ and $\mathit{LS}$ under the new hoist reservation, and job 1
inherits the 60-minute delay it did not have in the resource-free plan. That single
early commitment is what pushes the greedy schedule past the optimum: a solver willing
to run $\mathit{AddEngine1}$ first, finishing the hoist at 30, would free job 2 to
start its wheels sooner and reach the 115-minute optimum.

If a scheduling problem proves hard, it may be a mistake to hold the action set
fixed and squeeze a schedule out of it; reconsidering which actions to use can lead
to a far easier schedule. That argues for _integrating_ planning and scheduling
rather than strictly separating them, so that durations and overlaps inform plan
construction. Estimating total completion time this way is an active research area.

## Hierarchical planning

The planners so far work with a _fixed set of atomic actions_. That does not scale
to real life. Atomic actions for a human are muscle activations: roughly $10^3$
muscles, modulated perhaps 10 times a second, over about $10^9$ awake seconds — on
the order of $10^{13}$ actions in a lifetime, and even a two-week vacation is around
$10^{10}$ motor commands. No flat planner reasons over $10^{10}$ steps.

The solution is what humans plainly do: plan at higher levels of abstraction. A
Hawaii-vacation plan might be "go to San Francisco airport; take flight 11 to
Honolulu; vacation for two weeks; take flight 12 back; go home." Each of those, in
turn, is a planning task with its own solution ("drive to long-term parking; park;
take the shuttle"), decomposed further until we reach actions executable without
deliberation. This is **hierarchical decomposition**, the idea behind almost every
system for managing complexity: software is a hierarchy of subroutines, an army a
hierarchy of units, a corporation a hierarchy of departments. The benefit is that
at each level a task reduces to a _small_ number of activities at the level below,
so the cost of arranging them is small.

### High-level actions

The formalism is **hierarchical task network** (HTN) planning. As in classical
planning we assume full observability, determinism, and a set of **primitive
actions** with ordinary precondition–effect schemas. The new concept is the
**high-level action** (HLA) — for example, $\mathit{Go}(\mathit{Home},
\mathit{SFO})$. Each HLA has one or more **refinements** into a sequence of actions,
each of which may itself be an HLA or a primitive action. A primitive action has no
refinements. Refinements may carry preconditions and may be **recursive**.

$$
% caption: Two refinements of $Go(Home, SFO)$ (drive-and-shuttle, or take a taxi)
% and the recursive refinement of $Navigate([a,b],[x,y])$ in the vacuum world:
% either you are already there, or step one square and navigate the rest.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  hla/.style={draw, thick, minimum width=34mm, minimum height=9mm, align=center, font=\footnotesize},
  ref/.style={draw, minimum width=30mm, minimum height=8mm, align=center, font=\scriptsize}]
  \definecolor{acc}{HTML}{2348F2}
  \node[hla, draw=acc, text=acc] (go) at (0,0) {Go(Home, SFO)};
  \node[ref] (r1) at (-3.2,-1.8) {Drive; Shuttle};
  \node[ref] (r2) at (0.4,-1.8)  {Taxi(Home, SFO)};
  \draw[->, acc] (go) -- (r1);
  \draw[->, acc] (go) -- (r2);
  % navigate recursive
  \node[hla, draw=acc, text=acc] (nav) at (5.9,0) {Navigate([a,b],[x,y])};
  \node[ref] (n1) at (4.2,-1.8) {(empty) if a=x, b=y};
  \node[ref] (n2) at (7.9,-1.8) {Left; Navigate(...)};
  \draw[->, acc] (nav) -- (n1);
  \draw[->, acc] (nav) -- (n2);
  \draw[->, acc] (n2) to[out=-70, in=-70, looseness=2.6] (n2.east);
  \node[font=\scriptsize, anchor=west] at (9.3,-2.3) {recursion};
\end{tikzpicture}
$$

An HLA refinement containing only primitive actions is an **implementation** of the
HLA. In the vacuum world, both $[\mathit{Right}, \mathit{Right}, \mathit{Down}]$ and
$[\mathit{Down}, \mathit{Right}, \mathit{Right}]$ implement
$\mathit{Navigate}([1,3],[3,2])$. An implementation of a high-level _plan_ (a
sequence of HLAs) is the concatenation of implementations of each HLA. Given the
primitive schemas, it is straightforward to check whether a given implementation
achieves the goal. This lets us say: a high-level plan achieves the goal from a
state if _at least one_ of its implementations does.

That "at least one" is the crux. Unlike nondeterministic planning — where we
required a plan that works for _all_ outcomes because _nature_ chooses — here the
_agent_ chooses which implementation to execute, so one working implementation is
enough.[^atleastone] The simplest case is an HLA with exactly one implementation: we
can compute its precondition and effect from the implementation and treat it as a
new primitive. With the right library of such HLAs, the time complexity of blind
search can drop from exponential in the solution depth to linear.

### Searching for primitive solutions

HTN planning is often stated with a single top-level action $\mathit{Act}$, whose
refinements are chosen so that an implementation of $\mathit{Act}$ that achieves the
goal _is_ a solution. This is fully general: for each primitive $a_i$, give
$\mathit{Act}$ a refinement with steps $[a_i, \mathit{Act}]$ (a recursive definition
that lets us add actions), plus one refinement with empty steps and precondition
equal to the goal (which stops the recursion — if the goal already holds, do
nothing). The search then repeatedly picks an HLA in the current plan and replaces
it with one of its refinements, until the plan is primitive and achieves the goal.

```algorithm
caption: $\textsc{Hierarchical-Search}(\mathit{problem}, \mathit{hierarchy})$ — breadth-first refinement
$\mathit{frontier} \gets$ a FIFO queue with $[\mathit{Act}]$ as its only element
repeat
  if $\textsc{Empty?}(\mathit{frontier})$ then return failure
  $\mathit{plan} \gets \textsc{Pop}(\mathit{frontier})$ // shallowest plan in frontier
  $\mathit{hla} \gets$ the first HLA in $\mathit{plan}$, or null if none
  $\mathit{prefix}, \mathit{suffix} \gets$ the action subsequences before and after $\mathit{hla}$
  $\mathit{outcome} \gets \textsc{Result}(\mathit{problem}.\textsc{Initial-State}, \mathit{prefix})$
  if $\mathit{hla}$ is null then // plan is primitive; $\mathit{outcome}$ is its result
    if $\mathit{outcome}$ satisfies $\mathit{problem}.\textsc{Goal}$ then return $\mathit{plan}$
  else
    for each $\mathit{sequence}$ in $\textsc{Refinements}(\mathit{hla}, \mathit{outcome}, \mathit{hierarchy})$ do
      $\mathit{frontier} \gets \textsc{Insert}(\textsc{Append}(\mathit{prefix}, \mathit{sequence}, \mathit{suffix}), \mathit{frontier})$
```

This form of search explores the space of action sequences that _conform_ to the
knowledge in the HLA library about how things are done. A great deal of knowledge
sits in that library, in both the action sequences and the refinement preconditions.
For some domains, HTN planners generate huge plans with little search: O-Plan,
combining HTN planning with scheduling, has produced 30-day production schedules for
a product line of 350 products, 35 machines, and over 2000 operations, running to
tens of millions of steps.

The payoff can be quantified. Suppose a solution has $d$ primitive actions. A
nonhierarchical forward planner with $b$ actions per state costs $O(b^d)$. For a
regular HTN with $r$ refinements per nonprimitive and $k$ actions per refinement,
the number of levels below the root is $\log_k d$, and the number of possible
decomposition trees is $r^{(d-1)/(k-1)}$. Keeping $r$ small and $k$ large is
essentially taking the $k$-th root of the nonhierarchical cost — a huge saving. The
key to HTN planning is a library of HLAs with few refinements each yielding long,
reusable action sequences. Long sequences usable across many problems are what make
the library worthwhile, and one way to build it is to _learn_ methods from
problem-solving experience.

### Searching for abstract solutions

The search above refines every HLA all the way to primitives before it can tell
whether a plan works. That contradicts common sense: one should be able to see that
the two-HLA plan
$[\mathit{Drive}(\mathit{Home}, \mathit{Parking}), \mathit{Shuttle}(\mathit{Parking},
\mathit{SFO})]$ gets you to the airport without fixing a precise route or parking
spot. The fix is to write precondition–effect descriptions _for the HLAs
themselves_, so an abstract plan can be proven to achieve the goal in a small search
space of high-level actions. Committing to a provably good abstract plan, then
refining its steps, is where the exponential reduction comes from.

For this to be sound, every high-level plan that _claims_ to achieve the goal (by
its steps' descriptions) must in fact achieve it — meaning it has at least one
implementation that does. This is the **downward refinement property** of HLA
descriptions. The subtlety is how to describe the effect of an HLA with _multiple_
implementations. Requiring an effect to hold for _every_ implementation is too
conservative: it treats the HLA like a **nondeterministic** action where an
adversary picks the outcome (**demonic nondeterminism**). But here the agent picks,
so the right model is **angelic nondeterminism**.

The tool for angelic semantics is the **reachable set**. Given a state $s$, the
reachable set of an HLA $h$, written $\textsc{Reach}(s, h)$, is the set of states
reachable by _any_ of $h$'s implementations. The agent can choose _which_ element it
lands in, so an HLA with more refinements is more powerful. For a sequence,
$\textsc{Reach}(s, [h_1, h_2])$ is the union over all $s' \in \textsc{Reach}(s, h_1)$
of $\textsc{Reach}(s', h_2)$:

$$
\textsc{Reach}(s, [h_1, h_2]) \;=\; \bigcup_{s' \,\in\, \textsc{Reach}(s, h_1)} \textsc{Reach}(s', h_2).
$$

A high-level plan achieves the goal if its reachable set _intersects_ the goal set.
(Compare this to demonic semantics, where every member of the reachable set would
have to be a goal state.) If the reachable set does not intersect the goal, the plan
definitely does not work.

$$
% caption: Reachable sets, after Figure 11.6. The goal set is shaded. Left: the
% reachable set of one HLA $h_1$ from state $s$. Right: the reachable set of the
% sequence $[h_1, h_2]$; because it intersects the goal, the sequence achieves the
% goal.
\begin{tikzpicture}[>=stealth, font=\footnotesize]
  \definecolor{acc}{HTML}{2348F2}
  % ---- panel (a) ----
  \foreach \x in {0,0.6,...,2.4}
    \foreach \y in {0,0.6,...,2.4}
      \fill[black] (\x,\y) circle (1.6pt);
  \fill[black] (1.5,0.3) rectangle (2.55,1.35); % goal region
  \node[anchor=north] at (1.2,-0.2) {(a)};
  % start state
  \fill[acc] (0,1.2) circle (2.4pt);
  \node[acc, anchor=east, font=\scriptsize] at (-0.15,1.2) {s};
  % reachable set (dashed) around a couple of states
  \draw[dashed, acc] (0.45,0.85) rectangle (1.05,1.55);
  \draw[->, acc, thick] (0,1.2) to[bend left=18] (0.6,1.2);
  \draw[->, acc, thick] (0,1.2) to[bend left=18] (0.6,0.9);
  % ---- panel (b) ----
  \begin{scope}[xshift=5.4cm]
    \foreach \x in {0,0.6,...,2.4}
      \foreach \y in {0,0.6,...,2.4}
        \fill[black] (\x,\y) circle (1.6pt);
    \fill[black] (1.5,0.3) rectangle (2.55,1.35);
    \node[anchor=north] at (1.2,-0.2) {(b)};
    \fill[acc] (0,1.2) circle (2.4pt);
    \node[acc, anchor=east, font=\scriptsize] at (-0.15,1.2) {s};
    % first reachable set
    \draw[dashed, acc] (0.45,0.85) rectangle (1.05,1.55);
    \draw[->, acc, thick] (0,1.2) to[bend left=18] (0.6,1.2);
    % second reachable set intersecting goal
    \draw[dashed, red] (1.45,0.25) rectangle (2.05,1.55);
    \draw[->, black, thick] (0.6,1.2) to[bend left=14] (1.8,1.2);
    \draw[black] (1.8,0.6) circle (3.2pt); % goal-reaching state
  \end{scope}
  \definecolor{red}{HTML}{C0392B}
\end{tikzpicture}
$$

An HLA under angelic semantics can do more than a primitive action: it can _control_
a variable, setting it true or false depending on which implementation is chosen. To
express this, a tilde-style notation marks "possibly, if the agent so chooses": an
effect $\tilde{+}A$ means "either leave $A$ alone or make it true," and $\tilde{-}A$
means "possibly delete $A$." Because an HLA may have infinitely many implementations
and arbitrarily wiggly reachable sets, we often cannot describe the effect exactly.
Then we bracket it with two approximations: an **optimistic description**
$\textsc{Reach}^{+}(s, h)$ that may _overstate_ the reachable set, and a
**pessimistic description** $\textsc{Reach}^{-}(s, h)$ that may _understate_ it, with

$$
\textsc{Reach}^{-}(s, h) \;\subseteq\; \textsc{Reach}(s, h) \;\subseteq\; \textsc{Reach}^{+}(s, h).
$$

With approximate descriptions the goal test splits three ways. If the _optimistic_
set misses the goal, the plan fails. If the _pessimistic_ set already hits the goal,
the plan works. If the optimistic set hits but the pessimistic set misses, we cannot
yet tell, and must refine the plan further to resolve the uncertainty.

$$
% caption: The three-way test with approximate descriptions, after Figure 11.7.
% Solid outline = pessimistic set, dashed = optimistic. If the pessimistic set hits
% the goal the plan works; if the optimistic set misses, it fails; otherwise the
% plan must be refined further.
\begin{tikzpicture}[>=stealth, font=\footnotesize]
  \definecolor{acc}{HTML}{2348F2}
  % ------- (a) works -------
  \fill[black] (1.7,0.2) rectangle (2.9,1.3);
  \foreach \x in {0.2,0.8,1.4,2.0,2.6} \foreach \y in {0.2,0.8,1.4,2.0}
    \fill[black] (\x,\y) circle (1.4pt);
  \draw[dashed, acc] (1.5,0.6) rectangle (2.7,1.7); % optimistic
  \draw[acc, thick] (1.85,0.75) rectangle (2.55,1.45); % pessimistic hits goal
  \fill[acc] (0.2,1.0) circle (2.2pt);
  \draw[->, acc, thick] (0.2,1.0) to[bend left=16] (2.0,1.1);
  \node[anchor=north] at (1.4,-0.15) {(a) works};
  % ------- (b) unknown -------
  \begin{scope}[xshift=5.6cm]
    \fill[black] (1.7,0.2) rectangle (2.9,1.3);
    \foreach \x in {0.2,0.8,1.4,2.0,2.6} \foreach \y in {0.2,0.8,1.4,2.0}
      \fill[black] (\x,\y) circle (1.4pt);
    \draw[dashed, acc] (1.5,0.6) rectangle (2.7,1.7); % optimistic hits goal
    \draw[acc, thick] (1.5,0.9) rectangle (2.05,1.55); % pessimistic misses goal
    \fill[acc] (0.2,1.0) circle (2.2pt);
    \draw[->, acc, thick] (0.2,1.0) to[bend left=16] (1.7,1.2);
    \node[anchor=north] at (1.4,-0.15) {(b) undecided};
  \end{scope}
\end{tikzpicture}
$$

A tiny instance shows the three cases decided by nothing but set membership. Take a
state with two fluents $A$ and $B$, both false in $s$, and the goal set
$\{A \wedge B\}$. Suppose HLA $h_1$ has the optimistic effect $\tilde{+}A,\,
\tilde{+}B$ (it _can_ set either fluent, agent's choice) and the pessimistic effect
$+A$ (it _will_ at least set $A$). Then $\textsc{Reach}^{+}(s, h_1) =
\{\overline{A}\overline{B},\, A\overline{B},\, \overline{A}B,\, AB\}$ contains the goal
$AB$, so the optimistic test passes; and $\textsc{Reach}^{-}(s, h_1) =
\{A\overline{B},\, AB\}$, the states forced by $+A$ with $B$ free, also contains $AB$,
so the pessimistic test passes and the plan $[h_1]$ provably works. Weaken the
pessimistic effect to "$h_1$ guarantees nothing" and $\textsc{Reach}^{-}(s, h_1) =
\{\overline{A}\overline{B}\}$ misses the goal while $\textsc{Reach}^{+}$ still hits it:
now the plan is undecided and must be refined. Drop $\tilde{+}B$ from the optimistic
effect and $\textsc{Reach}^{+}(s, h_1) = \{\overline{A}\overline{B},\, A\overline{B}\}$
never contains $AB$: the plan provably fails, with no refinement worth trying.

The ability to commit to a good abstract plan and reject a bad one gives an angelic
search a large advantage. Cleaning a vacuum world of rectangular rooms connected by
corridors makes the point: a plain breadth-first search costs $5^d$ for solution
length $d$ and cannot manage even two $2 \times 2$ rooms; the angelic search, given
a $\mathit{Navigate}$ HLA and a $\mathit{CleanWholeRoom}$ HLA, commits to a good
high-level sequence and scales roughly _linearly_ in the number of squares. Cleaning
rooms one at a time is easy for humans precisely because of the hierarchical
structure of the task.


## Where this continues

Time and hierarchy relaxed two of classical planning's four assumptions, but the
planner still assumes it can see the whole world and predict every outcome — and
that it is the only agent acting. Real environments break both assumptions: sensors
are partial, actions can fail, and other agents move at the same time.

This continues in
[Planning Under Uncertainty](/artificial-intelligence/logic-and-planning/planning-under-uncertainty),
which plans in belief-state space when the agent cannot see or predict the world
(sensorless, contingent, and online replanning), and then puts other agents in the
loop with joint plans, coordination, and conventions.

[^intro]: **AIMA**, Ch. 11 — Planning and Acting in the Real World: real planners for spacecraft, factories, and military logistics extend both the representation language and the agent's interaction with the environment beyond classical planning's assumptions.
[^scheduling]: **AIMA**, §11.1 — Time, Schedules, and Resources: the "plan first, schedule later" decomposition, and the observation that any planner producing minimally ordered plans (GraphPlan, SatPlan, partial-order planning) can supply the planning phase.
[^atleastone]: **AIMA**, §11.2.1 — High-Level Actions: a high-level plan achieves the goal if at least one of its implementations does, in contrast to nondeterministic planning where a plan must work for every outcome because nature, not the agent, chooses.