Planning Under Uncertainty

This builds on Planning and Acting 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, 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: $RemoveLid(can)$ opens a can, and $Paint(x,can)$ paints object $x$ with an open can. Partial observability forces one new wrinkle: the $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.

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 cColor(x,c)$. After Skolemizing, the initial belief state is $b_0=Color(x,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

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 }condition: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:

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-\text{Del}(a))\cup \text{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.

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.

In action monitoring the agent keeps its original $wholeplan$ and the unexecuted remainder $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.

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.

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.

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 $⟨a_1,\dots ,a_n⟩$, 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:[Go(A,RightBaseline),Hit(A,Ball)]$ and $B:[NoOp,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 — $Hit$ returns the ball only if no other $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 $Carry$'s concurrent list demands a matching $Carry$ by the other actor.

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

Now a joint action $⟨\text{Hit}(A,Ball),\text{Hit}(B,Ball)⟩$ 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 $⟨\text{Hit}(A,Ball),\text{NoOp}(B)⟩$. The cooler's list works the other way: a lone $⟨\text{Carry}(A,Cooler,Van),\text{NoOp}(B)⟩$ is rejected because $A$'s concurrent list has no matching carry, so only the joint lift $⟨\text{Carry}(A,Cooler,Van),\text{Carry}(B,Cooler,Van)⟩$ 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:[Go(A,RightBaseline),Hit(A,Ball)]$, $B:[NoOp,NoOp]$.
• Plan 2 — $A:[Go(A,LeftNet),NoOp]$, $B:[Go(B,RightBaseline),Hit(B,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.

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.

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 and, downstream, of learning to act from experience in reinforcement learning.