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)
 
Avaa tiedosto
Lataukset: 

URL:
https://doi.org/10.1007/978-3-030-98015-3_1

Daneshvaramoli, Mohammadreza
Kiarostami, Mohammad Sina
Monfared, Saleh Khalaj
Karisani, Helia
Visuri, Aku
Hosio, Simo
Rahmati, Dara
Gorgin, Saeid
Springer Nature
12.03.2022

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

https://rightsstatements.org/vocab/InC/1.0/
© 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/
doi:https://doi.org/10.1007/978-3-030-98015-3_1
Näytä kaikki kuvailutiedot
Julkaisun pysyvä osoite on
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