Push and rotate: a complete multi-agent pathfinding algorithm

摘要: Multi-agent Pathfinding is a relevant problem in wide range of domains, for example robotics and video games research. Formally, the considers graph consisting vertices edges, set agents occupying vertices. An agent can only move to an unoccupied, neighbouring vertex, finding minimal sequence moves transfer each from its start location destination NP-hard problem. We present Push Rotate, new algorithm that complete problems which there are at least two empty Rotate first divides into subgraphs within it possible reach any position subgraph, then uses simple push, swap, rotate operations find solution; post-processing also presented eliminates redundant moves. be seen as extending Luna Bekris's Swap algorithm, we showed incomplete previous publication. In our experiments compare approach with Swap, MAPP, Bibox algorithms. The latter restricted smaller class instances requires biconnected graphs, but nevertheless considered state art due strong performance. Our show suffers incompleteness, MAPP generally not competitive better than on randomly generated instances, while performs grids.