Reversibility and Reachability in HTN Planning: Formalization and Computational Complexities in the Totally-Ordered Setting

Abstract

Action reversibility, that is, whether it is possible to undo effects of an action by other actions, has been studied in classical planning and, recently, in non-deterministic planning. In this paper, we formalize the notions of method and primitive task reversibility in the context of hierarchical task network (HTN) planning and provide complexity results. On top of that, we introduce various notions of reachability in the HTN setting, for which the reachability is still an unexplored area (in contrast to classical planning, in which reachability is well studied) We divide the reachability into two classes based on two perspectives, one restricting the allowed progression rules (i.e., reachability using executions of primitive tasks, or reachability using decompositions of compound tasks), and the other focusing on the desired target (i.e., a state, independently on a task network; a task network, independently of a state; or both at once). We show that the complexity of these problems varies significantly, ranging from EXPTIMEcomplete to constant-time. We also show that the introduced reversibility problems exhibit theoretical properties and complexity results analogous to the broader reachability classes.