Multi-agent path finding(MAPF) is a challenging problem widely employed in automated docks and warehouse systems. However, when the above scenarios require car-like agents to perform the tasks, due to the complexity of the environment and the specificity of the shape of the agents, numerous conflicts between agents may occur in the process of path planning, which seriously affects the efficiency of the system and leads to a long runtime. To address these above problems, we propose a regional constraint module-based car-like conflict-based search(RCM-CL-CBS), which sets up the safe region to detect the conflicts between agents, maximizing the selection of paths with larger spatial resources under the same cost, and specifies the safe-exclusive region for colliding agents, reducing the probability of agents' collisions within a certain region. We conduct experiments under four scenario types including factory and warehousing instances. Compared with the baseline algorithms,the experimental results denote that our method reduces the computational burden in terms of resolving agent conflicts, and improves the efficiency of problem-solving. In particular, in the warehouse scenario, compared to the car-like conflict-based search(CL-CBS), CL-CBS in the sequential framework(CL-CBS-SE), and improved CL-CBS(ICL-CBS), our method in the sequential framework minimizes the runtime by 89.6%, 53.4%, and 46.6%,respectively.
Fang Chengyuan, Mao Jianlin, Li Dayan, Wang Ning, Wang Niya
. Regional Constraint Module-Based Multi-Agent Path Planning Approach for Car-like Agents[J]. Journal of Shanghai Jiaotong University(Science), 2026
, 31(4)
: 1003
-1013
.
DOI: 10.1007/s12204-024-2777-1
[1] LI J Y, SURYNEK P, FELNER A, et al. Multi-agent path finding for large agents [J]. Proceedings of the AAAI Conference on Artificial Intelligence, 2019, 33(1): 7627-7634.
[2] YU J J, LAVALLE S M. Optimal multirobot path planning on graphs: Complete algorithms and effective heuristics [J]. IEEE Transactions on Robotics, 2016, 32(5): 1163-1177.
[3] CHEN Z, ALONSO-MORA J, BAI X S, et al. Integrated task assignment and path planning for capacitated multi-agent pickup and delivery [J]. IEEE Robotics and Automation Letters, 2021, 6(3): 5816-5823.
[4] DU H K, GUO Z Y, ZHANG L L, et al. Multi-objective loosely synchronized search for multi-objective multi-agent path finding with asynchronous actions [J]. Journal of Shanghai Jiao Tong University (Science), 2024, 29(4): 667-677.
[5] ANDREYCHUK A, YAKOVLEV K, SURYNEK P, et al. Multi-agent pathfinding with continuous time [J]. Artificial Intelligence, 2022, 305: 103662.
[6] REN Z Q, RATHINAM S, CHOSET H. MS*: A new exact algorithm for multi-agent simultaneous multi-goal sequencing and path finding [C]//2021 IEEE International Conference on Robotics and Automation. Xi’an: IEEE, 2021: 11560-11565.
[7] WEN L C, LIU Y, LI H L. CL-MAPF: Multi-Agent Path Finding for Car-Like robots with kinematic and spatiotemporal constraints [J]. Robotics and Autonomous Systems, 2022, 150: 103997.
[8] SHARON G, STERN R, FELNER A, et al. Conflict-based search for optimal multi-agent pathfinding [J]. Artificial Intelligence, 2015, 219: 40-66.
[9] YU J J, LAVALLE S. Structure and intractability of optimal multi-robot path planning on graphs [J]. Proceedings of the AAAI Conference on Artificial Intelligence, 2013, 27(1): 1443-1449.
[10] GOLDENBERG M, FELNER A, STERN R, et al. Enhanced partial expansion A * [J]. Journal of Artificial Intelligence Research, 2014, 50: 141-187.
[11] STANDLEY T, KORF R. Complete algorithms for cooperative pathfinding problems [C]// 22nd International Joint Conference on Artificial Intelligence. Barcelona: AAAI, 2011: 668-673.
[12] STANDLEY T. Finding optimal solutions to cooperative pathfinding problems [J]. Proceedings of the AAAI Conference on Artificial Intelligence, 2010, 24(1): 173-178.
[13] WAGNER G, CHOSET H. Subdimensional expansion for multirobot path planning [J]. Artificial Intelligence, 2015, 219: 1-24.
[14] BOYARSKI E, FELNER A, STERN R, et al. ICBS: The improved conflict-based search algorithm for multi-agent pathfinding [J]. Proceedings of the International Symposium on Combinatorial Search, 2015, 6(1): 223-225.
[15] LAM E, LE BODIC P, HARABOR D, et al. Branch-and-cut-and-price for multi-agent path finding [J]. Computers & Operations Research, 2022, 144: 105809.
[16] ZHANG K X, MAO J L, ZHANG S F, et al. A priority-based hierarchical framework for k-robust multi-agent path finding [J]. IEEE Transactions on Intelligent Vehicles, 2024. https://doi.org/10.1109/TIV.2024.3355423
[17] GUO T, HAN S D, YU J J. Spatial and temporal splitting heuristics for multi-robot motion planning [C]//2021 IEEE International Conference on Robotics and Automation. Xi’an: IEEE, 2021: 8009-8015.
[18] SILVER D. Cooperative pathfinding [J]. Proceedings of the AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment, 2021, 1(1): 117-122.
[19] MA H, HARABOR D, STUCKEY P J, et al. Searching with consistent prioritization for multi-agent path finding [J]. Proceedings of the AAAI Conference on Artificial Intelligence, 2019, 33(1): 7643-7650.
[20] BARER M, SHARON G, STERN R, et al. Suboptimal variants of the conflict-based search algorithm for the multi-agent pathfinding problem [J]. Proceedings of the International Symposium on Combinatorial Search, 2021, 5(1): 19-27.
[21] LI J Y, RUML W, KOENIG S. EECBS: A bounded-suboptimal search for multi-agent path finding [J]. Proceedings of the AAAI Conference on Artificial Intelligence, 2021, 35(14): 12353-12362.
[22] OKUMURA K. LaCAM: Search-based algorithm for quick multi-agent pathfinding [J]. Proceedings of the AAAI Conference on Artificial Intelligence, 2023, 37(10): 11655-11662.
[23] TAI R C, WANG J C, CHEN W D. A prioritized planning algorithm of trajectory coordination based on time windows for multiple AGVs with delay disturbance [J]. Assembly Automation, 2019, 39(5): 753-768.
[24] 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.
[25] HOENIG W, KUMAR T K, COHEN L, et al. Multi-agent path finding with kinematic constraints [J]. Proceedings of the International Conference on Automated Planning and Scheduling, 2016, 26: 477-485.
[26] 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.
[27] FANG C Y, MAO J L, LI D Y, et al. A coordinated scheduling approach for task assignment and multi-agent path planning [J]. Journal of King Saud University - Computer and Information Sciences, 2024, 36(1): 101930.
[28] ISHIHARA S, KANAI M, NARIKAWA R, et al. A proposal of path planning for robots in warehouses by model predictive control without using global paths [J]. IFAC-PapersOnLine, 2022, 55(37): 573-578.
[29] 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).
