Obstacle region for a rigid body

Suppose that the world, $ {\cal W}= {\mathbb{R}}^2$ or $ {\cal W}= {\mathbb{R}}^3$, contains an obstacle region, $ {\cal O}\subset {\cal W}$. Assume here that a rigid robot, $ {\cal A}\subset {\cal W}$, is defined; the case of multiple links will be handled shortly. Assume that both $ {\cal A}$ and $ {\cal O}$ are expressed as semi-algebraic models (which includes polygonal and polyhedral models) from Section 3.1. Let $ q \in {\cal C}$ denote the configuration of $ {\cal A}$, in which $ q = (x_t,y_t,\theta)$ for $ {\cal W}= {\mathbb{R}}^2$ and $ q = (x_t,y_t,z_t,h)$ for $ {\cal W}= {\mathbb{R}}^3$ ($ h$ represents the unit quaternion).

The obstacle region, $ {\cal C}_{obs}\subseteq {\cal C}$, is defined as

$\displaystyle {\cal C}_{obs}= \{ q \in {\cal C}\;\vert\; {\cal A}(q) \cap {\cal O}\not = \emptyset \} ,$ (4.34)

which is the set of all configurations, $ q$, at which $ {\cal A}(q)$, the transformed robot, intersects the obstacle region, $ {\cal O}$. Since $ {\cal O}$ and $ {\cal A}(q)$ are closed sets in $ {\cal W}$, the obstacle region is a closed set in $ {\cal C}$.

The leftover configurations are called the free space, which is defined and denoted as $ {\cal C}_{free}= {\cal C}\setminus {\cal C}_{obs}$. Since $ {\cal C}$ is a topological space and $ {\cal C}_{obs}$ is closed, $ {\cal C}_{free}$ must be an open set. This implies that the robot can come arbitrarily close to the obstacles while remaining in $ {\cal C}_{free}$. If $ {\cal A}$ ``touches'' $ {\cal O}$,

$\displaystyle \operatorname{int}({\cal O}) \cap \operatorname{int}({\cal A}(q)) = \emptyset$$\displaystyle \mbox { and } {\cal O}\cap {\cal A}(q) \not = \emptyset ,$ (4.35)

then $ q \in {\cal C}_{obs}$ (recall that $ \operatorname{int}$ 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 $ {\cal C}_{free}$ is open, it becomes impossible to formulate some optimization problems, such as finding the shortest path. In this case, the closure, $ \operatorname{cl}({\cal C}_{free})$, should instead be used, as described in Section 7.7.

Steven M LaValle 2012-04-20