首页 >

基于改进冲突搜索的多智能体路径规划算法(ICGNC2022推荐优秀论文)

于连波1,曹品钊1,王东2,连捷1,王伟2   

  1. 1. 大连理工大学控制科学与工程学院
    2. 大连理工大学
  • 收稿日期:2022-06-20 修回日期:2022-09-20 出版日期:2022-09-22 发布日期:2022-09-22
  • 通讯作者: 王东
  • 基金资助:
    国家重点研发计划项目;国家自然科学基金项目;国家自然科学基金项目;辽宁省兴辽英才计划项目;中央高校基本科研业务费;中央高校基本科研业务费

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

中图分类号: