babylonpolice.com

We study the complexity-theoretic boundaries of tractability for three
classical problems in the context of Hierarchical Task Network Planning: the
validation of a provided plan, whether an executable plan exists, and whether a
given state can be reached by some plan. We show that all three problems can be
solved in polynomial time on primitive task networks of constant partial order
width (and a generalization thereof), whereas for the latter two problems this
holds only under a provably necessary restriction to the state space. Next, we
obtain an algorithmic meta-theorem along with corresponding lower bounds to
identify tight conditions under which general polynomial-time solvability
results can be lifted from primitive to general task networks. Finally, we
enrich our investigation by analyzing the parameterized complexity of the three
considered problems, and show that (1) fixed-parameter tractability for all
three problems can be achieved by replacing the partial order width with the
vertex cover number of the network as the parameter, and (2) other classical
graph-theoretic parameters of the network (including treewidth, treedepth, and
the aforementioned partial order width) do not yield fixed-parameter
tractability for any of the three problems.