Encoding HTN Planning in Propositional Logic

Casting planning problemsas propositional satlsfiability problems has recently been shownto be an effective wayof scaling up plan synthesis. Until now, the benefits of this approach have only been utUized in primitive action-based planning models. Motivated by the conventional wisdomin the planning community about the effectiveness of hierarchical task network (HTN)planning models, in this paper we adapt the "planningas satlsfiability" approachto HT_X planning models. HTNplanning models can be thought of as an augmentationof primitive action based planning models with a grammarof legal solutions, provided in the form of non-primitive tasks and task reduction schemas. Accordingly, we argue that any action-based encoding scheme can be generalized to handle HTN planning models. Informally, this generalization involves adding constraints to the encoding to ensure that the solutions produced by solving the encoding will conform to the grammar provided by the HTN planning model. The constraints can be added in either a ’~op-down"or "bottom-up" fashion, resulting in two HTNencoding schemesfor each primitive action-based encoding scheme. Weillustrate this process by providing three different HTNencodings. We discuss the asymptoticsizes of these encodings, as well as the complexityof finding modelsfor them.

Authors

• Amol Dattatraya Mali
• Subbarao Kambhampati

Keywords

No keywords are indexed for this paper.