J Shanghai Jiaotong Univ Sci ›› 2024, Vol. 29 ›› Issue (4): 667-677.doi: 10.1007/s12204-024-2744-x

• • 上一篇    

基于多目标松散同步搜索的多目标多智能体异步路径规划

杜海阔1,2, 郭正玉3,4, 章露露1,2, 蔡云泽1,2   

  1. (1.上海交通大学 自动化系,上海200240;2.系统控制与信息处理教育部重点实验室,上海200240;3. 中国空空导弹研究院,河南 洛阳 471000;4. 空基信息感知与融合国家重点实验室,河南 洛阳 471000)
  • 接受日期:2023-10-18 出版日期:2024-07-28 发布日期:2024-07-28

Multi-Objective Loosely Synchronized Search for Multi-Objective Multi-Agent Path Finding with Asynchronous Actions

DU Haikuo1,2 (杜海阔), GUO Zhengyu3,4(郭正玉), ZHANG Lulu1,2(章露露), CAI Yunze1,2∗ (蔡云泽)   

  1. (1. Department of Automation, Shanghai Jiao Tong University, Shanghai 200240, China; 2. Key Laboratory of System Control and Information Processing, Ministry of Education, Shanghai 200240, China; 3. China Airborne Missile Academy, Luoyang 471000, Henan, China; 4. National Key Laboratory of Air-based Information Perception and Fusion, Luoyang 471000, Henan, China)
  • Accepted:2023-10-18 Online:2024-07-28 Published:2024-07-28

摘要: 近年来,多智能体路径规划技术逐渐成熟,并取得了突破性进展。多智能体路径规划的主要难点是状态空间大,算法运行时间长,优化目标多,以及多智能体动作异步。针对上述问题,本文首先介绍了研究的主要问题:多目标多智能体异步路径规划,并提出了多目标松散同步(MO-LS)搜索的算法框架。结合A*和M*,分别提出了MO-LS-A*和MO-LS-M*算法。证明了算法的完备性和最优性,并设计了一系列对比实验以分析影响算法性能的因素,验证了提出的MO-LS-M*算法具有一定的优势。

关键词: 多智能体路径规划,多目标路径规划,异步行动,松散同步搜索

Abstract: In recent years, the path planning for multi-agent technology has gradually matured, and has made breakthrough progress. The main difficulties in path planning for multi-agent are large state space, long algorithm running time, multiple optimization objectives, and asynchronous action of multiple agents. To solve the above problems, this paper first introduces the main problem of the research: multi-objective multi-agent path finding with asynchronous action, and proposes the algorithm framework of multi-objective loose synchronous (MOLS) search. By combining A∗ and M∗, MO LS-A∗ and MO-LS-M∗ algorithms are respectively proposed. The completeness and optimality of the algorithm are proved, and a series of comparative experiments are designed to analyze the factors affecting the performance of the algorithm, verifying that the proposed MO-LS-M∗ algorithm has certain advantages.

Key words: multi-agent path finding, multi-objective path planning, asynchronous action, loosely synchronous search

中图分类号: