edoc

Correlation Complexity of Classical Planning Domains

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] 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
Last Modified:16 Oct 2018 14:48
Deposited On:11 Oct 2017 09:44

Repository Staff Only: item control page