融合进化蚁群算法与冲突预测消解的双层路径规划

于凯营; 徐斌

doi:10.12299/jsues.24-0087

融合进化蚁群算法与冲突预测消解的双层路径规划

doi: 10.12299/jsues.24-0087

于凯营,
徐斌^,

上海工程技术大学机械与汽车工程学院, 上海 201620

基金项目: 国家自然科学基金（61703268）

详细信息

作者简介:
于凯营（1995 − ），男，硕士生，研究方向为路径规划。E-mail：kmkying@foxmail.com

通讯作者:
徐　斌（1984 − ），男，副教授，博士，研究方向为智能计算及应用。E-mail：bxu@sues.edu.cn

中图分类号: TP242
计量
- 文章访问数: 15
- HTML全文浏览量: 11
- PDF下载量: 1
- 被引次数: 0
出版历程
- 收稿日期: 2024-03-25
- 网络出版日期: 2025-09-30
- 刊出日期: 2025-06-30

Double-layer path planning based on evolutionary ant colony algorithm and conflict prediction resolution

YU Kaiying,
XU Bin^,

School of Mechanical and Automotive Engineering, Shanghai University of Engineering Science, Shanghai 201620, China

摘要

摘要: 针对蚁群算法求解多移动机器人协同路径规划问题时存在的搜索效率较低、路径冲突难以协调等问题，提出一种双层协同路径规划方法。在静态层，将遗传算法的交叉机制融入蚁群算法建立进化路径交叉策略，提高规划路径的质量，同时采用信息素增量差异化计算方式，提高蚁群算法的收敛速度。在动态层，基于三维时空图进行碰撞预测，利用优先无冲突策略有效解决路径的冲突问题。仿真结果表明，提出的双层动态协同路径规划方法能够提高算法的综合性能，解决协同路径规划问题，并验证了算法的可行性和有效性。
- 多机器人 /
- 协同路径规划 /
- 蚁群算法 /
- 进化思想 /
- 冲突消解
Abstract: Aiming at the problems of low search efficiency and difficulty in resolving path conflicts when the ant colony algorithm was used to the cooperative path planning problem of multiple mobile robots, a dual-layer cooperative path planning method was proposed. In the static layer, the crossover mechanism of genetic algorithm was integrated into ant colony algorithm, and the evolutionary path crossover strategy was established to improve the quality of planning path.Concurrently, the calculation method of pheromone increment differentiation was adopted to accelerate the convergence speed of ant colony algorithm. In the dynamic layer, collision prediction was conducted based on a three-dimensional space-time map, and a priority conflict-free strategy was employed to effectively resolve path conflict. Simulation results show that the proposed dual-layer dynamic cooperative path planning method can improve the comprehensive performance of the algorithm and solve the cooperative path planning problem, which verifying the feasibility and effectiveness of the proposed algorithm.
- multi-robot /
- cooperative path planning /
- ant colony algorithm /
- evolutionary thought /
- conflict resolution

HTML全文

图 1 机器人冲突类型

Figure 1. Types of robot conflicts

下载: 全尺寸图片幻灯片

图 2 路径交叉策略示意图

Figure 2. Schematic diagram of path crossover strategy

下载: 全尺寸图片幻灯片

图 3 EACO 算法流程图

Figure 3. EACO algorithm flow chart

下载: 全尺寸图片幻灯片

图 4 三维时空状态图

Figure 4. Three-dimensional space-time state diagram

下载: 全尺寸图片幻灯片

图 5 双层协同路径规划流程

Figure 5. Double-layer cooperative path planning process

下载: 全尺寸图片幻灯片

图 6 3种算法搜索路径对比

Figure 6. Comparison of search paths of three algorithms

下载: 全尺寸图片幻灯片

图 7 协同路径规划验证

Figure 7. Verification of cooperative path planning

下载: 全尺寸图片幻灯片

表 1 突消解策略

Table 1. Conflict resolution strategy

