Show simple item record

On the Nature of Modal Truth in Plans

dc.contributor.authorNau, D.S.en_US
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.relation.ispartofseriesISR; TR 1993-14en_US
dc.subjectcomputational complexityen_US
dc.subjectSystems Integrationen_US
dc.titleOn the Nature of Modal Truth in Plansen_US
dc.typeTechnical Reporten_US

Files in this item


This item appears in the following Collection(s)

Show simple item record