Push and Swap
Planning a path for a single robot is an exceptionally difficult problem. A common method to achieve tractability is to abstract the system and its environment to a discrete graph where the motion plan is a path through the graph. Such a path can be found efficiently using a traditional graph search. Computing disjoint paths for multiple robots on the same graph, however, is a difficult endeavor. Extending a traditional graph search to the space of multiple robots results in an exponential increase in the number of states that must be searched to find the solution; such methods do not scale well beyond just a handful of robots.
Push and Swap is a combinatorial search algorithm that is able to solve a very large set of discrete multi-robot path planning instances. To make the planning problem tractable, the algorithm computes a sequential solution in which only one robot moves at any given timestep. The implicit search of the multi-robot graph allows the algorithm to run in time polynomial with respect to the number of robots. For reasonable problems, Push and Swap is able to compute solutions for hundreds or thousands of robots in seconds while making minimal concessions on optimality.
The Push and Swap algorithm makes use of two simple primitives to guide the multi-robot search. The first is push, in which a robot greedily moves along a shortest path to its destination, "pushing" other robots that are not at their goal out of the way. When push can no longer make progress, the second primitive, swap exchanges the position of two robots while simultaneously ensuring that all other robots return to their current positions. The combination of these two primitives is sufficient to solve a large class of multi-robot planning instances, so long as there are at least two empty vertices in the graph.
An open-source implementation of Push and Swap in C++ is freely available for non-profit, research, and educational purposes. The latest version of the code and related documentation can be found on BitBucket. Additional information on the algorithm can be found at the project website and in the publications below.
Download
Related Publications
- Athanasios Krontiris, Ryan Luna, and Kostas E. Bekris. From Feasibility Tests to Path Planners for Multi-Agent Pathfinding. The Sixth Annual Symposium on Combinatorial Search (SoCS), July 11-13, 2013. PDF
- Ryan Luna and Kostas E. Bekris, Efficient and Complete Centralized Multi-Robot Path Planning, IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pp. 3268-3275, Sept. 25-30, 2011. PDF
- Ryan Luna and Kostas E. Bekris, Push and Swap: Fast Cooperative Path-Finding with Completeness Guarantees, International Joint Conference on Artificial Intelligence (IJCAI), pp. 294-300, July 16-22, 2011. PDF