Planning and Decision-Making Under Uncertainty

Classical planning's assumptions — full observability, determinism, a static world — break down the moment an agent cannot be certain what state it is in or what a given action will actually do. One response, conformant (or sensorless) planning, forgoes sensing altogether and seeks a single action sequence that achieves the goal regardless of which of several possible initial states or outcomes actually occurred, reasoning instead over a belief state — the set of all states consistent with what the agent has assumed or is told, rather than a single known state. Instead of tracking one world state, a conformant planner tracks how an entire set of possible states evolves together under each action, and it only declares success when every state in that set has reached the goal. This is workable only when the uncertainty is limited enough that some single sequence of actions is robust to every possibility; if the uncertainty is too broad, no conformant plan may exist at all, even though the goal is trivially reachable once sensing is allowed.

When the agent can sense information at execution time, contingent planning instead produces a branching plan: rather than one fixed sequence, the plan specifies different continuations depending on what the agent actually perceives once it acts. Consider a simplified vacuum-world robot uncertain whether a particular room contains dirt: a contingent plan might specify 'move to the room, then sense; if dirt is detected, suck; otherwise, move on to the next room' — the plan branches on the percept rather than committing in advance to sucking or not sucking, and it can be executed correctly no matter which of the two possibilities turns out to be true. Formally, this means the plan is a tree or graph over belief states, where sensing actions split a belief state into the narrower belief states consistent with each possible percept, and the plan specifies what to do in every branch that might be reached, so that following the tree from the root to any leaf always yields a sequence of actions that achieves the goal under the assumptions that hold along that particular branch.

This branching structure is more expressive than either the classical single-sequence plan or the ambitious sensorless conformant plan, capturing what most competent real-world plans actually need: a policy that adapts to a small number of foreseeable percepts rather than a single guess that must work no matter what is actually true. The cost of this added expressiveness is combinatorial: a contingent plan must specify a correct continuation for every combination of possible percepts the agent might encounter along the way, so the size of the plan can grow quickly as the number of sensing points and possible percepts at each point increases, which is why contingent planning is generally reserved for problems where uncertainty is concentrated at a small, identifiable number of decision points rather than pervasive throughout. Choosing among conformant, contingent, and (as the next lesson introduces) fully probabilistic representations is therefore itself a planning decision, driven by how much uncertainty the domain actually contains, how reliably the agent can sense to resolve it, and how much branching the resulting plan can afford to carry.

When action outcomes are genuinely stochastic rather than merely unknown-but-fixed, a further shift in representation helps: framing the problem as a Markov Decision Process (MDP), defined by a set of states, a set of actions, a transition function giving the probability of reaching each next state given the current state and chosen action, and a reward function assigning value to states or state-action pairs, under the Markov property that the outcome of an action depends only on the current state, not on the history of how the agent arrived there. This reframing changes what a 'solution' even means: rather than a single sequence of actions or even a branching contingent plan tied to specific anticipated percepts, an MDP's solution is a policy — a mapping from every state to the action to take there — because in a stochastic world, the agent may revisit similar situations repeatedly and needs a general rule rather than a one-off sequence.

Standard dynamic-programming methods compute an optimal policy from an MDP's transition and reward functions: value iteration repeatedly updates an estimate of each state's long-run expected value by looking one step ahead at the expected reward plus the discounted value of successor states under the best available action, sweeping over every state and repeating the update until the values stop changing appreciably. These estimates provably converge to the true optimal values as the updates repeat, at which point the greedy action with respect to those converged values at each state constitutes an optimal policy — an action selection rule that is simultaneously correct for every state the agent could ever find itself in, not just the states along one anticipated trajectory. This differs fundamentally from classical planning's search for a single satisfying path from a known start to a known goal, since an MDP-based planner is instead solving for value across the entire state space simultaneously, in order to be prepared for whatever state the stochastic transitions actually produce, even states the agent never expected to visit.

MDPs give planning-under-uncertainty a mathematically precise objective — maximizing expected cumulative (typically discounted) reward — where classical planning had only a binary notion of a plan succeeding or failing outright. This precision lets a policy be meaningfully described as 'better' or 'worse' rather than simply valid or invalid, and lets the planner trade off, for instance, a risky short path against a safer longer one according to how the reward function actually weighs the outcomes — a distinction with no real counterpart in classical planning, where any plan reaching the goal counts as equally successful regardless of the risk it carried along the way. The discount factor typically applied to future rewards also gives the planner a principled way to prefer reaching a goal sooner rather than later when both are otherwise equally achievable, rather than treating all successful plans as interchangeable. This reward-based framing is also what connects planning under uncertainty to reinforcement learning: whereas an MDP-based planner computes a policy from a fully specified transition and reward model, a reinforcement-learning agent facing the same kind of stochastic environment must instead learn an equally good policy from experience, when the transition or reward function is not known in advance.

MDPs still assume the agent always knows its current state exactly; when observations are also uncertain or incomplete, the natural extension is the Partially Observable Markov Decision Process (POMDP), which adds an observation function describing the (possibly noisy or incomplete) percept the agent receives after each transition, rather than direct access to the true underlying state. Because the true state is no longer directly known, the agent must instead track a belief state — a probability distribution over possible underlying states, updated after each action and observation using the transition and observation functions together — and a POMDP policy maps belief states, rather than raw states, to actions, since the belief state is the most complete summary of the agent's situation actually available to it. Exact POMDP solution methods represent policies through structures such as alpha vectors over the belief simplex, though because belief space is continuous (a probability distribution over states, rather than a single discrete state), exact solution is far more computationally expensive than for fully observable MDPs, motivating approximate and point-based methods, such as PBVI-style algorithms that evaluate policies only at a sampled set of representative belief points, for anything beyond small toy problems.

Even the best contingent or POMDP-derived plan can be executed against a world that behaves differently than the model predicted — an action might silently fail, an unmodeled obstacle might appear, or a sensor might return a misleading reading — so real deployed systems pair planning with execution monitoring, which checks at three distinct levels whether things are proceeding as expected. Action monitoring verifies, immediately after each step, that the just-executed action actually achieved its expected effect before the system moves on to the next step, catching low-level failures early. Plan monitoring checks, before continuing to execute later steps, whether the remaining portion of the plan is still expected to achieve the goal given everything that has actually happened so far, catching cases where earlier steps succeeded individually but left the world in a state the rest of the plan did not anticipate. Goal monitoring, operating at a still higher level, periodically checks whether some better opportunity has arisen that would justify abandoning the current goal altogether in favor of a more valuable one, which none of the lower monitoring levels are positioned to notice on their own.

When monitoring detects a discrepancy serious enough that the current plan is no longer expected to reach the goal, the system replans — invoking the planner again from the actual current state (or current belief state) rather than the originally assumed one, in effect treating the unexpected situation as a fresh planning problem rather than trying to patch the now-invalid original plan. This replanning loop is what lets contingent planning's branch-on-anticipated-percepts approach and probabilistic planning's policy-over-states approach both cope gracefully with genuine surprises that neither approach fully anticipated in advance, closing the gap between an idealized plan built from an inevitably imperfect model and the messiness of actual execution in the real world, where some divergence between model and reality is essentially guaranteed over a long enough horizon. In the delivery-robot scenario, this means a plan built around the assumption that a hallway is passable does not need to anticipate every possible obstruction in advance; it only needs monitoring vigilant enough to notice when that assumption fails, and a planner fast enough to produce a workable replacement plan before the delay becomes costly, which is a substantially easier engineering target than trying to enumerate every contingency ahead of time.