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.
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]. Journal of Shanghai Jiaotong University(Science), 2024
, 29(4)
: 667
-677
.
DOI: 10.1007/s12204-024-2744-x
[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).
