PSIPOP: Planning with Sensing over Partially Closed Worlds

Search Techniques for Problem Solving Under Uncertainty and Incomplete Information

Volume

Search Techniques for Problem Solving Under Uncertainty and Incomplete Information

Contents

We present a new partial order planner called PSIPOP, which builds on SNLP. We drop the closed world assumption, add sensing actions, add a class of propositions about the agent’s knowledge, and add a class of universally quantified propositions. This latter class of propositions, which we call C-forms, distinguishes this research. C-forms represent partially closed worlds, such as "Block A is clear", or "x.ps is the only postscript file in directory/rex." We present our theory of planning with sensing and show how partial order planning is performed using C-forms. Noteworthy are the facts that lack of information iscan be represented precisely and all quantified reasoning has polynomial complexity. Thus, in finite domains where the maximum plan length is bounded, PSIPOP is NPcomplete.