M. Bennewitz, W. Burgard, and S. Thrun
Constraint-based Optimization
of Priority Schemes for Decoupled Path Planning Techniques
Proc. of the German Conference on Artificial Intelligence (KI), 2001
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 [.ps.gz]
(207,248 bytes)
Bibtex
@InProceedings{Benn01Con,
author = {Bennewitz, M. and Burgard, W.
and Thrun S.},
title = {Constraint-based Optimization
of Priority Schemes for Decoupled Path Planning Techniques},
booktitle = {Proc. of the German Conference on Artificial Intelligence (KI)},
year = {2001},
publisher = {Springer Verlag}
}