冲突类型	冲突消解策略
节点冲突	等待策略/重规划策略
交叉冲突	等待策略/重规划策略
对位冲突	退回策略/重规划策略
占用冲突	退回策略/重规划策略

下载: 导出CSV

表 2 3种算法性能指标对比

Table 2. Performance comparison of three algorithms

仿真环境	规划算法	平均路径长度/m	路径长度标准差/m	平均迭代次数	平均时间/s
简单环境	EACO算法	43.36	0.00	10.60	10.20
	文献[11]算法	43.36	0.00	26.20	8.32
	文献[12]算法	43.36	0.00	2.00	9.29
	遗传算法	46.58	2.38	24.75	0.18
U型环境	EACO算法	45.31	0.33	14.30	10.89
	文献[11]算法	46.32	1.00	34.80	7.55
	文献[12]算法	46.09	1.47	7.30	10.60
	遗传算法	—	—	—	—

下载: 导出CSV

表 3 机器人起点及终点位置

Table 3. Starting point and end point positions of robots

机器人	起点位置	终点位置	优先级
R1	(15.5, 0.5)	(4.5, 15.5)	1
R2	(5.5, 14.5)	(17.5, 2.5)	2
R3	(12.5, 7.5)	(2.5, 7.5)	3
R4	(6.5, 2.5)	(6.5, 16.5)	4
R5	(12.5, 14.5)	(2.5, 4.5)	5

下载: 导出CSV

参考文献(12)

[1]	臧冀原, 刘宇飞, 王柏村, 等. 面向2035的智能制造技术预见和路线图研究[J] . 机械工程学报, 2022, 58(4): 285 − 308.
[2]	刘志飞, 曹雷, 赖俊, 等. 多智能体路径规划综述[J] . 计算机工程与应用, 2022, 58(20): 43 − 62. doi: 10.3778/j.issn.1002-8331.2203-0467
[3]	张迎雪, 陈萌, 陈金宝, 等. 多机器人智能化协同技术研究进展[J] . 载人航天, 2021, 27(6): 767 − 778. doi: 10.3969/j.issn.1674-5825.2021.06.014
[4]	马滕, 茅健. 改进多步长蚁群算法移动机器人路径规划研究[J] . 上海工程技术大学学报, 2023, 37(3): 255 − 262. doi: 10.12299/jsues.22-0174
[5]	MIAO C W, CHEN G Z, YAN C L, et al. Path planning optimization of indoor mobile robot based on adaptive ant colony algorithm[J] . Computers & Industrial Engineering, 2021, 156: 107230.
[6]	徐劲力, 柳佳, 司马立萱. 多因素A^*蚁群算法的机器人路径规划[J] . 组合机床与自动化加工技术, 2022(8): 21 − 25.
[7]	李健, 孙晓海, 廖昌义, 等. 基于双起点蚁群算法的机器人路径规划新方法[J/OL] . 吉林大学学报(工学版), 1 − 7[2024-04-15] . https://doi.org/10.13229/j.cnki.jdxbgxb.20230339.
[8]	汪繁荣, 杜力, 徐光辉. 基于改进蚁群算法的分布式多机器人协同路径规划[J] . 中南民族大学学报(自然科学版), 2023, 42(5): 650 − 657.
[9]	李志敏. 基于三维时空状态图−并行排序蚁群算法的多机器人路径协同规划[J] . 现代制造工程, 2021(12): 41 − 47.
[10]	LI P, YANG L W. Conflict-free and energy-efficient path planning for multi-robots based on priority free ant colony optimization[J] . Mathematical Biosciences and Engineering, 2023, 20(2): 3528 − 3565.
[11]	张恒, 何丽, 袁亮, 等. 基于改进双层蚁群算法的移动机器人路径规划[J] . 控制与决策, 2022, 37(2): 303 − 313.
[12]	刘加奇, 王泰华, 董征. 基于改进蚁群算法的移动机器人路径规划[J] . 传感器与微系统, 2022, 41(5): 140 − 143.