An ordinary motion planning problem?

On the surface it may appear that there is nothing unusual about the multiple-robot problem because the formulations used in Chapter 4 already cover the case in which the robot consists of multiple bodies. They do not have to be attached; therefore, $ X$ can be considered as an ordinary C-space. The planning algorithms of Chapters 5 and 6 may be applied without adaptation. The main concern, however, is that the dimension of $ X$ grows linearly with respect to the number of robots. For example, if there are $ 12$ rigid bodies for which each has $ {\cal C}^i = SE(3)$, then the dimension of $ X$ is $ 6 \cdot 12 = 72$. Complete algorithms require time that is at least exponential in dimension, which makes them unlikely candidates for such problems. Sampling-based algorithms are more likely to scale well in practice when there many robots, but the dimension of $ X$ might still be too high.

Steven M LaValle 2012-04-20