AUV实时避障算法研究进展

郭银景, 鲍建康, 刘 琦, 屈衍玺, 吕文红

AUV实时避障算法研究进展

郭银景1,2, 鲍建康3, 刘 琦1, 屈衍玺1, 吕文红4

(1. 山东科技大学 电子信息工程学院, 山东 青岛, 266590; 2. 青岛智海牧洋科技有限公司, 山东 青岛, 266590; 3. 山东科技大学 电气与自动化工程学院, 山东 青岛, 266590; 4. 山东科技大学 交通学院, 山东 青岛, 266590)

针对目前在研究自主水下航行器(AUV)实时避障算法过程中出现的重点难点及研究趋势, 文中从动态障碍物、多约束与多目标以及海流干扰3方面分析了水下实时避障算法的研究难点, 然后从人工势场法、模糊逻辑法和智能仿生算法3个方面重点阐述水下实时避障算法的研究进展。对比3种避障算法的研究现状得知, 通过修正势场函数、引入AUV运动约束、考虑障碍物相对速度和复杂海流影响等, 使改进的人工势场法克服了陷阱问题、局部极小值和目标不可达等问题, 成为解决AUV实时避障问题的重点研究方向。在躲避动态障碍物方面, 多种避障算法融合将成为一种趋势; 在多约束与多目标问题中, 能耗问题尤为重要却很少被作为参数引入到避障算法中, 具有很大的研究潜力; 针对海流干扰问题, 多数避障算法仅考虑了水平方向的定常流或涡流, 因此考虑三维海流干扰也是未来水下实时避障算法的研究方向之一。

自主水下航行器; 实时避障算法; 人工势场; 模糊逻辑; 仿生

0 引言

近年来, 随着新材料、新能源和人工智能等技术的不断进步, 各海洋大国都加快了对自主水下航行器(autonomous undersea vehicle, AUV)的研究步伐并取得了重要进展[1-2]。与载人水下航行器相比, AUV凭借着机动性强、无人员伤亡风险、适应能力与生存能力高、制造与维护成本低等优点得到了各国学者的重点关注, 成为海洋勘察和科学研究的重要设备[3-5]。AUV需要实时应对复杂多变的水下环境, 以便顺利规划路径到达目的地, 因而水下避障算法已成为AUV领域的重点研究方向之一。

目前AUV水下避障算法通常分为2类: 第1类为全局路径规划, 在已知整体环境模型的情况下, AUV根据相应算法规划出起始点到目的地的一条安全路径, 具体方法包括栅格法[6]、可视图法[7]和A*算法[8]等, 该算法在动态环境下的避障效果并不理想; 第2类为局部路径规划, AUV通过声呐、激光等传感器感知周围的环境信息, 确定当前环境中障碍物的分布情况, 并根据传感器采集到的水下数据进行小范围避障, 具体方法包括遗传算法[9]、人工势场法[10-14]、神经网络法[15]、模糊逻辑法[16-18]和蚁群算法[19-20]等。

目前AUV水下实时避障的研究难点主要包括以下几点。

1) 动态障碍物避障

AUV在航行过程中, 除了需要规避预定路线上的岩石、珊瑚等静态障碍物以外, 还需通过及时调整自身运动姿态来避开如鱼群、渔网、浮标等动态障碍物[21], 并及时回归规划路线。

2) 多约束与多目标

AUV的航行存在物理约束和几何约束。物理约束指AUV的最大线速度、最大角速度和能量等, 几何约束指AUV的形状和尺寸。AUV规划局部最优路径时存在多个目标, 如路径最短、耗时最短、能耗最低、安全性最佳等, 这些目标之间往往存在冲突[22]。为了进一步提高AUV的避障性能, 在设计实时避障算法时需要引入其多种约束条件并兼顾局部路径规划的多个目标。

3) 海流干扰

AUV通常在复杂多变的海流中工作, 海流会对其航行轨迹造成较大的干扰, 与其相关的路径规划不仅需要考虑避障问题, 还需考虑海流对AUV航行的影响。在路径规划时, 可充分利用海流场的能量, 减少因抵消海流而造成的能量消耗, 因此需要规划出一条能量消耗尽可能少、航行距离尽可能短的路径[20]。

1 避障算法发展历程

