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
接受日期:
2023-10-18
出版日期:
2024-07-28
发布日期:
2024-07-28
DU Haikuo1,2 (杜海阔), GUO Zhengyu3,4(郭正玉), ZHANG Lulu1,2(章露露), CAI Yunze1,2∗ (蔡云泽)
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*算法具有一定的优势。
中图分类号:
杜海阔1,2, 郭正玉3,4, 章露露1,2, 蔡云泽1,2. 基于多目标松散同步搜索的多目标多智能体异步路径规划[J]. J Shanghai Jiaotong Univ Sci, 2024, 29(4): 667-677.
DU Haikuo1,2 (杜海阔), GUO Zhengyu3,4(郭正玉), ZHANG Lulu1,2(章露露), CAI Yunze1,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). |
[1] | 董玉博1, 崔涛1, 周禹帆1, 宋勋2, 祝月2, 董鹏1. 基于长周期极坐标系追击问题的多智能体强化学习奖赏函数设计方法[J]. J Shanghai Jiaotong Univ Sci, 2024, 29(4): 646-655. |
[2] | 李舒逸,李旻哲,敬忠良*. 动态环境下基于改进DQN的多智能体路径规划方法[J]. J Shanghai Jiaotong Univ Sci, 2024, 29(4): 601-612. |
[3] | 徐亚茹1,2,李克鸿1,2,商新娜2,金晓明1,2,刘荣3,张建成1,2. 基于影响系数法的机器人动力学方程约束关系建立[J]. J Shanghai Jiaotong Univ Sci, 2024, 29(3): 450-456. |
[4] | 赵英策1,张广浩2,邢正宇2,李建勋2. 面向确定进攻对手策略的层次强化学习对抗算法研究[J]. J Shanghai Jiaotong Univ Sci, 2024, 29(3): 471-479. |
[5] | 李茹1,陈方2,俞文伟3,IGARASH Tatsuo3,4,舒雄鹏1,谢叻1,5,6. 一种新型线驱动手术软体机器人[J]. J Shanghai Jiaotong Univ Sci, 2024, 29(1): 60-72. |
[6] | 贺贵松, 黄学功, 李峰, 汪辉兴. 助力型下肢外骨骼机器人研究综述[J]. J Shanghai Jiaotong Univ Sci, 2024, 29(1): 1-15. |
[7] | 陶璟, 周振欢. 个性化下肢康复外骨骼机器人的关键技术综述[J]. J Shanghai Jiaotong Univ Sci, 2024, 29(1): 16-28. |
[8] | . 基于场端RGB-D相机阵列的室内停车场车辆定位系统[J]. J Shanghai Jiaotong Univ Sci, 2023, 28(1): 61-69. |
[9] | . 外参标定的激光-视觉-惯性里程计[J]. J Shanghai Jiaotong Univ Sci, 2023, 28(1): 70-76. |
[10] | . 基于栅格图特征点提取下的蚁群算法路径规划[J]. J Shanghai Jiaotong Univ Sci, 2023, 28(1): 86-99. |
[11] | . [J]. J Shanghai Jiaotong Univ Sci, 2022, 27(5): 621-630. |
[12] | . [J]. J Shanghai Jiaotong Univ Sci, 2022, 27(5): 631-637. |
[13] | . [J]. J Shanghai Jiaotong Univ Sci, 2022, 27(5): 589-601. |
[14] | . [J]. J Shanghai Jiaotong Univ Sci, 2022, 27(5): 602-613. |
[15] | . [J]. J Shanghai Jiaotong Univ Sci, 2022, 27(5): 614-620. |
阅读次数 | ||||||
全文 |
|
|||||
摘要 |
|
|||||