---
title: Planning Under Uncertainty
module: Logic and Planning
moduleNumber: 3
lessonNumber: 10
order: 310
summary: >
  Classical planning assumed the world was deterministic, fully observable, and
  the agent alone. This part drops the last two assumptions. When the agent cannot
  see or predict the world, planning moves into belief-state space: sensorless
  plans that coerce the world into the goal without sensing, contingent plans
  that branch on what is sensed, and online agents that monitor and replan when execution diverges. Then
  we add other agents — joint plans, the coordination problem, and the conventions
  that let a team act without constant negotiation.
topics: [Logic]
sources:
  - book: AIMA
    ref: "Ch. 11 — Planning and Acting in the Real World; §11.3 Planning and Acting in Nondeterministic Domains"
  - book: AIMA
    ref: "§11.4 Multiagent Planning"
---

This builds on
[Planning and Acting in the Real World](/artificial-intelligence/logic-and-planning/planning-in-the-real-world),
which added time and resources to classical planning and let a planner reason at
multiple altitudes. Here we drop the remaining two assumptions: that the world is
observable and deterministic, and that the agent acts alone.

## Planning and acting in nondeterministic domains

Now drop full observability and determinism. Three settings arise, mirroring the
extensions to search:

- **Sensorless (conformant) planning** for environments with no observations.
- **Contingent planning** for partially observable, nondeterministic environments —
  plans that branch on percepts.
- **Online planning and replanning** for unknown environments, interleaving
  deliberation and execution.

The concepts match those in [search](/artificial-intelligence/search/local-search),
but planners work over _factored_ representations, so the agent's capability for
action and observation, and its **belief states** — the sets of possible physical
states it might be in — are all represented with logical formulas rather than
enumerated sets.

The running problem: given a chair and a table, make them the same color. The agent
has two cans of paint of unknown color; the furniture colors are unknown; only the
table is initially in view. Two actions apply: $\mathit{RemoveLid}(\mathit{can})$
opens a can, and $\mathit{Paint}(x, \mathit{can})$ paints object $x$ with an open
can. Partial observability forces one new wrinkle: the $\mathit{Paint}$ schema
mentions a color variable $c$ not in the action's argument list, universally
quantified, because the agent may not know what color is in the can. To reason about
percepts we augment PDDL with a **percept schema** — for instance, "whenever an
object is in view, the agent perceives its color."

$$
% caption: Three responses to the painting problem, from least to most informed. A
% sensorless plan coerces both objects to a common color; a contingent plan
% branches on what it sees; an online plan replans when execution reveals a problem.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  box/.style={draw, minimum width=32mm, minimum height=15mm, align=center, font=\scriptsize}]
  \definecolor{acc}{HTML}{2348F2}
  \node[box] (a) at (0,0)   {sensorless\\no percepts\\coerce to one color};
  \node[box] (b) at (4.2,0) {contingent\\percepts at plan time\\branch on observation};
  \node[box, draw=acc, text=acc, thick] (c) at (8.4,0) {online\\percepts at run time\\replan on failure};
  \draw[->, acc, thick] (a) -- (b) node[midway, above, font=\scriptsize] {more info};
  \draw[->, acc, thick] (b) -- (c) node[midway, above, font=\scriptsize] {more info};
\end{tikzpicture}
$$

### Sensorless planning

A sensorless problem is solved by searching in **belief-state** space, exactly as in
Section 4.4.1, but with the belief state written as a logical formula and the
transition model as action schemas. For the painting problem the agent knows only
that objects and cans have _some_ color: $\forall x\, \exists c\; \mathit{Color}(x,
c)$. After Skolemizing, the initial belief state is $b_0 = \mathit{Color}(x,
\mathit{C}(x))$. Classical planning made the **closed-world assumption** (unmentioned
fluents are false); sensorless planning switches to the **open-world assumption**,
where a fluent absent from the belief state has unknown value.

Even a sensorless agent can solve the painting problem, by **coercion**: open one
can and apply its paint to _both_ chair and table, forcing them to match without ever
knowing the color. The belief state is progressed through the action sequence with

$$
b' = \textsc{Result}(b, a) = (b - \textsc{Del}(a)) \cup \textsc{Add}(a),
$$

