On the Complexity of Domain-Independent Planning

Kutluhan Erol, Dana S. Nau, V. S. Subrahmanian

In this paper, we examine how the complexity of domain-independent planning with STRIPS-Style operators depends on the nature of the planning operators. We show how the time complexity varies depending on a wide variety of conditions: whether or not delete lists are allowed; whether or not negative preconditions are allowed; whether or not the predicates are restricted to be propositions (i.e., 0-ary); whether the planning operators are given as part of the input to the planning problem, or instead are fixed in advance.


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.