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.

研究了多智能体路径规划中如何利用蒙特卡洛树搜索（Monte-Carlo Tree Search）解决问题，提出了一种适用于多智能体路径规划的改进 MCTS 变种，通过计算个体路径和奖励来指导搜索过程，实验证明该方法优于基线规划算法。

多代理路径规划的蒙特卡洛树搜索：初步结果

Monte-Carlo Tree Search for Multi-Agent Pathfinding: Preliminary Results

We provide a variant of Azuma's concentration inequality for martingales, in
which the standard boundedness requirement is replaced by the milder
requirement of a subgaussian tail.

我们提供了 Azuma's 集中不等式的一个变体，其中标准的有界性要求被更轻松的亚高斯尾部要求所替代。