k-Color Multi-Robot Motion Planning
An example of a 3-color scenario where three different groups of robots occupy the same workspace. The star-shaped (orange) robots are required to exchange "rooms" with the snake (red) robots while the two puzzle-like (purple) robots should return to their start positions in the end of the motion. Obstacles are drawn in gray. |
Abstract
We present a simple and natural extension of the multi-robot motion planning problem where the robots are partitioned into groups (colors), such that in each group the robots are interchangeable. Every robot is no longer required to move to a specific target, but rather to some target placement that is assigned to its group. We call this problem k-color multi-robot motion planning and provide a sampling-based algorithm specifically designed for solving it.
At the heart of the algorithm is a novel technique where the k-color problem is reduced to several discrete multi-robot motion planning problems. These reductions amplify basic samples into massive collections of free placements and paths for the robots.
We demonstrate the performance of the algorithm by an implementation for the case of disc robots and polygonal robots translating in the plane. We show that the algorithm successfully and efficiently copes with a variety of challenging scenarios, involving many robots, while a simplified version of this algorithm, that can be viewed as an extension of a prevalent sampling-based algorithm for the k-color case, fails even on simple scenarios. Interestingly, our algorithm outperforms a well established implementation of PRM for the standard multi-robot problem, in which each robot has a distinct color.
From a theoretic point of view, we show that the algorithm is probabilistically complete when a few simple assumptions are made.
Scenarios
Listed below are challenging scenarios on which we tested the algorithm. Start positions of the robots are indicated by discs while target positions are illustrated as circles in respective colors (unless otherwise indicated) (a) Unlabeled (1-Color) scene with twenty five robots. (b) 2-Color scene; the two groups are required to switch positions. (c) Fully-colored scene with eight robots. (d) Fully-colored scene with five robots. (e) 4-Color scene; every group has to move in a clockwise manner to the next room, e.g., blue group should move to the bottom room.
(a) Unlabeled (1-Color) |
(b) 2-Color |
(c) Fully-Colored (8-Color) |
|||
(d) Fully-Colored (5-Color) |
(e) 4-Color |
Links
- Kiril Solovey and Dan Halperin
k-Color Multi-Robot Motion Planning,
International Journal on Robotics Research (IJRR), special issue from WAFR2012, 2014, 33(1): 82-97 [link];
In Proceedings of the 10th International Workshop on the Algorithmic Foundations of Robotics (WAFR), 2012, pages 191-207 [link]. - Kiril Solovey
k-Color Multi-Robot Motion Planning [pdf],
Master's thesis, Tel Aviv University, February 2013
Advisor: Prof. Dan Halperin.
Contacts
Kiril Solovey | ![]() |
![]() |
Dan Halperin | ![]() |
![]() |