  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.
