Learned Representations Enhance Multi Agent Path Planning

Multi-Agent Pathfinding (MAPF) involves coordinating multiple agents to find collision-free paths in a shared environment. For large-scale instances, sub-optimal heuristics can be used that are either hand-crafted or learned from data. In this paper, we attempt to combine these approaches by training a neural network to modify problem representations such that Prioritized Planning, a conventional heuristic solver, will produce closer-to-optimal solutions. Thereby, we can leverage the strong performance of existing heuristics with the flexibility of data-driven algorithms. Training the neural network requires propagating learning signals through prioritized planning. This is achieved by calculating gradients of a relaxation of the algorithm using a black-box differentiation approach. Experiments on standard MAPF benchmarks demonstrate that our approach reduces PP's optimality gap without significantly compromising computational efficiency.