AAAI Publications, Twenty-Fourth International Conference on Automated Planning and Scheduling

Font Size: 
The Complexity of Partial-Order Plan Viability Problems
Xing Tan, Michael Gruninger

Last modified: 2014-05-11


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.


Partial-Order Planning Viability Problems; Computational Complexity; Event Systems

Full Text: PDF