Constructing Belief Networks to Evaluate Plans

Paul E. Lehner, Chris Elsaesser, Scott A. MusmanUAI 1994

TL;DR

This paper introduces a method for constructing belief networks (PE-nets) to evaluate plans, particularly those with complex features like contingencies and overlapping actions. By systematically building these networks, the authors enable probabilistic reasoning about plan success, moving beyond reactive planning to proactive robustness assessment.

What Problem Does This Paper Address?

Traditional AI planning systems often operate on symbolic reasoning, which struggles to quantify uncertainty. While some systems can adapt to unexpected events, they lack the ability to provide a probabilistic estimate of future states or to deduce if a plan is robust against probable futures. This limitation means planners can only react to unforeseen circumstances rather than proactively design for them. The paper addresses this by proposing a way to build belief networks that can represent and reason about uncertainties within various types of plans, enabling a more quantitative evaluation of plan success.

Methods

The core method is the construction of "plan evaluation networks" (PE-nets) using belief networks. This involves:

  • Probabilistic Action and Persistence Models: These are the building blocks, essentially small belief networks that specify probability distributions for action outcomes (consequences) based on initial conditions (predecessors) and how states persist over time.
  • Sequential Pasting: PE-nets are built by sequentially "pasting" these action and persistence models onto a growing network. When pasting, conflicting information is resolved, and missing connections are filled in by working backward.
  • Handling Complicating Features: The paper details how to extend this basic approach to handle:
  • Partial Models: Using persistence models to fill in gaps where action models are underspecified, and a default "no change" persistence model when persistence is underspecified.
  • Derived Effects: Separating causal effects (across time) from derived effects (within a situation) to prevent issues where derived effects might incorrectly override action models. This is achieved by structuring predicates into primitive (causal) and derived (within-situation) levels.
  • Context-Dependent Effects: Iterating through possible node states to determine outcomes when action consequences depend on the situation.
  • Planned Contingencies: Merging contingent actions into a single node, conditioned on the factors that determine which action is executed.
  • Multiple Levels of Abstraction: Pasting probabilistic action models for operators at each level of abstraction.
  • Overlapping Actions: Arbitrarily selecting a linear ordering of situations and using "during conditions" and "during effects" to model actions that occur concurrently.
  • Specific Times and Durations: Introducing clock time predicates and modifying action models to account for temporal durations.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Belief Networks as a Formal Foundation: The paper strongly advocates for belief networks as a suitable formal framework for probabilistic plan evaluation, offering a way to move beyond purely symbolic reasoning.
  • Systematic Construction is Feasible: The authors demonstrate that automated procedures can be developed to construct these complex PE-nets, making the approach practical.
  • The Challenge of Derived Effects: A key insight is how derived effects, while intuitive, can lead to problematic interactions with action models if not carefully managed. The proposed primitive/derived predicate structure is a novel solution to this.
  • Handling Temporal Complexity: Overlapping actions and non-linear temporal ordering pose significant challenges. Splitting situations and introducing "relative end time" nodes are proposed as solutions to maintain temporal ordering in the PE-net.
  • Computational Complexity is a Major Concern: While PE-nets offer a powerful evaluation tool, the authors acknowledge that processing them can be computationally expensive, especially for non-linear plans, suggesting the need for approximate inference algorithms.

Key Results

The paper doesn't present quantitative results from running experiments on specific datasets. Instead, it focuses on demonstrating the methodology and feasibility of constructing PE-nets for increasingly complex plans. The key "result" is the proposed framework and the techniques for handling various complicating plan features, showing that it is possible to build belief networks that can represent these complexities.

Limitations and Future Work

  • Computational Complexity: The authors explicitly state that processing large PE-nets can be computationally expensive, suggesting that approximate algorithms (like Monte Carlo methods) are necessary for practical applications.
  • Exponential Growth of Node States: For linear plans, the number of node states can grow exponentially with plan length unless carefully managed (e.g., by defining an "OTHER" state).
  • Non-linear Plans: These are noted as being more problematic, leading to a rapid increase in the number of situations and predicates within the PE-net.
  • Future Work: The paper implies that further work is needed to refine the computational efficiency of processing these PE-nets and to explore the practical application of these methods in real-world planning systems. The authors also suggest that defining "OTHER" node states can mitigate state explosion issues.

Summary updated

BibTeX
@inproceedings{lehner1994constructing,
  author = {Paul E. Lehner and Chris Elsaesser and Scott A. Musman},
  title = {{Constructing Belief Networks to Evaluate Plans}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {1994},
}
Figure