Operator Selection While Planning Under Uncertainty

Todd Michael Mansell, Grahame B. SmithUAI 1994

TL;DR

This paper introduces U-Plan, a novel planning system designed for uncertain environments. It tackles the challenge of creating robust plans by employing a "possible worlds" representation and a best-first search strategy guided by "expected fulfillment," a measure that balances probability and desirability. This approach allows U-Plan to generate adaptable "super-plans" that can handle a range of scenarios, making it particularly useful for time-critical applications like air combat.

What Problem Does This Paper Address?

Traditional AI planning systems often assume complete and accurate information about the environment and that the environment is static. These assumptions, while simplifying planning, make them ill-suited for real-world scenarios where information is often incomplete, uncertain, and the environment is dynamic. Devising useful plans in such situations requires a system that can reason effectively under uncertainty. The core challenge is to construct plans that are not only likely to succeed but also adaptable to various possible states of the world, even when those states are not precisely known. This paper addresses this by developing a planning framework that explicitly models and reasons about uncertainty.

Methods

U-Plan employs a hierarchical planning approach, breaking down complex goals into smaller subgoals. The system represents uncertainty using a "possible worlds" approach, where it constructs multiple potential initial states of the world, each associated with a degree of belief. The core of U-Plan's operator selection strategy is a best-first search guided by a quantitative measure called expected fulfillment (EF).

EF is calculated as the product of the probability of achieving a consequence and the degree of fulfillment that consequence provides. This metric allows U-Plan to prioritize actions that are both likely to succeed and contribute significantly to the overall goal.

Key methodological aspects include:

  • Abstraction Hierarchy: Plans are constructed in a hierarchy, starting with strategic decisions at higher levels and progressing to tactical details at lower levels. This allows for more manageable decision-making.
  • Possible Worlds Representation: U-Plan generates a set of possible world states, each with an associated belief measure, to represent uncertainty.
  • Expected Fulfillment (EF): This is the primary metric for guiding search and operator selection. It's calculated as $EF(a) = F(c) \times P(c|a, ps)$, where $F(c)$ is the degree of fulfillment of consequence $c$, and $P(c|a, ps)$ is the probability of achieving $c$ given action $a$ and the current possible world state $ps$.
  • Reviewing Selected Operators: U-Plan includes a mechanism to review and potentially revise earlier strategic decisions as more detailed information becomes available during planning. This helps to mitigate the optimistic nature of initial fulfillment estimates.
  • AND/OR Search Tree: The strategy hierarchy is represented as an AND/OR search tree, where AND nodes represent actions that must all be performed, and OR nodes represent choices between alternative actions.
  • Update Rules: Specific rules are defined for updating the EF values of parent nodes in the hierarchy based on the EF values of their children, differentiating between AND and OR node expansions.
  • Plan Reapplication and Super-Plans: U-Plan attempts to reuse existing plans for new scenarios and constructs a "super-plan" by merging plans for different possible worlds. This super-plan includes knowledge acquisition operators to decide between alternatives during execution.

Datasets

The paper mentions that the planning algorithm has been tested on an air combat domain. The specific details of this domain, including historical data for probability estimations, are described as being supplied at knowledge engineering. No explicit, publicly available dataset is listed or introduced.

Key Insights and Ideas

  • Expected Fulfillment as a Unified Metric: The concept of "expected fulfillment" is a crucial insight. It elegantly combines the probability of an action succeeding with the desirability of its outcome, providing a more robust criterion for decision-making under uncertainty than probability alone.
  • Hierarchical Planning with Uncertainty: U-Plan demonstrates a practical way to apply hierarchical planning to uncertain domains by using possible worlds and an abstraction hierarchy. This allows for strategic decisions to be made early, guiding more detailed tactical planning.
  • The Value of Reviewing Decisions: The inclusion of a mechanism to review and potentially revise earlier planning decisions is critical. It acknowledges that initial optimistic estimates of fulfillment can be misleading as more detailed information emerges, preventing the system from committing to suboptimal paths.
  • Super-Plans for Adaptability: The generation of "super-plans" by merging individual plans for different possible worlds is a significant contribution. This creates a single, overarching plan that is inherently more robust and adaptable to a wider range of environmental states.
  • Balancing Optimism and Caution: The update rules for AND nodes, particularly the use of the minimum fulfillment among children, highlight a deliberate choice towards a more cautious planning approach, ensuring that the overall plan's desirability is not overly optimistic.

Key Results

The paper presents U-Plan as an effective planning system, particularly demonstrated in the air combat domain. While specific quantitative results like success rates or plan generation times are not detailed with concrete numbers in this excerpt, the paper emphasizes:

  • U-Plan's ability to construct quantitatively ranked plans for uncertain environments.
  • Its effectiveness in generating multiple plans for multiple possible worlds.
  • The construction of a super-plan that merges these individual plans, offering a recommended course of action.
  • The system's ability to plan to acquire additional knowledge when beneficial.
  • The expected fulfillment calculation is presented as a reliable formula for operator selection.
  • The paper suggests that U-Plan produces a super-plan in less time than a traditional planner might take to produce one plan for every possible world.

Limitations and Future Work

  • Lack of Explanation: The authors note that "no explanation process currently exists in U-Plan." This means the system cannot currently explain why a particular decision was made, which is a significant limitation for user trust and understanding.
  • Optimistic Fulfillment Estimates: The paper acknowledges that the fulfillment component of EF is an optimistic assessment. While the review mechanism helps, it's an inherent challenge in planning under uncertainty.
  • Sensitivity Analysis: The paper discusses the importance of understanding the sensitivity of EF to errors in probability and fulfillment estimates. Figures 4 and 5 illustrate this, suggesting that further work could involve developing more sophisticated methods for handling such uncertainties and providing confidence measures.
  • Real-time Performance: The paper mentions that the plan produced is intended for post-mission analysis, not as a real-time planning aid, implying that current performance might not be sufficient for immediate, dynamic decision-making.
  • Future Work: The authors suggest that the sensitivity analysis data could be utilized in an extension to U-Plan that allows users to question decisions or produce confidence levels for operator selections. This directly addresses the lack of explanation.

Summary updated

BibTeX
@inproceedings{mansell1994operator,
  author = {Todd Michael Mansell and Grahame B. Smith},
  title = {{Operator Selection While Planning Under Uncertainty}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {1994},
}
Figure