Navigating in Complex Indoor Environments: A Comparative Study

Yıl 2023, Cilt: 3 Sayı: 2, 124 - 137, 15.12.2023

Alper Hüseyin Doğan Tarık Veli Mumcu

Öz

Autonomous robots face significant challenges in path planning and continuous motion planning in indoors due to their ability to navigate within these complex spaces. These complex problems arise in a wide range of application environments, including indoor areas such as corridors, rooms, and similar spaces. This study presents a comparative simulation analysis of path-finding techniques employed for indoor autonomous robot navigation. Conventional path-finding techniques, including Voronoi diagram and potential field, have been selected to illustrate these established methods. However, they were found to be unreliable and insufficient in coping with the intricacies of real-world situations characterised by non-linearity. Various artificial intelligence techniques were evaluated to showcase the superiority of artificial intelligence over conventional methods. The methods included genetics algorithm and neural networks. The use of these artificial intelligence methods proved their ability to handle complex navigation tasks with greater ease and strength, highlighting their vital contribution in overcoming obstacles. Additionally, we utilize the well-known A* algorithm as a benchmark to evaluate and compare the performance of filtering techniques, particularly Kalman and particle filters in the context of path tracking under diverse conditions, including scenarios with gaussian and exponential noise. Through these analyses, we shed light on the performance of Kalman and particle filters when applied in conjunction with the A* algorithm for path tracking, offering valuable insights into their effectiveness in real-world, noisy environments.

Anahtar Kelimeler

Adaptive Path Planning, autonomous robot navigation, path tracking

Kaynakça

