Correlation Complexity of Classical Planning Domains

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

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