Complexity, Decidability and Undecidability Results for Domain- Independent Planning
| dc.contributor.author | Erol, Kutluhan | en_US |
| dc.contributor.author | Nau, D.S. | en_US |
| dc.contributor.author | Subrahmanian, V.S. | en_US |
| dc.contributor.department | ISR | en_US |
| dc.date.accessioned | 2007-05-23T09:48:52Z | |
| dc.date.available | 2007-05-23T09:48:52Z | |
| dc.date.issued | 1991 | en_US |
| dc.description.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.<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.extent | 2250190 bytes | |
| dc.format.mimetype | application/pdf | |
| dc.identifier.uri | http://hdl.handle.net/1903/5142 | |
| dc.language.iso | en_US | en_US |
| dc.relation.ispartofseries | ISR; TR 1991-96 | en_US |
| dc.subject | computational complexity | en_US |
| dc.subject | Systems Integration | en_US |
| dc.title | Complexity, Decidability and Undecidability Results for Domain- Independent Planning | en_US |
| dc.type | Technical Report | en_US |
Files
Original bundle
1 - 1 of 1