The influence ofk-dependence on the complexity of planning

Publication year: 2011 Source: Artificial Intelligence, Available online 14 December 2011 Omer Giménez, Anders Jonsson A planning problem isk-dependent if each action has at mostkpre-conditions on variables unaffected by the action. This concept is of interest becausekis a constant for all but a few of the current benchmark domains in planning, and is known to have implications for tractability. In this paper, we present an algorithm for solving planning problems in, the class ofk-dependent planning problems with binary variables and polytree causal graphs

Publication year: 2011 Source: Artificial Intelligence, Available online 14 December 2011 Omer Giménez, Anders Jonsson A planning problem isk-dependent if each action has at mostkpre-conditions on variables unaffected by the action. This concept is of interest becausekis a constant for all but a few of the current benchmark domains in planning, and is known to have implications for tractability. In this paper, we present an algorithm for solving planning problems in, the class ofk-dependent planning problems with binary variables and polytree causal graphs

View article:
The influence ofk-dependence on the complexity of planning