机器人避障算法的研究兴起于 20 世纪 60年代[23]。荷兰计算机科学家Dijkstra[24]在 1959 年提出 Dijkstra 算法, 该算法以起点为中心向四周拓展, 直至拓展到终点为止来寻找一条最短的路径。这种算法计算量大, 容易在寻找路径时出现“死区”。1968 年, Hart等[25]提出了一种A*算法, 解决了Dijkstra 算法计算量大、计算时间长的问题。然而该算法较为复杂, 需要比较当前8个相邻栅格点才能得到下一个栅格路径。1975年, Howden等[26]提出了栅格法, 将路径规划问题变成寻求2个栅格节点间的最优路径问题, 但是随着机器人的移动, 环境信息越来越多, 处理时间和存储容量也越来越大, 无法满足实时性要求。Lozano-Perez等[27]在1979年提出了可视图法, 机器人规划最优路径的过程就是寻找从起点到终点直线距离最短的过程, 但是一旦目标移动, 可视图将重新构造并重新规划最佳路径, 因此该算法灵活性较差, 寻找路径的时间较长。由于可视图法仅适用于有棱角的多边形障碍物, 无法避开圆形障碍, Gowda等[28]在1983年对可视图法加以改进, 提出了Voronoi图法并由Takahashi等[29]实现了该算法。Liu等[30]提出了切线图法, 有效改进了可视图法的不足, 但该算法要求机器人必须在接近障碍物时才能避障, 避障精度较差。

1986年, Khatib[31]提出人工势场法, 该算法操作简单, 能够做到实时避障, 但易使规划路径陷入障碍区域的“死区”, 导致避障失败。Boren- stein等[32-33]将人工势场法和网格法结合起来, 提出了虚力场(virtual force field, VFF)算法和矢量场柱状图(vector field histogram, VFH)算法。

1995年, Kennedy等[34]提出粒子群优化(par- ticle swarm optimization, PSO)算法, 该算法具有整体性的优点。但是, 该算法由于粒子之间的相互作用变得非常复杂, 实际优化过程存在多样性, 难以得到适用于所有优化问题的结果。1998年, Kuffner等[35]提出了快速扩展随机树(rapidly-ex- ploring random tree, RRT)搜索算法, 该算法操作简单, 但一般很难一次找到最短路径。

目前常见的水下实时避障算法还包括模糊逻辑法, 以及人工神经网络法、粒子群算法和蚁群算法等智能仿生算法, 各类算法的优缺点如表1所示。

表1 常见水下实时避障算法优缺点对比

2 水下实时避障算法

2.1 改进人工势场法

人工势场法的基本思想是: 将AUV的运动视为一种在虚拟力场中的运动, 障碍物对AUV施加斥力, 目标点则对其施加引力, 引力和斥力的合力控制AUV的运动方向和位置。具体流程如图1所示。

虽然人工势场法对于简单环境很有效, 但由于对其的研究均处于静态环境中, 没有考虑到障碍物的速度和加速度的影响, 所以在动态避障过程中的避障效果不是很理想。在复杂多障碍的环境中, 不合理的势场数学方程容易产生局部极值点, 导致AUV未到达目标点就停止运动, 因此采用人工势场法实现水下避障主要有以下5个缺点: 1) 存在陷阱区域; 2) AUV在相近障碍物间不能发现路径; 3) AUV在障碍物前容易产生震荡; 4) AUV容易在狭窄通道中摆动; 5) 所规划的路径仅为可行路径, 而非最优路径[36]。

为了改进人工势场法仅根据相对距离来控制力的大小问题, 刘学敏等[37]通过设定各个自由度上的运动平衡点, 将AUV的自主避障规划和运动控制结合起来, 解决了人工势场法的陷阱问题。孙玉山等[38]在此基础上进一步改进, 将AUV的航行速度、电池电压等参数引入到警戒距离的设定、艏向角的规划及控制能力等参数中, 提高了AUV的动态避障能力。针对传统人工势场法未考虑到微小型AUV的自身约束条件这一缺点, 杨建等[11]将微小型AUV的运动特性嵌入到人工势场法中。为了解决目标不可达的问题, 李东方等[12]提出了一种基于人工势场和RRT搜索算法的水下避障算法, 通过RRT搜索算法解决路径被锁死的问题。为了寻找水下避障的最优路径, 李东方等[39]将人工势场法与浸入边界法-玻尔兹曼格子法(immersed boundary method-lattice Boltzmann method, IB-LBM)相结合, 实现实时避障功能并能够利用已知环境信息生成最优路径。

图1 人工势场法流程图

上述算法均是针对传统人工势场法的某一缺点进行改进, 计算复杂且并未从本质上解决人工势场法的局部极值问题。产生局部极值和目标不可达问题的本质是势场函数的定义存在缺陷。为了克服局部极值与目标不可达问题, 程志等[14]对斥力的生成和计算机制进行了调整以解决局部极值问题, 同时设立虚拟目标点以摆脱陷阱区域; 李沛伦等[40]对引、斥力势场函数进行改进, 同时引入速度势场函数, 将静态势场转变为动态势场, 综合考虑了水下滑翔机的运动约束和定常海流等因素。王奎民等[41]将海流作用力添加到势场力中, 分别采用定常流和涡流来分析AUV所受合力。同样是改进势场函数, 姚鹏[42]等不仅通过定义修正矩阵来量化障碍物对初始导航向量场的影响, 得到障碍空间下的修正导航向量场, 引导AUV躲避静态障碍, 而且通过引入动态障碍物的参考运动速度, 构建相对初始或相对修正导航向量场, 并采取有限时域推演与调整策略, 最终引导 AUV 躲避动态障碍。