almost identical to the observable case. A useful consequence: _the family
of belief states written as conjunctions of literals is closed under PDDL updates_.
In a world with $n$ fluents any such belief state has size $O(n)$, even though there
are $2^n$ states. The catch is that action schemas with **conditional effects** —
"$\text{when } \mathit{condition}\!: \mathit{effect}$" — can introduce dependencies
between fluents and push the belief state out of 1-CNF, into disjunctions of
exponential size in the worst case. One remedy is a **conservative approximation**:
keep only the literals whose truth values are determined and treat the rest as
unknown. This is _sound_ (never produces an incorrect plan) but _incomplete_ (may
miss solutions that require reasoning about the untracked interactions).

### Contingent planning

A **contingent plan** branches on percepts, and suits partial observability,
nondeterminism, or both. For the painting problem, a contingent plan looks like
this:

```algorithm
caption: A contingent plan for the painting problem, after §11.3.2 — branch on what is seen
$\textsc{LookAt}(\mathit{Table})$; $\textsc{LookAt}(\mathit{Chair})$
if $\mathit{Color}(\mathit{Table}, c) \wedge \mathit{Color}(\mathit{Chair}, c)$ then
  $\textsc{NoOp}$ // already matching; done
else
  $\textsc{RemoveLid}(\mathit{Can}_1)$; $\textsc{LookAt}(\mathit{Can}_1)$; $\textsc{RemoveLid}(\mathit{Can}_2)$; $\textsc{LookAt}(\mathit{Can}_2)$
  if $\mathit{Color}(\mathit{Table}, c) \wedge \mathit{Color}(\mathit{can}, c)$ then
    $\textsc{Paint}(\mathit{Chair}, \mathit{can})$ // a can matches the table; paint the chair
  else if $\mathit{Color}(\mathit{Chair}, c) \wedge \mathit{Color}(\mathit{can}, c)$ then
    $\textsc{Paint}(\mathit{Table}, \mathit{can})$
  else
    $\textsc{Paint}(\mathit{Chair}, \mathit{Can}_1)$; $\textsc{Paint}(\mathit{Table}, \mathit{Can}_1)$ // fall back to coercion
```

At execution, the agent maintains its belief state as a formula and evaluates each
branch condition by testing whether the belief state entails the condition or its
negation. The condition variables are existentially quantified — "if there exists a
color $c$ shared by table and chair, do nothing." Computing the belief state after an
action _and_ a percept is done in two stages: first update for the action,
$\hat{b} = (b - \textsc{Del}(a)) \cup \textsc{Add}(a)$, then fold in the percept
literals. Contingent plans are generated by an extension of the **and–or** forward
search over belief states: the agent's own action choices are OR-nodes, and the
possible percepts are AND-nodes, since a valid plan must handle every observation.

$$
% caption: An and-or plan tree for the painting problem. The agent chooses actions
% at OR-nodes; the environment reveals a percept at AND-nodes (arc), so a solution
% must contain a branch for every possible observation.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  n/.style={draw, minimum width=17mm, minimum height=7mm, align=center, font=\scriptsize},
  leaf/.style={draw, minimum width=14mm, minimum height=6.5mm, align=center, font=\scriptsize}]
  \definecolor{acc}{HTML}{2348F2}
  \node[n, draw=acc, text=acc] (root) at (0,2.8) {LookAt};
  \node[n] (obs) at (0,1.4) {observe color};
  \draw[->, acc, thick] (root) -- (obs);
  % three percept branches (AND) under obs
  \node[leaf] (b1) at (-4.2,-0.6) {NoOp};
  \node[leaf] (b2) at (0,-0.6)    {Paint Chair};
  \node[leaf] (b3) at (4.2,-0.6)  {coerce both};
  \draw[->, black] (obs) -- (b1);
  \draw[->, black] (obs) -- (b2);
  \draw[->, black] (obs) -- (b3);
  % AND arc across the three edges, sitting below obs
  \draw[black] (-1.5,0.35) to[bend right=18] (1.5,0.35);
  \node[font=\scriptsize, anchor=south, black] at (0.75,0.55) {AND};
  % labels on branches, placed outside the edges
  \node[font=\scriptsize, anchor=east] at (-2.9,0.55) {match};
  \node[font=\scriptsize, anchor=west] at (0.25,0.15) {can matches};
  \node[font=\scriptsize, anchor=west] at (2.9,0.55) {none match};
\end{tikzpicture}
$$

### Online replanning and execution monitoring

Watch a spot-welding robot in a car plant: its fast, repeated motions look
impressive but not _intelligent_, because they are a fixed program. Now suppose a
door falls off just as the robot is about to weld. If it swaps in a gripper, picks up
the door, checks it, reattaches it, emails the supervisor, and resumes welding, the
behavior suddenly looks _purposive_ — because it comes not from a giant precomputed
contingent plan but from **online replanning**: the robot knows what it is trying to
do and recovers when reality diverges.

Replanning presupposes **execution monitoring** to detect the need for a new plan.
The online agent has three levels of vigilance:

- **Action monitoring**: before each action, verify its preconditions still hold.
- **Plan monitoring**: before each action, verify the entire remaining plan will
  still succeed.
- **Goal monitoring**: before each action, check whether a better set of goals is
  available.

$$
% caption: The plan-monitor-replan loop, after Figure 11.9. The agent executes the
% $\mathit{wholeplan}$ from $S$ toward $G$; after some steps it expects state $E$ but
% observes $O$. It replans a minimal repair from $O$ to some point $P$ on the plan,
% then continues from $P$ to $G$.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  st/.style={circle, draw, minimum size=8mm, inner sep=0pt, font=\scriptsize}]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  \node[st] (s) at (0,0)     {S};
  \node[st] (p) at (2.6,0)   {P};
  \node[st] (e) at (5.2,0)   {E};
  \node[st] (g) at (7.8,0)   {G};
  \node[st] (o) at (2.6,-2.1) {O};
  % whole plan path
  \draw[->, black] (s) -- (p);
  \draw[->, black] (p) -- (e);
  \draw[->, dashed, black] (e) -- (g) node[midway, above, font=\scriptsize] {continuation};
  % expected vs observed
  \node[font=\scriptsize, anchor=south, black] at (3.9,0.15) {expected};
  % observed drop to O
  \draw[->, red, thick] (e) -- (o) node[midway, right, font=\scriptsize] {observe O};
  % repair from O back to P
  \draw[->, acc, thick] (o) to[bend right=22] (p) node[midway, below left, font=\scriptsize] {repair};
  \node[font=\scriptsize, anchor=south] at (1.3,0.15) {whole plan};
\end{tikzpicture}
$$

In action monitoring the agent keeps its original $\mathit{wholeplan}$ and the
unexecuted remainder $\mathit{plan}$. After a few steps it expects state $E$ but
observes $O$. It then finds a point $P$ on the original plan it can get back to
(possibly $P = G$), and repairs the plan to minimize the total cost of the repair
(from $O$ to $P$) plus the continuation (from $P$ to $G$). The repair-execute loop
runs until the goal is perceived to hold, which is what handles a **missing
precondition** (removing a lid needs a screwdriver), a **missing effect** (paint gets
on the floor), a **missing state variable** (the amount of paint left in a can), or
an **exogenous event** (someone knocks over the can).

These four failure modes are worth separating because they demand different repairs
and different model fixes. A **missing precondition** is a fact the action needed but
the model never listed; the plan can still be salvaged by inserting the achiever the
model omitted (fetch the screwdriver, then remove the lid). A **missing effect** is a
consequence the action had but the model did not predict; the belief state diverges
from reality until a percept catches it, and the repair re-achieves whatever the stray
effect undid. A **missing state variable** is a quantity the model never tracked at
all — the paint level — so the failure is invisible to action monitoring, which only
checks the fluents the schema mentions, and surfaces only when a downstream action
runs dry. An **exogenous event** is a change no action of the agent caused; here the
plan was correct and reality moved under it, so the repair simply re-establishes the
disturbed condition. The first three are model defects that the same repair loop can
mask indefinitely but that a **learned** correction would eliminate at the source; the
fourth is a genuine property of an open environment that no model can preclude.

