APPLICATIONS OF A LOGIC OF KNOWLEDGE TO MOTION PLANNING UNDER UNCERTAINTY

Inspired by the success of the distributed computing community in appl ying logics of knowledge and time to reasoning about distributed proto cols,we aim for a similarly powerful and high-level abstraction when r easoning about control problems involving uncertainty. This paper conc entrates on robot motion planning with uncertainty in both control and sensing, a problem that has already been well studied within the robo tics community. First, a new and natural problem in this domain is def ined: Does there exists a sound and complete termination condition for a motion, given initial and goal locations? If yes, how to construct it? Then we define a high-level language, a logic of time and knowledg e, which we use to reason about termination conditions and to state ge neral conditions for the existence of sound and complete termination c onditions in a broad domain. Finally, we show that sound termination c onditions that are optimal in a precise sense provide a natural exampl e of knowledge-based programs with multiple implementations.