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.