Heuristics for HTN Planning as Satisfiability

Contents

Classical planning is the problem of synthesizing a sequence of actions to reach the goal state starting from the initial state. Hierarchical task networks (HTNs) have been used as a guidance for solving planning problems where tasks are decomposed into subtasks. Recently, both action-based planning as well as HTNbased planning have been east as SAT. The performance of planning as SAT has been hitherto remarkably improved by using a variety of techniques. However none of these techniques is sensitive to the structure of domain specific knowledge. To bridge this gap, we develop and evaluate several heuristics that are sensitive to the structure of the given domain knowledge (in the form of HTNs), to generate propositional encodings of HTN planning. The resulting encodings are smaller and easier to solve on most of the problems. Given that the current SAT solvers can handle a limited number of variables (10,000) and clauses (100,000) in real time, such heuristics sensitive to the structure of the domain knowledge are important.