The Multi-Agent Pathfinding (MAPF) problem involves finding a set of
conflict-free paths for a group of agents confined to a graph. In typical MAPF
scenarios, the graph and the agents' starting and ending vertices are known
beforehand, allowing the use of centralized planning algorithms. However, in
this study, we focus on the decentralized MAPF setting, where the agents may
observe the other agents only locally and are restricted in communications with
each other. Specifically, we investigate the lifelong variant of MAPF, where
new goals are continually assigned to the agents upon completion of previous
ones. Drawing inspiration from the successful AlphaZero approach, we propose a
decentralized multi-agent Monte Carlo Tree Search (MCTS) method for MAPF tasks.
Our approach utilizes the agent's observations to recreate the intrinsic Markov
decision process, which is then used for planning with a tailored for
multi-agent tasks version of neural MCTS. The experimental results show that
our approach outperforms state-of-the-art learnable MAPF solvers. The source
code is available at this https URL

我们提出了一种基于分布式多智能体蒙特卡罗树搜索方法的多智能体路径规划算法，通过利用智能体的观察结果重新创建内在的马尔科夫决策过程，并结合针对多智能体任务的定制化神经蒙特卡罗树搜索算法进行路径规划，实验证明该方法优于现有的学习型多智能体路径规划器。

分布式蒙特卡洛树搜索用于部分可观察多智体路径规划

Decentralized Monte Carlo Tree Search for Partially Observable  Multi-agent Pathfinding

Multi-agent Pathfinding (MAPF) problem generally asks to find a set of
conflict-free paths for a set of agents confined to a graph and is typically
solved in a centralized fashion.
Conversely, in this work, we investigate the decentralized MAPF setting, when
the central controller that posses all the information on the agents' locations
and goals is absent and the agents have to sequientially decide the actions on
their own without having access to a full state of the environment. We focus on
the practically important lifelong variant of MAPF, which involves continuously
assigning new goals to the agents upon arrival to the previous ones. To address
this complex problem, we propose a method that integrates two complementary
approaches: planning with heuristic search and reinforcement learning through
policy optimization. Planning is utilized to construct and re-plan individual
paths. We enhance our planning algorithm with a dedicated technique tailored to
avoid congestion and increase the throughput of the system. We employ
reinforcement learning to discover the collision avoidance policies that
effectively guide the agents along the paths. The policy is implemented as a
neural network and is effectively trained without any reward-shaping or
external guidance.
We evaluate our method on a wide range of setups comparing it to the
state-of-the-art solvers. The results show that our method consistently
outperforms the learnable competitors, showing higher throughput and better
ability to generalize to the maps that were unseen at the training stage.
Moreover our solver outperforms a rule-based one in terms of throughput and is
an order of magnitude faster than a state-of-the-art search-based solver.

在这项工作中，我们研究了分布式多智能体路径规划问题的设置，通过集成启发式搜索和强化学习方法，提出了一种解决复杂的问题的方法。我们的方法在广泛的设置中得到了验证，并且在吞吐量和泛化能力上表现优越，同时比现有的基于规则和基于搜索的解决方法快一个数量级。