动态环境下改进蚁群算法的多Agent路径规划

计算机工程与科学

动态环境下改进蚁群算法的多Agent路径规划

郑延斌1,2，王林林1，席鹏雪1，樊文鑫1，韩梦云1

（1.河南师范大学计算机与信息工程学院，河南新乡 453007；

2.智慧商务与物联网技术河南省工程实验室，河南新乡 453007）

收稿日期:2018-07-06 修回日期:2018-09-26 出版日期:2019-06-25 发布日期:2019-06-25
基金资助:
河南省科技攻关项目(142300410349,132102210538);河南省软科学项目(142400411001);河南师范大学青年基金（2017QK20）

An improved ant colony algorithm for multi-agent

path planning in dynamic environments

ZHENG Yanbin1,2,WANG Linlin1,XI Pengxue1,FAN Wenxin1,HAN Mengyun1

（1.College of Computer and Information Engineering,Henan Normal University,Xinxiang 453007;

2.Henan Engineering Laboratory of Intellectual Business and Internet of Things Technologies,Xinxiang 453007,China）

Received:2018-07-06 Revised:2018-09-26 Online:2019-06-25 Published:2019-06-25

摘要/Abstract

摘要：

针对动态环境下的多Agent路径规划问题，提出了一种改进的蚁群算法与烟花算法相结合的动态路径规划方法。通过自适应信息素强度值及信息素缩减因子来加快算法的迭代速度，并利用烟花算法来解决路径规划过程中的死锁问题，避免陷入局部最优。在多Agent动态避碰过程中，根据动态障碍物与多Agent之间的运行轨迹是否相交制定相应的避碰策略，并利用路径转变函数解决多Agent的正面碰撞问题。仿真实验表明，该方法优于经典蚁群算法，能够有效解决多Agent路径规划中的碰撞问题，从而快速找到最优无碰路径。

关键词: 蚁群算法, 动态环境, 烟花算法, 避碰策略, 路径规划

Abstract:

Aiming at the problem of multi-agent path planning in dynamic environments, we propose an improved dynamic path planning method by combining the ant colony algorithm and fireworks algorithm. This method accelerates the iteration speed of the algorithm by adapting the pheromone intensity value and the pheromone reduction factor, and uses the fireworks algorithm to solve the deadlock problem in the path planning process and avoid falling into a local optimum. In the process of multi-agent dynamic collision avoidance, corresponding collision avoidance strategies are made according to whether the motion trajectory between dynamic obstacles and multiagent intersects, and the path collision function is used to solve the multi-agent frontal collision problem. Simulation results show that the proposed algorithm is superior to the traditional ant colony algorithm. It can effectively solve the collision problem in multiagent path planning, and quickly find the optimal collision-free path.

Key words: ant colony algorithm, dynamic environment, fireworks algorithm, collision avoidance strategy, path planning

郑延斌1,2，王林林1，席鹏雪1，樊文鑫1，韩梦云1. 动态环境下改进蚁群算法的多Agent路径规划[J]. 计算机工程与科学.

ZHENG Yanbin1,2,WANG Linlin1,XI Pengxue1,FAN Wenxin1,HAN Mengyun1.

An improved ant colony algorithm for multi-agent

path planning in dynamic environments

[J]. Computer Engineering & Science.

[1]	吕倩茹, 杨翔瑞, 蔡志平. 基于影响力地图的计算机兵棋推演路径规划[J]. 计算机工程与科学, 2024, 46(06): 1041-1049.
[2]	沈克宇, 游志宇, 刘永鑫. 基于拟合优先搜索的多场景自适应改进A*算法[J]. 计算机工程与科学, 2024, 46(01): 142-149.
[3]	李中华, 袁杰, 郭振宇. 基于信息启发的目标导向Bi-RRT机器人路径规划[J]. 计算机工程与科学, 2023, 45(12): 2237-2245.
[4]	张贝, 闵华松, 张新明. 差分变异和领地搜索的平衡优化算法及其机器人路径规划[J]. 计算机工程与科学, 2023, 45(11): 2078-2090.
[5]	张志远, 陈海进, 章一鸣. 基于局部障碍率预获取和双向父节点变更的A*算法优化[J]. 计算机工程与科学, 2023, 45(09): 1661-1669.
[6]	于家斌, 陈志豪, 邓维, 许继平, 赵峙尧, 王小艺. 一种无人巡航船遍历多目标点的路径规划算法研究[J]. 计算机工程与科学, 2023, 45(05): 840-848.
[7]	申晓宁, 许笛, 宋丽妍, 姚铖滨, 王玉芳, . 采用离散烟花算法的移动群智感知异构任务分配[J]. 计算机工程与科学, 2023, 45(02): 321-331.
[8]	顾楚梅, 曹建军, 王保卫, 徐雨芯, . 基于蚁群参数优化的LightGBM辐射源个体识别[J]. 计算机工程与科学, 2023, 45(01): 85-94.
[9]	杨炳媛, 袁杰, 郭园园. 一种自适应鲸鱼快速优化算法[J]. 计算机工程与科学, 2023, 45(01): 145-153.
[10]	申晓宁, 游璇, 陈庆洲, 潘红丽, 黄遥. 采用双档案协同进化离散多目标烟花算法的低碳疫苗冷链优化配送[J]. 计算机工程与科学, 2022, 44(12): 2255-2265.
[11]	郭园园, 袁杰, 赵克刚. 基于改进A*算法和动态窗口法的机器人路径规划[J]. 计算机工程与科学, 2022, 44(07): 1273-1281.
[12]	赵广元, 赵英. 基于改进蚁群优化算法的养殖场机器人路径规划[J]. 计算机工程与科学, 2022, 44(05): 910-915.
[13]	赵炳巍, 贾峰, 曹岩, 孙瑜, 刘一鸿. 基于模拟退火算法的人工势场法路径规划研究[J]. 计算机工程与科学, 2022, 44(04): 746-752.
[14]	刘雨青, 向军, 曹守启. 基于改进蚁群算法的水下自主航行机器人路径规划[J]. 计算机工程与科学, 2022, 44(03): 536-544.
[15]	张志远, 陈海进. 基于动态矩阵的未知环境地图构建与路径规划[J]. 计算机工程与科学, 2022, 44(03): 563-570.