A method for Planning Given Uncertain and Incomplete Information

Todd Michael MansellUAI 1993

TL;DR

This paper introduces U-Plan, a novel AI planning system designed to operate in environments characterized by uncertainty and incomplete information. U-Plan constructs "super-plans" by representing the world as a set of possible states at various abstraction levels, allowing for more efficient and adaptable planning than traditional methods.

What Problem Does This Paper Address?

Traditional AI planning systems often assume a complete and deterministic understanding of the world. However, real-world scenarios are rarely so straightforward. Agents often face situations where information about the environment is incomplete, uncertain, or dynamic. This paper tackles the challenge of creating AI plans that can effectively navigate these ambiguous conditions. The authors aim to bridge the gap between planning in perfectly known, static worlds and reactive decision-making in completely unknown, dynamic environments. Specifically, they want to develop plans that can adapt to uncertainty, potentially acquire new information when needed, and still achieve desired goals.

Methods

U-Plan employs a multi-faceted approach to address planning under uncertainty:

  • Possible Worlds Representation: Instead of a single world state, U-Plan represents the environment as a set of "possible states" (P-states). Each P-state is a complete description of one potential reality.
  • Hierarchical Abstraction: Each P-state is described at multiple levels of abstraction, from coarse strategic views to detailed tactical ones. This allows the planner to make high-level decisions first and then refine them into more specific actions.
  • Dempster-Shafer Theory: This theory is used to quantify uncertainty and incomplete information about the world. It allows for belief to be associated with propositions, explicitly capturing what is known and unknown.
  • Hierarchical Planning with Reduction Operators: U-Plan uses a strategy hierarchy, akin to a decision tree, where nodes represent subgoals. "Reduction operators" define how to achieve these subgoals, acting as actions that transition between abstraction levels or define tactical steps.
  • Expected Fulfilment for Operator Selection: Instead of just probability, U-Plan uses "expected fulfilment" to select operators. This metric considers both the operator's probability of success and how well it contributes to the parent goal, guiding the planning process towards more promising actions.
  • Plan Reapplication: A key innovation is U-Plan's ability to attempt to reuse parts of plans generated for one P-state in other P-states. This significantly reduces the need to generate entirely new plans for every possible world.
  • Super-Plans: U-Plan constructs a single "super-plan" by merging common sequences of actions from multiple individual plans. This super-plan incorporates knowledge acquisition operators at decision points, guiding the system on when and what information to gather to make the next strategic choice.

Datasets

The paper describes the system being tested using a simplified air combat domain. This domain serves as a benchmark for evaluating U-Plan's performance. No specific publicly available datasets are mentioned; the domain appears to be a custom-built scenario for the research.

Key Insights and Ideas

  • Abstraction is Key to Managing Uncertainty: By representing the world at multiple abstraction levels, U-Plan can make robust strategic decisions that remain relevant even as tactical details become clearer or change.
  • Reusing Plans is More Efficient: The ability to reapply existing plans to new, similar possible worlds dramatically reduces the planning effort compared to generating a unique plan for every conceivable state.
  • "Expected Fulfilment" is a Better Decision Metric: Simply relying on probability isn't enough. Considering how well an action contributes to the overall goal (expected fulfilment) leads to more effective operator selection.
  • Super-Plans Consolidate Knowledge: Merging plans into a single, branched super-plan with integrated knowledge acquisition steps provides a more compact and actionable representation of planning strategies.
  • Strategic Decisions First, Tactical Details Later: The hierarchical approach ensures that the overall strategy is sound before getting bogged down in low-level execution details, which is crucial in uncertain environments.

Key Results

The paper presents results from experiments in the air combat domain, comparing U-Plan to a control planner (C-Plan) that does not reapply plans or acquire knowledge.

  • Fewer Plans Generated: U-Plan produced substantially fewer plans than C-Plan, especially as the number of possible states increased. In some cases, U-Plan generated one plan per initial P-state, whereas C-Plan generated a plan for every P-state.
  • Efficiency Gains (with Heuristics): When heuristics were used to quickly evaluate plan reapplicability, U-Plan's CPU time closely shadowed C-Plan's. This suggests that U-Plan can achieve comparable performance to a classical planner while managing uncertainty more effectively.
  • Potential for Significant Speedup: The authors hypothesize that for problems with a large number of P-states, U-Plan's approach of managing a smaller set of plans would lead to significant benefits in system time compared to C-Plan's overhead.
  • Heuristics are Crucial for Reapplication: The efficiency of plan reapplication is heavily dependent on effective heuristics. Without them, the overhead of checking reapplicability can become a bottleneck.

Limitations and Future Work

  • Heuristic Dependency: The efficiency of U-Plan's plan reapplication relies heavily on the availability and effectiveness of heuristics. Developing good heuristics can be domain-specific and challenging.
  • Domain Dependence: The effectiveness of U-Plan's approach, particularly the number of plans generated and the success of reapplication, is influenced by the domain's characteristics. Domains requiring a unique plan for every possible world would be computationally more expensive.
  • Future Work: The authors suggest further exploration into selecting the best part of a partially applicable plan and the development of more sophisticated heuristics for plan reapplication. They also mention that the system is currently being applied to a fire hazard action response domain, indicating a direction for real-world application. The choice of Dempster-Shafer theory is noted as being flexible, with probability theory or fuzzy logic being potential alternatives.

Summary updated

BibTeX
@inproceedings{mansell1993method,
  author = {Todd Michael Mansell},
  title = {{A method for Planning Given Uncertain and Incomplete Information}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {1993},
}
Figure