Monte-Carlo Tree Search for Multi-Agent Pathfinding: Preliminary Results
In this work we study a well-known and challenging problem of Multi-agent Pathfinding, when a set of agents is confined to a graph, each agent is assigned a unique start and goal vertices and the task is to find a set of collision-free paths (one for each agent) such that each agent reaches its respective goal. We investigate how to utilize Monte-Carlo Tree Search (MCTS) to solve the problem. Although MCTS was shown to demonstrate superior performance in a wide range of problems like playing antagonistic games (e.g. Go, Chess etc.), discovering faster matrix multiplication algorithms etc., its application to the problem at hand was not well studied before. To this end we introduce an original variant of MCTS, tailored to multi-agent pathfinding. The crux of our approach is how the reward, that guides MCTS, is computed. Specifically, we use individual paths to assist the agents with the the goal-reaching behavior, while leaving them freedom to get off the track if it is needed to avoid collisions. We also use a dedicated decomposition technique to reduce the branching factor of the tree search procedure. Empirically we show that the suggested method outperforms the baseline planning algorithm that invokes heuristic search, e.g. A*, at each re-planning step.
Code (0)
등록된 구현이 없습니다.
Tasks
Heuristic SearchMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
Competing in a Complex Hidden Role Game with Information Set Monte Carlo Tree Search
Advances in intelligent game playing agents have led to successes in perfect information games like Go and imperfect information games like Poker. The Information Set Monte Carlo Tree Search (ISMCTS) family of algorithms…
A Fast Evolutionary adaptation for MCTS in Pommerman
Artificial Intelligence, when amalgamated with games makes the ideal structure for research and advancing the field. Multi-agent games have multiple controls for each agent which generates huge amounts of data while incr…
Convex Hull Monte-Carlo Tree Search
This work investigates Monte-Carlo planning for agents in stochastic environments, with multiple objectives. We propose the Convex Hull Monte-Carlo Tree-Search (CHMCTS) framework, which builds upon Trial Based Heuristic …
Multi-Armed BanditsDeep Reinforcement Learning with Model Learning and Monte Carlo Tree Search in Minecraft
Deep reinforcement learning has been successfully applied to several visual-input tasks using model-free methods. In this paper, we propose a model-based approach that combines learning a DNN-based transition model with …
Deep Reinforcement LearningMinecraftReinforcement LearningReinforcement Learning (RL)Monte Carlo Search Algorithms Discovering Monte Carlo Tree Search Exploration Terms
Monte Carlo Tree Search and Monte Carlo Search have good results for many combinatorial problems. In this paper we propose to use Monte Carlo Search to design mathematical expressions that are used as exploration terms f…