Data Entry: Please note that the research database will be replaced by UNIverse by the end of October 2023. Please enter your data into the system https://universe-intern.unibas.ch. Thanks
Correlation Complexity of Classical Planning Domains
Editor(s)
Kambhampati, Subbarao
Book title (Conference Proceedings)
Proceedings of the 25th International Joint Conference on Artificial Intelligence (IJCAI 2016)
Volume
4
Place of Conference
New York
Publisher
AAAI Press
Pages
3242-3250
ISSN/ISBN
978-1-57735-771-1
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.
