When Acyclicity Is Not Enough: Limitations of the Causal Graph

Authors

  • Anders Jonsson Universitat Pompeu Fabra
  • Peter Jonsson Linköping University
  • Tomas Lööw Linköping University

DOI:

https://doi.org/10.1609/icaps.v23i1.13550

Keywords:

Classical planning, computational complexity

Abstract

Causal graphs are widely used in planning to capture the internal structure of planning instances. In the past, causal graphs have been exploited to generate hierarchical plans, to compute heuristics, and to identify classes of planning instances that are easy to solve. It is generally believed that planning is easier when the causal graph is acyclic. In this paper we show that this is not true in the worst case, proving that the problem of plan existence is PSPACE-complete even when the causal graph is acyclic. Since the variables of the planning instances in our reduction are propositional, this result applies to STRIPS planning with negative pre-conditions. Having established that planning is hard for acyclic causal graphs, we study a subclass of planning instances with acyclic causal graphs whose variables have strongly connected domain transition graphs. For this class, we show that plan existence is easy, but that bounded plan existence is hard, implying that optimal planning is significantly harder than satisficing planning for this class.

Downloads

Published

2013-06-02

How to Cite

Jonsson, A., Jonsson, P., & Lööw, T. (2013). When Acyclicity Is Not Enough: Limitations of the Causal Graph. Proceedings of the International Conference on Automated Planning and Scheduling, 23(1), 117-125. https://doi.org/10.1609/icaps.v23i1.13550