Improved PBS Multi-Agent Path Planning Algorithm Based on Conflict Cost Bayesian Weighting

QIAN Cheng-ze; MAO Jian-lin; LI Rui-qi; ZHOU Wen-na; GONG De-zheng; ZHANG Jin-bao

doi:10.12263/DZXB.20241074

您当前的位置：

首页 >

文章列表页 >

Improved PBS Multi-Agent Path Planning Algorithm Based on Conflict Cost Bayesian Weighting

PAPERS | 更新时间：2025-12-10

- Improved PBS Multi-Agent Path Planning Algorithm Based on Conflict Cost Bayesian Weighting
- ACTA ELECTRONICA SINICA Vol. 53, Issue 7, Pages: 2358-2371(2025)
- 作者机构：
  
  1.昆明理工大学信息工程与自动化学院，云南昆明 650500
  2.昆明理工大学机电工程学院，云南昆明 650500
- 作者简介：
- 基金信息：
  
  National Natural Science Foundation of China(62263017)
- DOI：10.12263/DZXB.20241074
  CLC： TP242;TP18
- Received：29 November 2024，
  
  Revised：2025-05-29，
  
  Published：25 July 2025
- 稿件说明：
移动端阅览
钱诚泽, 毛剑琳, 李睿褀, 等. 基于冲突代价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 .

Views

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

A Collaborative Multi-Agent Model for Database Parameter Tuning

Autoimmune Dynamic Attack Generation Method Based on Reinforcement Learning

A Flower Pollination Algorithm Based on Nonlinear Cross-Generation Differential Evolution and Its Application Study

Cooperative Fission Control Algorithm of UAV Swarm Based on Attention Mechanism

Related Author

LI Rui-qi

LI Jiang-min

QIAO Shao-jie

HAN Nan

WU Tao

GAO Rui-wei

PENG Yu-han

XIE Tian-cheng

Related Institution

School of Cyber Security and Information Law， Chongqing University of Posts and Telecommunications

School of Management， Chengdu University of Information Technology

School of Software Engineering， Chengdu University of Information Technology

School of Cyber Engineering， Xidian University

School of Microelectronics and Communication Engineering， Chongqing University

⁰