| 基于冲突搜索算法的多机器人路径规划 |
| |
| 引用本文： | 乔乔,王艳,纪志成. 基于冲突搜索算法的多机器人路径规划[J]. 系统仿真学报, 2022, 34(12): 2659-2669. DOI: 10.16182/j.issn1004731x.joss.22-FZ0926 |
| |
| 作者姓名： | 乔乔 王艳 纪志成 |
| |
| 作者单位： | 江南大学 教育部物联网技术应用工程中心，江苏 无锡 214122 |
| |
| 基金项目： | 国家自然科学基金(61973138);国家重点研发计划(2018YFB1701903) |
| |
| 摘 要： | 针对冲突搜索法（conflict-based search,CBS）在多机器人路径规划（multi-agent path finding,MAPF）过程中规划路径过长、单向搜索运行时间长等缺陷，从搜索方向和搜索方式提出一种改进的双向A*焦点搜索来优化冲突搜索算法。将次优因子ω引入冲突搜索算法的底层搜索函数中，以提高路径搜索的效率；将冲突搜索算法中的单向搜索优化为双向A*搜索。实验结果表明：改进的冲突搜索算法的路径成本缩短了14.82%，总运行时间缩短了10.63%。
|
| 关 键 词： | 多机器人路径规划 双向搜索 焦点搜索 路径规划 冲突搜索算法 |
| 收稿时间： | 2022-08-07 |
Multi-robot Path Planning Based on CBS Algorithm |
| |
| Qiao Qiao,Yan Wang,Zhicheng Ji. Multi-robot Path Planning Based on CBS Algorithm[J]. Journal of System Simulation, 2022, 34(12): 2659-2669. DOI: 10.16182/j.issn1004731x.joss.22-FZ0926 |
| |
| Authors: | Qiao Qiao Yan Wang Zhicheng Ji |
| |
| Affiliation: | Engineering Research Center of Internet of Things Technology Applications Ministry of Education, Jiangnan University, Wuxi 214122, China |
| |
| Abstract: | Aiming at the long multi-robot planning path and long one-way search running time of conflict-based search(CBS) in the multi-agent path finding(MAPF), an improved CBS algorithm is proposed, which in a two-way A* focus search is used to optimize the search direction and search method. The suboptimal factoris introduced into the underlying search function of the CBS algorithm to improve the efficiency of path search. The one-way search in the conflict search algorithm is optimized to a two-way A* search. The experimental results show that the path cost of the improved CBS algorithm is shortened by 14.82%, and the total running time is shortened by 10.63%. |
| |
| Keywords: | multi-agent path finding(MAPF) two-way search focus search path planning conflict-based search(CBS) |
|
| 点击此处可从《系统仿真学报》浏览原始摘要信息 |
|
点击此处可从《系统仿真学报》下载全文 |
