Skip to content Skip to navigation

Complete and Tractable Multi-Robot Path Planning

Approach and Motivation

 

This project focuses on Multi-Robot Path Planning, with the goal of providing a complete and tractable solution to such instances. The current work considers an abstraction of the traditional multi-robot path planning problem that is abstracted as computing non-colliding paths for multiple agents between their start and goal locations on a graph. Such a formulation is known to be NP-complete, indicating that a naive search to solve the problem will have exponential complexity in the number of robots.
                    

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.

Analysis

 

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.

Results

 

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.

Videos

 

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.  

 

Related Publications

 

 

Acknowledgements

 

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.

People Involved