ML Anthology

Correlation Complexity of Classical Planning Domains

Jendrik Seipp, Florian Pommerening, Gabriele Röger, Malte Helmert
IJCAI 2016 pp. 3242-3250
/ijcai/2016/seipp2016ijcai-correlation/

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. PDF

PDF IJCAI Semantic Scholar

Cite

Text

Seipp et al. "Correlation Complexity of Classical Planning Domains." International Joint Conference on Artificial Intelligence, 2016.

Markdown

[Seipp et al. "Correlation Complexity of Classical Planning Domains." International Joint Conference on Artificial Intelligence, 2016.](https://mlanthology.org/ijcai/2016/seipp2016ijcai-correlation/)

BibTeX

@inproceedings{seipp2016ijcai-correlation,
  title     = {{Correlation Complexity of Classical Planning Domains}},
  author    = {Seipp, Jendrik and Pommerening, Florian and Röger, Gabriele and Helmert, Malte},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year      = {2016},
  pages     = {3242-3250},
  url       = {https://mlanthology.org/ijcai/2016/seipp2016ijcai-correlation/}
}