Correlation Complexity of Classical Planning Domains

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

Correlation Complexity of Classical Planning Domains

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

Download BibTeX Cite

Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence. Pages 3242-3249.

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.

Jendrik Seipp, Florian Pommerening, Gabriele Röger, and Malte Helmert. 2016. Correlation Complexity of Classical Planning Domains. In Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence, IJCAI-16. IJCAI, 3242–3249. https://ijcai.org/proceedings/2016/459

@inproceedings{ijcai2016p459,
  title     = {Correlation Complexity of Classical Planning Domains},
  author    = {Seipp, Jendrik and Pommerening, Florian and Röger, Gabriele and Helmert, Malte},
  booktitle = {Proceedings of the Twenty-Fifth International Joint Conference on
               Artificial Intelligence, {IJCAI-16}},
  publisher = {AAAI Press / International Joint Conferences on Artificial Intelligence},
  editor    = {Subbarao Kambhampati},
  pages     = {3242--3249},
  year      = {2016},
  month     = {7},
  url       = {https://ijcai.org/proceedings/2016/459},
}

TY  - CPAPER
TI  - Correlation Complexity of Classical Planning Domains
AU  - Seipp, Jendrik
AU  - Pommerening, Florian
AU  - Röger, Gabriele
AU  - Helmert, Malte
T2  - Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence, IJCAI-16
PB  - AAAI Press / International Joint Conferences on Artificial Intelligence
PY  - 2016
SP  - 3242
EP  - 3249
UR  - https://ijcai.org/proceedings/2016/459
ER  -