$$
% caption: Four execution-monitoring failure modes and their repairs. The first three
% are gaps in the world model (a fact, a consequence, or a quantity the schema never
% named); the fourth is a change no agent action caused. Action monitoring alone
% cannot see a missing state variable, because it only checks fluents the schema
% mentions.
\begin{tikzpicture}[font=\footnotesize,
  cell/.style={draw, minimum width=38mm, minimum height=13mm, align=center, font=\scriptsize}]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  \definecolor{tintb}{HTML}{DDE3FE}
  \definecolor{tintr}{HTML}{F7E1DD}
  \node[cell, fill=tintb, draw=acc] (a) at (0,1.5)   {missing precondition\\insert the omitted achiever};
  \node[cell, fill=tintb, draw=acc] (b) at (4.6,1.5) {missing ef\/fect\\re-achieve what it undid};
  \node[cell, fill=tintb, draw=acc] (c) at (0,0)     {missing state variable\\unseen until it runs dry};
  \node[cell, fill=tintr, draw=red] (d) at (4.6,0)   {exogenous event\\re-establish the condition};
  \node[anchor=east, font=\scriptsize, acc] at (-2.05,1.5) {model gap:};
  \node[anchor=east, font=\scriptsize, red] at (-2.05,0)   {world moved:};
\end{tikzpicture}
$$

Plan monitoring is smarter than action monitoring: it checks the preconditions for
success of the _entire_ remaining plan (except those achieved by later steps), so it
aborts a doomed plan as early as possible instead of executing until failure
occurs. It also allows **serendipity** — if someone else happens to
achieve the goal, the agent notices and stops early. Does this loop guarantee
success? Only under two conditions: no dead ends (there is always a plan to the goal
from any reachable state) and genuine nondeterminism (every attempt has _some_ chance
of success). When failures actually stem from a hidden precondition the agent does
not model, the better long-term fix is to _learn_ a corrected model — every
prediction failure is an opportunity to update the world model, covered in
[learning from examples](/artificial-intelligence/learning/learning-from-examples).

## Multiagent planning

The last assumption to drop is that the agent is alone. When other agents share the
environment, each faces a **multiagent planning problem**: achieve its own goals with
the help or hindrance of others. Between the pure single-agent case and the truly
multiagent case lies a spectrum of decompositions of the "monolithic" agent:

- **Multieffector planning**: one agent with several effectors that act concurrently
  (a person who types and speaks at once), managing interactions among them.
- **Multibody planning**: the effectors are physically separate bodies (a fleet of
  robots), but their sensor data is pooled into a common world estimate, so they act
  as a single agent. When communication makes pooling impossible, this becomes
  **decentralized planning** — centralized planning phase, partly decoupled execution.
- **True multiagent planning**: distinct agents that each do their own planning and
  may have _identical_ goals (doubles tennis partners) or _opposing_ goals (the two
  teams), the latter reducing to the zero-sum situation of
  [adversarial search](/artificial-intelligence/search/adversarial-search).

$$
% caption: The spectrum of multiagent settings, from one agent with many effectors
% to distinct agents with their own plans. Coupling between subplans is what makes
% each step harder.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  box/.style={draw, minimum width=28mm, minimum height=13mm, align=center, font=\scriptsize}]
  \definecolor{acc}{HTML}{2348F2}
  \node[box] (a) at (0,0)    {multi-ef{}fector\\one agent,\\many ef{}fectors};
  \node[box] (b) at (3.8,0)  {multibody\\pooled sensing,\\one plan};
  \node[box] (c) at (7.6,0)  {decentralized\\separate execution};
  \node[box, draw=acc, text=acc, thick] (d) at (11.4,0) {multiagent\\own plans,\\coordination};
  \draw[->, acc, thick] (a) -- (b);
  \draw[->, acc, thick] (b) -- (c);
  \draw[->, acc, thick] (c) -- (d);
\end{tikzpicture}
$$

