基于算法融合的多机器人多目标路径规划研究

范县成, 凌新宇, 余叶青, 黄洪斌

PDF(2930 KB)
PDF(2930 KB)
云南民族大学学报(自然科学版) ›› 2025, Vol. 34 ›› Issue (03) : 342-349. DOI: 10.3969/j.issn.1672-8513.2025.03.012
信息与计算机科学

基于算法融合的多机器人多目标路径规划研究

作者信息 +

Research on multi-robot multi-objective path planning based on algorithm fusion

Author information +
History +

摘要

针对多机器人多目标路径规划问题,提出基于算法融合的多机器人多目标路径规划算法.算法采用改进A*算法进行全局路径规划,采用改进模拟退火算法规划多机器人在组合全局路径最优的情况下,保证最远机器人路径最短,采用DWA算法进行局部路径规划,实现机器人局部运动避障.为了验证所提算法的可行性和优越性,对其进行仿真实验,实验结果表明,改进A*算法比经典A*算法在转弯次数、转弯角度、遍历节点、规划距离分别减少16.66%、41.24%、23.3%、0.77%,改进模拟退火算法与传统模拟退火算法在仿真时间、最长路径长度、总路径分别减少12.09%、22.26%、5.74%,DWA算法能够实现多机器人局部路径规划与避障.

Abstract

Aiming at the problem of multi - robot multi - objective path planning, a multi - robot multi - objective path planning algorithm based on algorithm fusion is proposed. The algorithm adopts the improved A* algorithm for global path planning, the improved simulated annealing algorithm for planning multiple robots to ensure the shortest path for the farthest robot in the case of combining the optimal global paths, and uses the DWA algorithm for local path planning to realize the local motion obstacle avoidance of robots. In order to verify the feasibility and superiority of the proposed algorithm, simulation experiments are carried out. The experimental results show that the improved A* algorithm reduces the number of turns, turning angles, traversal nodes, and planned distance by 16.66%, 41.24%, 23.3%, and 0.77% respectively compared to the classical A* algorithm. The improved simulated annealing algorithm reduces simulation time, longest path length, and total path by 12.09%, 22.26%, and 5.74% respectively compared to the traditional simulated annealing algorithm. The DWA algorithm can achieve multi robot local path planning and obstacle avoidance.

关键词

多机器人 / 多目标 / A*算法 / 模拟退火算法 / 路径规划 / DWA算法

Key words

multi - robot / multi - objective / A* algorithm / simulated annealing algorithm / path planning / DWA algorithm

中图分类号

TP242.6

引用本文

导出引用
范县成 , 凌新宇 , 余叶青 , . 基于算法融合的多机器人多目标路径规划研究. 云南民族大学学报(自然科学版). 2025, 34(03): 342-349 https://doi.org/10.3969/j.issn.1672-8513.2025.03.012
FAN Xian-cheng, LING Xin-yu, YU Ye-qing, et al. Research on multi-robot multi-objective path planning based on algorithm fusion[J]. Journal of Yunnan University of Nationalities(Natural Sciences Edition). 2025, 34(03): 342-349 https://doi.org/10.3969/j.issn.1672-8513.2025.03.012

参考文献

