基于贪心蚁群算法的无人水面艇全局路径规划

贺嘉　肖英杰

摘要：

为解决无人水面艇（unmanned surface vessel， USV）在地型较复杂小型水域内的全局路径规划问题，提出一种以贪心算法、蚁群算法、栅格法建模为基础，通过加入双向搜索算法来解决传统贪心算法搜索时易陷入局部最优解等问题的贪心蚁群算法。该算法利用贪心算法规划基础路线，利用蚁群算法的信息素机制摆脱局部收敛状态，并通过双向搜索算法降低局部收敛概率。仿真结果表明：该算法搜索时间较传统蚁群算法减少70%以上，迭代次数较传统蚁群算法减少约85%;该算法在处理USV的全局路径规划问题中具有一定的有效性、合理性。

关键词：

无人水面艇（USV）; 路径规划; 蚁群算法; 贪心算法

中图分类号：  U675.79; TP273+.5

文献标志码：  A

收稿日期： 2020-04-05

修回日期： 2020-11-06

基金项目： 国家自然科学基金（51909155）

作者简介：

贺嘉（1997—），男，湖南衡阳人，硕士研究生，研究方向为海上智能交通，（E-mail）457341658@qq.com;

肖英杰（1959—），男，广东潮州人，教授，船长，博士，研究方向为载运工具应用工程、通航安全保障，（E-mail）xiaoyj@shmtu.edu.cn

Global path planning for unmanned surface vessels

based on  greedy ant colony algorithm

HE Jia， XIAO Yingjie

（Merchant Marine College， Shanghai Maritime University， Shanghai 201306， China）

Abstract：

In order to solve the global path planning problem for unmanned surface vessels （USVs） in small waters with complex terrain，  a greedy ant colony algorithm is proposed， where the greedy algorithm， the ant colony algorithm and the grid method modeling are based on， and the two-way search algorithm is added to solve the problem that the traditional greedy algorithm is easy to fall into the local optimal solution when searching. In the algorithm， the greedy algorithm is used to plan the basic route， the pheromone mechanism of the ant colony algorithm is used to get out of the local convergence state， and the two-way search algorithm is used to reduce the local convergence probability. The simulation results show that， the search time of the algorithm is reduced by more than 70% compared with the traditional ant colony algorithm， the number of iterations is reduced by about 85% compared with the traditional ant colony algorithm， and the algorithm is effective and reasonable in dealing with the USV global path planning problem.

Key words：

unmanned surface vessel （USV）; path planning; ant colony algorithm;  greedy algorithm

0 引 言

近年来，随着计算机科学、传感器、无线网络等技术的快速发展，无人运输设备的研究日新月异。无人水面艇（unmanned surface vessel， USV）技术得到了世界范围内的关注和深入研究。熊勇等[1]对USV的研究现状进行了总结，针对国内外USV研究普遍存在的问题，提出USV研究的根本目标是研发出稳定性强、通用性高、简单好用的控制算法。王石等[2]分析了USV在军事活动中的应用，得出USV在现代战争中有非常重大战略意义的结论。无论是军用USV还是民用USV，在复杂多变的水域内自主规划出一条航程较短的、安全的路径，是保证USV顺利完成任务的基础。

截至目前，国内外许多优秀学者提出了无人运输设备路径规划方案。范云生等[3]通过融合电子海图与雷达图像对空间動态环境进行建模，并利用改进人工势场法对USV路径进行规划。陶重犇等[4]用栅格法对搬运机器人工作环境进行简化建模，并采用改进的模拟退火算法对模型进行求解。孙功武等[5]将改进的蚁群算法用于USV路径规划，通过在蚂蚁发生不同死锁时采取不同策略，大幅度提高了算法搜索过程中有效蚂蚁的数量，加快了算法的收敛速度。DANANCIER等[6]在对无人机进行路径规划时发现，在障碍物随机分布的情况下路径点生成算法的收敛速度明显比Dijkstra算法的快。张毅等[7]在对移动机器人进行路径规划时将独狼视场机制引入精英蚁群算法中，改进了蚁群的寻径能力并提高了算法的全局搜索能力。张岳星等[8]利用电子海图建立静态的三维环境模型，并使用改进的粒子群优化算法对模型进行求解，该方法基本可满足自主式水下潜器在复杂海域航行的全局路径规划需求。

