Daneshvaramoli, M. et al. (2022). A Study on Non-overlapping Multi-agent Pathfinding. In: Arai, K. (eds) Advances in Information and Communication. FICC 2022. Lecture Notes in Networks and Systems, vol 439. Springer, Cham. https://doi.org/10.1007/978-3-030-98015-3_1
A study on non-overlapping multi-agent pathfinding
|Author:||Daneshvaramoli, Mohammadreza1; Kiarostami, Mohammad Sina2; Monfared, Saleh Khalaj1;|
1School of Computer Sciences, Institute for Research in Fundamental Sciences (IPM), Tehran, Iran
2Center for Ubiquitous Computing, Faculty of ITEE, University of Oulu, Oulu, Finland
3Computer Science and Engineering Department, Shahid Beheshti University, Tehran, Iran
4Iranian Research Organization for Science and Technology (IROST), Tehran, Iran
|Persistent link:|| http://urn.fi/urn:nbn:fi-fe2022060844853
|Publish Date:|| 2023-03-12
In this work, first, we model the non-overlapping Multi-Agent Pathfinding (MAPF) to an NP-complete traditional puzzle called Numberlink puzzle owing to its features. Interestingly, this puzzle is reasonably shown to be analogous to the Flow Free game. Hence an approach that solves the puzzle can be considered as the AI for solving Flow Free game. Then, we investigate various promising approaches such as SAT, Heuristics, and Monte-Carlo Tree Search (MCTS) based methods to find a fast and accurate solution and provide a fair comparison. We implement and evaluate two SAT and MCTS-based approaches. Finally, we propose an enhanced MCTS with three optimizations to solve the problem faster with lower memory consumption, particularly in significant test sizes with many agents. All the methods are compared and analyzed on the same test cases in different grid sizes and various agents. The optimized MCTS-based method solves the most extensive test case with a size of 40 × 40 with 100 agents in 988.5 s, respectively, indicating 22.8% and 63.6% improvements in time and memory consumption compared to the state-of-the-art MCTS-based method. It also shows 72% and 39.2% improvement in performance with lower memory consumption than the best results of investigated SAT and heuristic-based methods, sequentially.
Lecture notes in networks and systems
|Pages:||1 - 18|
Advances in Information and Communication. FICC 2022
|Host publication editor:||
Future of Information and Communication Conference
|Type of Publication:||
A4 Article in conference proceedings
|Field of Science:||
113 Computer and information sciences
This research is connected to the GenZ strategic profiling project at the University of Oulu, supported by the Academy of Finland (project number 318930),and CRITICAL (Academy of Finland Strategic Research, 335729). Part of the work was also carried out with the support of Biocenter Oulu, spearhead project ICON.
|Academy of Finland Grant Number:||
318930 (Academy of Finland Funding decision)
© 2022 The Author(s), under exclusive license to Springer Nature Switzerland AG. This is a post-peer-review, pre-copyedit version of an article published in Lecture Notes in Networks and Systems. The final authenticated version is available online at https://doi.org/10.1007/978-3-030-98015-3_1.