A study on non-overlapping multi-agent pathfinding
Daneshvaramoli, Mohammadreza; Kiarostami, Mohammad Sina; Monfared, Saleh Khalaj; Karisani, Helia; Visuri, Aku; Hosio, Simo; Rahmati, Dara; Gorgin, Saeid (2022-03-12)
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
© 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.
https://rightsstatements.org/vocab/InC/1.0/
https://urn.fi/URN:NBN:fi-fe2022060844853
Tiivistelmä
Abstract
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.
Kokoelmat
- Avoin saatavuus [31928]