Prioritized Motion Planning for Multiple Robots
Jur P. van den Berg, Mark H. Overmars
In this paper we address the problem of motion
planning for multiple robots. We introduce a prioritized
method, based on a powerful method for motion planning
in dynamic environments, recently developed by the authors.
Our approach is generically applicable: there is no limitation
on the number of degrees of freedom of each of the robots,
and robots of various types –for instance free-flying robots
and articulated robots– can be used simultaneously. Results
show that high-quality paths can be produced in less than a
second of computation time, even in confined environments
involving many robots. We examine three issues in particular
in this paper: the assignment of priorities to the robots,
the performance of prioritized planning versus coordinated
planning, and the influence of the extent by which the robot
motions are constrained on the performance of the method.
Results are reported in terms of both running time and the
quality of the paths produced.
Download this deliverable.