×

zbMATH — the first resource for mathematics

Range-only SLAM with indistinguishable landmarks; a constraint programming approach. (English) Zbl 1368.90108
Summary: This paper deals with the simultaneous localization and mapping problem (SLAM) for a robot. The robot has to build a map of its environment while localizing itself using a partially built map. It is assumed that (i) the map is made of point landmarks, (ii) the landmarks are indistinguishable, (iii) the only exteroceptive measurements correspond to the distance between the robot and the landmarks. This paper shows that SLAM can be cast into a constraint network the variables of which being trajectories, digraphs and subsets of \(\mathbb {R}^{n}\). Then, we show how constraint propagation can be extended to deal with such generalized constraint networks. As a result, due to the redundancy of measurements of SLAM, we demonstrate that a constraint-based approach provides an efficient backtrack-free algorithm able to solve our SLAM problem in a guaranteed way.
MSC:
90C10 Integer programming
90C35 Programming involving graphs or networks
90C90 Applications of mathematical programming
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Abdallah, F; Gning, A; Bonnifait, P, Box particle filtering for nonlinear state estimation using interval analysis, Automatica, 44, 807-815, (2008) · Zbl 1283.93262
[2] Apt, K, The essence of constraint propagation, Theoretical Computer Science, 221, 179-210, (1998) · Zbl 0930.68164
[3] Apt, K. (2003). Principles of constraint programming: Cambridge University Press. · Zbl 1187.68132
[4] Araya, I., Trombettoni, G., & Neveu, B. (2012). A Contractor Based on Convex Interval Taylor, vol. 7, 1-16, LNCS 7298: Springer.
[5] Beldiceanu, N., Carlsson, M., Demassey, S., & Petit, T. (2006). Graph properties based filtering, Constraint Programming. Principles and Practice of Constraint Programming, 13, 59-74.
[6] Chabert, G; Jaulin, L, Contractor programming, Artificial Intelligence, 3, 1079-1100, (2009) · Zbl 1191.68628
[7] Chabert, G., Jaulin, L., & Lorca, X. (2009). A constraint on the number of distinct vectors with application to localization, CP 2009, Vol. 7.
[8] Colle, E; Galerne, Mobilerobotlocalizationbymultiangulationusingsetinversion, No article title, Robotics and Autonomous Systems, 61, 39-48, (2013)
[9] Davey, B. A., & Priestley, H. A. (2002). Introduction to Lattices and Order: Cambridge University Press. (ISBN 0521784514). · Zbl 1002.06001
[10] Dooms, G; Deville, Y; Dupont, P, Introducing a graph computation domain in constraint programming, Principles and Practice of Constraint Programming, 7, 211-225, (2005) · Zbl 1153.68457
[11] Drevelle, V., & Bonnifait, P. (2009). High integrity gnss location zone characterization using interval analysis, ION GNSS, Vol. 7. · Zbl 1348.93082
[12] Drocourt, C., Delahoche, L., Brassart, E., & Clerentin, A. (2005). Incremental construction of the robot environmental map using interval analysis, Global Optimization and Constraint Satisfaction: Second International Workshop, COCOS 2003, 127-141.
[13] Gning, A; Bonnifait, P, Constraints propagation techniques on intervals for a guaranteed localization using redundant data, Automatica, 42, 1167-1175, (2006) · Zbl 1117.93367
[14] Jaulin, L. (2009). A Nonlinear Set-membership Approach for the Localization and Map Building of an Underwater Robot using Interval Constraint Propagation. IEEE Transaction on Robotics, 88-98.
[15] Jaulin, L., & maps, Range-only SLAM with occupancy (2011). A set-membership approach. IEEE Transaction on Robotics, 1004-1010.
[16] Jaulin, L. (2012). Solving set-valued constraint satisfaction problems. Computing, 297-311. · Zbl 1282.62008
[17] Jaulin, L. (2015). MSLAM, a solver for range-only SLAM with indistinguisable landmarks, available at www.ensta-bretagne.fr/jaulin/mslam.html, LabSTICC, ENSTA Bretagne.
[18] Jaulin, L., Kieffer, M., Didrit, O., & Walter, E. (2001). Applied interval analysis, with examples in parameter and state estimation, robust rontrol and robotics. London: Springer-Verlag. · Zbl 1023.65037
[19] Kurzhanski, A., & Valyi, I. (1997). Ellipsoidal Calculus for Estimation and Control. MA: Birkhauser. · Zbl 0865.93001
[20] Le Bars, F., Sliwka, J., Reynet, O., & Jaulin, L. (2012). State estimation with fleeting data. Automatica, 381-387. · Zbl 1260.93153
[21] Leonard, J. J., & Durrant-Whyte, H. F. (1992). Dynamic map building for an autonomous mobile robot. · Zbl 0760.68008
[22] Messine, F. (2004). Deterministic global optimization using interval constraint propagation techniques. Operations Research, 277-293. · Zbl 1114.90156
[23] Newman, P., & Leonard, J. (2003). Pure range-only sub-sea slam, ICRA03, pp. 1921-1926. Washington. · Zbl 1191.68628
[24] Sainudiin, R. (2010). Machine interval experiments: Accounting for the physical limits on empirical and numerical resolutions. Germany: LAP Academic, Koln. · Zbl 1153.68457
[25] Soares, G., Arnold-Bos, A., Jaulin, L., Vasconcelos, J. A., & Maia, C. A. (2008). An interval-based target tracking approach for range-only multistatic radar. IEEE Transactions on Magnetics, 1350-1353.
[26] Spletzer, J. (2004). A new approach to range-only slam for wireless sensor networks, LU-CSE-04-008. Lehigh University. · Zbl 1117.93367
[27] Tarski, A. (1955). A lattice-theoretical fixpoint theorem and its applications. Pacific Journal of Mathematics, 285-309. · Zbl 0064.26004
[28] Thrun, S., Bugard, W., & Fox, D. (2005). Probabilistic Robotics. Cambridge: MIT Press. · Zbl 1081.68703
[29] Trombettoni, G., & Chabert, G. (2007). Constructive Interval Disjunction. In Proc. CP, Constraint Programming, LNCS 4741 (pp. 635-650). · Zbl 1145.68530
[30] Tucker, W. (2002). A Rigorous ODE Solver and Smale’s 14th Problem. Foundations of Computational Mathematics, 53-117. · Zbl 1047.37012
[31] van Emden, M. (1999). Algorithmic power from declarative use of redundant constraints, p. 363-381. · Zbl 0949.68041
[32] van Hentenryck, P., Deville, Y., & Michel, L. (1997). Numerica: A modeling language for global optimization. MA: MIT Press. · Zbl 0930.68164
[33] Waltz, D. (1975). Generating semantic descriptions from drawings of scenes with shadows. In P. H. Winston (Ed.), The Psychology of Computer Vision (pp. 19-91). New York: McGraw-Hill.
[34] Wilczak, D., & Zgliczynski, P. (2011). Cr-lohner algorithm. Schedae Informaticae, 9-46.
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.