路径规划主要分为静态路径规划和动态路径规划[9-10]。当前，无人运输设备常用的路径规划算法有Dijkstra算法、贪心算法、蚁群算法

[5，7，11-12]、A*算法[11，13]、遗传算法[14-17]等。

其中贪心算法计算量小、算法简单，且其第一个解通常是最优解，十分适合应用于复杂度较陆地来说偏低的水域，因此本文利用贪心算法解决USV的全局路径规划问题。为弥补贪心算法易陷入局部最优解的缺陷，引入蚁群算法。通过贪心算法规划USV基础路线，通过双向搜索算法降低算法局部收敛的概率，利用蚁群算法的信息素机制使算法摆脱局部收敛状态。

1 基于栅格法的水域模型建立

本文运用栅格法对水域进行建模。栅格法建模是采用一系列同样大小的栅格对水域进行建模的方

法。用栅格法建立10×10的水域模型，见图1。图1中：白色栅格为可行栅格，代表可行水域;黑色栅格为不可行栅格，代表不可行水域，即该水域有碍航物，USV无法安全通过;左下角黑色圆点表示USV当前所处位置;右上角方块表示USV需要到达的位置。栅格坐标由栅格的序号表示，如第一行第一列的栅格坐标为（0，0），第一行第二列栅格坐标为（0，1）。当USV处在模型中除模型边缘外的任意栅格时，其周围都应存在8个栅格，此时USV可以向周围任意一个可行栅格移动。

用栅格法建立水域模型后，USV较为复杂的工作环境被转化为简单的环境，USV的路径规划问题问题也被转化为在两个栅格点之间寻找最优路径的问题。

2 改进贪心算法

2.1 传统贪心算法

贪心算法是一种在每一步都作出当前状态下的最佳选择，以期得到的最终结果也是整体最优的算法。比如在背包问题中，每次都选择单位价值最高的一样物品装入背包，就是一种贪心算法。如果一个问题可以使用贪心算法解决，那么在一般情况下，贪心算法会是解决这个问题的最好办法。由于贪心算法具有高效性，且运算所得到的结果比较接近最优结果，因此贪心算法也常被用作辅助算法或者直接被用于解决一些简单问题。

如图2所示，USV处于栅格0中。若USV周围的8个栅格均为可行栅格，则这8个栅格均为USV下一步可以到达的位置;若8个栅格中存在不可行栅格，

则必须

在下一步计算前除去这些栅格。找到所有下一步可以到达的栅格后，计算栅格i与目标栅格end之间的距离：

Di=（xend-xi）2+（yend-yi）2，

i=0，1，2，…，n

式中：xend和yend分别表示栅格end的横、纵坐标;

xi和yi分别表示栅格i的横、纵坐标。D0表示栅格0（USV所处位置）与栅格end之间的距离。

从所有可行栅格中选出距离栅格end最近的栅格，即选取满足条件min{D1，D2，…，Dn}

到达的栅格。若找不到满足这一条件的栅格，则算法陷入局部收敛状态，无法继续进行搜索。

若存在两个栅格a和b（a，b=0，1，2，…，n;a≠b）满足Da=Db，

即USV在路线选择时碰到“分岔路口”时，一般随机作出选择进行下一步计算并对该路线的总路程进行记录。最终进行多次迭代，保留最短的路径。

传统的贪心算法收敛快、计算量小，但一旦该算法陷入局部收敛状态，就无法自行脱出。因此，即使进行多次实验也不一定能找到起始点与终点之间的最佳路径。

2.2 贪心算法的改进

当USV在路径搜索过程中移动到某个不是终点的栅格，找不出满足条件的下一个栅格时，算法就无法继续进行，此类问题即局部收敛问题。

图3所示为

最常见的局部收敛问题：当USV由栅格7向目标点移动时，由贪心算法计算可得向栅格0移动是最优方案;而当USV移动到栅格0后，通过计算发现无法从集合{D1，D5，D6，D7，D8}中找出小于D0的元素，即USV到达栅格0后，找不到能进行下一步计算的最优解，路径搜索陷入停滞，局部收敛问题出现。

实际上，在利用贪心算法进行路径搜索的过程中，只要USV前进方向上存在凹型障碍区域，算法陷入局部收敛状态的可能性就很大。

