## 7.2.1 Problem Formulation

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

 (7.6)

A state specifies all robot configurations and may be expressed as . The dimension of is , which is .

There are two sources of obstacle regions in the state space: 1) robot-obstacle collisions, and 2) robot-robot collisions. For each such that , the subset of that corresponds to robot in collision with the obstacle region, , is

 (7.7)

This only models the robot-obstacle collisions.

For each pair, and , of robots, the subset of that corresponds to in collision with is

 (7.8)

Both (7.7) and (7.8) will be combined in (7.10) later to yield .

Formulation 7..2 (Multiple-Robot Motion Planning)
1. The world and obstacle region are the same as in Formulation 4.1.
2. There are robots, , , , each of which may consist of one or more bodies.
3. Each robot , for from to , has an associated configuration space, .
4. The state space is defined as the Cartesian product

 (7.9)

The obstacle region in is

 (7.10)

in which and are the robot-obstacle and robot-robot collision states from (7.7) and (7.8), respectively.
5. A state is designated as the initial state, in which . For each such that , specifies the initial configuration of .
6. A state is designated as the goal state, in which .
7. The task is to compute a continuous path such that and .

Subsections
Steven M LaValle 2012-04-20