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. We developed
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
Finding and Optimizing Solvable
Priority Schemes for Decoupled Path Planning Techniques for Teams of
M. Bennewitz, W. Burgard and S. Thrun. In: Robotics and Autonomous Systems, Vol. 41, 2002.
Constraints During Prioritized Path Planning for Teams of Mobile Robots.
M. Bennewitz, W. Burgard, and S. Thrun. In: Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), 2001.
Schedules for Prioritized Path Planning of Multi-Robot Systems.
M. Bennewitz, W. Burgard, and S. Thrun. In: Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), 2001.
Please check this webpage for further related publications in the years 2000-2001.
|Experiment with the robots of the CS Freiburg|
|A team of 10 robots in a corridor environment (simulation)|
|A team of 30 robots in a cluttered environment (simulation)|