A Review on Comparative Analysis of Path Planning and Collision Avoidance Algorithms

Authors: Divya Agarwal, Pushpendra S. Bharti

Abstract:

Autonomous mobile robots (AMR) are expected as smart tools for operations in every automation industry. Path planning and obstacle avoidance is the backbone of AMR as robots have to reach their goal location avoiding obstacles while traversing through optimized path defined according to some criteria such as distance, time or energy. Path planning can be classified into global and local path planning where environmental information is known and unknown/partially known, respectively. A number of sensors are used for data collection. A number of algorithms such as artificial potential field (APF), rapidly exploring random trees (RRT), bidirectional RRT, Fuzzy approach, Purepursuit, A* algorithm, vector field histogram (VFH) and modified local path planning algorithm, etc. have been used in the last three decades for path planning and obstacle avoidance for AMR. This paper makes an attempt to review some of the path planning and obstacle avoidance algorithms used in the field of AMR. The review includes comparative analysis of simulation and mathematical computations of path planning and obstacle avoidance algorithms using MATLAB 2018a. From the review, it could be concluded that different algorithms may complete the same task (i.e. with a different set of instructions) in less or more time, space, effort, etc.

Keywords: Autonomous mobile robots, obstacle avoidance, path planning, and processing time.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1316879

References:

