An Approach to Planning with Incomplete Information.

Abstract

Classical planners presuppose complete and correct information about the world. This paper provides the syntax and semantics for uwl, a representation for goals and actions that facilitates planning with incomplete information about the world's state. While the expressive power of uwl is limited compared to previous work on logics of knowledge and belief, uwl has the advantage of being easily incorporated into planning algorithms. We describe a provably correct planning algorithm based on uwl. To demonstrate uwl's expressive power we encode a subset of the UNIX 1 domain (planning to achieve UNIX goals, using UNIX shell commands as primitive actions), which is difficult to capture using existing planning languages. 3 Authors' names are listed alphabetically within two status-oriented equivalence classes. Our research was funded in part by National Science Foundation Grants IRI-8957302 and IRI--9008670, Office of Naval Research Grants 92-J-1946, 90-J-1904, a NASA Graduate Student Res...