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.