Font Size:

The Influence of

*k-*Dependence on the Complexity of PlanningLast modified: 2009-10-16

#### 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.
Full Text:
PDF