2.2 模糊逻辑法

由于水下环境的复杂性, 建立精确的避障过程数学模型十分困难, 因此无需建立环境数学模型的模糊逻辑法逐渐得到更多的重视。其原理是基于实时传感器信息的模糊逻辑, 参考前人的经验, 通过查表得到规划信息, 实现局部路径规划(如图2所示)。同时因为模糊逻辑法规则库中的每条规则都具有明确的物理意义, 这一独特优点也让利用专家知识调整模糊逻辑规则成为可能。

图2 模糊逻辑法流程图

传统的模糊逻辑法只考虑了AUV周围的环境信息, 但事实上AUV的实时避障过程还和其运动学约束、动力学特性和操纵性有关。为此, 张禹等[17]提出了一种复合模糊实时避障算法, 当遇到障碍时, 由运动控制器和实时避障规划器共同进行运动控制, 提高了远程AUV实时避障过程的机动性和实时性。针对水下非结构化区域, Anwary等[43]采用前馈自适应共振理论(adaptive resonance theory, ART)组件分析非结构化水下环境, 采用模糊BK(Bandler-Kohout)乘积算法对模糊规则集进行插值, 使模糊单元的性能不断适应环境的变化并对最优路径进行决策。模糊逻辑法的另一缺点是主观性强, 而且当输入量增多时, 推理规则和模糊控制规则表会急剧膨胀。基于此, 林政等[16]在模糊逻辑法的基础上进行改进, 提出了一种考虑障碍物所有分布情况的模糊推理规则表并进行了简化处理, 根据环境情况调整航速, 增强了无人水面艇在复杂环境下避障的适应能力。Sun等[44]将三维路径规划简化为水平面和垂直面两部分, 并加入速度综合法, 得到实际的速度和角速度, 同时开发了一种具有加速/中断(a/b)模块的实时导航模糊推理系统, 使AUV能够自动避开动态障碍物。在此基础上, Sun等[45]采用量子粒子群算法(quantum PSO, QPSO)生成隶属度函数的最优边界值, 克服了模糊算法主观性强、环境适应性差的问题, 将优化策略与模糊设计相结合规划三维最优路径。多AUV编队避障方面, Sahu等[46]将人工势场法与模糊算法相结合, 将势函数设计成AUV间距离的因变量来实现多AUV在期望路径上的协同运动和依次避障。

2.3 智能仿生算法

人工神经网络是一种模拟生物神经网络进行信息处理的数学模型, 它模拟大脑的某些机理与机制, 可以有效地实现并行处理、自学习和非线性映射等功能, 在水下实时避障领域具有很大的应用价值[47-48]。

Yan等[49]针对完全未知环境下的AUV, 提出了一种基于生物激励神经网络的无碰撞全覆盖路径规划方法, 不需要事先了解时变工作空间和显式地优化全局代价函数。针对河口环境, Li等[50]研究了河流状况下的生物启发神经网络路径规划, 但仅考虑了静态障碍物, 未对AUV三维动态避障这一核心问题进行研究。为此, 朱大奇等[51]针对突发障碍物和水下三维环境, 在生物启发神经网络模型的基础上将相邻神经元的权值影响加入到模型激励项, 无需样本学习与训练就可实现AUV自主避障。Huang等[52]采用该方法实现了多AUV协同避障, 但该方法未考虑海流对水下实时避障的影响。

针对复杂海流环境下AUV的路径规划问题, 朱大奇等[53]给出了一种基于离散生物启发神经网络(glasius bio-inspired neural networks, GBNN)模型的AUV实时避障算法, 首先神经网络中的每一个神经元与栅格地图中的位置单元一一对应, 然后根据神经元的活性输出值分布情况并结合方向信度算法实现AUV自主路径规划, 最后考虑障碍物环境与动态时变海流对AUV实时避障的影响, 自适应地规划出一条无碰撞且节能的安全路径, 可实现在线路径重规划, 具有较好的实时性。

除了人工神经网络法以外, 遗传算法、PSO算法、蜂群算法[54]、快速搜索随机树算法[55]以及萤火虫算法[56]等智能仿生算法也被应用到水下实时避障领域中。Yao等[57]为了获得最优的避障路径, 对遗传算法中的变异因子进行改进, 并将海流的影响也考虑其中。孙兵等[58]采用粒子群算法对模糊控制器的隶属度函数参数进行优化, 将具有最大适应度值的粒子选作最优解, 最大程度地优化模糊控制器进而指导AUV规划出最优路径。考虑到水下机器人和障碍物的实际尺寸不可忽略, 罗颀栋[59]将警戒栅格的概念引入蚁群算法中, 提出了一种基于保守原则的蚁群算法, 提高了水下避障的安全性, 但延长了避障路径。马焱等[20]将蚁群算法与烟花算法相融合, 先利用烟花算法收敛快的特点寻找参考路径, 然后将其转化为蚁群算法的初始化信息素分布, 在复杂环境下, 该算法在效率和精度上均优于烟花算法和蚁群算法。

