自由运动方向下改进蚁群算法的AUV路径规划*

周 鑫 徐荣武，2 程 果，2 高端阳

（1.海军工程大学振动与噪声研究所 武汉 430033）（2.船舶振动噪声重点实验室 武汉 430033）（3.海军大连舰艇学院航海系 大连 116000）

1 引言

水下自主航行器（AUV）具有机动范围大，灵活性好、隐蔽性高等优点，使它广泛应用于军用、民用领域［1］。水下航行器在执行水下任务的过程中，常常会遇到各种障碍物，或不可靠近的物体，尤其是在对抗演练，搜素穿越的过程中，其关键问题就是路径规划。

蚁群算法是路径规划的常用方法，使用蚁群算法进行环境建模的基本思路为栅格法［2～4］，即将环境划分为大小相同的正方形栅格，将AUV 视为一个质点，每次移动时从当前位置向临近的栅格移动。这种方法虽然建立简单表示方便，但却限制了AUV 其移动角度，只能向固定的方向前进，如0°，45°，90°等；同时允许其在较短步长内改变较大的移动方向，甚至可以调转180°，这与AUV 在水下实际运行状况存在较大差异。

由于AUV 所处的水下环境，及其自生结构原因，其机动能力、姿态调整能力有限，传统意义上无约束的路径规划方式在实际运用中具有一定的难度。针对这个问题，本文提出一种自由运动方向下基于信息素初始布置的改进蚁群算法，该方法以改进的人工势场法规划路径作为初始路径进行信息素初始布置，能够在AUV 在转向角度受到合理限制的情况下完成对复杂动态环境路径规划。

2 改进的人工势场法路径规划

人工势场法（Artificial Potential Field，APF）是由Khatib 最早引入到移动机器人的避障及路规划领域中［5］，用它进行路径规划虽然简单，但是也有着其固有的局限性，例如存在局部极小值、目标不可达，狭窄路线抖动等问题［6～8］。而在面对动态障碍物时，这些问题在应对动态障碍物环境时会被弱化，但也容易出现受迫运动的情况。为此提出有利前进方向判断解决AUV 受迫运动的问题，同时基于可视图法对路径规划进一步优化，并以该路径为基础作为改进蚁群算法进行初始信息素布置。

2.1 人工势场法的有利前进方向判断

对AUV 而言，该方法是在AUV 运动环境中建立虚拟势场，由目标点产生的引力势场和障碍物产生的斥力势场组成，AUV 在引力和斥力的共同作用下，向目标点移动。

通过分析AUV 受力情况可知，在AUV 所受到的引力与斥力角度接近同向或反向时，会使AUV移动出现抖动，在引力与斥力角度完全同向或反向时，则会出现局部极小值。若任其保持在此状态下，会使得AUV无法解脱或需要大量时间解脱。

本文结合AUV 与动态障碍物相遇的方向和位置，采用向有利于规避障碍物并靠近目标点的方向调整引力角度的方式，在脱离抖动状态的同时，以有利方向绕过障碍物。

当AUV 规避动态障碍物时，可以根据相AUV与障碍物的相对运动方向分为正向障碍物和侧向［9］。对于正面障碍物，AUV移动方向与障碍物移动方向相同或相反，AUV 可以选择顺时针方向或逆时针方向进行规避；对于侧向相遇障碍物，AUV移动方向与障碍物移动方向形成一定的夹角，选择有利于靠近目标点的方向前进，如图1所示。

图1 测向障碍物

2.2 基于可视图法的动态障碍物规避路径优化

为进一步优化AUV 规避动态障碍物的移动路径，通过可视图法［10］对AUV 所受引力方向进行调整，从而达到移动路径优化的目的。

可视图法的基本思想是在AUV 移动空间中的任意形状的障碍物看成是由多边形或者多面体组成的，在此基础上，连接AUV、障碍物、目标点的所有顶点，并确保所有连接线与障碍物都没有任何的交点。将可视图法与人工势场法相结合，通过可视图法对AUV 所受引力方向进行调整，可以达到移动路径优化的目的。根据可视图法的基本原则，最优路径应为AUV 所在位置到障碍物边界点连线，对曲边的障碍物而言即为切线。当判断得知AUV与动态障碍物在相遇路线上时，找到一个时间点t，使得AUV 初始位置到该时刻上障碍物的切线长度，等于这段时间AUV 的运动距离。如图2所示，即：

图2 可视图法角度调整示意图

