University of Oulu

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

Saved in:
Author: Daneshvaramoli, Mohammadreza1; Kiarostami, Mohammad Sina2; Monfared, Saleh Khalaj1;
Organizations: 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
Format: article
Version: accepted version
Access: embargoed
Persistent link: http://urn.fi/urn:nbn:fi-fe2022060844853
Language: English
Published: Springer Nature, 2022
Publish Date: 2023-03-12
Description:

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.

see all

Series: Lecture notes in networks and systems
ISSN: 2367-3370
ISSN-E: 2367-3389
ISSN-L: 2367-3370
ISBN: 978-3-030-98015-3
ISBN Print: 978-3-030-98014-6
Volume: 439
Pages: 1 - 18
DOI: 10.1007/978-3-030-98015-3_1
OADOI: https://oadoi.org/10.1007/978-3-030-98015-3_1
Host publication: Advances in Information and Communication. FICC 2022
Host publication editor: Arai, Kohei
Conference: Future of Information and Communication Conference
Type of Publication: A4 Article in conference proceedings
Field of Science: 113 Computer and information sciences
Subjects:
SAT
Funding: 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
Detailed Information: 318930 (Academy of Finland Funding decision)
Copyright information: © 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.