Suppose that the world,
or
, contains an
obstacle region,
. Assume here that a rigid robot,
, is defined; the case of multiple links will be handled
shortly. Assume that both and are expressed as
semi-algebraic models (which includes polygonal and polyhedral models)
from Section 3.1. Let
denote the *configuration* of , in which
for
and
for
( represents the
unit quaternion).

The *obstacle region*,
, is defined as

which is the set of all configurations, , at which , the transformed robot, intersects the obstacle region, . Since and are closed sets in , the obstacle region is a closed set in .

The leftover configurations are called the *free space*, which is
defined and denoted as
. Since is a
topological space and
is closed,
must be an open set.
This implies that the robot can come arbitrarily close to the
obstacles while remaining in
. If ``touches'' ,

(4.35) |

then (recall that means the interior). The condition above indicates that only their boundaries intersect.

The idea of getting arbitrarily close may be nonsense in practical robotics, but it makes a clean formulation of the motion planning problem. Since is open, it becomes impossible to formulate some optimization problems, such as finding the shortest path. In this case, the closure, , should instead be used, as described in Section 7.7.

Steven M LaValle 2012-04-20