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
An Empirical Study of Perfect Potential Heuristics
Book title (Conference Proceedings)
Proceedings of the Twenty-Ninth International Conference on Automated Planning and Scheduling
Volume
29
Place of Conference
Berkeley, California, USA
Year of Conference
2019
Publisher
AAAI Press
Pages
114-118
ISSN/ISBN
2334-0843
Abstract
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.
