Introduction
In the field of classical planning, a significant divide exists between satisficing planning—finding any valid sequence of actions to reach a goal—and optimal planning, which requires finding the shortest possible plan. While satisficing planners have achieved remarkable speeds, optimal planners frequently struggle with even seemingly simple problems.
Historically, theoretical work by Pohl, Gaschnig, and Pearl in the 1970s and 80s suggested that if a heuristic is "accurate enough," search algorithms like A should scale polynomially. However, in practice, optimal planners often fail on benchmark domains like GRIPPER or BLOCKSWORLD* that are theoretically straightforward. This research investigates whether this poor performance stems from inadequate heuristics or a fundamental limitation of heuristic search itself.
Defining the "Almost Perfect" Heuristic
To test the limits of search, the authors define an "almost perfect" heuristic as $h(s) = h^*(s) - c$, where $h^*(s)$ is the true optimal cost from state $s$ to the goal, and $c$ is a small, non-negative additive constant. For example, a heuristic with $c=1$ is always within one step of the optimal distance. This allows researchers to isolate the impact of minor heuristic inaccuracies on search complexity.
The Transposition Trap
A key finding of this work is that previous optimistic theories were built on the assumption that search spaces are trees with a single goal state and no "transpositions" (multiple paths to the same state). In reality, planning domains are dense graphs riddled with transpositions.
In these graph-based spaces, even a tiny heuristic error allows the search to "bleed" into massive subgraphs of near-optimal states. Because A* must explore all states where the estimated total cost $f(s)$ is less than the true optimal cost of the initial state, an admissible heuristic cannot prune these states unless it is perfectly accurate ($c=0$).
Case Study: The GRIPPER Domain
The GRIPPER domain involves a robot with two grippers moving balls between rooms. It is a classic example of a domain that is easy to solve but difficult to optimize.
The authors proved that for a task with $n$ balls, A with an error $c \ge 3$ expands essentially all reachable states. Even with a tiny error of $c=1$, the algorithm must expand roughly half the state space. This occurs because in GRIPPER, almost every reachable state lies on some* optimal path to the goal, making pruning nearly impossible for any imperfect admissible heuristic.
Case Study: The MICONIC Domain
The MICONIC domain models elevator scheduling, where passengers must be transported between floors.
Similar to GRIPPER, the search effort in MICONIC exhibits a sharp "phase transition." For an error $c \ge 4$, the number of expanded nodes becomes nearly equal to the total number of reachable states. The pruning power of A* effectively collapses once the heuristic error exceeds a very small threshold.
Key Insights and Empirical Results
Theoretical analysis was paired with empirical verification using benchmarks from the International Planning Competitions (IPC). The results confirmed that for domains like BLOCKSWORLD, even a "perfect minus 1" heuristic ($c=1$) leads to an exponential growth in expanded nodes, following a rate related to Bell numbers.
The study highlights a sobering reality: in many common planning domains, refining heuristic accuracy has diminishing returns. There is a "barrier" to scaling where search effort explodes at nearly the same rate as a blind search once a small error threshold is crossed.
Conclusion: Beyond Heuristics
The paper concludes that the "heuristic-only" approach to optimal planning has hit a theoretical and practical wall. To achieve better scalability, the planning community must focus on orthogonal enhancements that prune the search space in ways estimated costs cannot:
- Symmetry Reduction: Pruning the search by recognizing functionally identical objects (e.g., different balls in GRIPPER).
- Partial-Order Reduction: Limiting the exploration of different interleavings of independent actions.
- Problem Simplification: Reducing task complexity through pre-processing before the search begins.
Unless we can derive truly perfect heuristics, these structural techniques are essential for the future of optimal planning.
Summary updated