M. Bennewitz, W. Burgard, and S. Thrun
Optimizing Schedules for Prioritized
Path Planning of Multi-Robot Systems
Proc. of the IEEE International Conference on Robotics
& Automation (ICRA)
Abstract
The coordination of the motions of the robots is one of the fundamental
problems for multi-robot systems. A popular approach to avoid planning
in the high-dimensional composite configuration space are prioritized and
decoupled techniques. While these methods are very efficient, they
have two major drawbacks. First, they are incomplete, i.e.~they sometimes
fail to find a solution even if one exists, and second, the resulting solutions
are often not optimal. They furthermore leave open how to assign the priorities
to the individual robots. In this paper we present a method for optimizing
priority schemes for such prioritized and decoupled planning techniques.
Our approach performs a randomized search with hill-climbing to find solutions
and to minimize the overall path lengths. The technique has been
implemented and tested on real robots and in extensive simulation runs.
The experimental results demonstrate that our method is able to seriously
reduce the number of failures and to significantly reduce the overall path
length for different prioritized and decoupled path planning techniques
and even for large teams of robots.
Download
Full paper [.ps.gz]
(198,973 bytes)
Bibtex
@InProceedings{Benn01Opt,
author = {Bennewitz, M. and Burgard
W. and Thrun, S.},
title = {Optimizing Schedules for
Prioritized Path Planning of Multi-Robot Systems},
booktitle = ICRA,
year = {2001},
}