A straightforward approach to decoupled planning is to sort the robots by priority and plan for higher priority robots first [320,951]. Lower priority robots plan by viewing the higher priority robots as moving obstacles. Suppose the robots are sorted as , , , in which has the highest priority.
Assume that collision-free paths, , have been computed for from to . The prioritized planning approach proceeds inductively as follows:
A special case of prioritized planning is to design all of the paths, , , , , in the first phase and then formulate each inductive step as a velocity tuning problem. This yields a sequence of 2D planning problems that can be solved easily. This comes at a greater expense, however, because the choices are even more constrained. The idea of preplanned paths, and even roadmaps, for all robots independently can lead to a powerful method if the coordination of the robots is approached more carefully. This is the next topic.
Steven M LaValle 2012-04-20