University of Maryland LibrariesDigital Repository at the University of Maryland
    • Login
    View Item 
    •   DRUM
    • A. James Clark School of Engineering
    • Institute for Systems Research Technical Reports
    • View Item
    •   DRUM
    • A. James Clark School of Engineering
    • Institute for Systems Research Technical Reports
    • View Item
    JavaScript is disabled for your browser. Some features of this site may not work without it.

    On the Nature of Modal Truth in Plans

    Thumbnail
    View/Open
    TR_93-14.pdf (748.8Kb)
    No. of downloads: 257

    Date
    1993
    Author
    Nau, D.S.
    Metadata
    Show full item record
    Abstract
    Chapman'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.
    URI
    http://hdl.handle.net/1903/5361
    Collections
    • Institute for Systems Research Technical Reports

    DRUM is brought to you by the University of Maryland Libraries
    University of Maryland, College Park, MD 20742-7011 (301)314-1328.
    Please send us your comments.
    Web Accessibility
     

     

    Browse

    All of DRUMCommunities & CollectionsBy Issue DateAuthorsTitlesSubjectsThis CollectionBy Issue DateAuthorsTitlesSubjects

    My Account

    LoginRegister
    Pages
    About DRUMAbout Download Statistics

    DRUM is brought to you by the University of Maryland Libraries
    University of Maryland, College Park, MD 20742-7011 (301)314-1328.
    Please send us your comments.
    Web Accessibility