The distinction among the first three is about where the coupling sits, not about how
many physical parts move. A **multieffector** agent is one control locus commanding
several effectors that must not step on each other: a humanoid that types with its
hands while speaking has one planner reconciling two effector streams, and the
interactions (a hand cannot both type and gesture at once) are resolved inside that
single plan. A **multibody** agent spreads its effectors across separate bodies but
keeps one brain: a warehouse fleet whose robots stream their sensor readings to a
common estimator plans as though it were a single agent with many arms, because the
pooled world model removes any uncertainty about what the other bodies see or intend.
The distinction turns on communication. When bandwidth or reliability forbids pooling every
percept, the bodies can no longer share one live world estimate; **decentralized
planning** keeps the planning phase centralized (a single joint plan is computed
offline) but lets each body execute its share against its own local view, tolerating
the drift that pooling would have prevented. Only in **true multiagent planning** does
each agent run its own planner, which is why coordination becomes a problem the agents
themselves must solve rather than a constraint a single planner enforces.

### Planning with multiple simultaneous actions

Treat all these settings generically as **multiactor** settings, with **actor**
covering effectors, bodies, and agents. For $n$ actors the single action $a$ becomes
a **joint action** $\langle a_1, \ldots, a_n \rangle$, one $a_i$ per actor. Two
problems appear at once: the transition model must describe $b^n$ joint actions, and
the joint planning problem has branching factor $b^n$. Assuming perfect
**synchronization** (each action takes the same time, and simultaneous actions are
simultaneous), the research focus has been to _decouple_ the actors so complexity
grows linearly in $n$ rather than exponentially. When the actors are **loosely
coupled** — mostly independent, interacting only occasionally — the standard trick is
to pretend they are fully decoupled and then fix up the interactions.

The doubles-tennis problem shows how. Two actors $A$ and $B$ share the goal of
returning the ball and keeping the net covered. Write the schemas as if the actors
acted independently; then one obvious joint plan is $A: [\mathit{Go}(\mathit{A},
\mathit{RightBaseline}), \mathit{Hit}(\mathit{A}, \mathit{Ball})]$ and $B:
[\mathit{NoOp}, \mathit{NoOp}]$. The problem appears when a plan has _both_ actors
hitting the ball at once: the schema says the ball is returned, but in reality two
simultaneous hits fail. Preconditions constrain the _state_ an action runs in, not
what other actions run alongside it. The fix is a **concurrent action list** on the
schema stating which actions must or must not run concurrently — "$\mathit{Hit}$
returns the ball only if no other $\mathit{Hit}$ occurs at the same time." In the
SatPlan approach this is a partial **action exclusion axiom**. Some effects require
concurrency instead: two actors are needed to carry a full cooler, so
$\mathit{Carry}$'s concurrent list _demands_ a matching $\mathit{Carry}$ by the other
actor.

Concretely, augment the $\mathit{Hit}$ schema with a concurrent list that forbids a
simultaneous hit, and the $\mathit{Carry}$ schema with one that requires a
simultaneous carry:

```algorithm
caption: Two concurrent-action lists on the doubles-team schemas, after §11.4.1
$\textsc{Action}(\textsc{Hit}(\mathit{actor}, \mathit{Ball}))$
  $\textsc{Concurrent}$: for all $\mathit{other} \neq \mathit{actor}$, $\neg \textsc{Hit}(\mathit{other}, \mathit{Ball})$ // no other hit at the same instant
  $\textsc{Precond}$: $\textsc{Approaching}(\mathit{Ball}, \mathit{loc}) \wedge \textsc{At}(\mathit{actor}, \mathit{loc})$
  $\textsc{Effect}$: $\textsc{Returned}(\mathit{Ball})$
$\textsc{Action}(\textsc{Carry}(\mathit{actor}, \mathit{Cooler}, \mathit{to}))$
  $\textsc{Concurrent}$: exists $\mathit{other} \neq \mathit{actor}$ with $\textsc{Carry}(\mathit{other}, \mathit{Cooler}, \mathit{to})$ // a partner must lift too
  $\textsc{Effect}$: $\textsc{At}(\mathit{Cooler}, \mathit{to})$
```

