Seipp, Jendrik and Pommerening, Florian and Röger, Gabriele and Helmert, Malte. (2016) Correlation Complexity of Classical Planning Domains. In: Proceedings of the 25th International Joint Conference on Artificial Intelligence (IJCAI 2016), 4. pp. 3242-3250.
![[img]](https://edoc.unibas.ch/style/images/fileicons/application_pdf.png) |
PDF
- Published Version
647Kb |
Official URL: http://edoc.unibas.ch/45249/
Downloads: Statistics Overview
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.
| Faculties and Departments: | 05 Faculty of Science > Departement Mathematik und Informatik > Informatik > Artificial Intelligence (Helmert) |
|---|---|
| UniBasel Contributors: | Seipp, Jendrik and Pommerening, Florian and Röger, Gabriele and Helmert, Malte |
| Item Type: | Conference or Workshop Item, refereed |
| Conference or workshop item Subtype: | Conference Paper |
| Publisher: | AAAI Press |
| ISBN: | 978-1-57735-771-1 |
| Note: | Publication type according to Uni Basel Research Database: Conference paper |
| Language: | English |
| edoc DOI: | |
| Last Modified: | 16 Oct 2018 14:48 |
| Deposited On: | 11 Oct 2017 09:44 |
Repository Staff Only: item control page