Correlation Complexity of Classical Planning Domains

Jendrik Seipp, Florian Pommerening, Gabriele Röger, Malte Helmert

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.

The state space of the Gray Code task, illustrating a domain with a correlation complexity of 3.

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

Abstract

We analyze how complex a heuristic function must be to directly guide a state-space search algorithm towards the goal. As a case study, we examine functions that evaluate states with a weighted sum of state features. We measure the complexity of a domain by the complexity of the required features. We analyze conditions under which the search algorithm runs in polynomial time and show complexity results for several classical planning domains.
BibTeX
@inproceedings{seipp2016correlation,
  author = {Jendrik Seipp and Florian Pommerening and Gabriele Röger and Malte Helmert},
  title = {{Correlation Complexity of Classical Planning Domains}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2016},
}

Loading related content...

Figure