3 总结与展望

通过修正势场函数、引入AUV运动约束、考虑障碍物相对速度和复杂海流影响等, 使改进后的人工势场法克服了陷阱问题、局部极小值和目标不可达等缺陷, 成为解决AUV水下实时避障问题的热点研究方向。近年来水下实时避障技术取得了很多研究成果, 但也存在如动态避障效果差、难以兼顾多目标与多约束以及海流对避障干扰严重等亟待解决的技术难点, 结合对各类水下实时避障算法的总结与分析, 针对上述技术难点的研究有望在以下几方面取得突破。

1) 多种水下实时避障算法融合

针对水下复杂未知的动态障碍物, 单一避障算法难以帮助AUV顺利避障。因此学者们趋向于将多种水下实时避障算法进行融合以改善避障效果, 实现多种水下实时避障算法的优势互补, 充分发挥各自算法的优点。例如, 田广等[60]将行为运动学模型和模糊逻辑法相融合, 提高了AUV对未知环境的适应能力; 孙兵等[58]通过PSO迭代优化模糊控制器的设计, 寻找水下局部路径规划的最优解; 马焱等[20]将烟花算法与蚁群算法相融合, 在复杂环境下仍能快速、高精度地寻找到最优路径。因此, 研究如何将多种水下实时避障算法进行有效融合来实现各避障算法的优势互补是一个很有价值的研究方向。

2) 考虑能耗约束的避障算法研究

目前在水下实时避障算法的各种最优目标和约束条件中, 兼顾AUV能耗问题的研究成果较少[20], 罗颀栋[59]甚至通过延长避障路径, 牺牲能耗的方式来提高水下避障的安全性。然而事实上, AUV的能耗问题是影响其续航能力的重要因素, 也是设计和优化水下实时避障算法时必须考虑到的物理约束之一。在设计或改进各种水下实时避障算法时都应该将AUV的能耗问题考虑进来。例如, 在利用模糊逻辑法实现水下实时避障时, 可以设计关于AUV剩余能量的隶属度函数并结合专家经验给出规则表, 通过查表利用剩余能量来决定避障时AUV的线速度和角速度。为了减少避障过程中AUV所消耗的能量, 将其能耗作为参数引入水下实时避障算法会成为一个重要的研究方向。

3)考虑三维海流干扰的避障算法研究

AUV通常工作在复杂多变的海流中, 而海流会对其实时避障造成很大的影响, 因此在设计水下实时避障算法时需要将复杂海流对AUV的影响考虑进来。李沛伦[40]在利用人工势场法解决水下避障问题时仅考虑了定常海流, 该算法无法适应复杂多变的海流环境。王奎民等[41]将海流作用力添加到势场力中, 分别采用定常流和涡流来分析AUV所受合力, 但只考虑了水平方向上流速恒定的海流, 即仅在二维平面内对海流环境建模。Yao等[57]对障碍物附近的定常海流流场进行了三维建模, 通过调整流场权重系数使AUV在某些情况下顺着水流航行, 借此减少能耗或提高导航速度。朱大奇等[53]考虑三维空间下动态时变海流对AUV实时避障的影响, 但该算法存在空间爆炸问题, 即由于空间栅格数量急剧上升所带来的计算量增加, 影响了算法的实时性。随着对水下实时避障算法的进一步研究, 如何解决三维空间下复杂海流对AUV实时避障的干扰将成为水下实时避障研究的热点方向之一。

[1] 李硕, 刘健, 徐会希, 等. 我国深海自主水下机器人的研究现状[J]. 中国科学: 信息科学, 2018, 48(9): 1152-1164.Li Shuo, Liu Jian, Xu Hui-xi, et al. Research Status of Deep-Sea Autonomous Underwater Robot in China[J]. Chinese Science: Information Science, 2018, 48(9): 1152-1164.

[2] 钟宏伟, 李国良, 宋林桦, 等. 国外大型无人水下航行器发展综述[J]. 水下无人系统学报, 2018, 26(4): 273- 282.Zhong Hong-wei, Li Guo-liang, Song Lin-hua, et al. A Review of the Development of Large-Scale Unmanned Underwater Vehicles Abroad[J]. Journal of Unmanned Undersea Systems, 2018, 26(4): 273-282.

[3] Han G, Long X, Zhu C, et al. A High-Availability Data Collection Scheme based on Multi-AUVs for Underwater Sensor Networks[J]. IEEE Transactions on Mobile Com- puting, 2020, 19(5): 1010-1022.

