The Influence of k-Dependence on the Complexity of Planning

Authors

  • Omer Gimenez Universitat Politecnica de Catalunya
  • Anders Jonsson Universitat Pompeu Fabra

DOI:

https://doi.org/10.1609/icaps.v19i1.13349

Keywords:

planning, dependence, tractability

Abstract

A planning problem is k-dependent if each action has at most k pre-conditions on variables unaffected by the action. This concept is well-founded since k is a constant for all but a few of the standard planning domains, and is known to have implications for tractability. In this paper, we present several new complexity results for P(k), the class of k-dependent planning problems with binary variables and polytree causal graphs. The problem of plan generation for P(k) is equivalent to determining how many times each variable can change. Using this fact, we present a polytime plan generation algorithm for P(2) and P(3). For constant k > 3, we introduce and use the notion of a cover to find conditions under which plan generation for P(k) is polynomial.

Downloads

Published

2009-10-16

How to Cite

Gimenez, O., & Jonsson, A. (2009). The Influence of k-Dependence on the Complexity of Planning. Proceedings of the International Conference on Automated Planning and Scheduling, 19(1), 138-145. https://doi.org/10.1609/icaps.v19i1.13349