Fast motion planning for multiple moving robots

The author presents an efficient solution to the motion-planning problem for multiple translating robots in the plane. It is shown that careful priority assignment can greatly reduce the average running time of the planner. A priority assignment method is introduced which attempts to maximize the number of robots which can move in a straight line form their start point to their goal point, thereby minimizing the number of robots for which expensive collision-avoiding search is necessary. This prioritization method is extremely effective in sparse workspaces where the moving robots are the primary obstacle.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">></ETX>