Contingent Planning

The defining feature of a contingent plan is its tree or graph structure, where nodes represent actions and branches represent possible observational outcomes. Unlike a linear sequence, execution follows a path determined by the real-world results of sensing actions (e.g., 'if the door is locked, then pick the lock; else, open the door'). This structure explicitly encodes disjunctive future possibilities into a single executable policy.

Contingent plans incorporate actions whose sole purpose is to gather information. These sensing actions or observation actions query the environment to resolve key uncertainties. The plan's subsequent branches are contingent on their outcomes. For example, a robot's plan might include 'check inventory level' as a sensing action, with one branch for 'level > threshold' and another for 'level <= threshold', each leading to different procurement actions.

Mathematically, a contingent plan is a policy (π) that maps an agent's belief state—a probability distribution over possible world states—to an action. In a Partially Observable Markov Decision Process (POMDP), an optimal policy is a contingent plan that maximizes expected cumulative reward. The policy specifies what to do for every possible belief state the agent might find itself in, making it a universal recipe for action under uncertainty.

It is critical to distinguish contingent planning from conformant planning. Both handle uncertainty, but their strategies differ:

• Contingent Plan: Uses sensing to reduce uncertainty during execution. It's a conditional tree.
• Conformant Plan: A single, linear action sequence guaranteed to work for all possible initial states consistent with the agent's ignorance. It avoids sensing and must be robust to all possibilities, often making it more costly or conservative.

Executing a contingent plan requires a runtime dispatch function. This component:

1. Monitors the environment after each action.
2. Evaluates the conditions at branch points based on observations.
3. Dispatches the correct next action or subtree. This closed-loop execution is what transforms a static plan tree into adaptive behavior. Failure of a branch may trigger replanning from the current belief state.

Generating optimal contingent plans is computationally challenging, often EXPTIME-complete or NEXPTIME-complete for expressive formalisms like POMDPs. The complexity stems from reasoning about the exponentially large space of possible belief states and observation histories. This necessitates approximate solvers like point-based value iteration for POMDPs or heuristic search in belief space. The trade-off is between plan optimality and generation time.

The foundational mathematical framework for contingent planning. A Partially Observable Markov Decision Process models sequential decision-making where the agent cannot directly perceive the true world state. Instead, it receives observations that provide probabilistic clues, forcing it to maintain a belief state—a probability distribution over possible states. Solving a POMDP yields an optimal policy mapping belief states to actions, which is the formal equivalent of a contingent plan.

The output of a contingent planner. A policy is a complete strategy that specifies which action to take in every possible situation the agent might encounter. In contingent planning, this is often represented as:

• A policy tree, where branches represent possible observations.
• A set of condition-action rules.
• A function mapping belief states to actions. Unlike a linear sequence of actions (a plan), a policy defines behavior for all potential futures, making it robust to uncertainty.

The core internal representation in partially observable environments. A belief state is a probability distribution over all possible world states, summarizing everything the agent knows given its action and observation history. Contingent planners and POMDP solvers reason directly over this space. Key operations include:

• Belief update: Using Bayes' rule to incorporate a new observation after taking an action.
• Belief space planning: Searching for policies in the (continuous) space of possible belief states.

A simpler special case of planning under uncertainty. Conformant planning generates a single, linear sequence of actions that is guaranteed to achieve the goal regardless of which initial state is true from a known set of possibilities, and without any sensory feedback during execution. It handles ignorance but not ongoing uncertainty. Contingent planning is more powerful, as it can leverage sensors to adapt, often yielding shorter and more efficient solutions.

The fully observable counterpart to the POMDP. A Markov Decision Process provides the foundation for planning under probabilistic outcomes but with full state observability. The agent always knows the exact current state. Solutions are policies mapping known states to actions. Contingent planning reduces to MDP planning if the observation function perfectly reveals the state. MDP algorithms like value iteration are often subcomponents of POMDP solvers.

A fundamental action type in contingent planning. A sensing action (or information-gathering action) is explicitly executed to reduce uncertainty. Its primary effect is to refine the agent's belief state by providing a new observation, rather than changing the physical world. Effective contingent plans strategically interleave sensing actions with physical actions to minimize cost and risk. Examples include a robot scanning a barcode or an API call to check a system's status.