An Empirical Study of Perfect Potential Heuristics
ConferencePaper (Artikel, die in Tagungsbänden erschienen sind)
ID 4526728
Author(s) Corrêa, Augusto B.; Pommerening, Florian
Author(s) at UniBasel Blaas Corrêa, Augusto
Pommerening, Florian
Year 2019
Title 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.
Full Text on edoc Available

MCSS v5.8 PRO. 0.499 sec, queries - 0.000 sec ©Universität Basel  |  Impressum   |