Abstract
This paper introduces correlation complexity, a metric quantifying the number of state variables that must be considered simultaneously to construct a heuristic function free of local minima. We demonstrate that several classic planning domains, including Blocksworld and Gripper, possess a correlation complexity of 2. This explains why simple search guidance often succeeds in these domains. Furthermore, we establish a complexity hierarchy by introducing a synthetic Gray Code task with a correlation complexity of 3.
Introduction
In classical planning, the efficiency of finding a sequence of actions to reach a goal depends heavily on the quality of the heuristic function. An ideal heuristic has no local minima, allowing simple hill-climbing algorithms to reach the goal in polynomial time. However, facts in complex domains are often interrelated, making it difficult to design such heuristics. This research addresses the question: how complex must a heuristic be to perfectly guide a search without getting stuck?
Defining Correlation Complexity
The authors utilize potential heuristics, which represent a state's value as a weighted sum of features. While standard potential heuristics typically consider individual facts (dimension $d=1$), this work generalizes to features that are conjunctions of up to $d$ facts.
Correlation complexity is defined as the minimum dimension $d$ required to produce a heuristic that is both descending (every solvable non-goal state has a successor with a lower value) and dead-end avoiding. A low, fixed correlation complexity implies that the domain can be solved efficiently if the correct weights are identified.
The "Power of Two" in IPC Domains
A significant finding of this study is that many benchmark domains from the International Planning Competition (IPC)—including Spanner, Gripper, VisitAll, and Blocksworld—have a correlation complexity of exactly 2. This suggests that even in seemingly complex problems like Blocksworld, considering pairs of facts is sufficient to eliminate local minima. This metric captures global constraints, such as the irreversible nature of the Spanner domain, which other measures like "Width" might overlook.
The Gray Code Task: A Hierarchy of Complexity
To prove that correlation complexity does not always collapse to 2, the authors constructed a synthetic Gray Code task. This task is specifically designed to require a correlation complexity of 3, demonstrating that a genuine hierarchy of complexity exists.
In the Gray Code task, the state space transitions follow a sequence where only one bit changes at a time. The interdependencies between the bits necessitate a higher-dimensional heuristic to guide the search effectively toward the goal state (100) from the initial state (000).
Conclusion
The introduction of correlation complexity provides a theoretical framework for understanding why certain "hard" planning problems are solvable with relatively simple heuristics. While the paper proves the existence of these low-dimensional heuristics, future work remains in developing algorithms to automatically discover optimal weights and exploring the metric's applicability across a broader range of planning benchmarks.
Summary updated