Two-Layer Path Planner for AUVs Based on the Improved AAF-RRT Algorithm

Abstract

As autonomous underwater vehicles (AUVs) merely adopt the inductive obstacle avoidance mechanism to avoid collisions with underwater obstacles, path planners for underwater robots should consider the poor search efficiency and inadequate collision-avoidance ability. To overcome these problems, a specific two-player path planner based on an improved algorithm is designed. First, by combing the artificial attractive field (AAF) of artificial potential field (APF) approach with the random rapidly exploring tree (RRT) algorithm, an improved AAF-RRT algorithm with a changing attractive force proportional to the Euler distance between the point to be extended and the goal point is proposed. Second, a two-layer path planner is designed with path smoothing, which combines global planning and local planning. Finally, as verified by the simulations, the improved AAF-RRT algorithm has the strongest searching ability and the ability to cross the narrow passage among the studied three algorithms, which are the basic RRT algorithm, the common AAF-RRT algorithm, and the improved AAF-RRT algorithm. Moreover, the two-layer path planner can plan a global and optimal path for AUVs if a sudden obstacle is added to the simulation environment.

Keywords

Autonomous underwater vehicles (AUVs) / Path planner / Random rapidly exploring tree (RRT) / Artificial attractive field (AAF) / Path smoothing

References

[1] Cai W, Wu Y, Zhang M. Three-dimensional obstacle avoidance for autonomous underwater robot. IEEE Sensors Letters, 2020, 4(11): 1-4

[2] Carsten J, Ferguson D, Stentz A (2006) 3D Field D: Improved path planning and replanning in three dimensions. IEEE/RSJ International Conference on Intelligent Robots & Systems

[3] Dash AK, Chen IM, Song HY, Yang G (2003) Singularity-free path planning of parallel manipulators using clustering algorithm and line geometry. IEEE International Conference on Robotics & Automation

[4] Dong HK. Escaping route method for a trap situation in local path planning. International Journal of Control Automation & Systems, 2009, 7(3): 495-500

[5] Dong J (2013) Research on firefly algorithm and its application in path planning of underwater vehicle. Master thesis, Harbin Engineering University (in Chinese)

[6] Gasparetto A, Boscariol P, Lanzutti A, Vidoni R (2015) Path planning and trajectory planning algorithms: A general overview. Springer International Publishing

[7] Gong JF, Peng SX (2002) Approach to Robot path planning based on numerical potential field and genetic algorithm. Journal of Tianjin University (Science and Technology), (in Chinese) DOI: https://doi.org/10.1007/s11769-002-0038-4

[8] Gu GC, Fu Y, Liu HB. (2005). Path planning of AUV based on genetic simulated annealing algorithm. Journal of Harbin Engineering University. (in Chinese) DOI: https://doi.org/10.3969/j.issn.1006-7043.2005.01.018

[9] Hart PE, Nilsson N, Raphael B. A formal basis for the heuristic determination of minimum cost paths. IEEE Transactions on Systems Science & Cybernetics, 1972, 4(2): 28-29

[10] Jr J, Lavalle SM (2000) RRT-connect: an efficient approach to single-query path planning. Proceedings of the 2000 IEEE International Conference on Robotics and Automation, ICRA 2000, San Francisco, USA

[11] Kawaguchi K (2016) Deep learning without poor local minima.

[12] Khatib O (2003) Real-time obstacle avoidance for manipulators and mobile robots. IEEE International Conference on Robotics and Automation

[13] Lavalle SM, Kuffner JJ (2000) Rapidly-exploring random trees: progress and prospects. Algorithmic & Computational Robotics New Directions. DOI: https://doi.org/10.1201/9781439864135-43

[14] Li YS (2012) Research on the environmnet modeling method of the AUV path planning system. Master thesis, Harbin Engineering University (in Chinese)

[15] Liu C, Han J, An K. Dynamic path planning based on an improved RRT algorithm for roboCup robot. Robot, 2017, 39(1): 8-15 (in Chinese)

[16] Liu C, Zhao Y, Gao F, Liu L. Three-dimensional path planning method for autonomous underwater vehicle based on modified firefly algorithm. Mathematical Problems in Engineering, 2015, 2015(Pt.20): 1-10

[17] Liu G, Liu P, Mu W, Wang S. A path optimization algorithm for AUV using an improved ant colony algorithm with optimal energy consumption. Hsi-An Chiao Tung Ta Hsueh/Journal of Xi’an Jiaotong University, 2016, 50(10): 93-98 (in Chinese)

[18] Lozano-Pérez T (1990) Spatial planning: A configuration space approach. Autonomous Robot Vehicles 108–120. DOI: https://doi.org/10.1109/TC.1983.1676196

[19] Morris P (1993) The Breakout method for escaping from local minima. Proceedings of the 11th National Conference on Artificial Intelligence, Washington, DC, USA

[20] Orozco-Rosas U, Montiel O, Sepúlveda R (2019a). Mobile robot path planning using membrane evolutionary artificial potential field. Applied Soft Computing. DOI: https://doi.org/10.1016/j.asoc.2019.01.036

[21] Orozco-Rosas U, Picos K, Ross O. Hybrid path planning algorithm based on membrane pseudo-bacterial potential field for autonomous mobile robots. IEEE Access, 2019, 7(1): 156787-156803

[22] Sariff N, Buniyamin N (2006) An overview of autonomous mobile robot path planning algorithms. Conference on Research & Development

[23] Song JZ, Dai B, Shan EZ, He HG. An improved RRT path planning algorithm. Acta Electronica Sinica, 2010, 38: 225-228 (in Chinese)

[24] Sun Y, Wang L, Wu J, Ran X. A general overview of path planning methods for autonomous underwater vehicle. Ship Science an Technology, 2020, 42(4): 1-7 (in Chinese)

[25] Tanakitkorn K, Wilson PA, Turnock SR, Phillips AB (2014) Grid-based GA path planning with improved cost function for an over-actuated hover-capable AUV. AUV 2014

[26] Volpe R, Khosla P. Manipulator control with superquadric artificial potential functions: theory and experiments. Systems Man & Cybernetics IEEE Transactions, 1990, 20(6): 1423-1436

[27] Wang H, Wu X, Shi X. Global planning path method of AUV based on ant colony optimization Algorithm. Shipbuilding of China, 2008, 49(2): 88-93 (in Chinese)

[28] Wang LL, Sui ZZ, Pu ZQ, Liu Z, Yi JQ. An Improved RRT algorithm for multi-robot formation path planning. Acta Electronica Sinica, 2020, 48: 60-67 (in Chinese)

[29] Wang Q (2014) Research on rapidly-exploring random trees based global path planning and its application. Master thesis, National University of Defense Technology. (in Chinese)

[30] Xu H, Li Y (2010) An immune genetic algorithm for AUV local path planning. International Society of Offshore and Polar Engineers

[31] Xu M, Franti P (2004) A heuristic K-means clustering algorithm by kernel PCA. 2004 International Conference on Image Processing, ICIP’ 04.

[32] Xu YR, Yao YZ. Research on AUV global path planning considering ocean current. Shipbuilding of China, 2008, 49(4): 109-114 (in Chinese)

[33] Zhu DQ, Sun B, Li L. Algorithm for AUV’s 3-D path planning and safe obstacle avoidance based on biological inspired model. Control & Decision, 2015, 30(5): 798-806 (in Chinese)