7.2.1 Problem Formulation

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

$\displaystyle 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

$\displaystyle 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

$\displaystyle 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

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

    The obstacle region in $ X$ is

    $\displaystyle {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}$.



Subsections
Steven M LaValle 2020-08-14