[1] A. Yufka and O. Parlaktuna, “Performance Comparison of Bug Algorithms for Mobile Robots”, 5th International Advanced Technologies Symposium, pp. 1-5, 2009
[2] M.S. Ganeshmurthy, and G.R. Suresh, “Path planning algorithm for autonomous mobile robot in dynamic environment”, International Conference on Signal Processing, Communication and Networking, vol. 3, pp. 1-6, 2015
[3] K. M. Hasan, A. Al-Nahid, and K.J. Reza, “Path planning algorithm development for autonomous vacuum cleaner robots,” In Proceedings International Conference on Informatics, Electronics & Vision, pp. 1-6, 2014
[4] D. Dolgov, S. Thrun, M. Montemerlo, and J. Diebel, “Practical search techniques in path planning for autonomous driving”, AAAI Workshop - Technical Report, 2008.
[5] L. Huang, “Velocity Planning for a Mobile Robot to Track a Moving Target - A Potential Field Approach”, Robotics and Autonomous Systems, vol. 57, pp. 55-63, 2009
[6] Y.W. Chen, and W.Y. Chiu, “Optimal Robot Path Planning System by Using a Neural Network-Based Approach”, Proceedings of IEEE International Automatic Control Conference (CACS), pp. 85-90, 2015
[7] E.H. Shan, B. Dai, J. Song, and Z.P. Sun, “A dynamic RRT path planning algorithm based on B-spline,” In Proc. International Symposium on Computational Intelligence and Design, pp. 25-29, 2009
[8] J. J. Kuffner and S. M. LaValle, “RRT-connect: An efficient approach to single-query path planning,” in Proc. IEEE International Conf. on Robotics and Automation, pp. 995-1001, 2000
[9] A. Stentz, “Optimal and efficient path planning for partially-known environments,” In Proc. IEEE International Conf. on Robotics and Automation, pp. 3310-3317, 1994
[10] Z.J. Du, D.K. Qu, F. Xu, and D.G. Xu, “A hybrid approach for mobile robot path planning in dynamic environments,” In Proc. IEEE International Conf. on Robotics and Biomimetics, pp. 1058-1063, 2012
[11] M. Samuel, M. Hussein and M.B. Mohamad, “A Review of some Pure-Pursuit based Path Tracking Techniques for Control of Autonomous Vehicle”, International Journal of Computer Applications, vol. 135, no. 1, pp. 35- 38, 2016
[12] C. Wong, H. Wang, and S. Li, “PSO-based Motion Fuzzy Controller Design for Mobile Robots”, International Journal of Fuzzy Systems, vol. 10, issue no. 1, pp. 284-292, 2008
[13] H.Y. Chung, C.C. Hou and S.C. Liu, “Automatic Navigation of a Wheeled Mobile Robot using Particle Swarm Optimization and Fuzzy Control”, IEEE International Symposium on Industrial Electronics, Taiwan, pp. 1-6, 2013
[14] Y. Zhang, D.W. Gong, J.H. Zhang, “Robot Path Planning in Uncertain Environment using Multi-Objective Particle Swarm Optimization”, Elsevier Neurocomputing, vol. 103, pp. 172-185, 2013
[15] L.E. Zarate, M. Becker, B.D.M. Garrido, and H.S.C. Rocha, “An artificial neural network structure able to obstacle avoidance behaviour used in mobile robots”. IEEE Annual Conference of the Industrial Electronics Society, vol. 28, pp. 2457-246, 2002
[16] S.X. Yang and C. Luo, “A neural network approach to complete coverage path planning”, IEEE Transactions on Systems, Man and Cybernetics, vol. 34, issue 1, pp. 718-724, 2004
[17] K. Sedighi, K. Ashenayi, R. Wainwright and H. Tai, “Autonomous local path planning for a mobile robot using a genetic algorithm”, IEEE Congress on Evolutionary Computation, vol. 2, pp. 1338–1345, 2004
[18] P.O. Petterssonand P. Doherty, “Probabilistic roadmap based path planning for an autonomous unmanned helicopter’”, Journal of Intelligent & Fuzzy Systems: Applications in Engineering and Technology, vol. 17, no. 4, pp. 395-405, 2005
[19] H. Kristo, “Path Planning and Learning Strategies for Mobile Robots in Dynamic Partially Unknown Environments’”, Faculty of Mathematics and Computer Science, pp. 19-32, 2006
[20] R. Kala, A. Shukla, R. Tiwari, S. Roongta and R.R. Janghel, “Mobile Robot Navigation Control in Moving Obstacle Environment using Genetic Algorithm, Artificial Neural Networks and A* Algorithm”, Proceedings of the IEEE World Congress on Computer Science and Information Engineering, pp. 705-713, 2009
[21] L. Yang, J. Qi, D. Song, J. Xiao, J. Han and Y. Xia, “Survey of Robot 3D Path Planning Algorithms", Journal of Control Science and Engineering, vol. 2016, Article ID 7426913, 22 pages, 2016
[22] D. Nguyen and T. Nguyen, “A solution of obstacle collision avoidance for robotic fish based on fuzzy systems” IEEE International Conference on Robotics and Biomimetics (ROBIO), pp. 7-11 2011
[23] I. Ullah, F. Ullah, Q. Ullah and S. Shin, “Integrated tracking and accident avoidance system for mobile robots”, International Journal of Control, Automation and Systems, pp. 1253-1265, 2013
[24] J. A. Oroko and G. N. Nyakoe, “Obstacle Avoidance and Path Planning Schemes for Autonomous Navigation of a Mobile Robot: A Review”, Proceedings of Mechanical Engineering Conference on Sustainable Research and Innovation, Vol. 4, pp. 314-318, 2012
[25] L. Zeng and G.M. Bone, “Mobile Robot Collision Avoidance in Human Environments”, International Journal of Advanced Robotic Systems, vol. 10, pp. 1-14, 2013,
[26] A. Mohammadi, M. Rahimi, and A.A. Suratgar, “A New Path Planning and Obstacle Avoidance Algorithm in Dynamic Environment”, IEEE Iranian Conference on Electrical Engineering (ICEE 2014), vol. 22, pp. 1301-1306, 2014
[27] K.H. Su, F.L. Lian and C.Y. Yang, “Navigation design with SVM path planning and fuzzy-based path tracking for wheeled agent”, International Conference onFuzzy Theory and it’s Applications (iFUZZY), pp. 273,278, 2012
[28] M.Y. Ju and C.W. Cheng, “Smooth path planning using genetic algorithms”, World Congress onIntelligent Control and Automation (WCICA), vol. 9, pp.1103- 1107, 2011
[29] J.A. Goldman, “Path planning problems and solutions”, Proceedings of the IEEE Aerospace and Electronics Conference, pp. 105-108, 1994
[30] H.C. Huang “FPGA-Based Parallel Metaheuristic PSO Algorithm and its Application to Global Path Planning for Autonomous Robot Navigation”, Journal of Intelligent & Robotic Systems, vol. 76, issue no. (3-4), pp. 475- 488, 2014
[31] K. Chu, M. Lee and M. Sunwoo, “Local Path Planning for Off-Road Autonomous Driving With Avoidance of Static Obstacles”, IEEE Transactions on Intelligent Transportation Systems, vol.13, no.4, pp.1599-1616, 2012
[32] M. Aizzat, H. Zamzuri, R. Mamat and S. Amri, “A Path Tracking Algorithm Using Future Prediction Control with Spike Detection for an Autonomous Vehicle Robot”, International Journal of Advanced Robotics Systems, vol. 10, pp. 1-10, 2013.
[33] Y. Zhang, N. Fattahi and W. Li, “Probabilistic roadmap with self-learning for path planning of a mobile robot in a dynamic and unstructured environment”, IEEE International Conference on Mechatronics and Automation, pp. 1074-1079, 2013
[34] L. Gang, and J. Wang, “PRM path planning optimization algorithm research”, Wseas Transactions on Systems and control, vol. 11, pp. 81-86, 2016
[35] M. Zohaib, M. Pasha, R.A. Riaz, N. Javaid, M. Ilahi and R.D. Khan, “Control Strategies for Mobile Robot With Obstacle Avoidance”, Journal of basic and Applied Scientific Research, Vol. 3, issue no. 4, pp. 1027-1036, 2013
[36] P.O. Petterssonand P. Doherty, “Probabilistic Roadmap Based Path Planning for an Autonomous Unmanned Aerial Vehicle”, In Proceedings of the Workshop on Connecting Planning and Theory with Practice, pp. 1-8, 2004
[37] O. Khatib, “Real-Time Obstacle Avoidance for Manipulators and Mobile Robots”, The International Journal of Robotics Research, pp. 90-98, 1998
[38] J. Borenstein and Y. Koren, “The vector field histogram – fast obstacle avoidance for mobile robots”, IEEE Journal of Robotics and Automation, vol. 7, issue no. 3, pp. 278–288, 1991.
[39] M.C. Lee, and M.G. Park, “Artificial potential field based path planning for mobile robots using a virtual obstacle concept”, Proceedings in IEEE/ASME International Conference on Advanced Intelligent Mechatronics, vol. 2, pp. 735-740, 2003
[40] L. Xie, H. Chen, and G. Xie, “Artificial Potential Field Based Path Planning for Mobile Robots Using Virtual Water-Flow Method”, Advanced Intelligent Computing Theories and Applications, with Aspects of Contemporary Intelligent Computing Techniques, vol. 2, pp. 588-595, 2007
[41] A.A. Ahmed, T.Y. Abdalla, and A.A. Abed, “Path Planning of Mobile Robot by using Modified Optimized Potential Field Method”, International Journal of Computer Applications, vol. 113, no. 4, pp. 6-10, 2015
[42] S. Karaman and E. Frazzoli, “Sampling-based algorithms for optimal motion planning”, International Journal of Robotics Research, vol. 30, issue no. 7, pp. 846–894, 2011
[43] H. Yu, R. Sharma, R.W. Beard, and C.N. Taylor, “Observability-based local path planning and obstacle avoidance using bearing-only measurements”, Robotics and Autonomous Systems, vol. 61, pp. 1392–1405, 2013
[44] G. Zhang, S. Ferrari and M. Qian, “An Information Roadmap Method for Robotic Sensor Path Planning”, Journal of Intelligent and Robotic Systems, vol. 56, Issue no. 1–2, pp. 69–98, 2009
[45] C. Fragkopoulos and A. Graeser, “A RRT based path planning algorithm for Rehabilitation robots”, 41st International Symposium on Robotics and ROBOTIK, vol. 6, pp. 1-8, 2010
[46] L. Garrote, C. Premebida, M. Silva and U. Nunes, “An RRT-based navigation approach for mobile robots and automated vehicles”, In: 2014 IEEE International Conference on Industrial Informatics, pp. 326–331, 2014
[47] R. Seif and M.A. Oskoei, “Mobile Robot Path Planning by RRT* in Dynamic Environments”, International journal of intelligent systems and applications, vol. 5, pp. 24-30, 2015
[48] M. Wang, and J.N.K. Liu, (2005) “Fuzzy logic based robot path planning in unknown environment”, International Conference on Machine Learning and Cybernetics, vol. 2, pp. 813-818, 2005
[49] N. Kumar, M. Takács and Z. Vámossy, “Robot navigation in unknown environment using fuzzy logic”, IEEE International Symposium on Applied Machine Intelligence and Informatics, vol. 15, pp. 279-284, 2017
[50] W.G. Han, S.M. Baek, and T.Y. Kuc, “GA based online path planning of mobile robots playing soccer games”, Proceedings of the 40th Midwest Symposium on Circuits and Systems, vol.1, pp. 2-15 , 1997
[51] A. Elshamli, H. A. Abdullah and S. Areibi, “Genetic algorithm for dynamic path planning”, IEEE In: Proc. Canadian Conf. Elect. andComput. Eng., Vol.2, pp: 677-680, 2004
[52] C. E. Thomas, M. A. C. Pacheco, M.M. and B.R. Vellasco, “Mobile Robot Path Planning Using Genetic Algorithms”, In foundations and tools for neural modeling, vol. 1606/1999, Springer, pp. 671- 679, 1999
[53] J. Brank, “Evolutionary approaches to dynamic optimization problems-introduction and recent trends,” In Proc. GECCO Workshop on Evol. Algorithms for Dynamic Optimization Problems, pp. 2-4, 2003
[54] I.A. Taharwa, A.Sheta and M.A. Weshah, “A Mobile Robot Path Planning Using Genetic Algorithm in Static Environment”, Journal of Computer Science, vol. 4, issue 4, pp. 341-344, 2008
[55] J. Lu and D. Yang, “Path planning based on double-layer genetic algorithm,” In 3rd International Conference on Natural Computation, Vol. 4, pp: 357-361, 2007
[56] Z. Weiteng, H. Baoming, L. Dewei, and Z. Bin, “Improved Reversely A star Path Search Algorithm based on the Comparison in Valuation of Shared Neighbour Nodes”, Fourth International Conference on Intelligent Control and Information Processing, pp. 9 – 16, 2013
[57] A.K. Guruji, H. Agarwal, D.K. Parsediya, and A. Madhav, A. "Time-Efficient A* Algorithm for Robot Path Planning”, International Conference on Innovations in Automation and Mechatronics Engineering, vol. 3, pp. 144 – 149, 2016
[58] Q. Zhang and S. Li, “A Global Path Planning Approach based on Particle Swarm Optimization for a Mobile Robot”, International Conference on Robotics, Control & Manufacturing Technology World Scientific and Engineering Academy and Society (WSEAS), pp. 263-267, 2007
[59] E.V. Kumar, M. Aneja and D. Deodhare, “Solving A Path Planning Problem In A Partially Known Environment Using A Swaim Algorithm”, IEEE International Symposium on Measurements and Control in Robotics, pp. 15-26, 2008
[60] P. Raja and S. Pugazhenthi, “Path Planning for Mobile Robots in Dynamic Environments using Particle Swarm Optimization”, IEEE International Conference on Advances in Recent Technologies in Communication and Computing, pp. 401-405, 2009
[61] Masehian and D. Sedighizadeh, “ A Multi-Objective PSO-based Algorithm for Robot Path Planning”, IEEE International Conference on Industrial Technology (ICIT), pp. 465-470, 2010
[62] L. Lu and D. Gong, “Robot Path Planning in Unknown Environments using Particle Swarm Optimization”. IEEE International Conference on Natural Computation (ICNC), pp. 422-426, 2008
[63] Q. Li, Y. Tang, L. Wang, C. Zhang and Y. Yin, “A Specialized Particle Swarm Optimization for Global Path Planning of Mobile Robots”,. IEEE International Workshop on Advanced Computational Intelligence (IWACI), pp. 271-276, 2010
[64] Z.T. AllawiandT.Y.A. Abdalla, “PSO-Optimized Type-2 Fuzzy Logic Controller for Navigation of Multiple Mobile Robots”, IEEE International Conference on Methods and Models in Automation and Robotics, pp. 33-39, 2015
[65] M. Jordan, and A. Perez, “Optimal bidirectional rapidly-exploring random trees”, Technical Report MIT-CSAIL-TR, pp. 97-101, 2013
[66] A.H. Qureshi and Y. Ayaz, “Intelligent bidirectional rapidly-exploring random trees for optimal motion planning in complex cluttered environments”, Robotics and Autonomous Systems, vol. 68, pp. 1-11, 2015
[67] J.S. Kumar, and R. Kaleeswari, “Implementation of Vector Field Histogram based obstacle avoidance wheeled robot”, International Conference on Green Engineering and Technologies, pp. 1-6, 2016
[68] O. Hachour, “Path planning of Autonomous Mobile robot”, International Journal Of Systems Applications, Engineering & Development, vol. 2, no. 4, pp. 178-190, 2008