Fast algorithms for optimal multi-robot path planning are sought after in real-world applications. Known methods, however, generally do not simultaneously guarantee good solution optimality and good (e.g., polynomial) running time. In this work, we develop a first low-polynomial running time algorithm, called SplitAngGroup (SaG), that solves the multi-robot path planning problem on grids and grid-like environments, and produces constant factor makespan optimal solutions on average over all problem instances. That is, SaG is an average case O(1)-approximation algorithm and computes solutions with sub-linear makespan. SaG is capable of handling cases when the density of robots is extremely high - in a graph-theoretic setting, the algorithm supports cases where all vertices of the underlying graph are occupied. SaG attains its desirable properties through a careful combination of a novel divide-and-conquer technique, which we denote as global decoupling, and network flow based methods for routing the robots. Solutions from SaG, in a weaker sense, are also a constant factor approximation on total distance optimality.
Because general (labeled) optimal multi-robot path planning problems in continuous domains are extremely challenging, a common approach is to start with a discrete setting from the onset. Significant progress has been made on solving the problem optimally in discrete settings, in particular on grid-based environments. Multi-robot motion planning is less computationally expensive in discrete domains, with the feasibility problem readily solvable in @math time, in which @math is the number of vertices of the discrete graph where the robots may reside @cite_39 @cite_41 @cite_42 @cite_33 . In particular, @cite_33 shows that the setting considered in this paper is always feasible except when the grid graph has only four vertices (which is a trivial case that can be safely ignored).
@cite_41 @cite_42 @cite_33 @cite_39
2016374168 1844237500 2241357751 2083721544
We consider a graph with n vertices, and p<n pebbles of m colors. A pebble move consists of transferring a pebble from its current host vertex to an adjacent unoccupied vertex. The problem is to move the pebbles to a given new color arrangement. Given a connected, undirected, simple graph @math and @math pebbles labeled @math , a configuration of these @math pebbles is an injective map assigning the pebbles to vertices of @math . Let @math and @math be two such configurations. From a configuration, pebbles can move on @math as follows: In each step, at most one pebble may move from the vertex it currently occupies to an adjacent unoccupied vertex, yielding a new configuration. A natural question in this setting is the following: Is configuration @math reachable from @math and if so, how? We show that the feasibility of this problem can be decided in time @math . We study the problem of planning paths for (p ) distinguishable pebbles (robots) residing on the vertices of an (n )-vertex connected graph with (p n ). A pebble may move from a vertex to an adjacent one in a time step provided that it does not collide with other pebbles. When (p = n ), the only collision free moves are synchronous rotations of pebbles on disjoint cycles of the graph. We show that the feasibility of such problems is intrinsically determined by the diameter of a (unique) permutation group induced by the underlying graph. Roughly speaking, the diameter of a group ( G ) is the minimum length of the generator product required to reach an arbitrary element of ( G ) from the identity element. Through bounding the diameter of this associated permutation group, which assumes a maximum value of (O(n^2) ), we establish a linear time algorithm for deciding the feasibility of such problems and an (O(n^3) ) algorithm for planning complete paths.