×

zbMATH — the first resource for mathematics

A logical theory of localization. (English) Zbl 1371.03040
The authors consider a fundamental problem in cognitive robotics, namely the problem for a robot to identify its location and orientation to a reasonable certainty by means of available sensors and given a spatial characterization of its environment. The idea is to understand this localization problem as part of the situation calculus, a prominent first-order formalism for knowledge representation, in particular for reasoning about action and change. The central ingredient of the account given is an axiomatic basic action theory from which robot localization follows logically. This is illustrated by two examples of a robot in a two-dimensional grid, equipped with a moving action and distance sensor. Various properties of the basic action theory are shown to hold. Also, localization with multiple agents is treated.

MSC:
03B70 Logic in computer science
03B42 Logics of knowledge and belief (including belief change)
68T27 Logic in artificial intelligence
68T30 Knowledge representation
68T40 Artificial intelligence for robotics
68T42 Agent technology and artificial intelligence
Software:
GOLOG; PREGO
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Bacchus F.: Representing and Reasoning with Probabilistic Knowledge. MIT Press, Cambridge, MA (1990)
[2] Bacchus, F.; Halpern, J. Y.; Levesque, H. J., Reasoning about noisy sensors and effectors in the situation calculus, Artificial Intelligence, 111, 171-208, (1999) · Zbl 0996.68192
[3] Baltag, A., L. S. Moss, and S. Solecki, The logic of public announcements, common knowledge, and private suspicions, in Proceedings of TARK, 1998, pp. 43-56. · Zbl 1386.03019
[4] Belle, V., and G. Lakemeyer, A semantical account of progression in the presence of uncertainty, in Proceedings of AAAI, 2011, pp. 165-170.
[5] Belle, V., and H. J. Levesque, Reasoning about continuous uncertainty in the situation calculus, in Proceedings of IJCAI, 2013. · Zbl 1105.68333
[6] Belle, V., and H. J. Levesque, Reasoning about probabilities in dynamic systems using goal regression, in Proceedings of UAI, 2013. · Zbl 1079.68625
[7] Belle, V., and H. J. Levesque, Robot location estimation in the situation calculus, in Symposium on Logical Formalizations of Commonsense Reasoning, 2013. · Zbl 1388.68274
[8] Belle, V., and H. J. Levesque, How to progress beliefs in continuous domains, in Proceedings of KR, 2014.
[9] Belle, V., and H. J. Levesque, PREGO: An action language for belief-based cognitive robotics in continuous domains, in Proceedings of AAAI, 2014. · Zbl 0781.68038
[10] Billingsley, P., Probability and Measure, 3rd edn., Wiley-Interscience, New York, 1995. · Zbl 0822.60002
[11] Boutilier, C., R. Reiter, M. Soutchanski, and S. Thrun, Decision-theoretic, high-level agent programming in the situation calculus, in Proceedings of AAAI, 2000, pp. 355-362. · Zbl 1314.68299
[12] Burgard, W.; Cremers, A. B.; Fox, D.; Hähnel, D.; Lakemeyer, G.; Schulz, D.; Steiner, W.; Thrun, S., Experiences with an interactive museum tour-guide robot, Artificial Intelligence, 114, 3-55, (1999) · Zbl 0939.68865
[13] Choi, J., A. Guzman-Rivera, and E. Amir, Lifted relational Kalman filtering, in Proceedings of IJCAI, 2011, pp. 2092-2099.
[14] Cox, I. J., Blanche—an experiment in guidance and navigation of an autonomous robot vehicle, IEEE Transactions on Robotics and Automation, 7, 193-204, (1991)
[15] Da Prato, G., An Introduction to Infinite-Dimensional Analysis, Universitext, Springer, 2006. · Zbl 1109.46001
[16] Darwiche, A., and M. Goldszmidt, Action networks: A framework for reasoning about actions and change under uncertainty, in Proceedings of UAI, 1994, pp. 136-144. · Zbl 0131.00602
[17] De Giacomo, G., and H. J. Levesque, Two approaches to efficient open-world reasoning, in Logic-Based Artificial Intelligence, Kluwer Academic Publishers, Norwell, MA, 2000, pp. 59-78. · Zbl 0979.68097
[18] Delgrande, J. P., and H. J. Levesque, A formal account of nondeterministic and failed actions, in IJCAI, 2013.
[19] Dellaert, F., D. Fox, W. Burgard, and S.Thrun, Monte carlo localization for mobile robots, in Proceedings Robotics and Automation, vol. 2, IEEE, 1999, pp. 1322-1328. · Zbl 0971.68162
[20] Fagin, R.; Halpern, J. Y., Reasoning about knowledge and probability, Journal of the ACM, 41, 340-367, (1994) · Zbl 0806.68098
[21] Fox, D.; Burgard, W.; Kruppa, H.; Thrun, S., A probabilistic approach to collaborative multi-robot localization, Autonomous Robots, 8, 325-344, (2000)
[22] Gabaldon, A., and G. Lakemeyer, ESP: A logic of only-knowing, noisy sensing and acting, in Proceedings of AAAI, 2007, pp. 974-979.
[23] Ge, X., and J. Renz, Representation and reasoning about general solid rectangles, in IJCAI, 2013.
[24] De Giacomo, G., L. Iocchi, D. Nardi, and R. Rosati, Moving a robot: The kr & r approach at work, in Proceedings of KR, 1996, pp. 198-209.
[25] Hajishirzi, H., and E. Amir, Reasoning about deterministic actions with probabilistic prior and application to stochastic filtering, in Proceedings of KR, 2010. · Zbl 0806.68098
[26] Halpern, J. Y.; Tuttle, M. R., Knowledge, probability, and adversaries, Journal of the ACM, 40, 917-960, (1993) · Zbl 0783.68120
[27] Halpern, J. Y., An analysis of first-order logics of probability, Artificial Intelligence, 46, 311-350, (1990) · Zbl 0723.03007
[28] Hintikka, J., Knowledge and Belief: An Introduction to the Logic of the Two Notions, Cornell University Press, Ithaca, 1962.
[29] Jetto, L.; Longhi, S.; Vitali, D., Localization of a wheeled mobile robot by sensor data fusion based on a fuzzy logic adapted Kalman filter, Control Engineering Practice, 7, 763-771, (1999)
[30] Kelly, R. F.; Pearce, A. R., Asynchronous knowledge with hidden actions in the situation calculus, Artificial Intelligence, 221, 1-35, (2015) · Zbl 1328.68213
[31] Kripke, S., Semantical considerations on modal logic, Acta Philosophica Fennica, 16, 83-94, (1963) · Zbl 0131.00602
[32] Kushmerick, N., S. Hanks, and D. S. Weld, An algorithm for probabilistic planning, Artificial Intelligence 76(1):239-286, 1995.
[33] Lakemeyer, G., and H. J. Levesque, Cognitive robotics, in Handbook of Knowledge Representation, Elsevier, Amsterdam, 2007, pp. 869-886.
[34] Lee, J. H., J. Renz, and D. Wolter, Starvars—Effective reasoning about relative directions, in Francesca Rossi, (ed.), IJCAI, IJCAI/AAAI, 2013.
[35] Levesque, H. J., and R. Reiter, High-level robotic control: Beyond planning, Position paper at AAAI Spring Symposium on Integrating Robotics Research, 1998.
[36] Levesque, H. J., R. Reiter, Y. Lespérance, F. Lin, and R. Scherl, Golog: A logic programming language for dynamic domains, Journal of Logic Programming 31:59-84, 1997. · Zbl 0880.68008
[37] Levesque, H. J.; Pirri, F.; Reiter, R., Foundations for the situation calculus, Electronic Transactions in Artificial Intelligence, 2, 159-178, (1998)
[38] Lin, F.; Reiter, R., How to progress a database, Artificial Intelligence, 92, 131-167, (1997) · Zbl 1017.68510
[39] Mateus, P.; Pacheco, A.; Pinto, J.; Sernadas, A.; Sernadas, C., Probabilistic situation calculus, Annals of Mathematics and Artificial Intelligence, 32, 393-431, (2001) · Zbl 1314.68299
[40] McCarthy, J., and P. J. Hayes, Some philosophical problems from the standpoint of artificial intelligence, in Machine Intelligence, 1969, pp. 463-502. · Zbl 0226.68044
[41] McIlraith, S., G. Biswas, D. Clancy, and V. Gupta, Hybrid systems diagnosis, in Proceedings of Workshop on Hybrid Systems: Computation and Control, LNCS, 2000, pp. 282-295. · Zbl 0938.93553
[42] Moore, R. C., A formal theory of knowledge and action, in Formal Theories of the Commonsense World, Ablex, Norwood, NJ, 1985, pp. 319-358.
[43] Ng, R.; Subrahmanian, V.S., Probabilistic logic programming, Information and Computation, 101, 150-201, (1992) · Zbl 0781.68038
[44] Pearl, J., Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference, Morgan Kaufmann, San Mateo, CA, 1988. · Zbl 0746.68089
[45] Poole, D., Decision theory, the situation calculus and conditional plans, Electronic Transactions in Artificial Intelligence, 2, 105-158, (1998)
[46] Reiter, R., Knowledge in Action: Logical Foundations for Specifying and Implementing Dynamical Systems, MIT Press, Cambridge, MA, 2001. · Zbl 1018.03022
[47] Richardson, M.; Domingos, P., Markov logic networks, Machine learning, 62, 107-136, (2006)
[48] Sanner, S., Relational dynamic influence diagram language (rddl): Language description, Technical Report, Australian National University, 2011.
[49] Scherl, R. B.; Levesque, H. J., Knowledge, action, and the frame problem, Artificial Intelligence, 144, 1-39, (2003) · Zbl 1079.68625
[50] Shapiro, S., Belief change with noisy sensing and introspection, in NRAC Workshop, 2005, pp. 84-89.
[51] Shapiro, S., Y. Lespérance, and H. J. Levesque, The cognitive agents specification language and verification environment for multiagent systems, in Proceedings of AAMAS, 2002, pp. 19-26. · Zbl 1201.68127
[52] Shapiro, S., Y. Lespérance, and H. J. Levesque, Goal change, in Proceedings IJCAI, 2005, pp. 582-588.
[53] Thielscher, M., Planning with noisy actions (preliminary report), in Proceedings of the Australian Joint Conference on Artificial Intelligence, 2001, pp. 27-45.
[54] Thielscher, M., Flux: A logic programming method for reasoning agents, Theory and Practice of Logic Programming, 5, 533-565, (2005) · Zbl 1105.68333
[55] Thrun, S., W. Burgard, and D. Fox, Probabilistic Robotics, MIT Press, Cambridge, MA, 2005.
[56] Van Benthem, J.; Gerbrandy, J.; Kooi, B., Dynamic update with probabilities, Studia Logica, 93, 67-96, (2009) · Zbl 1183.03015
[57] Younes, H., and M. Littman, PPDDL 1.0: An extension to pddl for expressing planning domains with probabilistic effects, Technical Report, Carnegie Mellon University, 2004.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.