式中，l为AUV 初始位置R到切点P的距离，t0为初始时间或绕过上一个障碍物的时间点，f为移动频率，L为移动步长。

根据有利前进方向判断可得调整角度：

式中，θo为t时刻下，AUV 移动方向到障碍物位置方向的角度；θr为t时刻下，障碍物位置方向与相应切线的夹角；λ为有利前进方向。

当调整角度为正时，逆时针调整角度；当调整角度为负时，顺时针调整角度。当AUV 与障碍物距离较远时，采用基于可视图法优化的方案移动，当AUV 靠近障碍物时，在障碍物产生的斥力和抖动解除方法作用下，选择有利前进方向绕过障碍物，继续对下一个可能相遇的障碍物重复上述操作。

3 改进的蚁群算法路径规划

蚁群算法是由Dorigo.M 等在20世纪90年代提出的一种新型进化算法，由对蚂蚁搜索问题的研究得出此算法。蚂蚁在觅食过程中，会在通过的路径上会留下信息素，根据路径上信息素的大小，蚂蚁会逐渐选择信息素更大的路径前进，信息素浓度越大，该路径被选择的概率就越大，在整个蚂蚁系统中形成一个正反馈机制，最终找到一条从起点到终点的最优路径［11～13］。

本文针对AUV 在水下实际运动规律，提出了AUV 在合理的可转向范围内自由选择运动方向的算法模型，同时为提高路径收敛速度，提出初始信息素布置的改进方法。

3.1 自由运动方向下的蚁群算法

传统蚁群算法是将信息素分布在每一段可能经过的路径上，AUV 可以到达的位置是预先设定且有限的。自由运动方向下的蚁群算法模型是将AUV 移动的空间中设置若干个信息素点，用于储存蚁群算法中所需的信息素，这些信息素点仅用于计算每个步长附近的信息素，并不要求AUV 的每一步起点或终点落到这些信息素点上。从理论上说，AUV可以到达运动环境中的任意位置。

AUV 在移动过程中，根据上一步的移动方向和设定的最大转角，确定在新的步长时间段内最大可转向范围。如图3所示，AUV可以在此范围内进行转向，在转向范围内将可转向角度分为若干不同路径，对每个路径方向终点附近的信息素点的信息素均值，作为该路径上的信息素，最后依据轮盘赌的方式随机选择路径。

图3 自由运动方向下的算法模型示意图

3.2 信息素初始布置

在通过改进的人工势场法规划出初始路径后，基于此路径对移动空间中的信息素点进行初始化，将AUV 移动的空间中划分出i×j个信息素点，用于储存蚁群算法中的信息素，当信息素点到初始路径距离小于dL时，为该信息素点进行赋值，其信息素初始值为

3.3 人工势场法临时修正

为了加快路径收敛速度，可以利用AUV 与障碍物、目标点的位置关系，基于人工势场法受力分析，为引力方向上的信息素点的信息素数值，从而对AUV移动进行进一步引导。如图4所示。

图4 人工势场法临时信息素修正示意图

在AUV 前进到任意位置，会受到来自目标点的引力和来自障碍物的斥力，其合力为

在合力方向的一定距离上确定为临时目标点，对临时目标点附件的信息素点进行修正，距离该点越近，信息素点上的信息素变得越大：

式中：kf为临时信息素调整参数；df为势场法对信息素的影响范围；dijf为第i行、第j列信息素点到势场法目标点的距离。

3.4 转移概率

将传统算法中固定在路径中的信息素释放到整个移动空间内，用每个步长终点附近的信息素点作为选择该路径的概率计算依据，转移概率为

3.5 不利路径回溯与排除

为保证路径搜索的效率，当AUV 运行到超出信息素布置范围，或与障碍物相遇时，使其路径返回到上一步重新进行路径方向选择，若在同一位置已多次需要进行回溯，则增加路径向前回溯长度。同时设置一个阈值，当AUV 回溯次数超过这一阈值时，则判断该路径搜索失败，停止该路径的搜索并将该路径排除，重新进行新的路径搜索。

3.6 精英蚂蚁系统的信息素更新

在每一代蚁群搜索路径后，对到目前为止已经规划出的路径进行排序，选择所有历史路径中最短的一部分路径进行信息素更新；精英蚂蚁路径信息素更新方式与初始信息素更新方式类似，但其信息素作用距离应根据实际情况进行调整。

3.7 改进的蚁群算法路径规划流程

如图5所示。

图5 改进的蚁群算法路径规划流程图

