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 ${\cal A}^1$ , $\ldots$ , ${\cal A}^m$ , in which ${\cal A}^1$ has the highest priority.

Assume that collision-free paths, $\tau_i : [0,1] \rightarrow {\cal C}^i_{free}$ , have been computed for $i$ from $1$ to $n$ . 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, $\tau_1 : [0,1] \rightarrow {\cal C}^1_{free}$ for ${\cal A}^1$ . Compute a timing function, $\sigma_1$ , for $\tau_1$ , to yield $\phi_1 = \tau_1 \circ \sigma_1: T \rightarrow {\cal C}^1_{free}$ .

Inductive step: Suppose that $\phi_1$ , $\ldots$ , $\phi_{i-1}$ have been designed for ${\cal A}^1$ , $\ldots$ , ${\cal A}^{i-1}$ , and that these functions avoid robot-robot collisions between any of the first $i-1$ robots. Formulate the first $i-1$ robots as moving obstacles in ${\cal W}$ . For each $t \in T$ and $j \in \{1,\ldots,i-1\}$ , the configuration $q^j$ of each ${\cal A}^j$ is $\phi_j(t)$ . This yields ${\cal A}^j(\phi_j(t)) \subset {\cal W}$ , which can be considered as a subset of the obstacle ${\cal O}(t)$ . Design a path, $\tau_i$ , and timing function, $\sigma_i$ , using any of the time-varying motion planning methods from Section 7.1 and form $\phi_i = \tau_i \circ \sigma_i$ .

Although practical in many circumstances, Figure 7.8 illustrates how completeness is lost.

Figure 7.8: If ${\cal A}^1$ neglects the query for ${\cal A}^2$ , then completeness is lost when using the prioritized planning approach. This example has a solution in general, but prioritized planning fails to find it.

A special case of prioritized planning is to design all of the paths, $\tau_1$ , $\tau_2$ , $\ldots$ , $\tau_m$ , 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.