TY - JOUR AU - Helmert, Malte AU - Sievers, Silvan AU - Rovner, Alexander AU - B. CorrĂȘa, Augusto PY - 2022/06/13 Y2 - 2024/03/29 TI - On the Complexity of Heuristic Synthesis for Satisficing Classical Planning: Potential Heuristics and Beyond JF - Proceedings of the International Conference on Automated Planning and Scheduling JA - ICAPS VL - 32 IS - 1 SE - Main Track DO - 10.1609/icaps.v32i1.19793 UR - https://ojs.aaai.org/index.php/ICAPS/article/view/19793 SP - 124-133 AB - 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. ER -