基于改进蚁群算法的水面无人艇路径规划  

Path planning for unmanned surface vehicle based on improved ant colony algorithm

作　　者：孙功武 苏义鑫[2] 顾轶超 谢基榕[1] 王俊轩 SUN Gong-wu;SU Yi-xin;GU Yi-chao;XIE Ji-rong;WANG Jun-xuan(State Key Laboratory of Deep-sea Manned Vehicles,China Ship Scientific Research Center,Wuxi 214082,China;School of Automation,Wuhan University of Technology,Wuhan 430070,China)

机构地区：[1]中国船舶科学研究中心深海载人装备国家重点实验室,江苏无锡214082 [2]武汉理工大学自动化学院,武汉430070

出　　处：《控制与决策》2021年第4期847-856,共10页Control and Decision

基　　金：江苏省自然科学基金项目(K20170217);七〇二所自主培育项目(51811001K1741SK)。

摘　　要：针对水面无人艇路径规划问题,提出一种改进蚁群算法进行求解.该算法建立作用时效不同的局部禁忌表和全局禁忌表,实现对蚂蚁途经栅格的分类存储,在蚂蚁发生障碍死锁和自死锁时分别采取不同的死锁处理策略,从而降低无效蚂蚁产生的概率,提高解的多样性;引入当前蚂蚁所处栅格与终点栅格之间的欧式距离,设计自适应启发函数,以避免蚂蚁路径搜索的初期盲目性与后期单一性;适时采用历史最优路径替换本轮迭代中的最差路径,保证已搜索到的最优路径不会丢失.在不同规模、不同复杂度地图中的仿真结果表明,所提出改进算法能够大幅度提高搜索过程中有效蚂蚁的数量,其收敛速度与精度两方面性能均优于未改进算法.在规模较大、复杂度较高的地图中,更能体现应用改进算法的优越性.An improved ant colony algorithm for USV(unmanned surface vehicle) path planning is presented. A local tabu list and a global tabu list with different effect duration are set up to catalog the ants passed grids.Various deadlock processing strategies are introduced upon barrier deadlock and self deadlock situation in order to reduce the number of invalid ants and to improve the diversity of solutions. An adaptive heuristic function is designed by adopting the Euclidean distance between the ant and the destination to avoid the initial blindness and later singleness of ant path searching. The current worst path would be superseded by the historical best path when appropriate to retain the previous effort. Simulation results under different maps show that the improved algorithm considerably increases the number of effecive ants during the searhing process and the probability to find the optimal path, as well as the search speed. The improved algorithm performs even better in larger and more complex grid maps.

关 键 词：水面无人艇 路径规划 蚁群算法 死锁 自适应启发函数 最优路径 

分 类 号：TP242.2[自动化与计算机技术—检测技术与自动化装置]