SibylSatOpt: a MaxSAT-based Greedy Optimal Search for TOHTN Planning

Abstract

This paper introduces SibylSatOpt, a novel approach to finding optimal plans for Totally-Ordered HTN (TOHTN) problems by leveraging greedy search techniques with MaxSAT. Unlike previous SAT-based HTN planners that employed a blind breadth-first search strategy, SibylSatOpt is guided by an admissible heuristic. This heuristic combines a relaxed MaxSAT encoding of the problem with the Task Decomposition Graph (TDG) heuristic. As we demonstrate, the admissibility of the heuristic guarantees that the found solution is optimal. Experimental results on IPC benchmarks show that SibylSatOpt significantly outperforms existing optimal TOHTN planners in both runtime and problem coverage.