Applications of a logic of knowledge to motion planning under uncertainty

ABSTRACT

Inspired by the success of the distributed computing community in apply logics of knowledge and time to reasoning about distributed protocols, we aim for a similarly powerful and high-level abstraction when reasoning about control problems involving uncertainty. This paper concentrates on robot motion planning with uncertainty in both control and sensing, a problem that has already been well studied within the robotics community. First, a new and natural problem in this domain is defined: 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 knowledge, which we use to reason about termination conditions and to state general conditions for the existence of sound and complete termination conditions in a broad domain. Finally, we show that sound termination conditions that are optimal in a precise sense provide a natural example of knowledge-based programs with multiple implementations.

REFERENCES

• 1: Ronen I. Brafman , Jean-Claude Latombe , Yoram Moses , Yoav Shoham, Knowledge as a tool in motion planning under uncertainty, Proceedings of the 5th conference on Theoretical aspects of reasoning about knowledge, p.208-224, March 13-16, 1994, Pacific Grove, California
• 2: BRAFMAN, R. I., LATOMBE, J. C., AND SHOHAM, Y. 1993. Towards knowledge-level analysis of motion planning. In Proceedings of the llth National Conference on/II, pp. 670-675.
• 3: Ronen I. Brafman , Yoav Shoham, Knowledge Considerations in Robotics, Proceedings of the International Workshop on Reasoning with Uncertainty in Robotics, p.248-262, December 04-06, 1995
• 4: CANNY, J. f. 1989. On computability of fine motion plans. In Proceedings of the 1989 IEEE International Conference on Robotics and Automata. IEEE, New York, pp. 177-182.
• 5: Bruce R. Donald, Error detection and recovery in robotics, Springer-Verlag New York, Inc., New York, NY, 1989
• 6: Bruce Randall Donald, On information invariants in robotics, Artificial Intelligence, v.72 n.1-2, p.217-304, Jan. 1995 [doi>10.1016/0004-3702(94)00024-U]
• 7: Cynthia Dwork , Yoram Moses, Knowledge and common knowledge in a byzantine environment: crash failures, Information and Computation, v.88 n.2, p.156-186, Oct. 1990 [doi>10.1016/0890-5401(90)90014-9]
• 8: E. A. Emerson , Joseph Y. Halpern, Decision procedures and expressiveness in the temporal logic of branching time, Journal of Computer and System Sciences, v.30 n.1, p.1-24, Feb. 1985 [doi>10.1016/0022-0000(85)90001-7]
• 9: M Erdmann, Using backprojections for fine motion planning with uncertainty, International Journal of Robotics Research, v.5 n.1, p.19-45, Spring, 1986 [doi>10.1177/027836498600500102]
• 10: ERDMANN, M. 1994. Understanding actions and sensing by designing action-based sensors. In IEEE ICEA Workshop on Design. IEEE, New York.
• 11: Ronald Fagin , Joseph Y. Halpern , Moshe Y. Vardi , Yoram Moses, Reasoning about knowledge, MIT Press, Cambridge, MA, 1995
• 12: HALPERN, J. Y., AND FAGIN, R. 1989. Modelling knowledge and action in distributed systems. Dist. Comput. 3, 159-177.
• 13: Joseph Y. Halpern , Yoram Moses, Knowledge and common knowledge in a distributed environment, Journal of the ACM (JACM), v.37 n.3, p.549-587, July 1990 [doi>10.1145/79147.79161]
• 14: J Y Halpern , M Y Vardi, The complexity of reasoning about knowledge and time, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.304-315, May 28-30, 1986, Berkeley, California, United States [doi>10.1145/12130.12161]
• 15: HINTIKKA, J. 1962. Knowledge and Belief. Cornell University Press, Ithaca, N.Y.
• 16: KAELBLING, L. P., AND ROSENSCHEIN, S.J. 1990. Action and planning in embedded agents. Rob. Auto. Syst. 6, 35-48.
• 17: Jean-Claude Latombe, Robot Motion Planning, Kluwer Academic Publishers, Norwell, MA, 1991
• 18: Jean-Claude Latombe , Anthony Lazanas , Shashank Shekhar, Robot motion planning with uncertainty in control and sensing, Artificial Intelligence, v.52 n.1, p.1-47, Nov. 1991 [doi>10.1016/0004-3702(91)90023-D]
• 19: Anthony Lazanas, Reasoning about uncertainty in robot motion planning, Stanford University, Stanford, CA, 1995
• 20: Hector J. Levesque, Foundations of a functional approach to knowledge representation., Artificial Intelligence, v.23 n.2, p.155-212, July 1984 [doi>10.1016/0004-3702(84)90009-2]
• 21: LOZANO-PI#REZ, f. 1983. Spatial planning: A configuration space approach. IEEE Trans. Comput. C-32, 2, 108-120.
• 22: LOZANO-PI#REZ, f., MASON, M. f., AND TAYLOR, R.n. 1984. Automatic synthesis of fine-motion strategies for robots. Int. J. Robotics Res. 3, 1, 3-24.
• 23: MASON, M. f. 1984. Automatic planning of fine motions: Correctness and completeness. In Proceedings of the IEEE International Conference on Robotics and Automata. IEEE, New York.
• 24: MOORE, R.C. 1985. A formal theory of knowledge and action. In Formal Theories of the Common Sense World.
• 25: MOSES, Y., AND TUTTLE, M.R. 1988. Programming simultaneous actions using common knowledge. Algorithmica. 3, 121-169.
• 26: S J Rosenschein, Formal theories of knowledge in AI and robotics, New Generation Computing, v.3 n.4, p.345-357, 1985 [doi>10.1007/BF03037076]
• 27: TARSKI, A. 1955. A lattice-theoretic fixpoint theorem and its applications. Pac. J. Math. 5, 285-309.
• 28: Russell H. Taylor , Matthew T. Mason , Kenneth Y. Goldberg, Sensor-based manipulation planning as a game with nature, on The fourth international symposium, p.421-429, May 1988, Univ. of California, Santa Clara, California, United States

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE

Additional Classification:
  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.10 Vision and Scene Understanding
            Subjects: Motion

General Terms:
Design, Theory

Keywords:
analysis, knowledge representation, logics of knowledge and time, motion planning under uncertainty