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.
Similar to single robot problems involving potentially many degrees of freedom @cite_69 @cite_73 , multi-robot path planning is strongly NP-hard even for discs in simple polygons @cite_9 and PSPACE-hard for translating rectangles @cite_43 . The hardness of the problem extends to unlabeled case @cite_50 where it remains highly intractable @cite_46 @cite_64 . Nevertheless, under appropriate settings, the unlabeled case can be solved near optimally @cite_6 @cite_62 @cite_36 @cite_29 .
@cite_69 @cite_64 @cite_62 @cite_36 @cite_9 @cite_29 @cite_6 @cite_43 @cite_50 @cite_46 @cite_73
211895014 1485718613 1964462572 1628219785 2068796584 2963358853 2052819251 2072839015 2153159477 2036722182 1516027685
Abstract : This paper concerns the problem of planning a sequence of movements of linked polyhedra through 3 dimensional Euclidean space, avoiding contact with a fixed set of polyhedra obstacles. We prove this generalized mover's problem is polynomial space hard. Our proof provides strong evidence that robot movement planning is computationally intractable, i.e., any algorithm requires time growing exponentially with the number of degrees of freedom. Keywords: Robotics; Mover's problem; Obstacle avoidence; PSPACE; Combinatorial; Geometry; Collision avoidence. In unlabeled multi-robot motion planning several interchangeable robots operate in a common workspace. The goal is to move the robots to a set of target positions such that each position will be occupied by some robot. In this paper, we study this problem for the specific case of unit-square robots moving amidst polygonal obstacles and show that it is PSPACE-hard. We also consider three additional variants of this problem and show that they are all PSPACE-hard as well. To the best of our knowledge, this is the first hardness proof for the unlabeled case. Furthermore, our proofs can be used to show that the labeled variant (where each robot is assigned with a specific target position), again, for unit-square robots, is PSPACE-hard as well, which sets another precedence, as previous hardness results require the robots to be of different shapes. In this paper, we consider the problem of concurrent assignment and planning of trajectories (which we denote Capt) for a team of robots. This problem involves simultaneously addressing two challenges: (1) the combinatorially complex problem of finding a suitable assignment of robots to goal locations, and (2) the generation of collision-free, time parameterized trajectories for every robot. We consider the Capt problem for unlabeled (interchangeable) robots and propose algorithmic solutions to two variations of the Capt problem. The first algorithm, c-Capt, is a provably correct, complete, centralized algorithm which guarantees collision-free optimal solutions to the Capt problem in an obstacle-free environment. To achieve these strong claims, c-Capt exploits the synergy obtained by combining the two subproblems of assignment and trajectory generation to provide computationally tractable solutions for large numbers of robots. We then propose a decentralized solution to the Capt problem through d-Capt, a decentralized algorithm that provides suboptimal results compared to c-Capt . We illustrate the algorithms and resulting performance through simulation and experimentation. We consider the following motion-planning problem: we are given @math unit discs in a simple polygon with @math vertices, each at their own start position, and we want to move the discs to a given set of @math target positions. Contrary to the standard (labeled) version of the problem, each disc is allowed to be moved to any target position, as long as in the end every target position is occupied. We show that this unlabeled version of the problem can be solved in @math time, assuming that the start and target positions are at least some minimal distance from each other. This is in sharp contrast to the standard (labeled) and more general multi-robot motion planning problem for discs moving in a simple polygon, which is known to be strongly NP-hard. Le probleme de calcul du mouvement de gestion pour un systeme robotise simple a ete etudie plus recemment a partir d'un point de vue algorithmique. Le but de cet article est de montrer que le «probleme de nombreux disques» est NP-dur au sens fort We study the problem of path planning for unlabeled (indistinguishable) unit-disc robots in a planar environment cluttered with polygonal obstacles. We introduce an algorithm which minimizes the total path length, i.e., the sum of lengths of the individual paths. Our algorithm is guaranteed to find a solution if one exists, or report that none exists otherwise. It runs in time O ( m +mn ) , where m is the number of robots and n is the total complexity of the workspace. Moreover, the total length of the returned solution is at most OPT+4m, where OPT is the optimal solution cost. To the best of our knowledge this is the first algorithm for the problem that has such guarantees. The algorithm has been implemented in an exact manner and we present experimental results that attest to its efficiency. For the task of transferring a group of robots from one formation to another on a connected graph with unit edge lengths, we provide an efficient hierarchical algorithm that can complete goal assignment and path planning for 10,000 robots on a 250,000 vertex grid in under one second. In the extreme, our algorithm can handle up to one million robots on a grid with one billion vertices in approximately 30 minutes. Perhaps more importantly, we prove that with high probability, the algorithm supplies paths with total distance within a constant multiple of the optimal total distance. Furthermore, our hierarchical method also allows these paths to be scheduled with a tight completion time guarantee. In practice, our implementation yields a total path distance less than two times of the true optimum and a much shorter completion time. Coordinated motion planning for a large number af three-di mensional objects in the presence of obstacles is a computa tional problem whose complexity is important to calibrate. In this paper we show that even the restricted two-dimensional problem for arbitrarily many rectangles in a rectangular region is PSPACE-hard. This result should be viewed as a guide to the difficulty, of the general problem and should lead researchers to consider more tractable restricted classes of motion problems of practical interest. In many multirobot applications, the specific assignment of goal configurations to robots is less important than the overall behavior of the robot formation. In such cases, it is convenient to define a permutation-invariant multirobot formation as a set of robot configurations, without assigning specific configurations to specific robots. For the case of robots that translate in the plane, we can represent such a formation by the coefficients of a complex polynomial whose roots represent the robot configurations. Since these coefficients are invariant with respect to permutation of the roots of the polynomial, they provide an effective representation for permutation-invariant formations. In this paper, we extend this idea to build a full representation of a permutation-invariant formation space. We describe the properties of the representation, and show how it can be used to construct collision-free paths for permutation-invariant formations We present a nondeterministic model of computation based on reversing edge directions in weighted directed graphs with minimum in-flow constraints on vertices. Deciding whether this simple graph model can be manipulated in order to reverse the direction of a particular edge is shown to be PSPACE-complete by a reduction from Quantified Boolean Formulas. We prove this result in a variety of special cases including planar graphs and highly restricted vertex configurations, some of which correspond to a kind of passive constraint logic. Our framework is inspired by (and indeed a generalization of) the "Generalized Rush Hour Logic" developed by Flake and Baum [Theoret. Comput. Sci. 270(1-2) (2002) 8951.We illustrate the importance of our model of computation by giving simple reductions to show that several motion-planning problems are PSPACE-hard. Our main result along these lines is that classic unrestricted sliding-block puzzles are PSPACE-hard, even if the pieces are restricted to be all dominoes (1 × 2 blocks) and the goal is simply to move a particular piece. No prior complexity results were known about these puzzles. This result can be seen as a strengthening of the existing result that the restricted Rush HourTM puzzles are PSPACE-complete [Theoret. Comput. Sci. 270(1-2) (2002) 895], of which we also give a simpler proof. We also greatly strengthen the conditions for the PSPACE-hardness of the Warehouseman's Problem [Int. J. Robot. Res. 3(4) (1984) 76], a classic motion-planning problem. Finally, we strengthen the existing result that the pushing-blocks puzzle Sokoban is PSPACE-complete [In: Proc. Internat. Conf. on Fun with Algorithms, Elba, Italy, June 1998, pp. 65-76.], by showing that it is PSPACE-complete even if no barriers are allowed. The Complexity of Robot Motion Planning makes original contributions both to robotics and to the analysis of algorithms. In this groundbreaking monograph John Canny resolves long-standing problems concerning the complexity of motion planning and, for the central problem of finding a collision free path for a jointed robot in the presence of obstacles, obtains exponential speedups over existing algorithms by applying high-powered new mathematical techniques.Canny's new algorithm for this "generalized movers' problem," the most-studied and basic robot motion planning problem, has a single exponential running time, and is polynomial for any given robot. The algorithm has an optimal running time exponent and is based on the notion of roadmaps - one-dimensional subsets of the robot's configuration space. In deriving the single exponential bound, Canny introduces and reveals the power of two tools that have not been previously used in geometric algorithms: the generalized (multivariable) resultant for a system of polynomials and Whitney's notion of stratified sets. He has also developed a novel representation of object orientation based on unnormalized quaternions which reduces the complexity of the algorithms and enhances their practical applicability.After dealing with the movers' problem, the book next attacks and derives several lower bounds on extensions of the problem: finding the shortest path among polyhedral obstacles, planning with velocity limits, and compliant motion planning with uncertainty. It introduces a clever technique, "path encoding," that allows a proof of NP-hardness for the first two problems and then shows that the general form of compliant motion planning, a problem that is the focus of a great deal of recent work in robotics, is non-deterministic exponential time hard. Canny proves this result using a highly original construction.John Canny received his doctorate from MIT And is an assistant professor in the Computer Science Division at the University of California, Berkeley. The Complexity of Robot Motion Planning is the winner of the 1987 ACM Doctoral Dissertation Award.