#### Prioritized planning

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:

Base case: Use any motion planning algorithm from Chapters 5 and 6 to compute a collision-free path, for . Compute a timing function, , for , to yield .
Inductive step: Suppose that , , have been designed for , , , and that these functions avoid robot-robot collisions between any of the first robots. Formulate the first robots as moving obstacles in . For each and , the configuration of each is . This yields , which can be considered as a subset of the obstacle . Design a path, , and timing function, , using any of the time-varying motion planning methods from Section 7.1 and form .
Although practical in many circumstances, Figure 7.8 illustrates how completeness is lost.

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 2020-08-14