[4] LI D L, Wang P, Du L. Path Planning Technologies for Autonomous Underwater Vehicles-A Review[J]. IEEE Access, 2019, 7: 9745-9768.

[5] 潘光, 宋保维, 黄桥高, 等. 水下无人系统发展现状及其关键技术[J]. 水下无人系统学报, 2017, 25(2): 44-51. Pan Guang, Song Bao-wei, Huang Qiao-gao, et al. Development Status and Key Technologies of Underwater Unmanned System[J]. Journal of Unmanned Undersea System, 2017, 25(2): 44-51.

[6] Li J, Lee M, Lee W, et al. Real Time Obstacle Detection in a Water Tank Environment and its Experimental Study[C]//2014 IEEE/OES Autonomous Underwater Vehicles(AUV). Oxford, MS, USA: IEEE, 2014: 1-5.

[7] Xidias E, Zissis D. Real Time Autonomous Maritime Navigation Using Dynamic Visibility Graphs[C]//2018 IEEE/OES Autonomous Underwater Vehicle Workshop (AUV). Porto, Portugal: IEEE, 2018: 1-6.

[8] Huang C, Huang B, Zhang Y. An Improved A* Algorithm Applied to Three-Dimensional Space[C]//2019 IEEE 8th Jo- int International Information Technology and Artificial Intelligence Conference(ITAIC). Chongqing, China: IEEE, 2019.

[9] Lee J, Kim D W. An Effective Initialization Method for Genetic Algorithm-Based Robot Path Planning Using a Directed Acyclic Graph[J]. Information Sciences, 2016, 332: 1-18.

[10] Montiel O, Sepulveda R, Orozco-Rosas U. Optimal Path Planning Generation for Mobile Robots Using Parallel Evolutionary Artificial Potential Field[J]. Journal of Intelligent & Robotic Systems, 2015, 79(2): 237-257.

[11] 杨健, 孟凡尘. 基于人工势场法的微小型AUV避障运动方法研究[J]. 水雷战与舰船防护, 2017, 25(4): 67-71.Yang Jian, Meng Fan-chen. Research on Obstacle Avoidance Method of Micro AUV Based on Artificial Potential Field Method[J]. Mine Warfare and Ship Protection, 2017, 25(4): 67-71.

[12] 李东方, 王超, 邓宏彬, 等. 基于人工势场和RRT算法的机器蛇水下三维避障算法[J]. 兵工学报, 2017, 38(S1): 205-214.Li Dong-fang, Wang Chao, Deng Hong-bin, et al. Three Dimensional Obstacle Avoidance Algorithm Based on Artificial Potential Field and RRT Algorithm[J]. Journal of Military Engineering, 2017, 38(S1): 205-214.

[13] 吴正平, 唐念, 陈永亮, 等. 基于改进人工势场法的AUV路径规划[J]. 化工自动化及仪表, 2014, 41(12): 1421-1423.Wu Zheng-ping, Tang Nian, Chen Yong-liang, et al. AUV Path Planning Based on Improved Artificial Potential Field Method[J]. Chemical automation and instrumentation, 2014, 41(12): 1421-1423.

[14] 程志, 张志安, 李金芝, 等. 改进人工势场法的移动机器人路径规划[J]. 计算机工程与应用, 2019, 55(23): 1-6.Cheng Zhi, Zhang Zhi-an, Li Jin-zhi, et al. Path Planning of Mobile Robot Based on Improved Artificial Potential Field Method[J]. Computer Engineering and Application, 2019, 55(23): 1-6.

[15] Duan H B, Huang L Z. Imperialist Competitive Algorithm Optimized Artificial Neural Networks for UCAV Global Path Planning[J]. Neurocomputing, 2014, 125: 166-171.

[16] 林政, 吕霞付. 基于改进模糊算法的水面无人艇自主避障[J]. 计算机应用, 2019, 39(9): 1-7.Lin Zheng, Lü Xia-fu. Autonomous Obstacle Avoidance of Surface Unmanned Vehicle Based on Improved Fuzzy Algorithm[J]. Computer application, 2019, 39(9): 1-7.

[17] 张禹, 邢志伟, 黄俊峰, 等. 远程自治水下机器人三维实时避障方法研究[J]. 机器人, 2003, 25(6): 481-485.Zhang Yu, Xing Zhi-wei, Huang Jun-feng, et al. Research on 3D Real-Time Obstacle Avoidance Method of Autonomous Underwater Vehicle[J]. Robot, 2003, 25(6): 481-485.

[18] 韩伟, 孙凯彪. 基于模糊人工势场法的智能全向车路径规划[J]. 计算机工程与应用, 2018, 54(6): 105-109, 167.Han Wei, Sun Kai-biao. Intelligent Omnidirectional Vehicle Path Planning Based on Fuzzy Artificial Potential Field Method[J]. Computer Engineering and Application, 2018, 54(6): 105-109, 167.