解决该类问题的方案多为将此时USV所处的栅格加入禁忌表，即将图3中的栅格0由可行栅格转换为不可行栅格，以免USV再次进入该栅格。添加禁忌表的方法虽然有效，但将可行栅格转换为不可行栅格后，路径搜索必须从原点重新开始，会加大运算量，降低算法求得最终解的速度。

针对该类局部收敛问题，本文结合贪心算法的特点引入双向搜索算法。双向搜索算法，即在算法运行时同时进行两个方向的搜索：一个是从起始点向目标点进行正向搜索，另一个是从目标点向起始点进行反向搜索。当两个方向的搜索得到的路径在中间交会或发生部分重叠时，搜索即可停止。

传统贪心算法的路径搜索是从起始点向目标点进行的正向搜索。双向搜索算法在正向搜索的基础上，增加了一个从目标點向起始点的反向搜索。搜索停止后，将正向搜索路径与反向搜索路径结合便可得出USV的最终路径规划结果。采用该方法对随机生成的一张10×10水域模型进行路径搜索，结果见图4。

图4a为采用传统贪心算法计算的结果。由图4a可知，当USV移动到坐标为（4，6）的栅格时，其周围不存在满足“与目标栅格之间的距离<坐标为（4，6）的栅格与目标栅格之间的距离”的可行栅格，USV的运动陷入停滞，算法被迫中断。图4b为在传统贪心算法中引入双向搜索算法后的计算结果。双向搜索算法的正向搜索结果与传统贪心算法的搜索结果相同，反向搜索得到的路径与正向搜索得到的路径交会于坐标为（5，4）的栅格。将正向与反向搜索得到的路径相结合，便可得到最终路径规划结果。

通过多次实验可知，在传统贪心算法中引入双向搜索算法，既不会影响算法的复杂度，又能解决大部分的局部收敛问题，大大加快了算法的收敛速度。

然而，當正向搜索和反向搜索的路径上都存在凹型障碍区域时，用双向搜索贪心算法也无法得出结果。此时便需结合前文所提到的添加禁忌表的方法来解决问题。在此，规定水域模型中坐标为（m，n）的栅格的一项指标Imn

Imn=1， 蚂蚁优先选择该栅格0， 禁止蚂蚁选择该栅格

式中：Imn代表坐标为（m，n）的栅格中蚂蚁信息素的浓度，其中1为最高，0为最低。计算开始前，所有可行栅格中蚂蚁信息素浓度都较低，而所有不可行

栅格中蚂蚁信息素浓度为0。计算开始后，由贪心算法计算得到的下一步最优栅格中蚂蚁信息素浓度变更为1，这样设置的目的是加快下一步迭代的蚂蚁的搜索速度。当双向搜索中出现正向搜索路径与反向搜索路径无法会合的情况，算法陷入局部收敛（如图5a所示）时，USV所处的栅格中蚂蚁信息素浓度发生如下变化：

Imn=1Imn=0

即在发生局部收敛时，将正向和反向搜索路径上USV所处的栅格由可行栅格转换为不可行栅格。随后算法开始进行第二次双向搜索。本次搜索中USV不会进入初次搜索中发生局部收敛的栅格，而是跳出约束寻找更优路径。

图5a中，正向、反向搜索分别在坐标为（7，2）和（3，6）的栅格处陷入局部收敛，搜索中止。在第二次搜索开始时，这两个栅格已经被更改为不可行栅格（如图5b所示）。第二次搜索避开了第一次搜索时发生局部收敛的栅格，成功找到了一条新的最优路径，正向、反向搜索路径交会于坐标为（4，3）的栅格。

综上，结合了双向搜索算法、蚁群算法优势的贪心算法，既能在很大程度上减少计算量，加快算法收敛速度，又能解决大部分复杂度不太高环境下的路径寻优问题，可以用于USV的全局路径规划。

3 仿真验证及结果分析

为使改进后的算法更具有说服力，在Unity3D 5.6平台上将本文算法与传统蚁群算法进行对比。传统蚁群算法参数为：α=4，β=8，ρ=0.7，m=50，

其中α为信息启发式因子，β为期望启发式因子，ρ为信息挥发因子，m为蚂蚁数量

