Push and swap: fast cooperative path-finding with completeness guarantees

摘要: Cooperative path-finding can be abstracted as computing non-colliding paths for multiple agents between their start and goal locations on a graph. This paper proposes fast algorithm that provide completeness guarantees general class of problems without any assumptions about the graph's topology. Specifically, approach address solvable instance where there are at most n-2 in graph size n. The employs two primitives: "push" operation move towards goals up to point no progress made, "swap" allows swap positions altering configuration other agents. Simulated experiments provided hard instances cooperative path-finding, including comparisons against alternative methods. results favorable proposed show technique scales require high levels coordination, involving hundreds