[19] 张汝波, 李建军, 杨玉. 基于改进蚁群算法的AUV航路避障任务规划[J]. 华中科技大学学报(自然科学版), 2015, 43(S1): 428-430.Zhang Ru-bo, Li Jian-jun, Yang Yu. AUV Route Obstacle Avoidance Task Planning Based on Improved Ant Colony Algorithm[J]. Journal of Huazhong University of Science and Technology(Natural Science Edition), 2015, 43(S1): 428-430.

[20] 马焱, 肖玉杰, 陈轶, 等. 基于改进烟花-蚁群算法的海流环境下水下无人潜航器的避障路径规划[J]. 导航与控制, 2019, 18(1): 51-59.Ma Yi, Xiao Yu-jie, Chen Yi, et al. Obstacle Avoidance Path Planning of Underwater Vehicle Based on Improved Fireworks Ant Colony Algorithm[J]. Navigation and Control, 2019, 18(1): 51-59.

[21] 陈文渊, 沈斌坚. 基于三维成像声纳技术的AUV前视避障方法[J]. 传感器与微系统, 2015, 34(4): 12-15.Chen Wen-yuan, Shen Bin-jian. Obstacle Avoidance Me- thod of AUV Based on 3D Imaging Sonar Technology[J]. Sensors and Microsystems, 2015, 34(4): 12-15.

[22] 段群杰. 水下机器人实时路径规划方法研究[D]. 哈尔滨: 哈尔滨工程大学, 2007.

[23] Endo G, Togawa K, Hirose S. Study on Self-Contained and Terrain Adaptive Active Cord Mechanism[C]//Pro- ceedings of the 1999 IEEE/RSJ International Conference on Intelligent Robots and Systems(Cat. No.99CH36289). Kyongju, South Korea: IEEE, 1999: 1399-1405.

[24] Dijkstra E W. A Note on Two Problems in Connection with Graphs[J]. Numerische Mathematics, 1959, 1(1): 269-271.

[25] Hart P E, Nilsson N J, Raphael B. A Formal Basis for the Heuristic Determination of Minimum Cost Paths[J]. IEEE Transactions on Systems Science and Cybernetics, 1968, 4(2): 100-107.

[26] Howden W E. Solution Plans and Interactive Problem Solving[J]. Computers & Graphics, 1975, 1(1): 21-26.

[27] Lozano-Pérez T, Wesley M A. An Algorithm for Planning Collision-Free Paths among Polyhedral Obstacles[J]. Communications of the Acm, 1979, 22(10): 560-570.

[28] Gowda I, Kirkpatrick D, Lee D, et al. Dynamic Voronoi diagrams[J]. IEEE Transactions on Information Theory, 1983, 29(5): 724-731.

[29] Takahashi O, Schilling R J. Motion Planning in a Plane Using Generalized Voronoi Diagrams[J]. IEEE Transactions on Robotics and Automation, 1989, 5(2): 143-150.

[30] Liu Y H, Arimoto S. Finding the Shortest Path of a Disc Among Polygonal Obstacles Using a Radius-Independent Graph[J]. IEEE Transactions on Robotics and Automation, 1995, 11(5): 682-691.

[31] Khatib O. Real-time Obstacle Avoidance for Manipulators and Mobile Robots[J]. The International Journal of Robotics Research, 1986, 5(1): 90-98.

[32] Borenstein J, Koren Y. The Vector Field Histogram-Fast Obstacle Avoidance for Mobile Robots[J]. IEEE Tran- sactions on Robotics & Automation, 2002, 7(3): 278-288.

[33] Ulrich I, Borenstein J. VFH+: Reliable Obstacle Avoidance for Fast Mobile Robots[C]//Proceedings of the 1998 IEEE International Conference on Robotics and Automation. Leuven, Belgium: IEEE, 1998: 1572-1577.

[34] Kennedy J, Eberhart R. Particle Swarm Optimization[C]// Proceedings of ICNN’95-International Conference on Neural Networks. Perth, WA, Australia: IEEE, 1995: 1942-1948.

[35] Kuffner J J, Lavalle S M. RRT-connect: An Efficient Approach to Single-Query Path Planning[J]. IEEE International Conference on Robotics & Automation, 2000, 2(1): 995-1001.

[36] 高云峰, 黄海. 复杂环境下基于势场原理的路径规划方法[J]. 机器人, 2004, 26(2): 114-118.Gao Yun-feng, Huang Hai. Path Planning Method Based on Potential Field Principle in Complex Environment[J]. Robot, 2004, 26(2): 114-118.

