Research Status and Prospect of AUV Path Planning Algorithms

doi:10.3778/j.issn.1673-9418.2003061

Abstract

Abstract:

Path planning algorithm is one of the core algorithms for autonomous underwater vehicle (AUV) to complete autonomous underwater cruise. In this paper, two kinds of AUV path planning algorithms based on environment modeling and path searching are reviewed. The domestic and foreign research status of environmental modeling methods such as grid method, visibility graph method and Voronoi diagram method is expounded, and their advantages and disadvantages are pointed out. In addition, the research results of predecessors in artificial potential field algorithm, fast marching algorithm, A* algorithm and other traditional path search algorithms are analyzed, and compared with the recent intelligent bionics path search algorithms such as particle swarm optimization algorithm, ant colony algorithm, genetic algorithm and artificial neural network algorithm. It is found that, in the face of the influence of complex underwater environment factors, improving the practicability of the algorithms in three-dimensional ocean environment such as ocean currents and complex obstacles, thus achieving AUV's efficient obstacle avoidance and energy saving is the focus of path planning algorithm research. Finally, the research trends of AUV path planning algorithm in intelligent development, fusion and multi-AUV collaboration, and the development of AUV remoteness for wide-area detection are prospected.

Key words: autonomous underwater vehicle (AUV), environmental modeling method, path search algorithm

摘要：

路径规划算法是自主水下航行器（AUV）完成水下自主巡航的核心算法之一。分别综述了基于环境建模和路径搜索两类AUV路径规划算法。阐述了栅格法、可视图法和维诺图法等环境建模方法的国内外研究现状，并指出了它们的优缺点。对前人在人工势场法、快速步进法和A*算法等传统路径搜索算法方面的研究成果进行分析，并与近期粒子群优化算法、蚁群算法、遗传算法和人工神经网络算法等智能仿生学路径搜索算法进行比较。分析发现，面对复杂水下环境因素的影响，提高算法在海流、复杂障碍物等三维海洋环境中的实用性，从而实现AUV的高效避障和节约能耗是路径规划算法研究的重点。最后对AUV路径规划算法在智能化发展、融合、多AUV协作以及向广域探测的AUV远程化方向发展等方面的研究趋势进行展望。

关键词: 自主水下航行器（AUV）, 环境建模方法, 路径搜索算法

GUO Yinjing, MENG Qingliang, KONG Fang, LYU Wenhong. Research Status and Prospect of AUV Path Planning Algorithms[J]. Journal of Frontiers of Computer Science and Technology, 2020, 14(12): 1981-1994.

郭银景，孟庆良，孔芳，吕文红. AUV路径规划算法研究现状与展望[J]. 计算机科学与探索, 2020, 14(12): 1981-1994.

References

