Reasons to study multi-robot motion planning

Even though multiple-robot motion planning can be handled like any other motion planning problem, there are several reasons to study it separately:

1. The motions of the robots can be decoupled in many interesting ways. This leads to several interesting methods that first develop some kind of partial plan for the robots independently, and then consider the plan interactions to produce a solution. This idea is referred to as decoupled planning.
2. The part of ${X_{obs}}$ due to robot-robot collisions has a cylindrical structure, depicted in Figure 7.6, which can be exploited to make more efficient planning algorithms. Each $X^{ij}_{obs}$ defined by (7.8) depends only on two robots. A point, $x = (q^1,\ldots,q^m)$, is in ${X_{obs}}$ if there exists $i,j$ such that $1 \leq i,j \leq m$ and ${\cal A}^i(q^i) \cap {\cal A}^j(q^j) \not = \emptyset$, regardless of the configurations of the other $m-2$ robots. For some decoupled methods, this even implies that ${X_{obs}}$ can be completely characterized by 2D projections, as depicted in Figure 7.9.
3. If optimality is important, then a unique set of issues arises for the case of multiple robots. It is not a standard optimization problem because the performance of each robot has to be optimized. There is no clear way to combine these objectives into a single optimization problem without losing some critical information. It will be explained in Section 7.7.2 that Pareto optimality naturally arises as the appropriate notion of optimality for multiple-robot motion planning.

Figure 7.6: The set $X^{ij}_{obs}$ and its cylindrical structure on $X$.