Probabilistic HTN Planning: Formalization and Computational Complexity Analysis

Hierarchical Task Network (HTN) planning is an approach to sequential decision making that allows expressing complex grammar-like path constraints. In this paper, we first introduce an extension to HTN planning that takes probabilistic outcomes into account, and then study the computational complexity of deciding such problems either by finding a fixed sequence of actions (i.e., a conformant solution) or an outcome-dependent policy. This formalization extends factored Markov Decision Processes (MDPs) to have a hierarchical structure. In all studied cases, the conformant solutions are harder to obtain than their non-deterministic analogues, whereas policies are not always harder. Surprisingly, unlike their deterministic counterparts, severely restricted cases of probabilistic HTN problems are proven to be undecidable. The result holds even if all of the transition probabilities are bounded to be 0, 0.5, or 1.