6.4.1 Basic Definitions and Concepts

This section builds on the semi-algebraic model definitions from Section 3.1 and the polynomial definitions from Section 4.4.1. It will be assumed that $ {\cal C}\subseteq {\mathbb{R}}^n$, which could for example arise by representing each copy of $ SO(2)$ or $ SO(3)$ in its $ 2 \times 2$ or $ 3 \times 3$ matrix form. For example, in the case of a 3D rigid body, we know that $ {\cal C}= {\mathbb{R}}^3 \times {\mathbb{RP}}^3$, which is a six-dimensional manifold, but it can be embedded in $ {\mathbb{R}}^{12}$, which is obtained from the Cartesian product of $ {\mathbb{R}}^3$ and the set of all $ 3 \times 3$ matrices. The constraints that force the matrices to lie in $ SO(2)$ or $ SO(3)$ are polynomials, and they can therefore be added to the semi-algebraic models of $ {\cal C}_{obs}$ and $ {\cal C}_{free}$. If the dimension of $ {\cal C}$ is less than $ n$, then the algorithm presented below is sufficient, but there are some representation and complexity issues that motivate using a special parameterization of $ {\cal C}$ to make both dimensions the same while altering the topology of $ {\cal C}$ to become homeomorphic to $ {\mathbb{R}}^n$. This is discussed briefly in Section 6.4.2.

Suppose that the models in $ {\mathbb{R}}^n$ are all expressed using polynomials from $ {\mathbb{Q}}[x_1,\ldots, x_n]$, the set of polynomials6.6 over the field of rational numbers $ {\mathbb{Q}}$. Let $ f \in {\mathbb{Q}}[x_1,\ldots, x_n]$ denote a polynomial.

Steven M LaValle 2012-04-20