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.
\begin{figure}\centerline{\psfig{figure=figs/priplan2.eps,width=4.0truein} }\end{figure}

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.

Steven M LaValle 2012-04-20