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

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

This only models the robot-obstacle collisions.

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

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

- The
*world*and*obstacle region*are the same as in Formulation 4.1. - There are
*robots*, , , , each of which may consist of one or more bodies. - Each robot
, for from to , has an associated
*configuration space*, . - The
*state space*is defined as the Cartesian product

The obstacle region in is

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