路径规划方法是智能水下机器人技术研究的核心内容之一，是实现自主航行和作业的关键环节。本文将水下机器人的路径规划方法按智能程度分为传统和智能两大类。传统方法包括基于路线图构建的路径规划方法、基于单元分解的路径规划方法以及基于人工势场的路径规划方法，智能方法包括基于群智能的路径规划方法和基于机器学习的路径规划方法。针对水下机器人规划环境的特点，分别对这几类典型方法进行总结与评价，重点分析了智能方法的优缺点和关键问题，最后展望智能水下机器人路径规划的未来研究方向。
The path planning is one of the core contents of autonomous underwater vehicle research and it is the key link for autonomous navigation and operation. In this paper, the path planning methods for autonomous underwater vehicle are specifically divided into the traditional and intelligent methods. Traditional methods include path planning based on road map, path planning based on unit decomposition and path planning based on artificial potential field. Intelligent methods include path planning based on swarm intelligence and path planning based on machine learning. In view of the characteristics of the underwater environment, these typical methods are summarized and evaluated respectively. The advantages and disadvantages and key problems of the intelligent methods are analyzed. Finally, the future research direction of the autonomous underwater vehicle path planning method is predicted.
2020,42(4): 1-7 收稿日期：2019-06-04
DOI：10.3404/j.issn.1672-7649.2020.04.001
分类号：TP242.6
作者简介：孙玉山(1973-)，男，教授，研究方向为水下机器人导航、控制和规划系统
参考文献：
[1] 徐玉如, 李彭超. 水下机器人发展趋势[J]. 自然杂志, 2011, 33(3): 125–132
[2] GUAN-YAN K E, TAO W U, MING L I, et al. The Improvements and trends of the unmanned underwater vehicles[J]. National Defense Science & Technology, 2013, 34(5): 44–47
[3] 冯正平. 国外自治水下机器人发展现状综述[J]. 鱼雷技术, 2005, 13(1): 5–9
[4] SARIFF N, BUNIYAMIN N. An Overview of autonomous mobile robot path planning algorithms[C]//Research and Development, 2006. Scored 2006. Student Conference on. IEEE, 2006: 183-188.
[5] GASPARETTO A, BOSCARIOL P, LANZUTTI A, et al. Path planning and trajectory planning algorithms: a general overview[M]//Motion and Operation Planning of Robotic Systems. Springer International Publishing, 2015: 3-27.
[6] GUO-CHANG G U, YAN F U, LIU H B. Path planning of AUV based on genetic simulated annealing algorithm[J]. Journal of Harbin Engineering University, 2005
[7] LOZANO-P, WESLEY T, MICHAEL A. An algorithm for planning collision-free paths among polyhedral obstacles[J]. Communications of the Acm, 1979, 22(10): 560–570
[8] LOZANO-P, REZ T. Spatial planning: a configuration space approach[M]//Autonomous Robot Vehicles. Springer-Verlag New York, Inc. 1990: 108-120.
[9] TAKAHASHI O, SCHILLING R J. Motion planning in a plane using generalized voronoi diagrams[J]. IEEE Transactions on Robotics & Automation, 1989, 5(2): 143–150
[10] CANNY JF. A voronoi method for the piano movers problem[J]. IEEE International Conferenceon Robotics and Automa-tion, 1985: 530–535
[11] GARRIDO S, MORENO L, LIMA P U. Robot formation motion planning using fast marching[J]. Robotics & Autonomous Systems, 2011, 59(9): 675–683
[12] 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]//Autonomous Underwater Vehicles. IEEE, 2014: 1-8.
[13] YAO K, LI J, SUN B, et al. An adaptive grid model based on mobility constraints for UAV path planning[C]//International Conference on Control Science and Systems Engineering. IEEE, 2016: 207-211.
[14] 李雅斯. AUV路径规划系统的环境建模方法研究[D]. 哈尔滨: 哈尔滨工程大学, 2012.
[15] HART P E, NILSSON N J, RAPHAEL B. A formal basis for heuristic determination of minimum path cost[C]//Sequences, Subsequences, & Consequences. 1968.
[16] 郭强. 基于改进的A星算法和B样条函数的仿生机器鱼路径规划研究[D]. 天津: 天津大学, 2012.
[17] ZHOU Y, LIU S, JIANCHENG Y U, et al. Underwater glider path planning based on local flow field construction[J]. Robot, 2018
[18] 邓顺平, 张艳军, 刘会平. 一种基于威胁势场的A星路径规划算法[J]. 科技视界, 2014(3): 6–6
[19] CARSTEN J, FERGUSON D, STENTZ A. 3D Field D: Improved path planning and replanning in three dimensions[C]//Ieee/rsj International Conference on Intelligent Robots and Systems. IEEE, 2006: 3381-3386.
[20] Khatib. Real-time obstacle avoidance for manipulators and mobile robots[C]//IEEE International Conference on Robotics and Automation. Proceedings. IEEE, 2003: 90-98.
[21] VOLPE R, KHOSLA P. Manipulator control with superquadric artificial potential functions: theory and experiments[J]. Systems Man & Cybernetics IEEE Transactions on, 1990, 20(6): 1423–1436
[22] WARREN C W. A technique for autonomous underwater vehicle route planning[C]//Autonomous Underwater Vehicle Technology, 1990. Auv '90. Proceedings of the. IEEE, 1990: 201-205.
[23] CHAO W, ZHU D Q. Path planning for autonomous underwater vehicle based on artificial potential field and velocity synthesis[J]. Control Engineering of China, 2015, 2015: 717–721
[24] WANG F. Path planning based on improved artificial potential field for autonomous underwater vehicles[J]. Journal of Huazhong University of Science & Technology, 2011
[25] CHENG C, ZHU D, SUN B, et al. Path planning for autonomous underwater vehicle based on artificial potential field and velocity synthesis[C]//Electrical and Computer Engineering. IEEE, 2015: 717-721.
[26] FERRARI S, FODERARO G. A potential field approach to finding minimum-exposure paths in wireless sensor networks[C]//IEEE International Conference on Robotics and Automation. IEEE, 2010: 335-341.
[27] JOHN H. HOLLAND adaptation in natural and artificial systems[J]. Ann Arbor, 1975, 6(2): 126–137
[28] 徐玉如, 姚耀中. 考虑海流影响的水下机器人全局路径规划研究[J]. 中国造船, 2008, 49(4): 109–114
[29] XU H, LI Y. An Immune genetic algorithm for AUV local path planning[C]//International Society of Offshore and Polar Engineers, 2010.
[30] ANAKITKORN 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]//Autonomous Underwater Vehicles. IEEE, 2014: 1-8.
[31] Marco DORIGO, Gianni Di Caro, Luca M. GAMBARDELLA Ant Algorithms for Discrete Optimization[J]. Artificial Life, 1999, 5(2): 137–172
[32] DORIGO M, CARO G D, GAMBARDELLA L M. Ant algorithms for discrete optimization[M]. MIT Press, 1999.
[33] 王宏健, 伍祥红, 施小成. 基于蚁群算法的AUV全局路径规划方法[J]. 中国造船, 2008, 49(2): 88–93
[34] 潘昕, 吴旭升, 侯新国, 等. 基于遗传蚂蚁混合算法的AUV全局路径规划[J]. 华中科技大学学报(自然科学版), 2017, 45(5): 45–49 + 76
[35] LIU G, LIU P, MU W, 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
[36] YANG X S. Nature-inspired metaheuristic algorithms[M]. Luniver Press, 2008.
[37] 董静. 萤火虫算法研究及其在水下潜器路径规划中的应用[D]. 哈尔滨工程大学, 2013.
[38] LIU C, ZHAO Y, 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.
[39] SIMON D. Biogeography-based optimization[J]. IEEE Transactions on Evolutionary Computation, 2008, 12(6): 702–713
[40] 关晓蕾. 生物地理优化算法及其在机器人路径规划中的应用[D]. 哈尔滨: 哈尔滨工程大学, 2011.
[41] MAHMOUDZADEH S, POWERS D M W, SAMMUT K. An autonomous reactive architecture for efficient AUV mission time management in realistic dynamic ocean environment[J]. Robotics & Autonomous Systems, 2017, 87: 81–103
[42] GHATEE M, MOHADES A. Motion planning in order to optimize the length and clearance applying a hopfield neural network[J]. Expert Systems with Applications, 2009, 36(3): 4688–4695
[43] TAVARES J. Bio-inspired algorithms for the vehicle routing problem[J]. Studies in Computational Intelligence, 2009
[44] 段群杰, 张铭钧, 张菁. 基于模糊神经网络的水下机器人局部路径规划方法[J]. 船舶工程, 2001(1): 54–58
[45] YAN M Z, ZHU D Q. An algorithm of complete coverage path planning for autonomous underwater vehicles[J]. Key Engineering Materials, 2011, 467-469: 1377–1385
[46] LI S, GUO Y. Neural-network based AUV path planning in estuary environments[C]//Intelligent Control and Automation. IEEE, 2012: 3724-3730.
[47] ZHU D Q, BING S, LI L I. Algorithm for AUV's 3-D path planning and safe obstacle avoidance based on biological inspired model[J]. Control & Decision, 2015, 30(5): 798–806
[48] FUJISAWA S, KUROZUMI R, YAMAMOTO T, et al. Path planning for mobile robots using an improved reinforcement learning scheme[C]//IEEE International Symposium on Intelligent Control. IEEE, 2003: 67-74.
[49] VIEN N A, VIET N H, LEE S G, et al. Obstacle avoidance path planning for mobile robot based on Ant-Q reinforcement learning algorithm[C]//International Symposium on Neural Networks. Springer, Berlin, Heidelberg, 2007: 704-713.
[50] LIU B, LU Z. AUV Path planning under ocean current based on reinforcement learning in electronic chart[C]//International Conference on Computational & Information Sciences. IEEE, 2013: 1939-1942.
[51] 徐莉. Q-learning研究及其在AUV局部路径规划中的应用[D]. 哈尔滨: 哈尔滨工程大学, 2004.
[52] GAUTAM U, MALMATHANRAJ R, SRIVASTAV C. Simulation for path planning of autonomous underwater vehicle using flower pollination algorithm, genetic algorithm and Q-learning[C]//International Conference on Cognitive Computing and Information Processing. IEEE, 2015: 1-5.
[53] JING S, GUO-CHANG G U, LIU H B. Mobile robot path planning based on hierarchical reinforcement learning in unknown dynamic environment[J]. Robot, 2006, 28(5): 544–547
[54] SILVER D, HUANG A, MADDISON C J, et al. Mastering the game of Go with deep neural networks and tree search[J]. Nature, 2016, 529(7587): 484–489
[55] CAICEDO J C, LAZEBNIK S. Active object localization with deep reinforcement learning[C]//IEEE International Conference on Computer Vision. IEEE, 2015: 2488-2496.
[56] PFEIFFER M, SCHAEUBLE M, NIETO J, et al. From perception to decision: a data-driven approach to end-to-end motion planning for autonomous ground robots[C]//IEEE International Conference on Robotics and Automation. IEEE, 2017: 1527-1533.
[57] TAI L, PAOLO G, LIU M. Virtual-to-real deep reinforcement learning: continuous control of mobile robots for mapless navigation[J]. 2017.
[58] CHENG Y, ZHANG W. Concise deep reinforcement learning obstacle avoidance for underactuated unmanned marine vessels[J]. Neurocomputing, 2017: 272
[59] LI Y, CHENG W, YU L H, et al. Genetic algorithm enhanced by machine learning in dynamic aperture optimization[J]. Neurocomputing, 2018, 21(5).
