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 novel priority assignment method is introduced which attempts to maximize the number of robots which can move in a straight line from 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.