Complexity, Decidability and Undecidability Results for Domain-Independent Planning: A Detailed Analysis

Loading...
Thumbnail Image

Files

CS-TR-2797.ps (543.72 KB)
No. of downloads: 170
CS-TR-2797.pdf (501.62 KB)
No. of downloads: 661

Publication or External Link

Date

1998-10-15

Advisor

Citation

DRUM DOI

Abstract

In this paper, we examine how the complexity of domain-independent planning with STRIPS-like operators depends on the nature of the planning operators.

We show conditions under which plannning is decidable and undecidable. 

Our results on this topic solve an open problem posed by Chapman [4], and
clear up some difficulties with his undecidability theorems.

For those cases where planning is decidable, we show how the time 

complexity varies depending on a wide variety of conditions: . whether or not function symbols are allowed; . whether or not delete lists are a]]owed; . whether or not negative preconditions are allowed; . whether or not the predicates are restricted to be propositional(i.e., 0-ary); . whether the planning operators are given as part of the input to the planning prob]em, or instead are fixed in advance. (Also cross-referenced as UMIACS-TR-91-154)

Notes

Rights