Finding Optimal Solutions in HTN Planning - A SAT-based Approach

Finding Optimal Solutions in HTN Planning - A SAT-based Approach

Gregor Behnke, Daniel Höller, Susanne Biundo

Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence
Main track. Pages 5500-5508. https://doi.org/10.24963/ijcai.2019/764

Over the last years, several new approaches to Hierarchical Task Network (HTN) planning have been proposed that increased the overall performance of HTN planners. However, the focus has been on agile planning - on finding a solution as quickly as possible. Little work has been done on finding optimal plans. We show how the currently best-performing approach to HTN planning - the translation into propositional logic - can be utilised to find optimal plans. Such SAT-based planners usually bound the HTN problem to a certain depth of decomposition and then translate the problem into a propositional formula. To generate optimal plans, the length of the solution has to be bounded instead of the decomposition depth. We show the relationship between these bounds and how it can be handled algorithmically. Based on this, we propose an optimal SAT-based HTN planner and show that it performs favourably on a benchmark set.
Keywords:
Planning and Scheduling: Planning Algorithms
Planning and Scheduling: Hierarchical planning
Constraints and SAT: SAT: Applications