Optimal Limited Contingency Planning

Nicolas Meuleau, David E. SmithUAI 2003

TL;DR

This paper introduces "Optimal Limited Contingency Planning" (OKP), an algorithm that finds optimal plans with a limited number of decision branches, addressing the complexity of traditional Markov Decision Processes (MDPs). By framing the problem as a Partially Observable MDP (POMDP), OKP efficiently prunes the search space, offering a practical solution for domains like Mars rover planning where plan simplicity is crucial.

What Problem Does This Paper Address?

Traditional Markov Decision Processes (MDPs) offer a powerful framework for planning under uncertainty. The optimal policy in an MDP, especially over a finite horizon, can be represented as a "contingent plan" where decisions branch out based on possible future states. However, these plans can become incredibly large and complex, with a potentially massive number of branches. This complexity is a significant drawback in real-world applications.

Consider the example of planning for a Mars rover. While there's a lot of uncertainty (e.g., energy usage, position), the plans need to be:

  • Cognitively simple: Easy for humans to understand and modify.
  • Structurally simple: To allow for rapid and detailed analysis and simulation (e.g., of illumination, thermal characteristics).
  • Compact: Due to limited communication bandwidth and onboard storage.

This paper tackles the problem of finding optimal k-contingency plans, which are optimal plans containing at most k branching points. This is a harder problem than standard conformant planning (k=0) or finding the full optimal policy (k=∞) because it requires balancing optimality with structural constraints.

Methods

The core innovation of this paper is framing the limited contingency planning problem as a Partially Observable Markov Decision Process (POMDP). This allows them to leverage Bellman's optimality principle for dynamic programming, which is a standard technique for solving MDPs and POMDPs.

Here's how they adapt it:

  • POMDP Framework: They model the original problem as a POMDP, where the "state" includes not only the environment's state but also information about how many branching opportunities are left.
  • Layered POMDPs: For a k-contingency plan, they construct a series of POMDPs, denoted $M^0, M^1, \dots, M^k$.
  • $M^0$ represents conformant planning (no branches).
  • $M^1$ is built upon $M^0$ by adding an "observe-and-branch" action. This action allows for a single observation and then transitions to a state in $M^0$ with one fewer branching opportunity.
  • $M^i$ is built upon $M^{i-1}$ by adding observe-and-branch actions that allow for branching based on observations, consuming one of the k allowed branches.
  • Value Iteration (VI): They use value iteration to solve these layered POMDPs. The value function at level i ($V^i$) depends on the value function at level i-1 ($V^{i-1}$). This allows them to compute the optimal plan incrementally.
  • Belief States: The key insight is that the belief state (a probability distribution over the environment's states) in a POMDP is sufficient to represent the planning problem, even with limited branches. They extend this to include the number of remaining branches as part of the state.
  • Types of Plans: The paper discusses variants:
  • Balanced k-contingency planning: The simplest to implement, where each branch point can potentially lead to a full k-contingency plan.
  • Linear k-contingency planning: Branches only occur along a single main trajectory.
  • General k-contingency planning: The most flexible, with at most k branches anywhere in the plan.
  • Branch Conditions: They also explore how to adapt the algorithm for different branching rules, such as binary branching or threshold-based branching on numerical observations.

Datasets

Not discussed in the paper. The paper uses small, custom testbed problems for evaluation.

Key Insights and Ideas

  • POMDPs as a Unified Framework: The paper elegantly demonstrates that limited contingency planning, a seemingly distinct problem, can be effectively modeled and solved within the existing POMDP framework. This is a powerful unification.
  • Bellman's Principle for Pruning: The core advantage of OKP is its ability to prune the vast search space of possible contingent plans by leveraging Bellman's optimality principle. This is crucial for making the problem tractable.
  • Belief State Sufficiency: The paper highlights that the belief state, which captures uncertainty about the environment's state, is sufficient to guide optimal decision-making even when limiting the number of branches.
  • Trade-off Between Optimality and Complexity: OKP explicitly addresses the trade-off between finding a perfectly optimal plan (which might be too complex) and a simpler, yet still optimal (within the k-branch constraint), plan.
  • Incremental Solution: The layered POMDP approach allows for an incremental solution, where solving for k branches builds upon the solution for k-1 branches.

Key Results

The paper presents experimental results on two testbed problems: a variant of the tiger problem and a small maze world.

  • Tiger Problem:
    • OKP was able to find optimal contingent plans for different values of k and planning horizons (H).
  • Figures 2 and 3 show that as k increases, the value of the optimal plan generally increases (or stays the same), and the execution time of OKP also increases, but significantly less than brute-force plan enumeration.
  • The results demonstrate that OKP's pruning mechanism (Bellman's principle) is highly effective in reducing search complexity compared to brute-force enumeration.
  • Maze Problem:
    • Similar to the tiger problem, OKP showed significant advantages over brute-force enumeration in terms of execution time.
  • However, for very small planning horizons, brute-force enumeration was sometimes faster. This is attributed to the fact that for small horizons, the number of reachable states is much smaller than the total state space, making reachability analysis more efficient than OKP's exhaustive belief-state evaluation.
  • GRID-10x10 Problem:
    • Results here were consistent with the maze problem, showing that plan enumeration could be faster for small horizons. The authors suggest that combining reachability analysis with Bellman's optimality principle might yield the best algorithms.

Limitations and Future Work

  • Plan Extraction Complexity: For "balanced k-contingency planning," the plan extraction phase can be exponential in k. The authors note this is an artifact of that specific variant and not present in others.
  • Computational Cost: While OKP prunes the search space, it still computes optimal values for all belief states, which can be computationally intensive. The paper suggests that for specific applications where only a single initial belief state is of interest, combining OKP's approach with reachability analysis could be more efficient.
  • General POMDPs: Relaxing the assumption of observation probabilities depending only on the arrival state (i.e., $O(s', o)$ to $O(a, s', o)$) requires modifications to the state representation, potentially by including the last action executed.
  • Future Work: The authors suggest that their framework can be adapted to other variants of limited contingency planning and that combining their approach with reachability analysis could lead to even more efficient algorithms. They also point out that their work allows existing POMDP algorithms to be applied to limited contingency planning problems.

Summary updated

BibTeX
@inproceedings{meuleau2003optimal,
  author = {Nicolas Meuleau and David E. Smith},
  title = {{Optimal Limited Contingency Planning}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2003},
}
Figure