ACTA AERONAUTICAET ASTRONAUTICA SINICA >
An improved conflict⁃based search algorithm for multi⁃agent path planning
Received date: 2022-06-20
Revised date: 2022-07-10
Accepted date: 2022-09-06
Online published: 2022-09-22
Supported by
National Key Research and Development Program of China(2019YFE0197700);National Natural Science Foundation of China(61973050);Liaoning Revitalization Talents Program(XLYC2007010);Fundamental Research Funds for the Central Universities(DUT20GJ209)
The multi-agent path planning problem is widely used in multi-machine tasks in the aerospace field， but it is difficult to solve the problem. The improved conflict-based search algorithm is designed to quickly solve the multi-agent path planning problem. In terms of global path planning， a multi-objective cost function is designed to give a comprehensive consideration of the sum of path costs and the make span， and a conflict classification and resolution scheme based on the unique shortest path is then proposed to reduce the computational cost of multi-agent path planning. In terms of online conflict resolution， the velocity obstacle method is used to detect and resolve the sudden conflict between agents and dynamic obstacles. Simulation results show that the algorithm proposed retains the optimality of the conflict-based search algorithm in global path planning and reduces the amount of calculation. Thus， this algorithm can effectively realize online conflict detection and resolution.
Lianbo YU , Pinzhao CAO , Liang SHI , Jie LIAN , Dong WANG . An improved conflict⁃based search algorithm for multi⁃agent path planning[J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2023 , 44(S1) : 727648 -727648 . DOI: 10.7527/S1000-6893.2022.27648
| 1 | 万逸飞， 彭力. 基于协同多目标算法的多机器人路径规划［J］. 信息与控制， 2020， 49（2）： 139-146. |
| WAN Y F， PENG L. Multi-robot path planning based on cooperative multi-objective algorithm［J］. Information and Control， 2020， 49（2）： 139-146 （in Chinese）. | |
| 2 | 晁永生， 孙文磊. 动态修改路径的多机器人路径规划［J］. 机械科学与技术， 2018， 37（10）： 1483-1488. |
| CHAO Y S， SUN W L. Dynamic path modification for multi-robot path planning［J］. Mechanical Science and Technology for Aerospace Engineering， 2018， 37（10）： 1483-1488 （in Chinese）. | |
| 3 | 曹其新， 黄先群， 朱笑笑， 等. 基于保留区域的分布式多机器人路径规划［J］. 华中科技大学学报（自然科学版）， 2018， 46（12）： 71-76. |
| CAO Q X， HUANG X Q， ZHU X X， et al. Distributed multi-robot path planning based on reserved area［J］ Journal of Huazhong University of Science and Technology （Natural Science Edition）， 2018， 46（12）：71-76 （in Chinese）. | |
| 4 | OROZCO-ROSAS U， MONTIEL O， SEPúLVEDA R. Mobile robot path planning using membrane evolutionary artificial potential field［J］. Applied Soft Computing， 2019， 77： 236-251. |
| 5 | BHATTACHARYA P， GAVRILOVA M L. Roadmap-based path planning-using the Voronoi diagram for a clearance-based shortest path［J］. IEEE Robotics & Automation Magazine， 2008， 15（2）： 58-66. |
| 6 | 胡章芳， 冯淳一， 罗元. 改进粒子群优化算法的移动机器人路径规划［J］. 计算机应用研究， 2021， 38（10）： 3089-3092. |
| HU Z F， FENG C Y， LUO Y. Improved particle swarm optimization algorithm for mobile robot path planning［J］. Application Research of Computers， 2021， 38（10）： 3089-3092 （in Chinese）. | |
| 7 | 蒋强， 易春林， 张伟， 等. 基于蚁群算法的移动机器人多目标路径规划［J］. 计算机仿真， 2021， 38（2）： 318-325. |
| JIANG Q， YI C L， ZHANG W， et al. The multi-objective path planning for mobile robot based on ant colony algorithm［J］. Computer Simulation， 2021， 38（2）： 318-325 （in Chinese）. | |
| 8 | LIU C， LIU H， YANG J. A path planning method based on adaptive genetic algorithm for mobile robot［J］. Journal of Information & Computational Science， 2011， 8（5）： 808-814. |
| 9 | SHARON G， STERN R， FELNER A， et al. Conflict-based search for optimal multi-agent pathfinding［J］. Artificial Intelligence， 2015， 219： 40-66. |
| 10 | MA H， LI J Y， KUMAR T K S， et al. Lifelong multiagent path finding for online pickup and delivery tasks［C］∥ Proceedings of the 16th Conference on Autonomous Agents and Multi-Agent Systems， 2017： 837-845. |
| 11 | MA H， YANG J， COHEN L， et al. Feasibility study： moving non-homogeneous teams in congested video game environments［C］∥ Proceedings of the AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment， 2017， 13（1）： 270-272. |
| 12 | H?NIG W， PREISS J A， KUMAR T K S， et al. Trajectory planning for quadrotor swarms［J］. IEEE Transactions on Robotics， 2018， 34（4）： 856-869. |
| 13 | BARER M， SHARON G， STERN R Z， et al. Suboptimal variants of the conflict-based search algorithm for the multi-agent pathfinding problem［C］∥ Proceedings of the 7th Annual Symposium on Combinatorial Search， 2014： 19-27. |
| 14 | COHEN L， KOENIG S. Bounded suboptimal multi-agent path finding using highways［C］∥ Proceedings of the 25th International Joint Conference on Artificial Intelligence， 2016： 978-3979. |
| 15 | BOYARSKI E， FELNER A， STERN R， et al. ICBS： Improved conflict-based search algorithm for multi-agent pathfinding［C］∥ Proceedings of the 24th International Conference on Artificial Intelligence， 2015： 740-746. |
| 16 | FELNER A， LI J， BOYARSKI E， et al. Adding heuristics to conflict-based search for multi-agent path finding［C］∥ Proceedings of the International Conference on Automated Planning and Scheduling， 2018， 28： 83-87. |
| 17 | LI J， FELNER A， BOYARSKI E， et al. Improved heuristics for multi-agent path finding with conflict-based search［C］∥ Proceedings of the 28th International Joint Conference on Artificial Intelligence， 2019： 442-449. |
| 18 | LI J， HARABOR D， STUCKEY P J， et al. Symmetry-breaking constraints for grid-based multi-agent path finding［C］∥ Proceedings of the AAAI Conference on Artificial Intelligence， 2019， 33（1）： 6087-6095. |
| 19 | COHEN L， WAGNER G， CHAN D， et al. Rapid randomized restarts for multi-agent path finding solvers［C］∥ Proceedings of Eleventh Annual Symposium on Combinatorial Search， 2018： 148-152. |
| 20 | FIORINI P， SHILLER Z. Motion planning in dynamic environments using velocity obstacles［J］. The International Journal of Robotics Research， 1998， 17（7）： 760-772. |
| 21 | DURAND N， BARNIER N. Does ATM need centralized coordination？ autonomous conflict resolution analysis in a constrained speed environment［J］. Air Traffic Control Quarterly， 2015， 23（4）： 325-346. |
| 22 | 杨秀霞，周硙硙，张毅.基于速度障碍圆弧法的UAV自主避障规划研究［J］.系统工程与电子技术， 2017， 39（1）： 168-176. |
| YANG X X， ZHOU W W， ZHANG Y. Automatic obstacle avoidance planning for UVA based on velocity obstacle arc method［J］. Systems Engineering and Electronics， 2017， 39（1）： 168-176 （in Chinese）. | |
| 23 | DURAND N. Constant speed optimal reciprocal collision avoidance［J］. Transportation Research Part C： Emerging Technologies， 2018， 96： 366-379. |
/
| 〈 |
|
〉 |
CJA