Theoretical Foundations for Abstraction-Based Probabilistic Planning

Vu A. Ha, Peter HaddawyUAI 1996

TL;DR

This paper introduces a novel theoretical framework for decision-theoretic planning under uncertainty, using "affine-operators" to represent and manipulate sets of probability distributions. This framework provides a unified way to define and reason about action abstraction, crucial for tackling complex planning problems.

What Problem Does This Paper Address?

Decision-theoretic planning (DTP) deals with making optimal decisions in environments where both the state of the world and the outcomes of actions are uncertain. Representing this uncertainty, typically with probability distributions, and finding optimal plans can become computationally intractable for real-world problems. Abstraction techniques are a common solution, simplifying the problem by operating on higher-level representations. However, a unified and theoretically grounded approach to action abstraction in DTP has been lacking. This paper aims to fill that gap by providing a formal framework that can accommodate and compare different abstraction methods.

Methods

The core of the paper is the introduction of the affine-operator. This operator is used to construct convex sets of probability distributions, which are then represented as affine-trees. These trees dynamically evolve as actions are projected.

  • Affine-Operators: These are functions that map vectors of probability distributions to new probability distributions. They are defined by an "affine-vector" and generalize concepts like convex hulls of probability distributions.
  • Affine-Trees: These are tree structures where branches are associated with intervals and leaves are associated with "worlds" (states, probability distributions, or sets of distributions). They provide a way to represent complex sets of probability distributions.
  • Action Representation: Primitive actions are defined as mappings from states to probability distributions, while abstract actions map worlds (sets of distributions) to worlds.
  • Projection Rules: The paper proposes three projection rules (PR1, PR2, PR3) for applying actions to affine-worlds. These rules differ in their precision and computational tractability, illustrating the precision-complexity tradeoff. PR3, in particular, is designed for practical use by producing looser but more manageable approximations.
  • Abstraction Procedures: The paper formalizes three types of action abstraction (intra-action, sequential-action, and inter-action) and shows how they can be correctly implemented within the affine-tree framework using lemmas like Branch-Merging and Star-Merging.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Unified Framework for Abstraction: The affine-operator and affine-tree representation provide a single, elegant framework to define and reason about various forms of action abstraction, unifying previous disparate approaches.
  • Precision-Complexity Tradeoff: The three projection rules explicitly demonstrate that achieving higher precision in representing the post-action world comes at a greater computational cost. This is a fundamental insight for designing practical planning systems.
  • Affine-Worlds as Convex Sets: The framework establishes that affine-worlds are inherently convex sets of probability distributions, which simplifies reasoning and computation, particularly for expected utility calculations.
  • Correctness of Abstraction: The paper provides formal proofs for the correctness of abstraction procedures with respect to specific projection rules, ensuring that abstractions do not lead to suboptimal plans when used correctly.

Key Results

  • Correctness Proofs: The paper proves the correctness of three projection rules (PR1, PR2, PR3) and formalizes three action abstraction procedures with respect to the Second Projection Rule (PR2).
  • Affine-Worlds Utility Theorem: This theorem shows that for affine-worlds, computing the expected utility interval is equivalent to computing the expected utility, simplifying a crucial operation in DTP.
  • Generalization of Belief Functions: Belief functions are shown to be a special case of affine-worlds, demonstrating the generality of the proposed framework.

Limitations and Future Work

  • Computational Complexity of Abstraction: While the paper provides a framework for abstraction, the problem of automatically generating abstraction hierarchies and estimating the loss of information due to abstraction remains a significant challenge.
  • Extreme Cases in Tree Flattening: The paper notes that flattening trees in extreme cases (like a path) does not incur information loss, but the general complexity of multi-level trees versus single-level stars is discussed.
  • Future Work: The authors highlight the need for further research into automatically generating abstraction hierarchies and estimating the loss of information due to abstraction. They also mention that the DRIPS planner has been implemented using these concepts and applied to real-world domains.

Summary updated

BibTeX
@inproceedings{ha1996theoretical,
  author = {Vu A. Ha and Peter Haddawy},
  title = {{Theoretical Foundations for Abstraction-Based Probabilistic Planning}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {1996},
}
Figure