导航

Acta Aeronautica et Astronautica Sinica ›› 2023, Vol. 44 ›› Issue (S1): 727648-727648.doi: 10.7527/S1000-6893.2022.27648

• Articles • Previous Articles     Next Articles

An improved conflict⁃based search algorithm for multi⁃agent path planning

Lianbo YU1, Pinzhao CAO1, Liang SHI2, Jie LIAN1, Dong WANG1()   

  1. 1.School of Control Science and Engineering,Faculty of Electronic Information and Electrical Engineering,Dalian University of Technology,Dalian 116024,China
    2.Chinese Aeronautical Establishment,Beijing 100012,China
  • Received:2022-06-20 Revised:2022-07-10 Accepted:2022-09-06 Online:2023-06-25 Published:2022-09-22
  • Contact: Dong WANG E-mail:dwang@dlut.edu.cn
  • 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)

Abstract:

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.

Key words: multi-agent path planning, conflict-based search, conflict classification, conflict detection, conflict resolution

CLC Number: