The Complexity of Partial-Order Plan Viability Problems


  • Xing Tan University of Ottawa
  • Michael Gruninger University of Toronto



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


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.




How to Cite

Tan, X., & Gruninger, M. (2014). The Complexity of Partial-Order Plan Viability Problems. Proceedings of the International Conference on Automated Planning and Scheduling, 24(1), 307-313.