An Average Case Analysis of Planning

Tom BylanderAAAI 1993

Abstract

While propositional STRIPS planning is PSPACE-complete in the worst case, this study demonstrates that most random instances are computationally tractable. By defining a mathematical model for random planning and deriving probabilistic bounds, the research identifies that planning is only "hard" within narrow parameter ranges. Simple, greedy algorithms are shown to solve the majority of instances as the number of operators scales, suggesting that worst-case complexity does not reflect typical performance in many environments.

Introduction

The computational complexity of general-purpose planning has long been a hurdle for AI research. Specifically, propositional STRIPS planning was proven to be PSPACE-complete, implying that any general planner might encounter exponential time requirements. However, empirical evidence often contradicted this theoretical gloom, as many planners performed efficiently on practical problems. This paper bridges the gap by asking: is planning hard on average? Inspired by phase transitions in SAT problems, the research identifies conditions where planning instances are likely to be "easy"—either trivially solvable or provably impossible.

The Random Planning Model

To analyze average-case behavior, the paper defines a model for random planning instances characterized by several parameters:

  • $n$ conditions: The total number of ground atoms.
  • $o$ operators: The number of available actions.
  • $r$ and $s$: The average number of preconditions and postconditions per operator, respectively.

In this model, each condition is equally likely to be a pre- or post-condition, independent of others. This allows for a formal probabilistic analysis of the likelihood that an operator can be applied or that it will contribute to a goal state.

Probabilistic foundations of the random planning model.

As shown in the figure above, the probability that a state satisfies an operator's preconditions is modeled as $(1 - r/2n)^n$. Similarly, the probability that an operator's postconditions are consistent with existing goals is $(1 - s/2n)^{g-d}$. These expressions form the basis for determining the success rates of various search algorithms.

Algorithmic Analysis

The study evaluates three "sound but incomplete" algorithms to test the limits of random planning:

  1. POSTS-COVER-GOALS: A simple check that returns "no plan exists" if any goal condition is not present in the postconditions of at least one operator.
  2. FORWARD-SEARCH: A greedy hill-climbing approach that applies an operator only if it increases the number of satisfied goals.
  3. BACKWARD-SEARCH: A regression-style search that works from the goals back toward the initial state.

Key Results and the Hardness Gap

The analysis reveals that planning difficulty follows a phase-transition pattern similar to NP-complete problems like 3-SAT.

  • Provable Unsolvability: If the number of operators $o$ is less than approximately $O(n/s)$, it is highly probable that at least one goal cannot be satisfied, making the problem trivially unsolvable.
  • Trivial Solvability: If $o$ is at least $\Omega(n \ln g)$, a simple greedy forward search is likely to find a plan. This suggests that "reactive" behavior is theoretically sound for a large subset of planning problems; if you have enough "tools" (operators), deep lookahead is often unnecessary.
  • The Hardness Gap: Between these two bounds lies a narrow region where the problem is likely "hard." In this zone, simple algorithms fail to either find a plan or prove its non-existence.

One of the most striking insights is that plan modification is significantly easier than generation. While scratch-planning might require $O(n \ln g)$ operators to be "easy," modifying a plan (when the initial state or goal changes by a single condition) only requires a linear number of operators $O(n)$.

Discussion and Limitations

The author acknowledges that the "independent and identically distributed" (i.i.d.) assumption for conditions is a simplification. Real-world domains like Blocks World exhibit high correlations between conditions (e.g., clear(A) is highly correlated with on(B, A)), which random models do not capture. Future work is suggested to tighten these mathematical bounds and explore more structured distributions to better reflect practical planning challenges. Despite these limitations, the paper provides a foundational theoretical basis for why many planners succeed despite discouraging worst-case complexity results.

Summary updated

BibTeX
@inproceedings{bylander1993average,
  author = {Tom Bylander},
  title = {{An Average Case Analysis of Planning}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1993},
}
Figure