[37] 刘学敏, 李英辉, 徐玉如. 基于运动平衡点的水下机器人自主避障方式[J]. 机器人, 2001, 23(3): 270-274.Liu Xue-min, Li Ying-hui, Xu Yu-ru. Autonomous Obstacle Avoidance of Underwater Robot Based on Motion Balance Point[J]. Robot, 2001, 23(3): 270-274.

[38] 孙玉山, 张英浩, 常文田, 等. 基于改进运动平衡点的水下机器人自主避障方法研究[J]. 中国造船, 2013, 54 (2): 17-25.Sun Yu-shan, Zhang Ying-hao, Chang Wen-tian, et al. Research on Autonomous Obstacle Avoidance Method of Underwater Robot Based on Improved Motion Balance Point[J]. China Shipbuilding, 2013, 54(2): 17-25.

[39] 李东方, 李科伟, 邓宏彬, 等. 基于人工势场与IB- LBM的机器蛇水中2D避障控制算法[J]. 机器人, 2018, 40(3): 346-359.Li Dong-fang, Li Ke-wei, Deng Hong-bin, et al. 2D Obstacle Avoidance Control Algorithm in Snake Water Based on Artificial Potential Field and IB-LBM[J]. Robot, 2018, 40(3): 346-359.

[40] 李沛伦, 杨启. 基于改进人工势场法的水下滑翔机路径规划[J]. 舰船科学技术, 2019, 41(7): 89-93.Li Pei-lun, Yang Qi. Underwater Glider Path Planning Based on Improved Artificial Potential Field Method[J]. Ship Science and Technology, 2019, 41(7): 89-93.

[41] 王奎民, 赵玉飞, 侯恕萍, 等. 一种改进人工势场的UUV动碍航物规避方法[J]. 智能系统学报, 2014, 9(1): 47-52.Wang Kui-min, Zhao Yu-fei, Hou Shu-ping, et al. A Method to Improve UUV Obstacle Avoidance of Artificial Potential Field[J]. Journal of Intelligent Systems, 2014, 9(1): 47-52.

[42] 姚鹏, 解则晓. 基于修正导航向量场的AUV自主避障方法[J/OL]. 自动化学报. https://kns.cnki.net/KCMS/ detail/11.2109.TP.20190219.1551.005.html, 2019-02-19.Yao Peng, Jie Ze-xiao. AUV Autonomous Obstacle Avoi- dance Method Based on Modified Navigation Vector Field[J]. Acta Automatica Sinica. https://kns.cnki.net/KC MS/detail/11. 2109.TP.20190219.1551.005.html, 2019-02-19.

[43] Anwary A R, Lee Y, Jung H, et al. Unsupervised Real-time Obstacle Avoidance Technique Based on a Hybrid Fuzzy Method for AUVs[J]. International Journal of Fuzzy Logic and Intelligent Systems, 2008, 8(1): 82-86.

[44] Sun B, Zhu D Q, Jiang L S, et al. A Novel Fuzzy Control Algorithm for Three-Dimensional AUV Path Planning Based on Sonar Model[J]. Journal of Intelligent & Fuzzy Systems, 2014, 26(6): 2913-2926.

[45] Sun B, Zhu D Q, Yang S X. An Optimized Fuzzy Control Algorithm for Three-Dimensional AUV Path Planning[J]. In- ternational Journal of Fuzzy Systems, 2018, 20(2): 597-610.

[46] Sahu B K, Subudhi B. Flocking Control of Multiple AUVs Based on Fuzzy Potential Functions[J]. IEEE Transactions on Fuzzy Systems, 2018, 26(5): 2539-2551.

[47] 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: 4688-4695.

[48] Tavares J. Bio-inspired Algorithms for the Vehicle Routing Problem(Studies in Computational Intelligence)[M]. Berlin: Springer, 2009.

[49] 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.

[50] Li S, Guo Y. Neural-network based AUV Path Planning in Estuary Environments[C]//Proceedings of the 10th World Congress on Intelligent Control and Automation. Beijing, China: 10th World Congress on Intelligent Control and Automation, 2012: 3724-3730.

[51] 朱大奇, 孙兵, 李利. 基于生物启发模型的AUV三维自主路径规划与安全避障算法[J]. 控制与决策, 2015, 30(5): 798-806.Zhu Da-qi, Sun Bing, Li Li. AUV 3D Autonomous Path Planning and Obstacle Avoidance Algorithm Based on Bioheuristic Model[J]. Control and decision, 2015, 30(5): 798-806.

[52] Huang Z R, Zhu D Q, Sun B. A Multi-AUV Cooperative Hunting Method in 3-D Underwater Environment with Obstacle[J]. Engineering Applications of Artificial Intel- ligence, 2016, 50: 192-200.