4 试验仿真

设定AUV在10*10的空间内进行路径规划，在空间内设置2000*2000 个信息素点用于储存信息素，建立复杂的移动环境，在移动空间中设置动态障碍物3个和静态障碍物4个，各障碍物距离较近，相关参数如表1。

表1 复杂动态环境参数设置表

4.1 基于可视图法改进的人工势场法路径规划仿真分析

分别采用传统人工势场法（算法一）、加入有利前进方向判断的势场法（算法二）、基于可视图法改进的势场法（算法三）对AUV 移动路径进行规划，验证改进的人工势场法在路径规划中可行性。不同算法下路径规划情况如图6所示，靠近各障碍物步数及到达目标点步数分析如表2所示。

表2 路径节点分析表

图6 不同算法绕行障碍物

图7 简单环境-方案一-路径示意图

图8 简单环境-方案二-路径示意图

从图9、表2 可以看出，传统势场法在面对动态障碍物时，会使AUV 受迫与动态障碍物一起运动，需要大量时间进行解脱；而加入有利前进方向判断的势场法能够有效避免这个问题。同时，基于可视图法改进的势场法能够让AUV 更早的选择有利前进方向绕过障碍物；传统势场法使AUV 在静态障碍物3、4 的斥力和目标点的引力方向基本相反，导致其无法继续向目标点前进；基于可视图法改进的势场法，相对于加入有利方向判断的势场法能够提前选择绕行障碍物的方向，提高绕过障碍物的效率，优化率为4.2%。

图9 简单环境-方案三-路径示意图

4.2 改进的蚁群算法仿真分析

分别在简单动态环境和复杂动态环境中对改进的蚁群算法进行仿真分析，使AUV 能够在有限制的转向范围内自由选择前进方向，验证算法的可行性。算法基本参数如表3所示。

表3 改进的蚁群算法参数表

在此参数的基础上，每代蚂蚁寻路结束后，选取历史最优的10 条路径对环境信息素进行更新。同时对本文采用的不同优化模块（人工势场法临时修正、路径回溯与排除、信息素初始布置）进行分析，仿真方案如表4所示。

表4 优化模块选择方案表

1）简单动态环境仿真

简单动态环境中设置动态障碍物2 个，静态障碍物3 个，各障碍物距离较远，相关参数如表5所示，达到相应的迭代次数后，各方案历史最优的10条路径如图7～图10所示。

表5 简单动态环境障碍物设置

图10 简单环境-方案四-路径示意图

由图可知，在简单的动态环境中，方案一至方案三在一次迭代后找到的路径都比较分散，随着迭代次数的增加能够逐渐收敛，并且最终都能收敛到最优路径附近，而方案四中一次迭代后路径收敛程度明显优于其他方案。从表6可以看出，加入不同的优化模块能够有效加快迭代速度，并缩短最优路径，其中方案四用时最短、搜索路径最优，验证了改进的蚁群算法在动态障碍物环境下的可行性。

2）复杂动态环境

复杂动态环境中障碍物设置与验证势场法时一致，如表所示。各方案在不同迭代次数后历史最优的10条路径如图11～图14所示。

图11 复杂环境-方案一-路径示意图

图12 复杂环境-方案二-路径示意图

图13 复杂环境-方案三-路径示意图

图14 复杂环境-方案四-路径示意图

由路径图和表7可知，方案一至方案三在一次加入势场法修正算法和不利路径回溯与排除算法后，能够加快迭代速度，缩短最优路径，但难以适应复杂动态环境中的狭窄通道，只能找到局部次优路径。在方案四中，进行初始信息素布置后，能够迅速找到最优路径，验证了改进的蚁群算法在复杂的动态环境中的可行性。

表7 复杂动态环境下各方案仿真数据对比

5 结语

本文针对AUV 在水下姿态调整能力有限的特征，提出了一种自由运动方向下基于信息素初始布置的改进蚁群算法，使AUV 能够在合理可转向范围限制下完成路径规划。建立AUV 在合理的可转向范围内自由运动的算法模型，并以基于可视图法改进的人工势场法规划的路径为初始路径，为运动环境进行信息素初始布置，再引入势场法信息素临时修正和不利路径回溯与排除等优化算法，实现了对蚁群算法的改进。通过仿真实验验证可得，改进的人工势场法较传统势场法路径长度缩短约4.2%；改进的蚁群算法较改进的势场法路径长度再缩短约8.1%，并且能够在复杂的动态环境下快速找到最优路径。