7.2.1 Problem Formulation

A state space is defined that considers the configurations of all robots simultaneously,

$$X = {\cal C}^1 \times {\cal C}^2 \times \cdots \times {\cal C}^m .$$ (7.6)

A state $x \in X$ specifies all robot configurations and may be expressed as $x = (q^1, q^2, \ldots, q^m)$. The dimension of $X$ is $N$, which is $N = \sum_{i=1}^m \dim({\cal C}^i)$.

There are two sources of obstacle regions in the state space: 1) robot-obstacle collisions, and 2) robot-robot collisions. For each $i$ such that $1 \leq i \leq m$, the subset of $X$ that corresponds to robot ${\cal A}^i$ in collision with the obstacle region, ${\cal O}$, is

$$X^i_{obs} = \{ x \in X \;\vert\; {\cal A}^i(q^i) \cap {\cal O}\not = \emptyset \} .$$ (7.7)

This only models the robot-obstacle collisions.

For each pair, ${\cal A}^i$ and ${\cal A}^j$, of robots, the subset of $X$ that corresponds to ${\cal A}^i$ in collision with ${\cal A}^j$ is

$$X^{ij}_{obs} = \{ x \in X \;\vert\; {\cal A}^i(q^i) \cap {\cal A}^j(q^j) \not = \emptyset \} .$$ (7.8)

Both (7.7) and (7.8) will be combined in (7.10) later to yield ${X_{obs}}$.

Formulation 7..2 (Multiple-Robot Motion Planning)  

1. The world ${\cal W}$ and obstacle region ${\cal O}$ are the same as in Formulation 4.1.
2. There are $m$ robots, ${\cal A}^1$, $\ldots$, ${\cal A}^m$, each of which may consist of one or more bodies.
3. Each robot ${\cal A}^i$, for $i$ from $1$ to $m$, has an associated configuration space, ${\cal C}^i$.
4. The state space $X$ is defined as the Cartesian product

   $$X = {\cal C}^1 \times {\cal C}^2 \times \cdots \times {\cal C}^m .$$ (7.9)

   
   
   The obstacle region in $X$ is

   $${X_{obs}}= \left( \bigcup_{i=1}^m X^i_{obs} \right) \; \bigcup \; \left( \bigcup_{ij, \;\;i \not = j} X^{ij}_{obs} \right) ,$$ (7.10)

   
   
   in which $X^i_{obs}$ and $X^{ij}_{obs}$ are the robot-obstacle and robot-robot collision states from (7.7) and (7.8), respectively.
5. A state ${x_{I}}\in {X_{free}}$ is designated as the initial state, in which ${x_{I}}= ({q^1_{I}},\ldots,{q^m_{I}})$. For each $i$ such that $1 \leq i \leq m$, ${q^i_{I}}$ specifies the initial configuration of ${\cal A}^i$.
6. A state ${x_{G}}\in {X_{free}}$ is designated as the goal state, in which ${x_{G}}= ({q^1_{G}},\ldots,{q^m_{G}})$.
7. The task is to compute a continuous path $\tau: [0,1] \rightarrow X_{free}$ such that $\tau(0) = x_{init}$ and $\tau(1) \in x_{goal}$.