Planning with Observations and Knowledge

Contents

We are concerned with increasing the expressiveness of planning methods to handle observations and conditional execution. In previous work, two of us have argued that one cannot correctly construct such a planner without an explicit distinction between what is true in the world and what the agent knows (believes) be true. Also in previous work, one of us has created a planner, Cassandra, that appears to construct flexible plans with conditional execution and knowledge-gathering without such a representation. The work described here was done to address the tension between these two results. To address these issues, we have developed a formalization of action, WCPL, based on propositional dynamic logic (PDL). We have chosen dynamic logic as framework because it already has constructs we need, like conditionals and nondeterministic actions. PDL is also closer to the kinds of action representation (e.g., STRIPS, ADL) used by implemented planners than are competing languages like the situation calculus. We have used WCPL to give a semantics to Cassandra’s plan and have shown that the Cassandra algorithm is sound with respect to this semantics.