On the Complexity of Heuristic Synthesis for Satisficing Classical Planning: Potential Heuristics and Beyond

Authors

  • Malte Helmert University of Basel
  • Silvan Sievers University of Basel
  • Alexander Rovner Unaffiliated
  • Augusto B. Corrêa University of Basel

Keywords:

Classical Planning, Potential Heuristics, Complexity Results

Abstract

Potential functions are a general class of heuristics for classical planning. For satisficing planning, previous work suggested the use of descending and dead-end avoiding (DDA) potential heuristics, which solve planning tasks by backtrack-free search. In this work we study the complexity of devising DDA potential heuristics for classical planning tasks. We show that verifying or synthesizing DDA potential heuristics is PSPACE-complete, but suitable modifications of the DDA properties reduce the complexity of these problems to the first and second level of the polynomial hierarchy. We also discuss the implications of our results for other forms of heuristic synthesis in classical planning.

Downloads

Published

2022-06-13

How to Cite

Helmert, M., Sievers, S., Rovner, A., & B. Corrêa, A. (2022). On the Complexity of Heuristic Synthesis for Satisficing Classical Planning: Potential Heuristics and Beyond. Proceedings of the International Conference on Automated Planning and Scheduling, 32(1), 124-133. Retrieved from https://ojs.aaai.org/index.php/ICAPS/article/view/19793