• [1] G. Fragapane, R. De Koster, F. Sgarbossa, and J. O. J. E. J. o. O. R. Strandhagen, "Planning and control of autonomous mobile robots for intralogistics: Literature review and research agenda," vol. 294, no. 2, pp. 405-426, 2021.
• [2] J. A. Oroko and G. Nyakoe, "Obstacle avoidance and path planning schemes for autonomous navigation of a mobile robot: a review," in Proceedings of the Sustainable Research and Innovation Conference, 2022, pp. 314-318.
• [3] N. Adzhar, Y. Yusof, M. A. J. A. i. S. Ahmad, Technology, and E. S. Journal, "A review on autonomous mobile robot path planning algorithms," vol. 5, no. 3, pp. 236-240, 2020.
• [4] J. R. Sanchez-Ibanez, C. J. Perez-del-Pulgar, and A. J. S. García-Cerezo, "Path planning for autonomous mobile robots: A review," vol. 21, no. 23, p. 7898, 2021.
• [5] D. Chen, A. Xiao, M. Zou, W. Chi, J. Wang, and L. J. a. p. a. Sun, "GVD-Exploration: An Efficient Autonomous Robot Exploration Framework Based on Fast Generalized Voronoi Diagram Extraction," 2023.
• [6] G. Klančar, A. Zdešar, and M. J. S. Krishnan, "Robot Navigation Based on Potential Field and Gradient Obtained by Bilinear Interpolation and a Grid-Based Search," vol. 22, no. 9, p. 3295, 2022.
• [7] L. J. I. J. o. C. I. S. Magdalena, "What is soft computing? Revisiting possible answers," vol. 3, no. 2, pp. 148-159, 2010.
• [8] Z. Zhang, R. Lu, M. Zhao, S. Luan, M. J. J. o. I. Bu, and F. Systems, "Robot path planning based on genetic algorithm with hybrid initialization method," vol. 42, no. 3, pp. 2041-2056, 2022.
• [9] F. Cruz, R. Dazeley, P. Vamplew, I. J. N. C. Moreira, and Applications, "Explainable robotic systems: Understanding goal-driven actions in a reinforcement learning scenario," vol. 35, no. 25, pp. 18113-18130, 2023.
• [10] D. Foead, A. Ghifari, M. B. Kusuma, N. Hanafiah, and E. J. P. C. S. Gunawan, "A systematic literature review of A* pathfinding," vol. 179, pp. 507-514, 2021.
• [11] C. Urrea and R. J. J. o. S. Agramonte, "Kalman filter: historical overview and review of its use in robotics 60 years after its creation," vol. 2021, pp. 1-21, 2021.
• [12] Y. Wang, X. J. C. i. Wang, and neuroscience, "Research on SLAM road sign observation based on particle filter," vol. 2022, 2022.
• [13] R. C. J. T. I. j. o. r. r. Arkin, "Motor schema—based mobile robot navigation," vol. 8, no. 4, pp. 92-112, 1989.
• [14] D. M. J. I. A. T. O. M. Auslander, "What is mechatronics?," vol. 1, no. 1, pp. 5-9, 1996.
• [15] R. H. Bishop, The mechatronics handbook-2 volume set. CRC press, 2002.
• [16] J. J. A. Mireles Jr and U. o. T. a. A. Robotics Research Institute, "Kinematic models of mobile robots," 2004.
• [17] M. I. Ribeiro and P. J. I. d. S. e. R. Lima, "Kinematics models of mobile robots," vol. 1000, p. 1049, 2002.
• [18] R. Siegwart, I. R. Nourbakhsh, and D. Scaramuzza, Introduction to autonomous mobile robots. MIT press, 2011.
• [19] Z. Liang, X. Ma, and X. Dai, "Extended Monte Carlo algorithm to collaborate distributed sensors for mobile robot localization," in 2007 IEEE International Conference on Robotics and Biomimetics (ROBIO), 2007, pp. 1647-1652: IEEE.
• [20] M. Paskin and S. J. a. p. a. Thrun, "Robotic mapping with polygonal random fields," 2012.
• [21] J. Fuentes-Pacheco, J. Ruiz-Ascencio, and J. M. J. A. i. r. Rendón-Mancha, "Visual simultaneous localization and mapping: a survey," vol. 43, pp. 55-81, 2015.
• [22] T. Bailey, J. Nieto, J. Guivant, M. Stevens, and E. Nebot, "Consistency of the EKF-SLAM algorithm," in 2006 IEEE/RSJ International Conference on Intelligent Robots and Systems, 2006, pp. 3562-3568: IEEE.
• [23] R. C. Smith and P. J. T. i. j. o. R. R. Cheeseman, "On the representation and estimation of spatial uncertainty," vol. 5, no. 4, pp. 56-68, 1986.
• [24] G. Dissanayake, H. Durrant-Whyte, and T. Bailey, "A computationally efficient solution to the simultaneous localisation and map building (SLAM) problem," in Proceedings 2000 ICRA. Millennium Conference. IEEE International Conference on Robotics and Automation. Symposia Proceedings (Cat. No. 00CH37065), 2000, vol. 2, pp. 1009-1014: IEEE.
• [25] R. S. Pol and M. Murugan, "A review on indoor human aware autonomous mobile robot navigation through a dynamic environment survey of different path planning algorithm and methods," in 2015 International conference on industrial instrumentation and control (ICIC), 2015, pp. 1339-1344: IEEE.
• [26] P. Cheeseman, R. Smith, and M. Self, "A stochastic map for uncertain spatial relationships," in 4th international symposium on robotic research, 1987, pp. 467-474: MIT Press Cambridge.
• [27] S. Garrido, L. Moreno, M. Abderrahim, and F. Martin, "Path planning for mobile robot navigation using voronoi diagram and fast marching," in 2006 IEEE/RSJ International Conference on Intelligent Robots and Systems, 2006, pp. 2376-2381: IEEE.
• [28] H. Choset and J. Burdick, "Sensor based planning. I. The generalized Voronoi graph," in Proceedings of 1995 IEEE international conference on robotics and automation, 1995, vol. 2, pp. 1649-1655: IEEE.
• [29] P. Bhattacharya, M. L. J. I. R. Gavrilova, and A. Magazine, "Roadmap-based path planning-using the voronoi diagram for a clearance-based shortest path," vol. 15, no. 2, pp. 58-66, 2008.
• [30] R. Mahkovic, T. J. I. T. o. S. Slivnik, Man,, C.-P. A. Systems, and Humans, "Constructing the generalized local Voronoi diagram from laser range scanner data," vol. 30, no. 6, pp. 710-719, 2000.
• [31] R. Marie, H. B. Said, J. Stéphant, O. J. J. o. I. Labbani-Igbida, and R. Systems, "Visual servoing on the generalized voronoi diagram using an omnidirectional camera," vol. 94, pp. 793-804, 2019.
• [32] A. Datta, S. J. I. T. O. S. Soundaralakshmi, Man,, C.-P. A. Systems, and Humans, "Fast parallel algorithm for distance transform," vol. 33, no. 4, pp. 429-434, 2003.
• [33] F. Janabi-Sharifi and D. Vinke, "Integration of the artificial potential field approach with simulated annealing for robot path planning," in Proceedings of 8th IEEE international symposium on intelligent control, 1993, pp. 536-541: IEEE.
• [34] H. Lyu and Y. J. A. S. Yin, "Fast path planning for autonomous ships in restricted waters," vol. 8, no. 12, p. 2592, 2018.
• [35] T. Weerakoon, K. Ishii, A. A. F. J. J. o. A. I. Nassiraei, and S. C. Research, "An artificial potential field based mobile robot navigation method to prevent from deadlock," vol. 5, no. 3, pp. 189-203, 2015.
• [36] J. Zhang, J. Yan, and P. J. I. A. Zhang, "Fixed-wing UAV formation control design with collision avoidance based on an improved artificial potential field," vol. 6, pp. 78342-78351, 2018.
• [37] Z. Wu, G. Hu, L. Feng, J. Wu, and S. J. A. A. Liu, "Collision avoidance for mobile robots based on artificial potential field and obstacle envelope modelling," vol. 36, no. 3, pp. 318-332, 2016.
• [38] F. A. Cosío, M. P. J. M. Castañeda, and c. modelling, "Autonomous robot navigation using adaptive potential fields," vol. 40, no. 9-10, pp. 1141-1156, 2004.
• [39] M. G. Park and M. C. J. K. i. j. Lee, "A new technique to escape local minimum in artificial potential field based path planning," vol. 17, pp. 1876-1885, 2003.
• [40] J. Agirrebeitia, R. Avilés, I. F. De Bustos, G. J. M. Ajuria, and M. Theory, "A new APF strategy for path planning in environments with obstacles," vol. 40, no. 6, pp. 645-658, 2005.
• [41] T. Zhang, Y. Zhu, and J. J. I. R. A. I. J. Song, "Real‐time motion planning for mobile robots by means of artificial potential field method in unknown environment," vol. 37, no. 4, pp. 384-400, 2010.
• [42] T. Shibata and T. J. P. o. t. I. I. S. o. I. C. Fukuda, "Intelligent motion planning by genetic algorithm with fuzzy critic," pp. 565-570, 1993.
• [43] P. J. Angeline, "Genetic programming: On the programming of computers by means of natural selection: John R. Koza, A Bradford Book, MIT Press, Cambridge MA, 1992, ISBN 0-262-11170-5, xiv+ 819pp., US $55.00," ed: Elsevier, 1994.
• [44] Man-Tak Shing and G. B. Parker, "Genetic Algorithms for the Development of Real-Time Multi-Heuristic Search Strategies.," ICGA, pp. 565-572, 1993/7/17.
• [45] P. Shi and Y. Cui, "Dynamic path planning for mobile robot based on genetic algorithm in unknown environment," in 2010 Chinese control and decision conference, 2010, pp. 4325-4329: IEEE.
• [46] R. L. Haupt and S. E. Haupt, Practical genetic algorithms. John Wiley & Sons, 2004.
• [47] P. Beeson, N. K. Jong, and B. Kuipers, "Towards autonomous topological place detection using the extended voronoi graph," in Proceedings of the 2005 IEEE International Conference on Robotics and Automation, 2005, pp. 4373-4379: IEEE.
• [48] Bekey G. A. and G. K.Y., "Neural Networks in Robotics.," Kluwer Academic Publishers, 1993.
• [49] I. Engedy and G. Horváth, "Artificial neural network based mobile robot navigation," in 2009 IEEE International Symposium on Intelligent Signal Processing, 2009, pp. 241-246: IEEE.
• [50] N. Leena, K. J. I. J. o. M. Saju, and C. Engineering, "A survey on path planning techniques for autonomous mobile robots," vol. 8, pp. 76-79, 2014.
• [51] C. Li, J. Zhang, and Y. Li, "Application of artificial neural network based on q-learning for mobile robot path planning," in 2006 IEEE International Conference on Information Acquisition, 2006, pp. 978-982: IEEE.
• [52] P. E. Hart, N. J. Nilsson, B. J. I. t. o. S. S. Raphael, and Cybernetics, "A formal basis for the heuristic determination of minimum cost paths," vol. 4, no. 2, pp. 100-107, 1968.
• [53] N. J. Nilsson, Artificial Intelligence: A New Synthesis. Morgan Kaufmann Publishers Inc., 1998.
• [54] I. Pohl, "Bi-directional and heuristic search in path problems," 1969.
• [55] P. E. Hart and N. J. Nilsson, "A Formal Basis for the Heuristic Determination of Minimum Cost Paths.," EEE Transactions Systems Science and Cybernetics, vol. 4, pp. 100-107, 1968.
• [56] A. Felner, R. E. Korf, and S. J. J. o. A. I. R. Hanan, "Additive pattern database heuristics," vol. 22, pp. 279-318, 2004.
• [57] M. Goldenberg et al., "Enhanced Partial Expansion A*," The Journal of Artificial Intelligence Research (JAIR), vol. 50, 05/01 2014.
• [58] S. Haykin, Kalman filtering and neural networks. John Wiley & Sons, 2004.
• [59] K. Nagarajan, N. Gans, and R. Jafari, "Modeling human gait using a kalman filter to measure walking distance," in Proceedings of the 2nd Conference on Wireless Health, 2011, pp. 1-2.
• [60] F. Ahmed and R. Mandal, "Survey on the Kalman Filter and Related Algorithms," in Int. Res. J. of Eng. and Technol., vol. 5no. 5): International Research Journal of Engineering and Technology (IRJET), 2018, pp. 4219-4223.
• [61] A. Doucet, N. De Freitas, and N. J. S. M. C. m. i. p. Gordon, "An introduction to sequential Monte Carlo methods," pp. 3-14, 2001.
• [62] P. S. Maybeck, "Stochastic models, estimation and control," Navtech Book & Software Store, vol. volume 1, 1994.
• [63] B. Øksendal and B. Øksendal, Stochastic differential equations. Springer, 2003.
• [64] G. Kallianpur, Stochastic filtering theory. Springer Science & Business Media, 2013.
• [65] S. Brahimi, R. Tiar, O. Azouaoui, M. Lakrouf, and M. Loudini, "Car-like mobile robot navigation in unknown urban areas," in 2016 IEEE 19th International Conference on Intelligent Transportation Systems (ITSC), 2016, pp. 1727-1732: IEEE.