基于改进人工鱼群算法的蠕虫机器人路径规划  

New Grid Map Path Planning Based on Improved Artificial Fish Swarm Algorithm

作　　者：姜晓东 任奕辰 朱晓东[1] JIANG Xiaodong;REN Yichen;ZHU Xiaodong(School of Electrical and Information Engineering,Zhengzhou University,Zhengzhou 450001,China;School of Computer Science and Engineering,Hong Kong University of Science and Technology,Hong Kong 999077,China)

机构地区：[1]郑州大学电气与信息工程学院,河南郑州450001 [2]香港科技大学计算机科学与工程学系,中国香港999077

出　　处：《郑州大学学报（工学版）》2024年第3期55-63,共9页Journal of Zhengzhou University（Engineering Science）

基　　金：国家科学自然基金资助项目(61806179)。

摘　　要：针对人工鱼群算法在机器人路径规划中存在路径长、精度不高、易陷入局部最优等问题,提出了一种改进的人工鱼群算法,旨在提高算法效率及精度。首先,在算法觅食行为中加入寻优循环,减少算法在路径规划中选取位置点的随机性,使机器人能够更快地走向目标点;其次,融合禁忌搜索算法,通过引入禁忌表来记录算法陷入局部最优的路径,使算法在选取新位置点时能够避开局部最优区域,避免算法在局部过度循环,同时对规划出的路径进行优化处理,删去重复栅格点之间的路径,保证路径中没有重复的栅格点;最后,将改进后的人工鱼群算法应用在一种新型的三维栅格地图中。实验结果表明:相较于其他对比算法,在地图1、2、3中改进人工鱼群算法所取得的平均路径长度分别减少了10%、15%、30%,在复杂地图中路径规划的成功率提高了75%。Aiming at the problems of long paths,low accuracy and prone to local optima of the artificial fish swarm algorithm in robot path planning,an improved artificial fish swarm algorithm was proposed,which aimed to improve the efficiency and accuracy of the algorithm.An improved artificial fish swarm algorithm aimed at improving algorithm efficiency and accuracy was proposed in this study.Firstly,an optimization cycle was added to the algorithm′s foraging behavior to reduce the randomness of the algorithm′s selection of location points in path planning,enabling the robot to move towards the target point faster.Then,the tabu search algorithm was integrated,and the tabu table was introduced to record the path where the algorithm might fall into the local optimum,so that the algorithm can avoid the local optimum region when selecting new location points,and could avoid the algorithm′s local excessive cycle.At the same time,it could optimize the planned path,delete the paths between duplicate grid points,and ensure that there would be no duplicate grid points in the path.When the improved artificial fish swarm algorithm was applied to a new type of 3D raster map,simulation experiments showed that compared to other comparative algorithms,the average path length obtained by improving the artificial fish swarm algorithm in maps 1,2 and 3 was reduced by 10%,15%and 30%,respectively,and the success rate of path planning in complex maps was increased by 75%.

关 键 词：蠕虫机器人 人工鱼群算法 路径规划 禁忌搜索 栅格地图 

分 类 号：TP242[自动化与计算机技术—检测技术与自动化装置] TP391.9[自动化与计算机技术—控制科学与工程]