An Empirical Study of Perfect Potential Heuristics

Corrêa, Augusto B. and Pommerening, Florian. (2019) An Empirical Study of Perfect Potential Heuristics. In: Proceedings of the Twenty-Ninth International Conference on Automated Planning and Scheduling, 29. pp. 114-118.

[img] PDF - Accepted Version

Official URL: https://edoc.unibas.ch/74630/

Downloads: Statistics Overview


Potential heuristics are weighted functions over state features of a planning task. A recent study defines the complexity of a task as the minimum required feature complexity for a potential heuristic that makes a search backtrack-free. This gives an indication of how complex potential heuristics need to be to achieve good results in satisficing planning. However, these results do not directly transfer to optimal planning. In this paper, we empirically study how complex potential heuristics must be to represent the perfect heuristic and how close to perfect heuristics can get with a limited number of features. We aim to identify the practical trade-offs between size, complexity and time for the quality of potential heuristics. Our results show that, even for simple planning tasks, finding perfect potential heuristics might be harder than expected.
Faculties and Departments:05 Faculty of Science > Departement Mathematik und Informatik > Informatik > Artificial Intelligence (Helmert)
UniBasel Contributors:Blaas Corrêa, Augusto and Pommerening, Florian
Item Type:Conference or Workshop Item, refereed
Conference or workshop item Subtype:Conference Paper
Publisher:AAAI Press
Note:Publication type according to Uni Basel Research Database: Conference paper
edoc DOI:
Last Modified:03 Feb 2020 07:15
Deposited On:22 Jan 2020 12:33

Repository Staff Only: item control page