1
DUDEJA C KUMAR P. An improved weighted sum-fuzzy Dijkstra's algorithm for shortest path problem (iWSFDA)[J].Soft Computing202226(7):3217 - 3226.
2
FAN X C LING X Y HUANG H B. Robot path planning based on improved A* algorithm and artificial potential field method[J]. Artificial Intelligence Technology Research2024(2):36 - 43.
3
郑川川,柯福阳,汤琴琴.融合改进D*与Gmapping算法的自主导航仿真研究[J].计算机仿真.202340(10):452 - 457 + 518.
4
ZHANG R GUO H ANDRIUKAITIS D, et al. Intelligent path planning by an improved RRT algorithm with dual grid map[J]. Alexandria Engineering Journal202488:91 - 104.
5
莫杰,徐天奇,李琰,等.基于退火优化粒子群算法的负荷辨识方法[J].云南民族大学学报(自然科学版)202433 (5) :630 - 637.
6
黄荣杰,王亚刚.基于可视图与改进遗传算法的机器人平滑路径规划[J].控制工程202431(4):678 - 686.
7
MILAD N ESMAEEL K SAMIRA D. Multi - objective multi - robot path planning in continuous environment using an enhanced genetic algorithm[J]. Expert Systems with Applications2019115(1):106 - 120.
8
RAFAL S TOMASZ T KRYSTIAN E. Energy efficient local path planning algorithm based on predictive artificial potential field[J]. IEEE202210(1):39729 - 39742.
9
ZHANG L Y HAN Y JIANG B. Research on path planning method of unmanned boat based on improved DWA algorithm[J]. Journal of Sensors20222022:1 - 10.
10
郭志军,尹亚昆,李亦轩,等.融合改进A*和TEB算法的移动机器人路径规划[J].河南科技大学学报(自然科学版)202344(4):57 - 65.
11
TANG Z Z MA H Z. An overview of path planning algorithms[J]. Iop Conference Series: Earth and Environmental Science2021804(2):022024.
12
SANG H Q YOU Y S SUN X J, et al. The hybrid path planning algorithm based on improved A* and artificial potential field for unmanned surface vehicle formations[J]. 2021223(1):108709.
13
YIN X CAI P ZHAO K, et al. Dynamic path planning of AGV based on kinematical constraint A* algorithm and following DWA fusionalgorithms[J]. Sensors202323(8),4102.
14
李三平,袁龙强,吴立国,等.基于改进融合蚁群算法的移动机器人路径规划[J].机械设计202340(10):76 - 84.
15
有维宝,徐哲,刘东宁.基于拍卖谈判机制的分布式多技能多项目调度[J].运筹与管理202433(1):1 - 8.
16
陈剑,孙明月,马文静,等.基于VCG拍卖的智能车间主动调度机制研究[J].工业工程与管理202429(1):1 - 11.
17
OTTE M KUHLMAN M J SOFGE D. Auctions for multi - robot task allocation in communication limited environments[J].Autonomous Robots201044(3/4):547 - 584.
18
严李平,吴玉秀,张文忠.基于CVT和模拟退火的多机器人均匀部署[J].现代信息科技20226(17):143 - 149.
19
杨玮,李然,张堃.基于变邻域模拟退火算法的多自动导引车任务分配优化[J].计算机应用202141(10):3056 - 3062.
20
孟浩德,吴征天,吴闻笛,等.基于改进模拟退火算法的灭火小车多目标路径规划[J].计算机与数字工程202452(2):394 - 398.
21
白俊峰,白一辰,席嘉璐,等.基于改进A*算法的车间物料配送路径规划[J].吉林大学学报(理学版)202462(6):1401 - 1410.
22
姜海猛,张志安,潘孝斌.基于A*与DWA算法的融合优化策略研究[J].机械与电子202442(10):15 - 21.
23
牛晶,申传艳,张利鹏,等.基于改进ACO - DWA算法的轮式植保机器人避障路径研究[J].电子测量与仪器学报202438(5):188 - 200.
24
ZHANG W WANG N X WU W H. A hybrid path planning algorithm considering AUV dynamic constraints based on improved A* algorithm and APF algorithm[J]. Ocean Engineering2023285(1):115333.
25
FAN X C YU Y Q LI T. Research on path planning of patrol robot based on multi - algorithm fusion[J].Journal of Artificial Intelligence Practice20247(3):48 - 61.
26
KARLIJN F JOOST V E. Efficient path planning for automated guided vehicles using A* (Astar) algorithm incorporating turning costs in search heuristic[J].International Journal of Production Research202361(3):707 - 725.

基金

安徽省高等学校省级自然科学研究计划项目(2023AH052918)
安徽省高等学校省级自然科学研究计划项目(2024AH050637)
安徽信息工程学院青年科研基金项目(24QNJJJ012)

评论

PDF(2930 KB)

Accesses

Citation

Detail

段落导航
相关文章

/