Show simple item record

On the Nature of Modal Truth in Plans

dc.contributor.authorNau, D.S.en_US
dc.date.accessioned2007-05-23T09:53:29Z
dc.date.available2007-05-23T09:53:29Z
dc.date.issued1993en_US
dc.identifier.urihttp://hdl.handle.net/1903/5361
dc.description.abstractChapman's paper, "Planning for Conjunctive Goals", has been widely acknowledged as a major step towards understanding the nature of nonlinear planning, and it has been one of the bases of later work by others -- but it is not free of problems. This paper discusses the following problems with modal truth and the modal truth criterion.<P>1. It is NP-hard to tell, given a plan P and a ground atom p, whether P is possibly true in P's final situation. This is true despite the fact that modal truth criterion can be computed in a polynomial time.<P>2. The reason for this discrepancy is that the "possible truth" version of the modal truth criterion is incorrect. It tells whether - p is not necessarily true --- but this is different from telling whether p is possibly true. Possible truth is not the dual of necessary truth, as Chapman had thought it was.<P>3. Instead, possible truth is the dual of another problem, which is co-NP-hard: the problem of determining whether p is true over all executable completions of a plan.<P>Despite the above problems, the "necessary truth" version of the modal truth criterion (and hence the TWEAK planner) are still correct.en_US
dc.format.extent766847 bytes
dc.format.mimetypeapplication/pdf
dc.language.isoen_USen_US
dc.relation.ispartofseriesISR; TR 1993-14en_US
dc.subjectcomputational complexityen_US
dc.subjectplanningen_US
dc.subjectSystems Integrationen_US
dc.titleOn the Nature of Modal Truth in Plansen_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