Fast algorithms for optimal multi-robot path
planning are sought after in real-world applications. Known
methods, however, generally do not simultaneously guar-
antee good solution optimality and good (e.g., polynomial)
running time. In this work, we develop a first low-polynomial
running time algorithm, called SplitAndGroup (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 in-
stances. 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 al-
gorithm supports cases where all vertices of the underly-
ing graph are occupied. SaG attains its desirable proper-
ties 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.
more »
« less
Expected constant-factor optimal multi-robot path planning in well-connected environments
Fast algorithms for optimal multi-robot path planning are sought after in both research and real-world applications. Known methods, however, generally do not simultaneously guarantee good solution optimality and fast run time for difficult instances. In this work, we develop a low-polynomial running time algorithm, called SplitAndGroup, that solves the multi-robot path planning problem on grids and grid-like environments, and produces constant factor time- and distance-optimal solutions, in expectation. In particular, SplitAndGroup computes solutions with sub-linear makespan. SplitAndGroup is capable of handling cases when the density of robot is extremely high - in a graph-theoretic setting, the algorithm supports cases where all vertices of the underlying graph are occupied by robots. SplitAndGroup attains its desirable properties through a careful combination of divide-and-conquer technique and network flow based methods for routing the robots.
more »
« less
- Award ID(s):
- 1734419
- NSF-PAR ID:
- 10071643
- Date Published:
- Journal Name:
- 2017 International Symposium on Multi-Robot and Multi-Agent Systems (MRS)
- Page Range / eLocation ID:
- 48 to 55
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
We study the labeled multi-robot path planning problem in continuous 2D and 3D domains in the absence of obstacles where robots must not collide with each other. For an arbitrary number of robots in arbitrary initial and goal arrangements, we derive a polynomial time, complete algorithm that produces solutions with constant-factor optimality guarantees on both makespan and distance optimality, in expectation, under the assumption that the robot labels are uniformly randomly distributed. Our algorithm only requires a small constant-factor expansion of the initial and goal configuration footprints for solving the problem, i.e., the problem can be solved in a fairly small bounded region. Beside theoretical guarantees, we present a thorough computational evaluation of the proposed solution. In addition to the baseline implementation, adapting an effective (but non-polynomial time) routing subroutine, we also provide a highly efficient implementation that quickly computes near-optimal solutions. Hardware experiments on the microMVP platform composed of non-holonomic robots confirms the practical applicability of our algorithmic pipeline.more » « less
-
Let G = (V, E) be an m_1 \times \ldots \times m_k grid for some arbitrary constant k. We establish that O(\sum_{i=1}^km_i) (makespan) time-optimal labeled (i.e., each robot has a specific goal) multi-robot path planning can be realized on G in O(|V|^2) running time, even when vertices of G are fully occupied by robots. When all dimensions are of equal sizes, the running time approaches O(|V|). Using this base line algorithm, which provides average case O(1)-approximate (i.e., constant-factor) time-optimal solutions, we further develop a first worst case O(1)-approximate algorithm that again runs in O(|V|^2) time for two and three dimensions. We note that the problem has a worst case running time lower bound of \Omega(|V|^2).more » « less
-
more » « less
Abstract We consider the problem of multi-robot path planning in a complex, cluttered environment with the aim of reducing overall congestion in the environment, while avoiding any inter-robot communication or coordination. Such limitations may exist due to lack of communication or due to privacy restrictions (for example, autonomous vehicles may not want to share their locations or intents with other vehicles or even to a central server). The key insight that allows us to solve this problem is to stochastically distribute the robots across different routes in the environment by assigning them paths in different topologically distinct classes, so as to lower congestion and the overall travel time for all robots in the environment. We outline the computation of topologically distinct paths in a spatio-temporal configuration space and propose methods for the stochastic assignment of paths to the robots. A fast replanning algorithm and a potential field based controller allow robots to avoid collision with nearby agents while following the assigned path. Our simulation and experiment results show a significant advantage over shortest path following under such a coordination-free setup.
-
null (Ed.)Complex service robotics scenarios entail unpredictable task appearance both in space and time. This requires robots to continuously relocate and imposes a trade-off between motion costs and efficiency in task execution. In such scenarios, multi-robot systems and even swarms of robots can be exploited to service different areas in parallel. An efficient deployment needs to continuously determine the best allocation according to the actual service needs, while also taking relocation costs into account when such allocation must be modified. For large scale problems, centrally predicting optimal allocations and movement paths for each robot quickly becomes infeasible. Instead, decentralized solutions are needed that allow the robotic system to self-organize and adaptively respond to the task demands. In this paper, we propose a distributed and asynchronous approach to simultaneous task assignment and path planning for robot swarms, which combines a bio-inspired collective decision-making process for the allocation of robots to areas to be serviced, and a search-based path planning approach for the actual routing of robots towards tasks to be executed. Task allocation exploits a hierarchical representation of the workspace, supporting the robot deployment to the areas that mostly require service. We investigate four realistic environments of increasing complexity, where each task requires a robot to reach a location and work for a specific amount of time. The proposed approach improves over two different baseline algorithms in specific settings with statistical significance, while showing consistently good results overall. Moreover, the proposed solution is robust to limited communication and robot failures.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- https://doi.org/10.1109/MRS.2017.8250930
