Robust Localization Algorithm for Indoor Robots Based on the Branch-and-Bound Strategy
by Huaxi (Yulin) Zhang 1, Yuyang Wang2, Xiaochuan Luo*, 3 
, Baptiste Mereaux4, Lei Zhang5
1 LTI, Université de Picardie Jules Verne, Saint Quentin, 02100, France
2 Shanghai Research Institute for Intelligent Autonomous Systems, Tongji University, Shanghai, 201210, China
3 College of Information Science and Engineering,Northeastern University, Shenyang, 110819, China
4 Independent Researcher, Saint Quentin, 02100, France
5 euroDAO S.A.S., Saint Quentin, 02100, France
* Author to whom correspondence should be addressed.
Journal of Engineering Research and Sciences, Volume 3, Issue 2, Page # 22-42, 2024; DOI: 10.55708/js0302004
Keywords: Branch-and-bound, Global Localization, Position tracking, Robot kidnapping
Received: 04 January 2024, Revised: 09 February 2024, Accepted: 14 February 2024, Published Online: 29 February 2024
APA Style
Zhang, H., Wang, Y., Luo, X., Mereaux, B., & Zhang, L. (2024). Robust Localization Algorithm for Indoor Robots Based on the Branch-and-Bound Strategy. Journal of Engineering Research and Sciences, 3(2), 22-42. https://dx.doi.org/10.55708/js0302004
Chicago/Turabian Style
Zhang, Huaxi, Yuyang Wang, Xiaochuan Luo, Baptiste Mereaux, and Lei Zhang. “Robust Localization Algorithm for Indoor Robots Based on the Branch-and-Bound Strategy.” Journal of Engineering Research and Sciences 3, no. 2 (2024): 22-42. https://dx.doi.org/10.55708/js0302004.
IEEE Style
H. Zhang, Y. Wang, X. Luo, B. Mereaux, and L. Zhang, “Robust Localization Algorithm for Indoor Robots Based on the Branch-and-Bound Strategy,” Journal of Engineering Research and Sciences, vol. 3, no. 2, pp. 22-42, 2024. https://dx.doi.org/10.55708/js0302004.
146 Downloads
Abstract
Full Text
References
Cited By
Metrics
Abstract
Robust and accurate localization is crucial for mobile robot navigation in complex indoor environments. This paper introduces a robust and integrated robot localization algorithm designed for such environments. The proposed algorithm, named Branch-and-Bound for Robust Localization (BB-RL), introduces an innovative approach that seamlessly integrates global localization, position tracking, and resolution of the kidnapped robot problem into a single, comprehensive framework. The process of global localization in BB-RL involves a two-stage matching approach, moving from a broad to a more detailed analysis. This method combines a branch-and-bound algorithm with an iterative nearest point algorithm, allowing for an accurate initial estimation of the robot’s position. For ongoing position tracking, BB-RL uses a local map-based scan matching technique. To address inaccuracies that accumulate over time in the local maps, the algorithm creates a pose graph which helps in loop-closure optimization. Additionally, to make loop-closure detection less computationally intensive, the branch-and-bound algorithm is used to speed up finding loop constraints. A key feature of BB-RL is its Finite State Machine (FSM)-based relocalization judgment method, which is designed to quickly identify and resolve the kidnapped robot problem. This enhances the reliability of the localization process. BB-RL’s performance was thoroughly tested in real-world situations using commercially available logistics robots. These tests showed that BB-RL is fast, accurate, and robust, making it a practical solution for indoor robot localization.
Full Text
References
- DeSouza, Guilherme N and Kak, Avinash C, “Vision for mobile robot navigation: A survey”, IEEE transactions on pattern analysis and machine intelligence, vol. 24, no. 2, pp. 237–267, 2002.
- Georgiev, Atanas and Allen, Peter K, “Localization methods for a mobile robot in urban environments”, IEEE Transactions on Robotics, vol. 20, no. 5, 851–864, 2004.
- Alatise, Mary B and Hancke, Gerhard P, “A review on challenges of au- tonomous mobile robot and sensor fusion methods”, IEEE Access, vol. 8, pp. 39830–39846,
- Altan, Aytac¸ and Bayraktar, Ko¨ ksal and Hacıog˘ lu, Rıfat, “Simultaneous localization and mapping of mines with unmanned aerial vehicle”, 2016 24th Signal Processing and Communication Application Conference (SIU), 1433–1436, 2016, doi:10.1109/SIU.2016.7496019.
- Aytac¸ Altan and Rıfat Hacıog˘ lu, “Model predictive control of three-axis gimbal system mounted on uav for real-time target tracking under external disturbances”, Mechanical Systems and Signal Processing, vol. 138, p. 106548, 2020, doi:https://doi.org/10.1016/j.ymssp.2019.106548.
- Cox, Ingemar Johansson and Wilfong, Gordon Thomas, Autonomous robot vehicles, Springer, Schweiz, 1990.
- Thrun, Sebastian and Beetz, Michael and Bennewitz, Maren and Burgard, Wolfram and Cremers, Armin B and Dellaert, Frank and Fox, Dieter and Haehnel, Dirk and Rosenberg, Chuck and Roy, Nicholas and others, “Probabilistic algorithms and the interactive museum tour-guide robot minerva”, The international journal of robotics research, 19, no. 11, pp. 972–999, 2000.
- Alqahtani, Ebtesam J and Alshamrani, Fatimah H and Syed, Hajra F and Alhaidari, Fahd A, “Survey on algorithms and techniques for indoor navigation systems.”, 2018 21st Saudi Computer Society National Computer Conference (NCC), pp. 1–9, 2018, doi:10.1109/NCG.2018.8593096.
- Zafari, Faheem and Gkelias, Athanasios and Leung, Kin K, “A survey of indoor localization systems and technologies”, IEEE Communications Surveys & Tutorials, vol. 21, no. 3, pp. 2568–2599, 2019, doi: 1109/COMST.2019.2911558.
- Liu, Wenxin and Caruso, David and Ilg, Eddy and Dong, Jing and Mourikis, Anastasios I and Daniilidis, Kostas and Kumar, Vijay and Engel, Jakob, “Tlio: Tight learned inertial odometry”, IEEE Robotics and Automation Letters, 5, no. 4, pp. 5653–5660, 2020, doi:10.1109/LRA.2020.3007421.
- Brossard, Martin and Bonnabel, Silvere, “Learning wheel odometry and imu errors for localization”, 2019 International Conference on Robotics and Automation (ICRA), 291–297, 2019, doi:10.1109/ICRA.2019.8794237.
- Moore, Thomas and Stouch, Daniel, “Intelligent autonomous systems 13”, 335–348, Springer, Padua, 2016, doi:10.1007/978-3-319-08338-4 25.
- He, Chengyang and Tang, Chao and Yu, Chengpu, “A federated derivative cubature kalman filter for imu-uwb indoor positioning”, Sensors, vol. 20, 12, p. 3514, 2020, doi:10.3390/s20123514.
- Liu, Fei and Li, Xin and Wang, Jian and Zhang, Jixian, “An adaptive uwb/mems-imu complementary kalman filter for indoor location in nlos environment”, Remote Sensing, vol. 11, no. 22, p. 2628, 2019, doi: 3390/rs11222628.
- Cui, Jishi and Li, Bin and Yang, Lyuxiao and Wu, Nan, “Multi-source data fusion method for indoor localization system”, 2020 IEEE/CIC International Conference on Communications in China (ICCC), pp. 29–33, 2020, doi:10.1109/ICCC49849.2020.9238826.
- Yang, Xiaofei and Wang, Jun and Song, Dapeng and Feng, Beizhen and Ye, Hui, “A novel nlos error compensation method based imu for uwb indoor positioning system”, IEEE Sensors Journal, vol. 21, no. 9, pp. 11203–11212, 2021, doi:10.1109/JSEN.2021.3061468.
- Davison, Andrew J and Reid, Ian D and Molton, Nicholas D and Stasse, Olivier, “Monoslam: Real-time single camera slam”, IEEE transactions on pattern analysis and machine intelligence, vol. 29, no. 6, pp. 1052–1067, 2007, doi:10.1109/TPAMI.2007.1049.
- Pire, Taihu´ and Fischer, Thomas and Castro, Gasto´n and De Cristo´foris, Pablo and Civera, Javier and Berlles, Julio Jacobo, “S-ptam: Stereo parallel tracking and mapping”, Robotics and Autonomous Systems, vol. 93, pp. 27–42, 2017, doi:10.1016/j.robot.2017.03.019.
- Kerl, Christian and Sturm, Ju¨rgen and Cremers, Daniel, “Dense visual slam for rgb-d cameras”, 2013 IEEE/RSJ International Conference on Intelligent Robots and Systems, pp. 2100–2106, 2013, doi:10.1109/IROS.2013.6696650.
- Mur-Artal, Raul and Montiel, Jose Maria Martinez and Tardos, Juan D, “Orb-slam: a versatile and accurate monocular slam system”, IEEE transactions on robotics, vol. 31, no. 5, pp. 1147–1163, 2015, doi: 1109/TRO.2015.2463671.
- Engel, Jakob and Koltun, Vladlen and Cremers, Daniel, “Direct sparse odometry”, IEEE transactions on pattern analysis and machine intelligence, 40, no. 3, pp. 611–625, 2017, doi:10.1109/TPAMI.2017.2658577.
- Engel, Jakob and Scho¨ps, Thomas and Cremers, Daniel, “Lsd-slam: Large- scale direct monocular slam”, European conference on computer vision, 834–849, 2014, doi:10.1007/978-3-319-10605-2 54.
- Forster, Christian and Pizzoli, Matia and Scaramuzza, Davide, “Svo: Fast semi-direct monocular visual odometry”, 2014 IEEE international conference on robotics and automation (ICRA), pp. 15–22, 2014, doi: 1109/ICRA.2014.6906584.
- Campos, Carlos and Elvira, Richard and Rodr´ıguez, Juan J Go´mez and Mon- tiel, Jose´ MM and Tardo´s, Juan D, “Orb-slam3: An accurate open-source library for visual, visual–inertial, and multimap slam”, IEEE Transactions on Robotics, 2021, doi:10.1109/TRO.2021.3075644.
- Schubert, David and Demmel, Nikolaus and von Stumberg, Lukas and Usenko, Vladyslav and Cremers, Daniel, “Rolling-shutter modelling for direct visual-inertial odometry”, 2019 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pp. 2462–2469, 2019, doi:10.1109/IROS40897.2019.8968539.
- Li, Guangqiang and Yu, Lei and Fei, Shumin, “A deep-learning real-time visual slam system based on multi-task feature extraction network and self-supervised feature points”, Measurement, vol. 168, p. 108403, 2021, doi:10.1016/j.measurement.2020.108403.
- Kang, Rong and Shi, Jieqi and Li, Xueming and Liu, Yang and Liu, Xiao, “Df-slam: A deep-learning enhanced visual slam system based on deep local features”, arXiv preprint arXiv:1901.07223, 2019.
- Li, Ruihao and Wang, Sen and Long, Zhiqiang and Gu, Dongbing, “Un- deepvo: Monocular visual odometry through unsupervised deep learning”, 2018 IEEE international conference on robotics and automation (ICRA), 7286–7291, 2018, doi:10.1109/ICRA.2018.8461251.
- Mur-Artal, Raul and Tardo´s, Juan D, “Orb-slam2: An open-source slam system for monocular, stereo, and rgb-d cameras”, IEEE transactions on robotics, 33, no. 5, pp. 1255–1262, 2017, doi:10.1109/TRO.2017.2705103.
- Campos, Carlos and Elvira, Richard and Rodr´ıguez, Juan J Go´mez and Mon- tiel, Jose´ MM and Tardo´s, Juan D, “Orb-slam3: An accurate open-source library for visual, visual–inertial, and multimap slam”, IEEE Transactions on Robotics, vol. 37, no. 6, pp. 1874–1890, 2021.
- Gomez-Ojeda, Ruben and Moreno, Francisco-Angel and Zuniga-Noe¨l, David and Scaramuzza, Davide and Gonzalez-Jimenez, Javier, “Pl-slam: A stereo slam system through the combination of points and line segments”, IEEE Transactions on Robotics, vol. 35, no. 3, pp. 734–746, 2019, doi: 1109/TRO.2019.2899783.
- Cvisˇic´, Igor and Markovic´, Ivan and Petrovic´, Ivan, “Soft2: Stereo visual odometry for road vehicles based on a point-to-epipolar-line metric”, IEEE Transactions on Robotics, 273–288, 2023, doi:10.1109/TRO.2022. 3188121.
- Zhou, Yi and Gallego, Guillermo and Shen, Shaojie, “Event-based stereo visual odometry”, IEEE Transactions on Robotics, 2021, doi: 1109/TRO.2021.3062252.Labbe´, Mathieu and Michaud, Franc¸ois, “Rtab-map as an open-source lidar and visual simultaneous localization and mapping library for large-scale and long-term online operation”, Journal of Field Robotics, vol. 36, no. 2, pp. 416–446, 2019, doi:10.1002/rob.21831.
- Labbe´, Mathieu and Michaud, Franc¸ois, “Rtab-map as an open-source lidar and visual simultaneous localization and mapping library for large-scale and long-term online operation”, Journal of Field Robotics, vol. 36, no. 2, pp. 416–446, 2019, doi:10.1002/rob.21831.
- Dai, Angela and Nießner, Matthias and Zollho¨fer, Michael and Izadi, Shahram and Theobalt, Christian, “Bundlefusion: Real-time globally consistent 3d reconstruction using on-the-fly surface reintegration”, ACM Transactions on Graphics (ToG), 36, no. 4, p. 1, 2017, doi:10.1145/3072959.3054739.Whelan, Thomas and Kaess, Michael and Fallon, Maurice and Johannsson, Hordur and Leonard, John and McDonald, John, “Kintinuous: Spatially extended kinectfusion”, 2012.
- Whelan, Thomas and Kaess, Michael and Fallon, Maurice and Johannsson, Hordur and Leonard, John and McDonald, John, “Kintinuous: Spatially extended kinectfusion”, 2012.
- Rosinol, Antoni and Abate, Marcus and Chang, Yun and Carlone, Luca, “Kimera: an open-source library for real-time metric-semantic localization and mapping”, 2020 IEEE International Conference on Robotics and Automation (ICRA), pp. 1689–1696, 2020, doi:10.1109/ICRA40945.2020.9196885.
- Bruno, Hudson and Colombini, Esther, “Lift-slam: a deep-learning feature-based monocular visual slam method”, Neurocomputing, vol. 455, 2021, doi:10.1016/j.neucom.2021.05.027.
- “Objectfusion: Accurate object-level slam with neural object priors”, Graphical Models, 123, p. 101165, 2022, doi:https://doi.org/10.1016/j.gmod. 2022.101165.
- Qing Li and Rui Cao and Jiasong Zhu and Hao Fu and Baoding Zhou and Xu Fang and Sen Jia and Shenman Zhang and Kanglin Liu and Qingquan Li, “Learn then match: A fast coarse-to-fine depth image- based indoor localization framework for dark environments via deep learn- ing and keypoint-based geometry alignment”, ISPRS Journal of Photogrammetry and Remote Sensing, vol. 195, pp. 169–177, 2023, doi: https://doi.org/10.1016/j.isprsjprs.2022.10.015.
- Zhang, Ji and Singh, Sanjiv, “Loam: Lidar odometry and mapping in real-time.”, Robotics: Science and Systems, vol. 2, 2014.
- Koide, Kenji and Miura, Jun and Menegatti, Emanuele, “A portable 3d lidar-based system for long-term and wide-area people behavior measurement”, IEEE Trans. Hum. Mach. Syst, 2018, doi:10.1177/1729881419841532.
- Chen, Xieyuanli and Milioto, Andres and Palazzolo, Emanuele and Giguere, Philippe and Behley, Jens and Stachniss, Cyrill, “Suma++: Efficient lidar-based semantic slam”, 2019 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pp. 4530–4537, 2019, doi: 1109/IROS40897.2019.8967704.
- Shan, Tixiao and Englot, Brendan, “Lego-loam: Lightweight and ground- optimized lidar odometry and mapping on variable terrain”, 2018 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pp. 4758–4765, 2018, doi:10.1109/IROS.2018.8594299.
- Shan, Tixiao and Englot, Brendan and Meyers, Drew and Wang, Wei and Ratti, Carlo and Rus, Daniela, “Lio-sam: Tightly-coupled lidar inertial odometry via smoothing and mapping”, 2020 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pp. 5135–5142, 2020, doi:10.1109/IROS45743.2020.9341176.
- Montemerlo, Michael and Thrun, Sebastian and Koller, Daphne and Weg- breit, Ben and others, “Fastslam: A factored solution to the simultaneous localization and mapping problem”, Aaai/iaai, vol. 593598, 2002.
- Grisetti, Giorgio and Stachniss, Cyrill and Burgard, Wolfram, “Improved techniques for grid mapping with rao-blackwellized particle filters”, IEEE transactions on Robotics, vol. 23, no. 1, pp. 34–46, 2007, doi:10.1109/TRO.2006.889486.
- Konolige, Kurt and Grisetti, Giorgio and Ku¨ mmerle, Rainer and Burgard, Wolfram and Limketkai, Benson and Vincent, Regis, “Efficient sparse pose ad- justment for 2d mapping”, 2010 IEEE/RSJ International Conference on Intelli- gent Robots and Systems, pp. 22–29, 2010, doi:10.1109/IROS.2010.5649043.
- Hess, Wolfgang and Kohler, Damon and Rapp, Holger and Andor, Daniel, “Real-time loop closure in 2d lidar slam”, 2016 IEEE International Conference on Robotics and Automation (ICRA), pp. 1271–1278, 2016, doi: 1109/ICRA.2016.7487258.
- Konolige, Kurt and Grisetti, Giorgio and Ku¨ mmerle, Rainer and Burgard, Wolfram and Limketkai, Benson and Vincent, Regis, “Efficient sparse pose ad- justment for 2d mapping”, 2010 IEEE/RSJ International Conference on Intelligent Robots and Systems, pp. 22–29, 2010, doi:10.1109/IROS.2010.5649043.
- Kohlbrecher, Stefan and Von Stryk, Oskar and Meyer, Johannes and Klingauf, Uwe, “A flexible and scalable slam system with full 3d motion estimation”, 2011 IEEE international symposium on safety, security, and rescue robotics, 155–160, 2011, doi:10.1109/SSRR.2011.6106777.
- Lv, Wenjun and Kang, Yu and Qin, Jiahu, “Indoor localization for skid- steering mobile robot by fusing encoder, gyroscope, and magnetometer”, IEEE Transactions on Systems, Man, and Cybernetics: Systems, vol. 49, 6, pp. 1241–1253, 2017, doi:10.1109/TSMC.2017.2701353.
- Jiang, Ping and Chen, Liang and Guo, Hang and Yu, Min and Xiong, Jian, “Novel indoor positioning algorithm based on lidar/inertial measurement unit integrated system”, International Journal of Advanced Robotic Systems, 18, no. 2, p. 1729881421999923, 2021, doi:10.1177/1729881421999923.
- Ismail, Zool H and Bukhori, Iksan, “Efficient detection of robot kidnapping in range finder-based indoor localization using quasi-standardized 2d dynamic time warping”, Applied Sciences, vol. 11, no. 4, p. 1580, 2021, doi:10.3390/app11041580.
- Zhang, Lei, “Self-adaptive markov localization for single-robot and multi-robot systems”, Ph.D. thesis, Universite´ Montpellier II-Sciences et Tech- niques du Languedoc, 2010.
- Zhang, Lei and Zapata, Rene and Lepinay, Pascal, “Self-adaptive Monte Carlo localization for mobile robots using range finders”, Robotica, 30, no. 2, pp. 229–244, 2012, doi:10.1017/S0263574711000567.
- Zhang, Lei and Zapata, Rene´ and Le´pinay, Pascal, “Self-adaptive Monte Carlo localization for mobile robots using range sensors”, 2009 IEEE/RSJ International Conference on Intelligent Robots and Systems, pp. 1541–1546, 2009, doi:10.1109/IROS.2009.5354298.
- Zhang, Lei and Zapata, Rene´, “A three-step localization method for mobile robots”, Proceedings of International Conference on Automation, Robotics and Control Systems (ARCS 2009), pp. 50–56, 2009.
- Zhang, Lei and Zapata, Rene´, “Probabilistic localization methods of a mobile robot using ultrasonic perception system”, 2009 International Conference on Information and Automation, pp. 1062–1067, 2009, doi: 1109/ICINFA.2009.5205075.
- Yu, Wei and Li, Jie and Yuan, Jing and Ji, Xi, “Indoor mobile robot positioning based on uwb and low cost imu”, 2021 IEEE 5th Advanced Information Technology, Electronic and Automation Control Conference (IAEAC), vol. 5, 1239–1246, 2021, doi:10.1109/IAEAC50856.2021.9390754.
- Liu, Jianfeng and Pu, Jiexin and Sun, Lifan and He, Zishu, “An approach to robust ins/uwb integrated positioning for autonomous indoor mobile robots”, Sensors, vol. 19, no. 4, p. 950, 2019, doi:10.3390/s19040950.
- Cui, Wei and Liu, Qingde and Zhang, Linhan and Wang, Haixia and Lu, Xiao and Li, Junliang, “A robust mobile robot indoor positioning system based on wi-fi”, International Journal of Advanced Robotic Systems, vol. 17, 1, p. 1729881419896660, 2020, doi:10.1177/1729881419896660.
- Motroni, Andrea and Nepa, Paolo and Buffi, Alice and Tellini, Bernardo, “Robot localization via passive uhf-rfid technology: State-of-the-art and challenges”, 2020 IEEE International Conference on RFID (RFID), pp. 1–8, 2020, doi:10.1109/RFID49298.2020.9244884.
- Bernardini, Fabio and Buffi, Alice and Fontanelli, Daniele and Macii, David and Magnago, Valerio and Marracci, Mirko and Motroni, Andrea and Nepa, Paolo and Tellini, Bernardo, “Robot-based indoor positioning of uhf-rfid tags: The sar method with multiple trajectories”, IEEE Transactions on Instrumentation and Measurement, vol. 70, pp. 1–15, 2020, doi:10.1109/TIM.2020.3033728.
- Al-Forati, Israa Sabri Abdulameer and Rashid, Abdulmuttalib, “Design and implementation an indoor robot localization system using minimum bounded circle algorithm”, 2019 8th International Conference on Modeling Simulation and Applied Optimization (ICMSAO), pp. 1–6, 2019, doi:10.1109/ICMSAO.2019.8880404.
- Alfurati, IS and Rashid, Abdulmuttalib T, “An efficient mathematical approach for an indoor robot localization system”, Iraqi Journal of Electrical and Electronic Engineering, vol. 15, no. 2, pp. 61–70, 2019, doi: 37917/ijeee.15.2.7.
- Albuquerque, Daniel F and Gonc¸alves, Edgar S and Pedrosa, Eurico F and Teixeira, Francisco C and Vieira, Jose´ N, “Robot self position based on asynchronous millimetre wave radar interference”, 2019 International Conference on Indoor Positioning and Indoor Navigation (IPIN), pp. 1–6, 2019, doi:10.1109/IPIN.2019.8911809.
- Perez-Grau, Francisco J and Caballero, Fernando and Viguria, Antidio and Ollero, Anibal, “Multi-sensor three-dimensional monte carlo localization for long-term aerial robot navigation”, International Journal of Advanced Robotic Systems, vol. 14, no. 5, p. 1729881417732757, 2017.
- Chen, Xieyuanli and La¨be, Thomas and Nardi, Lorenzo and Behley, Jens and Stachniss, Cyrill, “Learning an overlap-based observation model for 3d lidar localization”, 2020 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pp. 4602–4608, IEEE, 2020.
- Wolfgang Hess and Damon Kohler and Holger Rapp and Daniel Andor, “Real-time loop closure in 2d LIDAR SLAM”, 2016 IEEE International Con- ference on Robotics and Automation, ICRA 2016, Stockholm, Sweden, May 16-21, 2016, pp. 1271–1278, IEEE, 2016, doi:10.1109/ICRA.2016.7487258.
- Koki Aoki and Kenji Koide and Shuji Oishi and Masashi Yokozuka and Atsuhiko Banno and Junichi Meguro, “3d-bbs: Global localization for 3d point cloud scan matching using branch-and-bound algorithm”, CoRR, vol. abs/2310.10023, 2023, doi:10.48550/ARXIV.2310.10023.
Cited By
Metrics