[1] Bonin-Font F, Burguera A, Lisani J L. Visual discrimination and large area mapping of posidonia oceanica using a light-weight AUV[J]. IEEE Access, 2017, 5: 24479-24494.
[2] Akács B, Dóczi R, Süt? B, et al. Extending AUV response robot capabilities to solve standardized test methods[J]. Acta Polytechnica Hungarica, 2016, 13(1): 157-170.
[3] McColgan J, McGookin E W, Mazlan A N A. A low fidelity mathematical model of a biomimetic AUV for multivehicle cooperation[C]//Proceedings of the OCEANS 2015, Genova, May 18-21, 2015. Piscataway: IEEE, 2015: 1-10.
[4] Chen C. Unmanned boat path planning based on improved grid method and artifitial potential field method[D]. Zhenjiang: Jiangsu University of Science and Technology, 2018.陈呈. 基于改进栅格法和人工势场法的无人艇路径规划研究[D]. 镇江: 江苏科技大学, 2018.
[5] Lu D Y, Cui R X, Wang P. Energy efficient path planning of autonomous underwater vehicles for environment modeling[C]//Proceedings of the 2014 International Conference on Multisensor Fusion and Information Integration for Intelligent Systems, Beijing, Sep 28-29, 2014. Piscataway: IEEE, 2014: 1-6.
[6] Li L, Zhu D Q, Sun B, et al. The 3-D map building of AUV based on DS information fusion[C]//Proceedings of the 33rd Chinese Control Conference, Nanjing, Jul 28-30, 2014. Pisca-taway: IEEE, 2014: 8639-8644.
[7] Cao X, Zhu D Q, Yang S X. Multi-AUV target search based on bioinspired neurodynamics model in 3-D underwater env-ironments[J]. IEEE Transactions on Neural Networks and Learning Systems, 2015, 27(11): 2364-2374.
[8] Tanakitkorn K, Wilson P A, Turnock S R, et al. Grid-based GA path planning with improved cost function for an over-actuated hover-capable AUV[C]//Proceedings of the 2014 IEEE/OES Autonomous Underwater Vehicles, Oxford, Oct 6-9, 2014. Piscataway: IEEE, 2014: 1-8.
[9] Zhu T T, Zhu D Q, Yan M Z. Multiple underwater target search path planning based on GBNN[C]//LNCS 11742: Pro-ceedings of the 12th International Conference on Intelligent Robotics and Applications, Shenyang, Aug 8-11, 2019. Berlin, Heidelberg: Springer, 2019: 225-232.
[10] Li J H, Kang H, Park G, et al. Real time path planning of underwater robots in unknown environment[C]//Proceedings of the 2017 International Conference on Control, Artificial Intelligence, Robotics & Optimization, Prague, May 20-22, 2017. Piscataway: IEEE, 2018: 312-318.
[11] Gal O. Unified trajectory planning algorithms for autonomous underwater vehicle navigation[J]. ISRN Robotics, 2013: 1-6.
[12] Xidias E, Zissis D. Real time autonomous maritime navigation using dynamic visibility graphs[C]//Proceedings of the 2018 IEEE/OES Autonomous Underwater Vehicle Workshop, Porto, Nov 6-9, 2018. Piscataway: IEEE, 2018: 1-6.
[13] Kim J, Kim M, Kim D. Variants of the quantized visibility graph for efficient path planning[J]. Advanced Robotics, 2011, 25(18): 2341-2360.
[14] Marino A, Antonelli G. Experiments on sampling patrolling with two autonomous underwater vehicles[J]. Robotics and Autonomous Systems, 2015, 67: 61-71.
[15] Candeloro M, Lekkas A M, S?erensen A J, et al. Continuous curvature path planning using Voronoi diagrams and fermat??s spirals[J]. IFAC Proceedings, 2013, 46(33): 132-137.
[16] Dong D Y, He B, Liu Y, et al. A novel path planning method based on extreme learning machine for autonomous underwater vehicle[C]//Proceedings of the OCEANS 2015, Washington, Oct 19-22, 2015. Piscataway: IEEE, 2015: 1-7.
[17] Grefstad ?, Schj?lberg I. Navigation and collision avoidance of underwater vehicles using sonar data[C]//Proceedings of the 2018 IEEE/OES Autonomous Underwater Vehicle Work-shop, Porto, Nov 6-9, 2018. Piscataway: IEEE, 2018: 1-6.
[18] Saravanakumar S, Asokan T. Waypoint guidance based planar path following and obstacle avoidance of autonomous under-water vehicle[C]//Proceedings of the 8th International Con-ference on Informatics in Control, Automation and Robotics, Noordwijkerhout, Jul 28-31, 2011. SciTePress, 2011: 191-198.
[19] Subramanian S, George T, Thondiyath A. Obstacle avoidance using multi-point potential field approach for an underactuated flat-fish type AUV in dynamic environment[C]//Proceedings of the 2012 International Conference on Intelligent Robotics, Automation, and Manufacturing, Malaysia, Nov 28-30, 2012. Berlin, Heidelberg: Springer, 2012: 20-27.
[20] Saravanakumar S, Asokan T. Multipoint potential field method for path planning of autonomous underwater vehicles in 3D space[J]. Intelligent Service Robotics, 2013, 6(4): 211-224.
[21] Yan X F, Gu F, Song C, et al. Dynamic formation control for autonomous underwater vehicles[J]. Journal of Central South University, 2014, 21(1): 113-123.
[22] Zhu D Q, Cheng C L, Sun B. An integrated AUV path planning algorithm with ocean current and dynamic obstacles[J]. International Journal of Robotics and Automation, 2016, 31(5): 382-389.
[23] Cheng Z, Zhang Z A, Li J Z, et al. Mobile robots path planning based on improved artificial potential field[J]. Computer Engineering and Applications, 2019, 55(23): 29-34.程志, 张志安, 李金芝, 等. 改进人工势场法的移动机器人路径规划[J]. 计算机工程与应用, 2019, 55(23): 29-34.
[24] Song J, Hao C, Su J C. Path planning for unmanned surface vehicle based on predictive artificial potential field[J]. International Journal of Advanced Robotic Systems, 2020,17(2): 1-13.
[25] Pêtrès C, Pailhas Y, Petillot Y, et al. Underwater path planning using fast marching algorithms[C]//Proceedings of the Europe Oceans 2005, Brest, Jun 20-23, 2005. Piscataway: IEEE, 2005: 814-819.
[26] Yu H, Wang Y J. Multi-objective AUV path planning in large complex battlefield environments[C]//Proceedings of the 7th International Symposium on Computational Intelligence and Design, Hangzhou, Dec 13-14, 2014. Piscataway: IEEE, 2014: 345-348.
[27] Yu H, Shen A W, Su Y S. Continuous motion planning in complex and dynamic underwater environments[J]. Intern-ational Journal of Robotics & Automation, 2015, 30(2): 192-204.
[28] Song R, Liu Y C, Richard B. A multi-layered fast marching method for unmanned surface vehicle path planning in a time-variant maritime environment[J]. Ocean Engineering, 2017, 129: 301-317.
[29] Li J H, Lee M J, Park S H, et al. Real time path planning for a class of torpedo-type AUVs in unknown environment[C]//Proceedings of the 2012 IEEE/OES Autonomous Under-water Vehicles, Southampton, Sep 24-27, 2012. Piscataway: IEEE, 2012: 1-6.
[30] Chen S, Liu C W, Huang Z P, et al. Global path planning for AUV based on sparse A* search algorithm[J]. Torpedo Technology, 2012, 20(4): 271-275.陈实, 刘纯武, 黄芝平, 等. 基于稀疏A*算法的AUV全局路径规划[J]. 鱼雷技术, 2012, 20(4): 271-275.
[31] Zhang H H, Liming G, Tao C, et al. Global path planning methods of UUV in coastal environment[C]//Proceedings of the 2016 IEEE International Conference on Mechatronics and Automation, Harbin, Aug 7-10, 2016. Piscataway: IEEE, 2016: 1018-1023.
[32] Wu P, Sang C J, Lu Z H, et al. Research on mobile robot path planning based on improved A* algorithm[J]. Computer Engineering and Applications, 2019, 55(21): 227-233. 吴鹏, 桑成军, 陆忠华, 等. 基于改进A*算法的移动机器人路径规划研究[J]. 计算机工程与应用, 2019, 55(21): 227-233.
[33] Yang L, Qi J T, Xiao J Z, et al. A literature review of UAV 3D path planning[C]//Proceeding of the 11th World Congress on Intelligent Control and Automation, Shenyang, Jun 29-Jul 4, 2014. Piscataway: IEEE, 2014: 2376-2381.
[34] Xue M, Xu H C, Wang S. Path planning of unmanned vehicle based on particle swarm optimization algorithm[J].China Science and Technology Information, 2018(24): 69-70.薛敏, 徐海成, 王硕. 基于粒子群优化算法的无人艇路径规划[J]. 中国科技信息, 2018(24): 69-70.
[35] Sun J, Liu X. Path plan of unmanned underwater vehicle using particle swarm optimization[C]//Proceedings of the 2015 International Conference on Intelligent Systems Research and Mechatronics Engineering, Nanjing, Jun 19-20, 2015. Atlantis Press, 2015: 1764-1767.
[36] Zhuang Y F, Sharma S, Subudhi B, et al. Efficient collision-free path planning for autonomous underwater vehicles in dynamic environments with a hybrid optimization algorithm[J]. Ocean Engineering, 2016, 127: 190-199.
[37] Yan Z P, Li J Y, Zou J J, et al. A hybrid PSO-WG algorithm for AUV path planning in unknown oceanic environment[C]//Proceedings of the 8th International Conference on Und-erwater System Technology: Theory and Applications, Wuhan, Dec 1-3, 2018. Piscataway: IEEE, 2018: 1-6.
[38] Sun J, Feng B, Xu W B. Particle swarm optimization with particles having quantum behavior[C]//Proceedings of the 2004 IEEE Congress on Evolutionary Computation, Portland, Jun 19-23, 2004. Piscataway: IEEE, 2004: 325-331.
[39] Lim H S, Fan S S, Chin C K H, et al. Constrained path planning of autonomous underwater vehicle using selectively-hybridized particle swarm optimization algorithms[J]. IFAC- PapersOnLine, 2019, 52(21): 315-322.
[40] Guo X H, Ji M J, Zhang W D, et al. Improved QPSO algorithm for dynamic path planning of autonomous underwater vehicle in variable ocean current environment[J/OL]. Systems Engin-eering-Theory & Practice(2020-04-09)[2020-06-20]. http://kns.cnki.net/kcms/detail/11.2267.N.20200408.2032.002.html.郭兴海, 计明军, 张卫丹, 等. 可变洋流环境中自主水下航行器动态路径规划的改进QPSO算法[J/OL]. 系统工程理论与实践(2020-04-09)[2020-06-20]. http://kns.cnki.net/kcms/detail/11.2267.N.20200408.2032.002.html.
[41] Wang H J, Xiong W. Research on global path planning based on ant colony optimization for AUV[J]. Journal of Marine Science and Application, 2009, 8(1): 58-64.
[42] Wang P, Meng P, Ning T F. Path planning based on hybrid adaptive ant colony algorithm for AUV[C]//Proceedings of the 11th International Symposium on Distributed Computing and Applications to Business, Engineering & Science, Guilin, Oct 19-22, 2012. Piscataway: IEEE, 2012: 157-160.
[43] Zhang G L, Jia H M. Global path planning of AUV based on improved ant colony optimization algorithm[C]//Pro-ceedings of the 2012 IEEE International Conference on Aut-omation and Logistics, Zhengzhou, Aug 15-17, 2012. Pis-cataway: IEEE, 2012: 606-610.
[44] Zhang G L, Jia H M. 3D path planning of AUV based on improved ant colony optimization[C]//Proceedings of the 32nd Chinese Control Conference, Xi’an, Jul 26-28, 2013. Piscataway: IEEE, 2013: 5017-5022.
[45] Pan X, Wu X S, Hou X G, et al. Global path planning based on genetic-ant hybrid algorithm for AUV[J]. Journal of Hua-zhong University of Science and Technology (Nature Science Edition), 2017, 45(5): 45-49.潘昕, 吴旭升, 侯新国, 等. 基于遗传蚂蚁混合算法的AUV全局路径规划[J]. 华中科技大学学报(自然科学版), 2017, 45(5): 45-49.
[46] Liu G J, Liu P, Mu W L, et al. A path optimization algorithm for AUV using an improved ant colony algorithm with optimal energy consumption[J]. Journal of Xi??an Jiaotong University, 2016, 50(10): 93-98.
[47] Yuan W H, You X M, Liu S. Dual-population ant colony algorithm on dynamic learning mechanism[J]. Journal of Frontiers of Computer Science and Technology, 2019, 13(7): 1239-1250.袁汪凰, 游晓明, 刘升. 动态学习机制的双种群蚁群算法[J]. 计算机科学与探索, 2019, 13(7): 1239-1250.
[48] Zhang N N, Jiang W G, Dou G. Research on autonomous underwater vehicle 3D path planning based on improved ant colony algorithm[J]. Computer Engineering and Applications, 2019, 55(11): 265-270. 张楠楠, 姜文刚, 窦刚. 改进蚁群算法在AUV三维路径规划中的研究[J]. 计算机工程与应用, 2019, 55(11): 265-270.
[49] Li P Y. Multi-objective path planning of unmanned aerial vehicle based on genetic algorithm[J]. Agricultural Equipment & Vehicle Engineering, 2019, 57(1): 68-70.李平阳. 基于遗传算法的无人机多目标路径规划[J]. 农业装备与车辆工程, 2019, 57(1): 68-70.
[50] Khan F A, Khan S A, Turgut D, et al. Optimizing resurfacing schedules to maximize value of information in UWSNs[C]//Proceedings of the 2016 IEEE Global Communications Con-ference, Washington, Dec 4-8, 2016. Piscataway: IEEE, 2016: 1-5.
[51] Yu W Z, She H Y, Ouyang Z L. Path planning of unmanned surface vehicle based on variable mesh improved genetic algorithm[J]. Navigation of China, 2018, 41(4): 101-105.余文曌, 佘航宇, 欧阳子路. 基于弹性网格的改进遗传算法在无人艇路径规划中的研究[J]. 中国航海, 2018, 41(4):101-105.
[52] Ataei M, Yousefi-Koma A. Three-dimensional optimal path planning for waypoint guidance of an autonomous under-water vehicle[J]. Robotics and Autonomous Systems, 2015, 67: 23-32.
[53] Zhang L. Research on fuzzy control of underwater vehicle path following based on genetic algorithm optimization[D].Hangzhou: Zhejiang University, 2017.张磊. 基于遗传算法优化的水下机器人路径跟踪模糊控制技术研究[D]. 杭州: 浙江大学, 2017.
[54] Yan S K, Pan F. Research on route planning of AUV based on genetic algorithms[C]//Proceedings of the 2019 IEEE International Conference on Unmanned Systems and Artificial Intelligence, Xi??an, Nov 22-24, 2019. Piscataway: IEEE, 2019: 184-187.
[55] He G Q, Zhu Y F, Zhang C R. Research of 3D flight path planning of UAV based on genetic algorithm[J]. Value Eng-ineering, 2020, 39(7): 215-218.何光勤, 朱一飞, 张才然. 基于遗传算法的无人机三维航迹规划研究[J]. 价值工程, 2020, 39(7): 215-218.
[56] Yang X S. Multi-objective firefly algorithm for continuous optimization[J]. Engineering with Computers, 2013, 29(2):175-184.
[57] Li L N, Guo Y Q, Zhang X D, et al. Path planning algorithm for robot based on firefly algorithm combined with artificial potential field method[J]. Computer Engineering and App-lications, 2018, 54(20): 104-109.李丽娜, 郭永强, 张晓东, 等. 萤火虫算法结合人工势场法的机器人路径规划[J]. 计算机工程与应用, 2018, 54(20):104-109.
[58] Dong J. Study on firefly algorithm and its application in path planning of underwater vehicles[D]. Harbin: Harbin Engineering University, 2013.董静. 萤火虫算法研究及其在水下潜器路径规划中的应用[D]. 哈尔滨: 哈尔滨工程大学, 2013.
[59] Liu C, Zhao Y X, Gao F, et al. Three-dimensional path planning method for autonomous underwater vehicle based on modified firefly algorithm[J]. Mathematical Problems in Engineering, 2015(11): 1-10.
[60] Li F L, Chen S, Fan X J, et al. Path planning based on firefly algorithm in dynamic unknown environment[J]. Automation & Instrumentation, 2019, 34(6): 53-58.李凤玲, 陈珊, 范兴江, 等. 基于萤火虫算法动态未知环境的路径规划[J]. 自动化与仪表, 2019, 34(6): 53-58.
[61] Wu H S, Zhang F M, Wu L S. New swarm intelligence algorithm—wolf pack algorithm[J]. Systems Engineering and Electronics, 2013, 35(11): 2430-2438.吴虎胜, 张凤鸣, 吴庐山. 一种新的群体智能算法——狼群算法[J]. 系统工程与电子技术, 2013, 35(11): 2430-2438.
[62] Shen J, Shi J, Xiong L. A route planning method for underwater terrain aided positioning based on gray wolf optimization algorithm[C]//LNCS 9937: Proceedings of the 17th Inter-national Conference on Intelligent Data Engineering and Automated Learning, Yangzhou, Oct 12-14, 2016. Berlin, Heidelberg: Springer, 2016: 126-133.
[63] Zhang L Y, Zhang L, Liu S, et al. Three-dimensional under-water path planning based on modified wolf pack algorithm[J]. IEEE Access, 2017, 5: 22783-22795.
[64] Wang Y X, Chen M Y, Cheng T L, et al. Research of improved wolf pack algorithm based on differential evolution[J]. Application Research of Computers, 2019, 36(8): 2305-2310.王盈祥, 陈民铀, 程庭莉, 等. 基于差分进化的改进狼群算法研究[J]. 计算机应用研究, 2019, 36(8): 2305-2310.
[65] Panda M, Das B, Pati B B. A hybrid approach for path planning of multiple AUVs[C]//Proceedings of the Innovation in Ele-ctrical Power Engineering, Communication, and Computing Technology, Singapore, Sep 24, 2020. Berlin, Heidelberg: Springer, 2020: 327-338.
[66] Zhu D Q, Lv R F, Cao X, et al. Multi-AUV hunting algorithm based on bio-inspired neural network in unknown environ-ments[J]. International Journal of Advanced Robotic Systems, 2015, 12(11): 166.
[67] Ni J J, Wu L Y, Shi P F, et al. A dynamic bioinspired neural network based real-time path planning method for autonomous underwater vehicles[J]. Computational Intelligence and Neuro-science, 2017: 1-16.
[68] Ni J J, Wu L Y, Wang S H, et al. 3D real-time path planning for AUV based on improved bio-inspired neural network[C]//Proceedings of the 2016 IEEE International Conference on Consumer Electronics, Taiwan, China, May 27-29, 2016. Piscataway: IEEE, 2016: 95-96.
[69] Cao X, Peng J. A potential field bio-inspired neural network control algorithm for AUV path planning[C]//Proceedings of the 2018 IEEE International Conference on Information and Automation, Wuyishan, Aug 11-13, 2018. Piscataway: IEEE, 2018: 1427-1432.
[70] Zhu D Q, Sun B, Li L. Algorithm for AUV??s 3-D path planning and safe obstacle avoidance based on biological inspired model[J]. Control and Decision, 2015, 30(5): 798-806.朱大奇, 孙兵, 李利. 基于生物启发模型的AUV三维自主路径规划与安全避障算法[J]. 控制与决策, 2015, 30(5):798-806.
[71] Zhu D Q, Qu Y, Yang S X. Multi-AUV SOM task allocation algorithm considering initial orientation and ocean current environment[J]. Frontiers of Information Technology & Electronic Engineering, 2019, 20(3): 330-341.
[72] Subramani D N, Wei Q J, Lermusiaux P F J. Stochastic time-optimal path-planning in uncertain strong and dynamic flows[J]. Computer Methods in Applied Mechanics and Engineering, 2018, 333: 218-237.
[73] Carreras M, Hernández J D, Vidal E, et al. Sparus II AUV—a hovering vehicle for seabed inspection[J]. IEEE Journal of Oceanic Engineering, 2018, 43(2): 344-355.
[74] Gan W Y, Zhu D Q. Complete coverage belief function path planning algorithm of autonomous underwater vehicle based on behavior strategy[J]. Journal of System Simulation, 2018, 30(5): 1857-1868.甘文洋, 朱大奇. 基于行为策略的AUV全覆盖信度函数路径规划算法[J]. 系统仿真学报, 2018, 30(5): 1857-1868.