[53] 朱大奇, 刘雨, 孙兵, 等. 自治水下机器人的自主启发式生物启发神经网络路径规划算法[J]. 控制理论与应用, 2019, 36(2): 183-191.Zhu Da-qi, Liu Yu, Sun Bing, et al. Autonomous Heuristic Bioheuristic Neural Network Path Planning Algorithm for Autonomous Underwater Vehicles[J]. Control Theory and Application, 2019, 36(2): 183-191.

[54] Liu H, Xu B, Lu D J, et al. A Path Planning Approach for Crowd Evacuation in Buildings Based on Improved Artificial Bee Colony Algorithm[J]. Applied Sofit Computing, 2018, 68: 360-376.

[55] Wei K, Ren B Y. A Method on Dynamic Path Planning for Robotic Manipulator Autonomous Obstacle Avoidance Based on an Improved RRT Algorithm[J]. Sensors, 2018, 18(2): 571.

[56] Patle B K, Pandey A, Jagadeesh A, et al. Path Planning in Uncertain Environment by Using Firefly Algorithm[J]. Defence Technology, 2018(14): 691-701.

[57] Yao P, Zhao S. Three-Dimensional Path Planning for AUV Based on Interfered Fluid Dynamical System Under Ocean Current[J]. IEEE Access, 2018, 6: 42904-42916.

[58] 孙兵, 朱大奇, 杨元元. 基于粒子群优化的自治水下机器人模糊路径规划[J]. 高技术通讯, 2013, 23(12): 1284-1291.Sun Bing, Zhu Da-qi, Yang Yuan-yuan. Fuzzy Path Planning of Autonomous Underwater Vehicle Based on Particle Swarm Optimization[J]. High Tech Communication, 2013, 23(12): 1284-1291.

[59] 罗颀栋. 水下球形机器人的运动控制方法研究[D]. 北京: 北京邮电大学, 2017.

[60] 田广, 刘和祥, 赵海鹰, 等. 自治式水下机器人避障行为机制研究[J]. 传感器与微系统, 2009, 28(12): 59-63.Tian Guang, Liu He-xiang, Zhao Hai-ying, et al. Research on Obstacle Avoidance Mechanism of Autonomous Underwater Vehicle[J]. Sensors and Microsystems, 2009, 28 (12): 59-63.

Research Progress of Real-Time Obstacle Avoidance Algorithms for Unmanned Undersea Vehicle: A Review

GUO Yin-jing1,2, BAO Jian-kang3, LIU Qi1, QU Yan-xi1, LÜ Wen-hong4

(1. College of Electronic Information Engineering, Shandong University of Science and Technology, Qingdao 266590, China; 2. Qingdao Intelligent Ocean Technology Co., Qingdao 266590, China; 3. College of Electrical Engineering and Automation, Shandong University of Science and Technology, Qingdao 266590, China; 4. College of Transportation, Shandong University of Science and Technology, Qingdao 266590, China)

Aiming at the difficulties and trends in the research of autonomous undersea vehicle(AUV) real-time obstacle avoidance algorithms, the difficulties in the research of underwater real-time obstacle avoidance algorithm are analyzed from three aspects of dynamic obstacles, multiple constraints and multiple objectives, and ocean current disturbance. Then, the research progress of underwater real-time obstacle avoidance algorithm is focused on the three aspects, i.e. artificial potential field method, fuzzy logic method, and intelligent bionic algorithm.By comparing the current researches on three kinds of obstacle avoidance algorithms, it is known that the improved artificial potential field method overcomes the problems of trap, local minimum, and goal unreachability, and becomes the key research direction to solve the real-time obstacle avoidance problem of unmanned undersea vehicle by modifying the potential field function, introducing the AUV motion constraint, considering the relative speed of obstacles and the influence of complex ocean current, etc.In the aspect of avoiding dynamic obstacles, the fusion of multiple obstacle avoidance algorithms will become a trend. As for the multi-constraint and multi-objective problem, energy consumption is particularly important but is rarely introduced into obstacle avoidance algorithm as a parameter, which has great research potential. For the ocean current disturbance, the majority of real-time obstacle avoidance algorithms only consider steady flow or eddy current in the horizontal direction, thus, consideration of the three-dimensional ocean current disturbance will also become one of the research directions of underwater real-time obstacle avoidance algorithm in the future.

autonomous undersea vehicle(AUV); real-time obstacle avoidance algorithm; artificial potential field; fuzzy logic; bionic

U674.941; TJ630.33

A

2096-3920(2020)04-0351-08

10.11993/j.issn.2096-3920.2020.04.001

2019-10-24;

2019-12-15.

山东省重点研发计划(公益类专项)项目(2018GHY115022); 国家自然科学基金(61471224).

郭银景(1966-), 男, 博士, 教授, 主要研究方向为无线通信、AUV导航与控制.

郭银景, 鲍建康, 刘琦, 等. AUV实时避障算法研究进展[J]. 水下无人系统学报, 2020, 28(4): 351-358.

(责任编辑: 陈 曦)