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.

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