Complete and Tractable Multi-Robot Path Planning
Approach and Motivation
This project proposes a fast algorithm that can provide completeness guarantees for a general class of problems without any assumptions about the graph’s topology. Specifically, the approach can address any solvable instance where there are at most n-2 agents in a graph of size n. The algorithm employs two primitives: a “push” operation where agents move towards their goals up to the point that no progress can be made, and a “swap” operation that allows two agents to swap positions without altering the configuration of other agents. Simulated experiments are provided on hard instances of cooperative path-finding, including comparisons against state of the art coupled and coupled planners.
It is also proven that the "Push and Swap" formulation has polynomial complexity (conservatively O(n^4)) in the number of robots, indicating computational tractability and good scalability. This method is also complete for cooperative path-finding problems where the number of agents is less than or equal to n-2.
Extension: Parallel Motion
This extension proposes an approach for computing a solution where agents can move simultaneously using similar
single-agent primitives. At a high level, the proposed PARALLEL PUSH AND SWAP method operates by allowing agents to execute either a PUSH or a SWAP primitive to progress toward its goal. All agents are grouped into one of two sets: (i) the “pushing” agents P, which try to individually make progress along their shortest paths, and (ii) the prioritized “swapping” pairs S, which need to execute a swap action to remove a dependency
between them. Initially all agents are in the “pushing” group P. When an agent reaches its goal, it is inserted into set U, indicating it should not be disturbed by “pushers” P.
The proposed technique is shown to be effective not only in large, sparse pathfinding contexts, but also in small, highly constrained situations where even the best optimal search algorithms often fail.
Comparisons with recent pathfinding algorithms, including both incomplete/decoupled and complete/coupled planners, suggest that the proposed method scales as well as an established decoupled algorithm, finds solutions as fast as Push and Swap algorithm, and that the quality of the solution is comparable to a recent anytime, optimal algorithm.
Extension: Feasibility Tests
Finding an optimal solution for this problem is NP-hard and raises scalability issues for optimal solvers. Interestingly, however, it takes linear time to check the feasibility of an instance. These linear-time feasibility tests can be extended to provide path planners. As an extension of this work a path planner that is inspired by a linear-time feasibility test for multi-agent pathfinding on general graphs has been implemented. The integration of the feasibility test algorithm left many choices to be decided during the development of the overall method so as to achieve an efficient implementation. Comparisons against optimal coupled planners and sub-optimal solutions showed that the resulting planner achieves scalability in terms of running time but results in low quality solutions. This work identifies the reasons for the poor path quality and proposes a way to address it by utilizing search primitives used in existing sub-optimal solutions for graphs. The result is a new algorithm that shares features of both the linear time feasibility tests and existing suboptimal solvers. The final algorithm achieves improved path quality relative to the alternatives, as well as strong performance in terms of running time.
The algorithms have been tested on a set of small benchmarks that are highly coupled.
The results are favorable for the Push and Swap technique, and show that the algorithm scales to problems that require high levels of coordination, involving hundreds of agents. Additionally, the solution returned can be smoothed in a post-processing step, yielding a highly competitive solution length to a complete coupled planner. The algorithm tested against different methods that tries to solve the same problem differently. The comparisons are shown in the following graph.
The first extension is tested on cooperative pathfinding problems, ranging from small benchmarks, where all agents share pair-wise dependencies, to larger scale problems.
To evaluate the second extension that uses feasibility test algorithm to solve the problem, a series of challenging instances of multi-robot path planning were considered that have appeared before in the literature. These problems include a set of small benchmarks that are highly coupled so that decoupled planner typically fail on them, as well as larger instances, including maps from an online repository of grid-worlds. The performance of the algorithm is compared against a coupled optimum algorithm and the previous work, Push and Swap. The following results are positive for the new proposed method.
These videos shows the different algorithms trying to solve the same problem. On the left the Pebble Motion Planner using feasibility algorithms, while on the right the new proposed PMG that combines ideas from feasibility test algorithms and Push and Swap algorithm.
- Krontiris A., Luna R., Bekris K E., "From Feasibility Tests to Path Planners for Multi-Agent Pathfinding", Symposium on Combinatorial Search (SoCS - 2013), Leavenworth, WA, July, 2013.
- Krontiris A., Sajid Q., Bekris KE. 2012. Towards Using Discrete Multiagent Pathfinding to Address Continuous Problems. Workshop on Multi-agent Pathfinding (in conjunction with AAAI 2012).
- Sajid Q., Luna R., Bekris KE. 2012. Multi-Agent Pathfinding with Simultaneous Execution of Single-Agent Primitives. Fifth Symposium on Combinatorial Search (SoCS).
- Luna R., Bekris KE. 2011. Efficient and Complete Centralized Multi-Robot Path Planning. IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS-11).
- Luna R., Bekris KE. 2011. Push and Swap: Fast Cooperative Path-Finding with Completeness Guarantees. International Joint Conferences in Artificial Intelligence (IJCAI-11). :294-300
This work has been supported by NSF CNS 0932423. Any opinions and findings expressed in this paper are those of the authors and do not necessarily reflect the views of the sponsor.