基于冲突代价Bayesian权重的改进PBS多智能体路径规划算法
Improved PBS Multi-Agent Path Planning Algorithm Based on Conflict Cost Bayesian Weighting
- 电子学报 2025年53卷第7期 页码：2358-2371
- 作者机构：
1.昆明理工大学信息工程与自动化学院，云南昆明 650500
2.昆明理工大学机电工程学院，云南昆明 650500
- 作者简介：
[ "钱诚泽 男，1999年12月生，云南昭通人.现为昆明理工大学信息工程与自动化学院硕士研究生.主要研究方向为多智能体路径规划. E-mail: AzerovO@outlook.com" ]
[ "毛剑琳 女，1976年5月生，广西桂林人.现为昆明理工大学教授、博士生导师.研究方向为多机器人协同调度与优化、无线传感器网络资源分配、智能优化算法研究等. E-mail: 1318524654@qq.com" ]
[ "李睿祺 男，1996年7月生，云南昆明人.现为昆明理工大学机电工程学院博士研究生.主要研究方向为智能调度." ]
[ "周雯娜 女，2001年8月生，湖南永州人.现为昆明理工大学信息工程与自动化学院硕士研究生.主要研究方向为多智能体路径规划. E-mail: 2929399036@qq.com" ]
[ "龚德正 男，2001年9月生，湖南岳阳人.现为昆明理工大学信息工程与自动化学院硕士研究生.主要研究方向为多智能体路径规划. E-mail: 2948151791@qq.com" ]
[ "张进宝 男，2002年7月生，湖南永州人.现为昆明理工大学信息工程与自动化学院硕士研究生.主要研究方向为多智能体路径规划. E-mail: 941138436@qq.com" ]
- 基金信息：国家自然科学基金(62263017)
DOI：10.12263/DZXB.20241074
中图分类号： TP242;TP18收稿：2024-11-29，
修回：2025-05-29，
纸质出版：2025-07-25
- 稿件说明：
移动端阅览
钱诚泽, 毛剑琳, 李睿褀, 等. 基于冲突代价Bayesian权重的改进PBS多智能体路径规划算法[J]. 电子学报, 2025, 53(07): 2358-2371.
QIAN Cheng-ze, MAO Jian-lin, LI Rui-qi, et al. Improved PBS Multi-Agent Path Planning Algorithm Based on Conflict Cost Bayesian Weighting[J]. Acta Electronica Sinica, 2025, 53(07): 2358-2371.
钱诚泽, 毛剑琳, 李睿褀, 等. 基于冲突代价Bayesian权重的改进PBS多智能体路径规划算法[J]. 电子学报, 2025, 53(07): 2358-2371. DOI：10.12263/DZXB.20241074
QIAN Cheng-ze, MAO Jian-lin, LI Rui-qi, et al. Improved PBS Multi-Agent Path Planning Algorithm Based on Conflict Cost Bayesian Weighting[J]. Acta Electronica Sinica, 2025, 53(07): 2358-2371. DOI：10.12263/DZXB.20241074
摘要
面向多智能体路径寻找（Multi-Agent Path Finding，MAPF）问题，基于优先级搜索（Priority-Based Search，PBS）算法融合了优先级机制和冲突搜索（Conflict-Based Search，CBS）的节点拓展框架，在路径规划效率方面具有显著优势.然而，PBS算法中对路径代价优先的贪婪机制会导致算法在优先级树（Priority Tree，PT）拓展过程中冲突消减速度慢.因此，本文提出基于冲突代价Bayesian权重的改进PBS算法IPBS-ccbw（Improved Priority-Based Search with conflict cost bayesian weight）.在路径代价的基础上，引入冲突数量构造了基于路径代价和冲突数量的综合指标，并在规划拓展时对子节点的冲突代价权重进行Bayesian更新，以此在冲突数量与路径代价之间进行有效权衡.进一步设计了冲突数据监测和策略性重构机制，避免算法在特定分支上陷入深度搜索陷阱.在Benchmark标准测试地图上的仿真对比实验以及小规模实物实验的结果显示，IPBS-ccbw算法在不同环境下均展现出优越的路径优化能力.与PBS算法相比，在大规模密集场景中，IPBS-ccbw算法展现出更强的冲突消减能力和更高的求解效率.其求解时间可减少27.3%~91.9%，在智能体数量达到最大值时，求解成功率提升幅度可达40%~85%.
Abstract
In the context of multi-agent path finding (MAPF)
the priority-based search (PBS) algorithm integrates a priority mechanism with the node expansion framework of conflict-based search (CBS)
achieving notable efficiency in path planning. However
the greedy strategy in PBS
which prioritizes path cost
often leads to slow conflict resolution during the expansion of the priority tree (PT). To address this limitation
this paper proposes an improved PBS algorithm
improved priority-based search with conflict cost bayesian weight (IPBS-ccbw). Building upon path cost
the proposed approach incorporates conflict counts to construct a composite metric that balances path cost and conflict frequency. During the planning and expansion process
Bayesian updates are applied to the conflict cost weights of child nodes
effectively balancing conflicts and path costs. In addition
the algorithm introduces conflict monitoring and strategy reconstruction mechanisms to prevent the algorithm from falling into deep search traps. The results of simulation comparison experiments on Benchmark standard test maps as well as small-scale physical experiments show that the IPBS-ccbw algorithm exhibits superior path optimization capabilities in different environments. Compared with the PBS algorithm
the IPBS-ccbw algorithm demonstrates stronger conflict mitigation capability and higher solving efficiency in large-scale dense scenarios. The solution time can be reduced by 27.3% to 91.9%
and the solution success rate can be improved by 40% to 85% when the number of intelligences reaches the maximum.
关键词
Keywords
references
SEMIZ F , YORGANCı M A , POLAT F . Solving an industry-inspired generalization of lifelong MAPF problem including multiple delivery locations [J ] . Advanced Engineering Informatics , 2023 , 57 : 102026 .
YU J J , LAVALLE S M . Optimal multirobot path planning on graphs: Complete algorithms and effective heuristics [J ] . IEEE Transactions on Robotics , 2016 , 32 ( 5 ): 1163 - 1177 .
HO F , SALTA A , GERALDES R , et al . Multi-agent path finding for UAV traffic management [C ] // Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems . New York : ACM , 2019 : 131 - 139 .
ZHANG Y L , FONTAINE M C , BHATT V , et al . Multi-robot coordination and layout design for automated warehousing (extended abstract) [J ] . Proceedings of the International Symposium on Combinatorial Search , 2024 , 17 : 305 - 306 .
LI J Y , SUN K X , MA H , et al . Moving agents in formation in congested environments [C ] // Proceedings of the 19th International Conference on Autonomous Agents and MultiAgent Systems . New York : ACM , 2020 : 726 - 734 .
WU M D , YAN W Y , HASAN H , et al . A review of multi-agent path finding algorithms [C ] // Proceedings of the 11th International Conference on Information Systems and Computing Technology . Piscataway : IEEE , 2023 : 69 - 73 .
MA H , YANG J X , COHEN L , et al . Feasibility study: Moving non-homogeneous teams in congested video game environments [J ] . Proceedings of the AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment , 2017 , 13 ( 1 ): 270 - 272 .
YU J J , LAVALLE S M . Structure and intractability of optimal multi-robot path planning on graphs [C ] // Proceedings of the 27th AAAI Conference on Artificial Intelligence . New York : ACM , 2013 : 1443 - 1449 .
高思华 , 李军辉 , 李建伏 , 等 . 面向公平性数据采集和能量补充的无人机路径规划算法研究 [J ] . 电子学报 , 2024 , 52 ( 11 ): 3699 - 3710 .
GAO S H , LI J H , LI J F , et al . Research on UAV path planning algorithm for fairness data collection and energy supplement [J ] . Acta Electronica Sinica , 2024 , 52 ( 11 ): 3699 - 3710 . (in Chinese)
王文涛 , 叶晨 , 田军 . 基于多策略改进人工兔优化算法的三维无人机路径规划方法 [J ] . 电子学报 , 2024 , 52 ( 11 ): 3780 - 3797 .
WANG W T , YE C , TIAN J . A 3D UAV path planning method based on multi-strategy improved artificial rabbit optimization algorithm [J ] . Acta Electronica Sinica , 2024 , 52 ( 11 ): 3780 - 3797 . (in Chinese)
SHARON G , STERN R , FELNER A , et al . Conflict-based search for optimal multi-agent pathfinding [J ] . Artificial Intelligence , 2015 , 219 : 40 - 66 .
BOYARSKI E , FELNER A , STERN R , et al . ICBS: The improved conflict-based search algorithm for multi-agent pathfinding [J ] . Proceedings of the International Symposium on Combinatorial Search , 2015 , 6 ( 1 ): 223 - 225 .
LI J Y , HARABOR D , STUCKEY P J , et al . Disjoint splitting for multi-agent path finding with conflict-based search [J ] . Proceedings of the International Conference on Automated Planning and Scheduling , 2019 , 29 : 279 - 283 .
SILVER D . Cooperative pathfinding [J ] . Proceedings of the AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment , 2005 , 1 ( 1 ): 117 - 122 .
PHILLIPS M , LIKHACHEV M . SIPP: Safe interval path planning for dynamic environments [C ] // 2011 IEEE International Conference on Robotics and Automation . Piscataway : IEEE , 2011 : 5628 - 5635 .
YAKOVLEV K , ANDREYCHUK A , STERN R . Revisiting bounded-suboptimal safe interval path planning [J ] . Proceedings of the International Conference on Automated Planning and Scheduling , 2020 , 30 : 300 - 304 .
RYBECKY T , KULICH M , ANDREYCHUK A , et al . Towards narrowing the search in bounded-suboptimal safe interval path planning [J ] . Proceedings of the International Symposium on Combinatorial Search , 2021 , 12 ( 1 ): 136 - 140 .
REN Z Q , RATHINAM S , LIKHACHEV M , et al . Multi-objective safe-interval path planning with dynamic obstacles [J ] . IEEE Robotics and Automation Letters , 2022 , 7 ( 3 ): 8154 - 8161 .
ČÁP M , NOVÁK P , KLEINER A , et al . Prioritized planning algorithms for trajectory coordination of multiple mobile robots [J ] . IEEE Transactions on Automation Science and Engineering , 2015 , 12 ( 3 ): 835 - 849 .
MA H , HARABOR D , STUCKEY P J , et al . Searching with consistent prioritization for multi-agent path finding [J ] . Proceedings of the AAAI Conference on Artificial Intelligence , 2019 , 33 ( 1 ): 7643 - 7650 .
LI J Y , RUML W , KOENIG S . EECBS: A bounded-suboptimal search for multi-agent path finding [J ] . Proceedings of the AAAI Conference on Artificial Intelligence , 2021 , 35 ( 14 ): 12353 - 12362 .
CHAN S H , STERN R , FELNER A , et al . Greedy priority-based search for suboptimal multi-agent path finding [J ] . Proceedings of the International Symposium on Combinatorial Search , 2023 , 16 ( 1 ): 11 - 19 .
LI J Y , CHEN Z , HARABOR D , et al . MAPF-LNS2: Fast repairing for multi-agent path finding via large neighborhood search [J ] . Proceedings of the AAAI Conference on Artificial Intelligence , 2022 , 36 ( 9 ): 10256 - 10265 .
OKUMURA K . LaCAM: Search-based algorithm for quick multi-agent pathfinding [J ] . Proceedings of the AAAI Conference on Artificial Intelligence , 2023 , 37 ( 10 ): 11655 - 11662 .
OKUMURA K . Improving lacam for scalable eventually optimal multi-agent pathfinding [EB/OL ] . ( 2023-05-05 )[ 2024-11-10 ] . https://arxiv.org/abs/2305.03632 https://arxiv.org/abs/2305.03632 .
KADURI O , BOYARSKI E , STERN R . Experimental evaluation of classical multi agent path finding algorithms [J ] . Proceedings of the International Symposium on Combinatorial Search , 2021 , 12 ( 1 ): 126 - 130 .
STERN R , STURTEVANT N , FELNER A , et al . Multi-agent pathfinding: Definitions, variants, and benchmarks [J ] . Proceedings of the International Symposium on Combinatorial Search , 2019 , 10 ( 1 ): 151 - 158 .
MA H . Target Assignment and Path Planning for Navigation Tasks with Teams of Agents [D ] . Los Angeles : University of Southern California , 2020 .
KOCHENDERFER M J . Decision Making under Uncertainty: Theory and Application [M ] . Cambridge, Mass : The MIT Press , 2015 .
0
浏览量
10
下载量
0
CSCD
- 网络PDF下载
- Meta-XML下载
- BibTeX下载
- Endnote下载
- RefMan 下载
- NoteExpress下载
- NoteFirst下载
关联资源
相关文章
相关作者
相关机构
- 技术支持由北京北大方正电子有限公司提供 京ICP备09064830号-19
京公网安备11010802024621 - 本系统建议在Chrome、 IE9+ 以上版本浏览器阅读本站内容，360浏览器请切换至极速模式
- Cookies帮助我们提供服务并提供个性化体验。使用本网站，即表示您同意我们使用Cookies