On the Hardness of Planning Problems with Simple Causal Graphs

Omer Gimenez, Anders Jonsson

We present three new complexity results for classes of planning problems with simple causal graphs. First, we describe a polynomial time algorithm that uses macros to generate plans for a class of planning problems with binary state variables and acyclic causal graphs. This implies that plan generation may not be intractable just because a planning problem has exponential length solution. We also prove that the problem of plan existence for planning problems with multi-valued variables and chain causal graphs is NP-hard. Finally, we show that plan existence for planning problems with binary state variables and polytree causal graphs is NP-complete.

Subjects: 1.11 Planning; 9.2 Computational Complexity

Submitted: Jun 27, 2007


This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.