M. Bennewitz, W. Burgard, and S. Thrun
Finding and Optimizing Solvable Priority Schemes for Decoupled Path Planning Techniques for Teams of Mobile Robots
Robotics and Autonomous Systems, 41 (2), pp. 89-99, 2002.
Abstract
Coordinating the motion of multiple mobile robots is one of the fundamental
problems in robotics. The predominant algorithms for coordinating teams of
robots are decoupled and prioritized, thereby avoiding combinatorially hard
planning problems typically faced by centralized approaches. 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. In this paper we
present a method for finding and optimizing priority schemes for such
prioritized and decoupled planning techniques. Existing approaches apply a
single priority scheme which makes them overly prone to failure in cases where
valid solutions exist. By searching in the space of priorization schemes, our
approach overcomes this limitation. It performs a randomized search with
hill-climbing to find solutions and to minimize the overall path length. To
focus the search, our algorithm is guided by constraints generated from the
task specification. To illustrate the appropriateness of this approach, this
paper discusses experimental results obtained with real robots and through
systematic robot simulation. The experimental results illustrate the superior
performance of our approach, both in terms of efficiency of robot motion and
in the ability to find valid plans.
Download
Full paper
[.pdf] (350 KB, 11 pages)
Bibtex
@ARTICLE{Bennewitz02Planning,
AUTHOR = {Bennewitz, M. and Burgard, W. and Thrun, S.},
TITLE = {Finding and Optimizing Solvable Priority Schemes for Decoupled Path Planning Techniques for Teams of Mobile Robots},
YEAR = {2002},
journal = {Robotics and Autonomous Systems},
volume = {41},
number = {2},
pages = {89-99},
}