Planning and Acting in the Real World

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.¹

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.²

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.

The example problem assembles two cars. Each job has the form $[AddEngine,AddWheels,Inspect]$. The $AddEngine$ actions use the single engine hoist; the $AddWheels$ actions consume lug nuts and use the single wheel station; each $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, $Inspectors(2)$, rather than as named individuals $Inspector(I_1)$ and $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 $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 $Start$ to $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 $ES$ and a latest start time $LS$. The slack is $LS-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 $ES$ and $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$:

Set $ES(Start)=0$; then, once every action immediately before $B$ has an $ES$, set $ES(B)$ to the maximum earliest finish time of those predecessors (earliest finish is earliest start plus duration). The $LS$ values are computed the same way, working backward from $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.

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

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

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 $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.

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 $ES$ and $LS$ of every affected action and repeat. It is the scheduling cousin of the minimum-remaining-values heuristic from 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 $AddEngine$ actions have all predecessors scheduled (their sole predecessor is $Start$). From the resource-free schedule $AddEngine1$ has slack 15 and $AddEngine2$ has slack 0, so the heuristic schedules $AddEngine2$ first, at time 0, on the hoist. That commits the hoist for $[0,60]$. Now $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 $ES$ and $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 $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, $Go(Home,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.

An HLA refinement containing only primitive actions is an implementation of the HLA. In the vacuum world, both $[Right,Right,Down]$ and $[Down,Right,Right]$ implement $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.³ 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 $Act$, whose refinements are chosen so that an implementation of $Act$ that achieves the goal is a solution. This is fully general: for each primitive $a_i$, give $Act$ a refinement with steps $[a_i,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.

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 $[Drive(Home,Parking),Shuttle(Parking,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 $\text{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, $\text{Reach}(s,[h_1,h_2])$ is the union over all $s^{\prime }\in \text{Reach}(s,h_1)$ of $\text{Reach}(s^{\prime },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.

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 $\widetilde{+}A$ means either leave $A$ alone or make it true, and $\widetilde{-}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${\text{Reach}}^{+}(s,h)$ that may overstate the reachable set, and a pessimistic description ${\text{Reach}}^{-}(s,h)$ that may understate it, with

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.

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 $\widetilde{+}A,\widetilde{+}B$ (it can set either fluent, agent's choice) and the pessimistic effect $+A$ (it will at least set $A$). Then ${\text{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 ${\text{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 ${\text{Reach}}^{-}(s,h_1)=\{\overline{A}\overline{B}\}$ misses the goal while ${\text{Reach}}^{+}$ still hits it: now the plan is undecided and must be refined. Drop $\widetilde{+}B$ from the optimistic effect and ${\text{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 $Navigate$ HLA and a $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, 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.