Search
Close this search box.

\(k\)-Color Multi-Robot Motion Planning

Abstract

An example of a 3-color scenario
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.

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)
(a) Unlabeled (1-Color)

(b) 2-Color
(b) 2-Color

(c) Fully-Colored (8-Color)
(c) Fully-Colored (8-Color)

(d) Fully-Colored (5-Color)
(d) Fully-Colored (5-Color)

(e) 4-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 WAFR 2012, 2014, 33(1): 82-97 [link][bibtex]
    Algorithmic Foundations of Robotics X2012, Volume 86 of STAR, pages 191-207 [link][bibtex]
  • Kiril Solovey
    k-Color Multi-Robot Motion Planning
    M.Sc. thesis, Tel Aviv University, February 2013 [pdf][bibtex]

Contacts

Kiril Solovey
Dan Halperin
@incollection{sh-kcmrm-13,
  author = {Kiril Solovey and and Dan Halperin},
  editor = {Emilio Frazzoli and Tomas Lozano-Perez and Nicholas Roy and Daniela Rus},
  title  = {$k$-Color Multi-robot Motion Planning},
  booktitle = {Algorithmic Foundations of Robotics X},
  series = {Springer Tracts in Advanced Robotics ({STAR})},
  volume = {86},
  year = {2013},
  publisher = {Springer},
  pages = {191--207},
  doi = {10.1007/978-3-642-36279-8_12}
}
@masterthesis{s-kcmrm-13,
  author       = {Kiril Solovey},
  title        = {$k$-Color Multi-Robot Motion Planning},
  type         = {{M}.{S}c. Thesis},
  school       = {The Blavatnik School of Computer Science, Tel-Aviv University},
  year         = {2013}
}
@article{sh-kcmrm-14,
  author = {Kiril Solovey and Dan Halperin},
  title = {$k$-color multi-robot motion planning},
  journal = {The International Journal of Robotics Research},
  year = {2014},
  volume = {33},
  number = {1},
  pages = {82--97},
  doi = {10.1177/0278364913506268}
}

Yair Oz - Webcreator

Contact

Skip to content