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

doi:10.1007/s12204-024-2744-x

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.上海交通大学自动化系，上海200240；2.系统控制与信息处理教育部重点实验室，上海200240；3. 中国空空导弹研究院，河南洛阳 471000；4. 空基信息感知与融合国家重点实验室，河南洛阳 471000）

接受日期:2023-10-18 出版日期:2024-07-14 发布日期:2024-07-14

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

DU Haikuo^1,2 (杜海阔), GUO Zhengyu^3，4(郭正玉), ZHANG Lulu^1,2(章露露), CAI Yunze^1,2∗ (蔡云泽)

(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-14 Published:2024-07-14

摘要/Abstract

摘要： 近年来，多智能体路径规划技术逐渐成熟，并取得了突破性进展。多智能体路径规划的主要难点是状态空间大，算法运行时间长，优化目标多，以及多智能体动作异步。针对上述问题，本文首先介绍了研究的主要问题：多目标多智能体异步路径规划，并提出了多目标松散同步(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

中图分类号:

TP242

杜海阔1,2, 郭正玉3,4, 章露露1,2, 蔡云泽1,2. 基于多目标松散同步搜索的多目标多智能体异步路径规划[J]. J Shanghai Jiaotong Univ Sci, 2024, 29(4): 667-677.

DU Haikuo^1,2 (杜海阔), GUO Zhengyu^3，4(郭正玉), ZHANG Lulu^1,2(章露露), CAI Yunze^1,2∗ (蔡云泽). Multi-Objective Loosely Synchronized Search for Multi-Objective Multi-Agent Path Finding with Asynchronous Actions[J]. J Shanghai Jiaotong Univ Sci, 2024, 29(4): 667-677.

参考文献

[1] STERN R, STURTEVANT N, FELNER A, et al. Multi-agent pathfinding: Definitions, variants, and benchmarks [J]. Proceedings of the International Symposium on Combinatorial Search, 2021, 10(1): 151-158.
[2] LIU Z F, CAO L, LAI J, et al. Overview of multi-agent path finding [J]. Computer Engineering and Applications, 2022, 58(20): 43-62 (in Chinese).
[3] WAGNER G, CHOSET H. Subdimensional expansion for multirobot path planning [J]. Artificial Intelligence,2015, 219: 1-24.
[4] SHARON G, STERN R, FELNER A, et al. Conflictbased search for optimal multi-agent pathfinding [J]. Artificial Intelligence, 2015, 219: 40-66.
[5] SHARON G, STERN R, GOLDENBERG M, et al. The increasing cost tree search for optimal multi-agent pathfinding [J]. Artificial Intelligence, 2013, 195: 470-495.
[6] WALKER T T, STURTEVANT N R, FELNER A, et al. Conflict-based increasing cost search [J]. Proceedings of the International Conference on Automated Planning and Scheduling, 2021, 31: 385-395.
[7] SURYNEK P. Makespan optimal solving of cooperative path-finding via reductions to propositional satisfiability [DB/OL]. (2016-10-18). https://arxiv.org/abs/1610.05452
[8] SURYNEK P, FELNER A, STERN R, et al. Efficient SAT approach to multi-agent path finding under the sum of costs objective [C]//22nd European Conference on Artificial Intelligence. Amsterdam: IOS Press, 2016: 810-818.
[9] WANG J X, LI J Y, MA H, et al. A new constraint satisfaction perspective on multi-agent path finding: Preliminary results [C]//18th International Conference on Autonomous Agents and Multi Agent Systems. Montreal: ACM, 2019: 2253–2255.
[10] ERDEM E, KISA D, OZTOK U, et al. A general formal framework for pathfinding problems with multiple agents [J]. Proceedings of the AAAI Conference on Artificial Intelligence, 2013, 27(1): 290-296.
[11] LAM E, LE BODIC P, HARABOR D, et al. Branchand-cut-and-price for multi-agent path finding [J]. Computers & Operations Research, 2022, 144: 105809.
[12] WANG L, WANG B, WANG C X. Collision-free path planning with kinematic constraints in urban scenarios [J]. Journal of Shanghai Jiao Tong University (Science), 2021, 26(5): 731-738.
[13] REN Z Q, RATHINAM S, CHOSET H. Subdimensional expansion for multi-objective multi-agent path finding [J]. IEEE Robotics and Automation Letters, 2021, 6(4): 7153-7160.
[14] REN Z Q, RATHINAM S, CHOSET H. A conflictbased search framework for multiobjective multiagent path finding [J]. IEEE Transactions on Automation Science and Engineering, 2023, 20(2): 1262-1274.
[15] WEISE J, MAI S, ZILLE H, et al. On the scalable multi-objective multi-agent pathfinding problem [C]//2020 IEEE Congress on Evolutionary Computation. Glasgow: IEEE, 2020: 1-8.
[16] REN Z Q, RATHINAM S, CHOSET H. Loosely synchronized search for multi-agent path finding with asynchronous actions [C]//2021 IEEE/RSJ International Conference on Intelligent Robots and Systems. Prague: IEEE, 2021: 9714-9719.
[17] ANDREYCHUK A, YAKOVLEV K, SURYNEK P, et al. Multi-agent pathfinding with continuous time [J]. Artificial Intelligence, 2022, 305: 103662.
[18] STEWART B S, WHITE C C. Multiobjective A? [J]. Journal of the ACM, 1991, 38(4): 775-814.
[19] QIU K J, BAO Z K, CHEN L. Task assignment and path planning for automatic guided vehicles in aircraft assembly workshop [J]. Journal of Shanghai Jiao Tong University, 2023, 57(1): 93-102 (in Chinese).

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

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

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价

[1]	. 近红外胶囊机器人无线能量接收线圈优化设计[J]. J Shanghai Jiaotong Univ Sci, 2025, 30(3): 425-432.
[2]	. 多机协调吊运系统的绳索矢量碰撞检测算法研究[J]. J Shanghai Jiaotong Univ Sci, 2025, 30(2): 319-329.
[3]	. 复杂光照下被动式双目光学运动捕捉技术[J]. J Shanghai Jiaotong Univ Sci, 2025, 30(2): 352-362.
[4]	. 基于RGB-D图像的机器人抓取检测高效全卷积网络和优化方法[J]. J Shanghai Jiaotong Univ Sci, 2025, 30(2): 399-416.
[5]	赵艳飞1,2,3, 肖鹏4, 王景川1,2,3, 郭锐4. 基于局部语义地图的移动机器人半自主导航[J]. J Shanghai Jiaotong Univ Sci, 2025, 30(1): 27-33.
[6]	傅航1，许江长 1，李寅炜2,4，周慧芳2,4，陈晓军1,3. 基于视频图像增强现实的视神经管减压手术导航系统[J]. J Shanghai Jiaotong Univ Sci, 2025, 30(1): 34-42.
[7]	周涵巍1，朱心平1，马有为2，王坤东1. 低延时纤维胆道镜机器人驱动控制系统[J]. J Shanghai Jiaotong Univ Sci, 2025, 30(1): 43-52.
[8]	贺贵松，黄学功，李峰. 基于主被动联合驱动的助力型踝关节外骨骼机器人的协调性设计[J]. J Shanghai Jiaotong Univ Sci, 2025, 30(1): 197-208.
[9]	刘月笙, 贺宁, 贺利乐, 张译文, 习坤, 张梦芮. 基于机器学习的移动机器人路径跟踪MPC控制器参数自整定[J]. J Shanghai Jiaotong Univ Sci, 2024, 29(6): 1028-1036.
[10]	董玉博1, 崔涛1, 周禹帆1, 宋勋2, 祝月2, 董鹏1. 基于长周期极坐标系追击问题的多智能体强化学习奖赏函数设计方法[J]. J Shanghai Jiaotong Univ Sci, 2024, 29(4): 646-655.
[11]	董德金1,2，董诗音3，章露露1,2，蔡云泽1,2. 基于A-Star和DWA算法的野外环境路径规划[J]. J Shanghai Jiaotong Univ Sci, 2024, 29(4): 725-736.
[12]	李舒逸, 李旻哲, 敬忠良. 动态环境下基于改进DQN的多智能体路径规划方法[J]. J Shanghai Jiaotong Univ Sci, 2024, 29(4): 601-612.
[13]	徐亚茹1,2，李克鸿1,2，商新娜2，金晓明1,2，刘荣3，张建成1,2. 基于影响系数法的机器人动力学方程约束关系建立[J]. J Shanghai Jiaotong Univ Sci, 2024, 29(3): 450-456.
[14]	赵英策1，张广浩2，邢正宇2，李建勋2. 面向确定进攻对手策略的层次强化学习对抗算法研究[J]. J Shanghai Jiaotong Univ Sci, 2024, 29(3): 471-479.
[15]	李茹1，陈方2，俞文伟3，IGARASH Tatsuo3,4，舒雄鹏1，谢叻1,5,6. 一种新型线驱动手术软体机器人[J]. J Shanghai Jiaotong Univ Sci, 2024, 29(1): 60-72.