。为验证本文算法的优越性，在不同复杂度的水域模型上进行对比。对真实水域进行精细建模，以验证本文算法在实际情况下运用的可行性。

3.1 20×20水域模型上实验对比

对比图6a与6b可知：在较简单的水域模型上，

本文算法与传统蚁群算法规划出来的最终路线相似，但本文算法规划出来的路径略短，且转弯次数较少。从图6a可以看出，从右下向左上的搜索很早就遇到凹形区域因而不能继续搜索，但此时相反方向的搜索还在继续并最终找到一条最短路径。由表1中的实验数据可知：传统蚁群算法经过21次迭代，历时2.024 s规划出最终路径;本文算法仅迭代1次，历时0.227 s就规划出了比传统蚁群算法更优的路径。

为进一步了解本文算法在更复杂环境下的全局路径规划能力，在30×30水域模型上将本文算法与传统蚁群算法再次进行路径规划对比，实验结果见图7。由图7可以看出，由本文算法规划出的最终路径明显更为简单。由图7a可以看出，本文算法在正向、反向搜索中均遇到凹形区域，因此将陷入局部收敛

的栅格加入禁忌表，然后再次进行搜索得到了最优路径。由表2可知，本文算法的迭代次数（3次）比传统蚁群算法的迭代次数（17次）大

大减少，在迭代时间上也有着极大的优势，并且最终规划出来的路径也更优。

经过大量对比实验可以得出：相较于传统蚁群算法，本文算法迭代次数平均减少约85%，路径规划时间平均减少70%以上。其原因大致如下：本文算法通过贪心算法确定初始路径，可以极大地减少算法迭代次数;由于蚂蚁信息素的存在，本文算法不会搜索多余路径，在寻找最优路径上的时间也大大减少;禁忌表的添加，较好地解决了贪心算法容易陷入局部收敛的问题。

3.3 真实水域模型搭建

为验证本文算法在真实环境下的可行性，对现实水域进行精细建模。本文选定上海海事大学临港校区智慧湖为水域环境的建模区域。

为使水域模型与原水域相似程度更为接近，算法搜索出的路径更优，在建模时使用的栅格极小，可近似视为坐标点。

水岸应向水域内延伸的距离S的计算公式为

S=r+R

式中：r是根据USV实际尺寸将其视为圆形时的半径;R是为防止USV触岸所预留的安全距离。

3.4 实验结果及分析

为方便算法搜索，在仿真时将USV视为质点。仿真时固定目标点，通过多次变换USV初始位置观察算法运行情况。

图8a显示了在初始位置与目标位置间有小型障碍物阻挡时，用本文算法进行路径规划的结果。其中，黑色部分为水域模型，两个方块分别为USV初始位置和目标位置。由图8a可见，USV在接近水岸或水面上的障碍物（不可行区域）时，会与水岸或障碍物保持一个安全距离（S）。最终，正向和反向搜索路径在中段交会，搜索结束，生成最优路径。

图8b显示了在初始位置与目标位置间有大型障碍物阻挡时，用本文算法进行路径规划的结果。由图8b可见：在本次搜索过程中，反向搜索因较大障碍物的影响而无法到达USV初始位置，陷入局部收敛;正向搜索则成功绕过障碍物并在接近目标位置的地方与反向搜索的路径交会，搜索结束，成功生成最优路径。

仿真结果表明，采用结合双向搜索和蚁群算法的贪心算法进行路径规划时，在绝大多数情况下都能够安全避开水域中的障碍物而成功找到一条较优路径。

4 结束语

针对传统的路径搜索算法迭代次数多、运算量较大的缺点，本文以计算简单、迭代次数少的贪心算法为基础算法，结合双向搜索算法、蚁群算法较好摆脱局部收敛问题的優点对算法进行改进，最终提出一种针对无人水面艇（USV）全局路径规划的改进贪心算法。对上海海事大学临港校区智慧湖进行建模，并在USV初始位置与目标位置之间设置障碍物进行路径规划仿真，发现USV能在避开水中障碍物的前提下成功找出一条最优路径。仿真结果表明，本文提出的算法是一种比较合理、效率较高的USV路径搜索算法。

参考文献：

[1]熊勇， 余俊， 张加， 等. 无人艇研究进展及发展方向[J]. 船舶工程， 2020， 42（2）： 12-19.

[2]王石， 张建强， 杨舒卉， 等. 国内外无人艇发展现状及典型作战应用研究[J]. 火力与指挥控制， 2019， 44（2）： 11-15. DOI： 10.3969/j.issn.1002-0640.2019.02.003.

[3]范云生， 柳健， 王国峰， 等. 基于异源信息融合的无人水面艇动态路径规划[J]. 大连海事大学学报， 2018， 44（1）： 9-16. DOI： 10.16411/j.cnki.issn1006-7736.2018.01.002.

[4]陶重犇， 雷祝兵， 李春光， 等. 基于改进模拟退火算法的搬运机器人路径规划[J]. 计算机测量与控制， 2018， 26（7）： 182-185. DOI： 10.16526/j.cnki.11-4762/tp.2018.07.040.

[5]孙功武， 苏义鑫， 顾轶超， 等. 基于改进蚁群算法的水面无人艇路径规划[J/OL]. 控制与决策： 1-10[2020-11-04]. DOI： 10.13195/j.kzyjc.2019.0839.

[6]DANANCIERK， RUVIO D， SUNG I，et al. Comparison of path planning algorithms for an unmanned aerial vehicle deployment under threats[C]//9th IFAC Conference on Manufacturing Modelling， Management and Control MIM 2019. IFAC， 2019， 52（13）： 1978-1983. DOI： 10.1016/j.ifacol.2019.11.493.

[7]张毅， 权浩， 文家富. 基于独狼蚁群混合算法的移动机器人路径规划[J]. 华中科技大学学报（自然科学版）， 2020， 48（1）： 127-132. DOI： 10.13245/j.hust.200123.

[8]张岳星， 王轶群， 李硕， 等. 基于海图和改进粒子群优化算法的AUV全局路径规划[J]. 机器人， 2020， 42（1）： 120-128. DOI： 10.13973/j.cnki.robot.190100.

[9]刘军， 冯硕， 任建华. 移动机器人路径动态规划有向D*算法[J]. 浙江大学学报（工学版）， 2020， 54（2）： 291-300. DOI： 10.3785/j.issn.1008-973X.2020.02.010.

[10]YANShuxue， LI Yiping， FENG Xisheng，et al. An AUV adaptive sampling path planning method based on online model prediction[C]//12th IFAC Conference on Control Applications in Marine Systems， Robotics， and Vehicles CAMS 2019. IFAC， 2019， 52（21）： 323-328. DOI： 10.1016/j.ifacol.2019.12.327.

[11]万逸飞， 彭力. 改进A*蚁群算法求解机器人路径规划问题[J]. 传感器与微系统， 2019， 38（12）： 153-156， 160. DOI： 10.13873/j.1000-9787（2019）12-0153-04.

[12]赵静， 汤云峰， 蒋国平， 等. 基于改进蚁群算法的移动机器人路径规划[J]. 南京邮电大学学报（自然科学版）， 2019， 39（6）： 73-78. DOI： 10.14132/j.cnki.1673-5439.2019.06.011.

[13]CHENBiyu， CHEN Xiaowei， CHEN Huiping，et al. Efficient algorithm for findingk shortest paths based on reoptimization technique[J]. Transportation Research Part E， 2020， 133： 101819. DOI： 10.1016/j.tre.2019.11.013.

[14]杜胜， 刘轶华， 陈茜， 等. 基于遗传算法的开敞水域帆船航线规划[J]. 上海海事大学学报， 2018， 39（2）： 1-6. DOI： 10.13340/j.jsmu.2018.02.001.

[15]李天童， 宁平凡， 牛萍娟. 基于改进遗传算法的工厂AGV安全路径规划[J]. 组合机床与自动化加工技术， 2020（3）： 160-163. DOI： 10.13462/j.cnki.mmtamt.2020.03.038.

[16]宋宇， 王志明. 基于改进遗传算法的移动机器人路径规划[J]. 现代电子技术， 2019， 42（24）： 172-175. DOI： 10.16652/j.issn.1004-373x.2019.26.041.

[17]孙波， 姜平， 周根荣， 等. 基于改进遗传算法的AGV路径规划[J]. 计算机工程与设计， 2020， 41（2）： 550-556. DOI： 10.16208/j.issn1000-7024.2020.02.038.

（编辑 贾裙平）