Now a joint action $\langle \textsc{Hit}(A, \mathit{Ball}), \textsc{Hit}(B,
\mathit{Ball}) \rangle$ is rejected before it is ever costed, because each component's
concurrent list is violated by the other; the planner is forced toward a joint action
in which exactly one partner hits, such as $\langle \textsc{Hit}(A, \mathit{Ball}),
\textsc{NoOp}(B) \rangle$. The cooler's list works the other way: a lone $\langle
\textsc{Carry}(A, \mathit{Cooler}, \mathit{Van}), \textsc{NoOp}(B) \rangle$ is
rejected because $A$'s concurrent list has no matching carry, so only the joint lift
$\langle \textsc{Carry}(A, \mathit{Cooler}, \mathit{Van}), \textsc{Carry}(B,
\mathit{Cooler}, \mathit{Van}) \rangle$ produces the effect.

### Cooperation and coordination

In the true multiagent setting each agent makes its own plan, and even with shared
goals and a shared knowledge base, more than one joint solution can exist. For the
doubles team, both of these work:

- **Plan 1** — $A: [\mathit{Go}(\mathit{A}, \mathit{RightBaseline}),
  \mathit{Hit}(\mathit{A}, \mathit{Ball})]$, $B: [\mathit{NoOp}, \mathit{NoOp}]$.
- **Plan 2** — $A: [\mathit{Go}(\mathit{A}, \mathit{LeftNet}), \mathit{NoOp}]$, $B:
  [\mathit{Go}(\mathit{B}, \mathit{RightBaseline}), \mathit{Hit}(\mathit{B},
  \mathit{Ball})]$.

If both agents pick plan 1, or both pick plan 2, the goal is met. But if $A$ chooses
plan 2 while $B$ chooses plan 1, nobody returns the ball; if $A$ chooses 1 and $B$
chooses 2, both lunge for it. This is the **coordination** problem: agreeing on a
joint plan when several exist.

$$
% caption: The doubles-tennis coordination matrix. The goal is met only on the
% diagonal, where both partners commit to the same joint plan. A convention or an
% act of communication is what selects the shared plan.
\begin{tikzpicture}[>=stealth, font=\footnotesize]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  \definecolor{tintb}{HTML}{DDE3FE}
  \definecolor{tintr}{HTML}{F7E1DD}
  % column headers (B)
  \node[font=\scriptsize] at (1.2,2.7) {B: plan 1};
  \node[font=\scriptsize] at (3.6,2.7) {B: plan 2};
  % row headers (A)
  \node[font=\scriptsize, anchor=east] at (-0.15,1.8) {A: plan 1};
  \node[font=\scriptsize, anchor=east] at (-0.15,0.6) {A: plan 2};
  % cells
  \draw[fill=tintb, draw=acc] (0.2,1.2) rectangle (2.2,2.4);  \node[acc] at (1.2,1.8) {ok};
  \draw[fill=tintr, draw=red] (2.6,1.2) rectangle (4.6,2.4); \node[red, font=\scriptsize] at (3.6,1.8) {both hit};
  \draw[fill=tintr, draw=red] (0.2,0.0) rectangle (2.2,1.2); \node[red, font=\scriptsize] at (1.2,0.6) {nobody};
  \draw[fill=tintb, draw=acc] (2.6,0.0) rectangle (4.6,1.2);  \node[acc] at (3.6,0.6) {ok};
\end{tikzpicture}
$$

Several mechanisms select a shared plan. A **convention** is any constraint on the
choice of joint plans agreed in advance: "stick to your side of the court" rules out
plan 1, so both partners pick plan 2. Driving on a fixed side of the road is a
convention; when conventions become widespread they are **social laws**. Without a
convention, agents can use **communication** to reach common knowledge of a feasible
joint plan — a tennis player shouting "Mine!" or "Yours!" But communication need not
be verbal: one player can signal a preferred plan simply by _executing its first
part_. If $A$ heads for the net, $B$ is obliged to go to the baseline, because plan 2
is the only joint plan that begins with $A$ heading for the net. This is **plan
recognition**, and it works with competitive agents as well as cooperative ones.

