Show simple item record

Complexity, Decidability and Undecidability Results for Domain- Independent Planning

dc.contributor.authorErol, Kutluhanen_US
dc.contributor.authorNau, D.S.en_US
dc.contributor.authorSubrahmanian, V.S.en_US
dc.date.accessioned2007-05-23T09:48:52Z
dc.date.available2007-05-23T09:48:52Z
dc.date.issued1991en_US
dc.identifier.urihttp://hdl.handle.net/1903/5142
dc.description.abstractIn this paper, we examine how the complexity of domain- independent planning with STRIPS-like operators depends on the nature of the planning operators.<P>We show conditions under which planning 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.<P>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 allowed; 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 problem, or instead are fixed in advance.<P>en_US
dc.format.extent2250190 bytes
dc.format.mimetypeapplication/pdf
dc.language.isoen_USen_US
dc.relation.ispartofseriesISR; TR 1991-96en_US
dc.subjectcomputational complexityen_US
dc.subjectSystems Integrationen_US
dc.titleComplexity, Decidability and Undecidability Results for Domain- Independent Planningen_US
dc.typeTechnical Reporten_US
dc.contributor.departmentISRen_US


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record