Multi-Agent non-Overlapping Pathfinding with Monte-Carlo Tree Search

In this work, we propose a novel implementation of Monte-Carlo Tree Search (MCTS) algorithm to solve a multiagent pathfinding (MAPF) problem. We employ an optimization of MCTS with low time-complexity and acceptable reliability to approach the MAPF problems with no time constraint. To examine the efficiency and performance of the proposed approach, the NumberLink problem as a MAPF is investigated. We show that the addressed problem could be characterized as multi-agent pathfinding problem with no overlapping paths for the agents. Furthermore, we define this problem to be a simplified and special case of Multi-commodity flow problem (MCFP). Our MCTS solution utilizes a modified search-tree structure to efficiently solve the problem based on a 2-dimensional search space which performs in quadratic time complexity (O(m4) where input size is m2) and linear memory complexity (O(m2)). To evaluate our algorithm, we investigate the efficiency of the proposed solution for the well-known Flow Free puzzle. Our implementation solves a large 40 × 40 Numberlink puzzle in 21 minutes. To the best of our knowledge, there is no other efficient solution for this puzzle where the size of the problem is considerably large.