Conventions can also arise without any planning at all, through evolution. Seed-eating
harvester ants execute elaborate joint plans with no centralized control and almost
no per-ant computation, each ant choosing a role from local conditions. Flocking
birds behave similarly: each **boid** watches its nearest neighbors and picks a
heading that balances cohesion (move toward the neighbors' average position),
separation (avoid crowding any one neighbor), and alignment (match the neighbors'
average heading). No boid holds a joint plan modeling the others, yet the flock shows
the **emergent behavior** of a coherent, density-preserving body. The hardest
multiagent problems mix cooperation within a team and competition against an opposing
team, all without centralized control — robotic soccer is the canonical example, and
efficient planning there is still in its infancy.

## From these extensions to deployed planners

The extensions in this chapter became the working parts of deployed planners; three
published systems mark the milestones.

Temporal planning got a standard interface when Fox and Long defined **PDDL2.1**, the
language of the 3rd International Planning Competition (Fox and Long, _Journal of
Artificial Intelligence Research_, 2003). PDDL2.1 added **durative actions** with
start, end, and over-all conditions, and numeric fluents for consumable and
producible resources — the same time-and-resource structure §11.1 introduces, given a
precise syntax and formal semantics that competing planners could all target.

The clearest deployment of onboard replanning was NASA's **Remote Agent**, which ran
as the flight-control software of the Deep Space 1 probe for a period in 1999
(Muscettola, Nayak, Pell, and Williams, _Artificial Intelligence_, 1998). It combined
a temporal-constraint planner and scheduler with a model-based executive that
monitored execution and reformulated plans in response to faults, demonstrating the
plan-monitor-replan loop of §11.3.3 on a spacecraft rather than in simulation.

For the multiagent case, Sharon, Stern, Felner, and Sturtevant introduced
**conflict-based search** (CBS) for multi-agent path finding (_Artificial
Intelligence_, 2015). CBS plans each agent's path independently, detects a conflict
where two paths collide in space and time, and branches by adding a constraint that
forbids one agent from that cell at that instant — a two-level search that resolves
interactions after the fact, exactly the loosely-coupled "pretend decoupled, then fix
up" strategy of §11.4.1, made into a complete and optimal algorithm.

$$
% caption: Three public milestones aligned to the chapter's four extensions. PDDL2.1
% (2003) formalized durative actions for §11.1; the Remote Agent (1998, flown 1999)
% demonstrated onboard replanning for §11.3; conflict-based search (2015) resolves
% multi-agent path conflicts for §11.4.
\begin{tikzpicture}[font=\footnotesize,
  ext/.style={draw, minimum width=30mm, minimum height=9mm, align=center, font=\scriptsize},
  work/.style={draw, minimum width=34mm, minimum height=11mm, align=center, font=\scriptsize}]
  \definecolor{acc}{HTML}{2348F2}
  \node[ext] (t1) at (0,2.0)  {time and resources};
  \node[ext] (t2) at (0,0.5)  {nondeterminism};
  \node[ext] (t3) at (0,-1.0) {other agents};
  \node[work, draw=acc, text=acc] (w1) at (5.6,2.0)  {PDDL2.1 durative actions\\Fox and Long, 2003};
  \node[work, draw=acc, text=acc] (w2) at (5.6,0.5)  {Remote Agent, DS1\\Muscettola et al., 1998};
  \node[work, draw=acc, text=acc] (w3) at (5.6,-1.0) {con\/f\/lict-based search\\Sharon et al., 2015};
  \draw[->, acc, thick] (t1) -- (w1);
  \draw[->, acc, thick] (t2) -- (w2);
  \draw[->, acc, thick] (t3) -- (w3);
\end{tikzpicture}
$$

## Where this leaves us

Across both parts, each step removed one assumption of classical planning.
Durations and resources turned a plan into a _schedule_; hierarchy let a planner
reason at multiple levels. This part removed the last two assumptions. Nondeterminism and
partial observability push the agent into belief-state space, where it either
coerces its way to the goal blind (sensorless), branches on what it sees
(contingent), or monitors and repairs on the fly (online). And other agents force
the questions of joint action and coordination.

This chapter still assumes the world is only _nondeterministic_ — outcomes are
possible or not, never weighted by probability. The next step is to attach
probabilities to outcomes and utilities to states, which is the subject of
[making decisions](/artificial-intelligence/uncertainty/making-decisions) and,
downstream, of learning to act from experience in
[reinforcement learning](/artificial-intelligence/learning/reinforcement-learning).