The Complexity of Partial-Order Plan Viability Problems

Estimating the distance from a current partial-order plan to the goal state of the plan task is a challenging problem, with past research achieving only limited success. In an effort to understand the reasons for this situation, we investigate the computational complexity of the partial-order plan viability problem. We define several boundaries between the tractable and intractable subclasses of the problem, from which we identify several constraints that contribute to the computational intractability of the problem. These results bring new insights into the design and the development of future  partial-order planning heuristics.