导航

ACTA AERONAUTICAET ASTRONAUTICA SINICA

    Next Articles

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

  

  • Received:2022-06-20 Revised:2022-09-20 Online:2022-09-22 Published:2022-09-22
  • Contact: Dong WANG
  • Supported by:
    National Key Research and Development Program of China;National Natural Science Foundation of China;National Natural Science Foundation of China;LiaoNing Revitalization Talents Program;Fundamental Research Funds for the Central Universities;Fundamental Research Funds for the Central Universities

Abstract: The multi-agent path planning problem is widely used in multi-machine tasks in the aerospace field, but it is difficult to solve. This paper designs an improved conflict-based search algorithm to quickly solve the multi-agent path planning problem. In terms of global path planning, first, a multi-objective cost function is designed that compre-hensively considers the sum of path costs and the makespan. Second, a conflict classification and resolution scheme based on the unique shortest path is proposed to reduce the computational cost of multi-agent path plan-ning. In the aspect of online conflict resolution, the velocity obstacle method is used to detect and resolve the sud-den conflict between agents and the dynamic obstacles. Simulation results show that the algorithm in this paper retains the optimality of the conflict-based search algorithm in global path planning and reduces the amount of cal-culation. 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: