On the Complexity of Blocks-World Planning

dc.contributor.authorGupta, Nareshen_US
dc.contributor.authorNau, Dana S.en_US
dc.contributor.departmentISRen_US
dc.date.accessioned2007-05-23T09:48:29Z
dc.date.available2007-05-23T09:48:29Z
dc.date.issued1991en_US
dc.description.abstractIn this paper, we show that blocks-world planning is difficult, in the sense that finding an optimal plan is NP-hard. This is true regardless of whether or not, the goal state is completely specified, and regardless of whether or not different blocks have different sizes. However, the difficulty of blocks-world planning is not due to deleted-condition interactions, but instead due to another kind of goal interaction, which we call a deadlock. For problems that do not contain deadlocks, there is a simple hill- climbing strategy that can easily find an optimal plan, regardless of whether or not the problem contains any deleted- condition interactions.<P>The fact that deleted-condition interactions are easy and deadlocks are difficult is rather surprising, for one of the primary roles of the blocks world in the planning literature has been to provide examples of deleted- condition interactions such as creative destruction and Sussman's anomaly. This suggests that a good topic for future research might be to investigate how easily such interactions can be handled in other planning domains.en_US
dc.format.extent1368464 bytes
dc.format.mimetypeapplication/pdf
dc.identifier.urihttp://hdl.handle.net/1903/5122
dc.language.isoen_USen_US
dc.relation.ispartofseriesISR; TR 1991-74en_US
dc.subjectalgorithmsen_US
dc.subjectcomputational complexityen_US
dc.subjectSystems Integrationen_US
dc.titleOn the Complexity of Blocks-World Planningen_US
dc.typeTechnical Reporten_US

Files

Original bundle
Now showing 1 - 1 of 1
Loading...
Thumbnail Image
Name:
TR_91-74.pdf
Size:
1.31 MB
Format:
Adobe Portable Document Format