Estimating Reaction Plan Size

Marcel SchoppersAAAI 1994

Abstract

This paper re-evaluates the complexity of "Universal Plans" in AI, challenging the long-held belief that pre-computed reactive plans are inherently too large for practical use. By accounting for state dependencies (fluents) and the compression power of dynamically bound object variables, the research demonstrates that plan sizes grow polynomially rather than exponentially, making reactive planning a viable approach for complex domains like robotics.

Introduction

In the late 1980s and early 1990s, a significant debate divided the AI community regarding the feasibility of "Universal Plans"—pre-computed responses for every possible state an agent might encounter. Critics, most notably Matthew Ginsberg, utilized Shannon’s circuit complexity theories to argue that a reaction plan for a domain with $n$ propositions would require approximately $O(2^n/4n)$ gates. For real-world problems, this estimate leads to numbers larger than the count of atoms in the universe, suggesting that reactive planning was a theoretical dead end. Marcel Schoppers addresses this critique by demonstrating that the mathematical models used to dismiss these plans were fundamentally mismatched with their actual construction.

Methods

Schoppers employs a two-pronged mathematical re-evaluation to correct these overestimations:

  1. Invalidating the Independence Assumption: Previous models assumed all Boolean propositions were independent. However, planning domains utilize "fluents"—constraints where, for example, a block can only be in one location at a time. This significantly reduces the number of reachable world states ($w$).
  2. Modeling Object Variables: The core contribution is a size estimate that incorporates variables. Instead of a plan requiring unique branches for every specific object (e.g., "If Block A is on Block B"), it uses generic branches (e.g., "If Block $X$ is on Block $Y$").
  3. Recurrence Relations: The author develops a formula to calculate the expected size of a decision tree based on the number of preconditions ($p$), variables ($v$), and possible bindings ($b$).

The Power of Variables

The "Aha!" moment of the research is the realization that variables act as a massive compression mechanism. A single subplan utilizing variables can replace thousands of grounded (specific) rules.

Comparison between a universal plan using variables (top left) and a grounded plan (bottom right).

Because world states are constrained by physics, the number of possible situations is much smaller than $2^n$. Shannon’s original estimate is deemed "generally worthless" for robotics because it ignores these dependencies. Furthermore, actual reaction plans are often recursive—such as a plan to clear a block calling a subplan to clear the block above it—which further minimizes the compiled size.

Key Results

The paper uses the Blocks World domain as its primary benchmark. While a standard formal environment rather than a modern dataset, it provides a rigorous test for planning complexity. The author compares theoretical estimates against actual compiled Universal Plans for versions ranging from 3 to 25 blocks.

Table 1: Comparison of plan size estimates across different models and actual compiled sizes for the Blocks World domain.

As shown in the table above, the results are striking:

  • Ginsberg’s Estimate: For a 25-block world, the old model predicted a plan size of $5.57 \times 10^{184}$ gates.
  • Improved Estimate (No Variables): Accounting for state dependencies alone still resulted in $0.58 \times 10^{26}$ gates.
  • Actual Plan Size (With Variables): The actual Universal Plan for 25 blocks requires only 7,225 nodes.

While previous estimates suggested exponential growth, Schoppers shows that for the Blocks World, actual Universal Plans grow at only $O(N^3)$.

Discussion and Limitations

While the results are promising, the author notes some limitations. The general formula is an approximation that tends to under-estimate size for small $N$ and over-estimate for very large $N$. Additionally, the analysis assumes a completely sensor-driven agent; the introduction of internal memory might alter complexity. While the $O(N^3)$ result is specific to the Blocks World, the "variable advantage" is expected to remain a universal principle in reducing plan complexity across various domains.

Summary updated

BibTeX
@inproceedings{schoppers1994estimating,
  author = {Marcel Schoppers},
  title = {{Estimating Reaction Plan Size}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1994},
}

Loading related content...

Figure