You are here: Home Research Prioritized Multi-robot Path Planning

Prioritized Multi-robot Path Planning

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 task specification.

Related publications:

Please check this webpage for further related publications in the years 2000-2001.


  Experiment with the robots of the CS Freiburg
  • Uncoordinated motions (mpg-video)
  • Executing the computed collision-free paths (mpg-video)
  A team of 10 robots in a corridor environment (simulation)
  A team of 30 robots in a cluttered environment (simulation)
Benutzerspezifische Werkzeuge