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
2191404279 2113832842 2791175394 2782960731
In this paper, we study the structure and computational complexity of optimal multi-robot path planning problems on graphs. Our results encompass three formulations of the discrete multi-robot path planning problem, including a variant that allows synchronous rotations of robots along fully occupied, disjoint cycles on the graph. Allowing rotation of robots provides a more natural model for multi-robot path planning because robots can communicate. Our optimality objectives are to minimize the total arrival time, the makespan (last arrival time), and the total distance. On the structure side, we show that, in general, these objectives demonstrate a pairwise Pareto optimal structure and cannot be simultaneously optimized. On the computational complexity side, we extend previous work and show that, regardless of the underlying multi-robot path planning problem, these objectives are all intractable to compute. In particular, our NP-hardness proof for the time optimal versions, based on a minimal and direct reduction from the 3-satisfiability problem, shows that these problems remain NP-hard even when there are only two groups of robots (i.e. robots within each group are interchangeable). Multi-robot path planning is abstracted as the problem of computing a set of non-colliding paths on a graph for multiple robots. A naive search of the composite search space, although complete, has exponential complexity and becomes computationally prohibitive for problems with just a few robots. This paper proposes an efficient and complete algorithm for solving a general class of multi-robot path planning problems, specifically those where there are at most n-2 robots in a connected graph of n vertices. This paper provides a full proof of completeness. The algorithm employs two primitives: “push”, where a robot moves toward its goal until no progress can be made, and “swap”, that allows two robots to swap positions without altering the position of any other robot. Additionally, this paper provides a smoothing procedure for improving solution quality. Simulated experiments compare the proposed approach with several other centralized and decoupled planners, and show that the proposed technique improves computation time and solution quality, while scaling to problems with 100s of robots, solving them in under 5 seconds. A novel multi-robot path planning approach is presented in this paper. Based on the standard Dijkstra, the algorithm looks for the optimal paths for a formation of robots, taking into account the possibility of split and merge. The algorithm explores a graph representation of the environment, computing for each node the cost of moving a number of robots and their corresponding paths. In every node where the formation can split, all the new possible formation subdivisions are taken into account accordingly to their individual costs. In the same way, in every node where the formation can merge, the algorithm verifies whether the combination is possible and, if possible, computes the new cost. In order to manage split and merge situations, a set of constrains is applied. The proposed algorithm is thus deterministic, complete and finds an optimal solution from a source node to all other nodes in the graph. The presented solution is general enough to be incorporated into high-level tasks as well as it can benefit from state-of-the-art formation motion planning approaches, which can be used for evaluation of edges of an input graph. The presented experimental results demonstrate ability of the method to find the optimal solution for a formation of robots in environments with various complexity. Swarms of mobile robots recently attracted the focus of the Distributed Computing community. One of the fundamental problems in this context is that of exploration: the robots must coordinate to visit all locations that are reachable from their initial positions. Despite its apparent simplicity, this problem proved quite hard to characterise fully, due to many model variants, leading to informal error-prone reasoning. Over the past few years, a significant effort permitted to set up a formal framework, relying on the Coq proof assistant, which was used to provide certified results when robots evolve in a continuous bi-dimensional Euclidean space. However, the most challenging issues with exploration arise in the discrete setting (a.k.a. graph), where locations are modeled as vertices and where edges between vertices denote the ability for a robot to move from one location to the next. We present a formal model to tackle problems and reason about robot algorithms arising in the discrete setting. Our approach extends and generalises previous research efforts focusing on the continuous model. As case studies, we consider fundamental impossibility results for exploration with stop in the discrete model. To our knowledge, those are the first certified results in this context. This framework paves the way for a general certification workflow dedicated to mobile robots on graphs.