Definition of basic motion planning

Figure 4.11: The basic motion planning problem is conceptually very simple using C-space ideas. The task is to find a path from ${q_{I}}$ to ${q_{G}}$ in ${\cal C}_{free}$. The entire blob represents ${\cal C}= {\cal C}_{free}\cup {\cal C}_{obs}$.

Finally, enough tools have been introduced to precisely define the motion planning problem. The problem is conceptually illustrated in Figure 4.11. The main difficulty is that it is neither straightforward nor efficient to construct an explicit boundary or solid representation of either ${\cal C}_{free}$ or ${\cal C}_{obs}$. The components are as follows:

Formulation 4..1 (The Piano Mover's Problem)  

1. A world ${\cal W}$ in which either ${\cal W}= {\mathbb{R}}^2$ or ${\cal W}= {\mathbb{R}}^3$.
2. A semi-algebraic obstacle region ${\cal O}\subset {\cal W}$ in the world.
3. A semi-algebraic robot is defined in ${\cal W}$. It may be a rigid robot ${\cal A}$ or a collection of $m$ links, ${\cal A}_1, {\cal A}_2, \ldots, {\cal A}_m$.
4. The configuration space ${\cal C}$ determined by specifying the set of all possible transformations that may be applied to the robot. From this, ${\cal C}_{obs}$ and ${\cal C}_{free}$ are derived.
5. A configuration, ${q_{I}}\in {\cal C}_{free}$ designated as the initial configuration.
6. A configuration ${q_{G}}\in {\cal C}_{free}$ designated as the goal configuration. The initial and goal configurations together are often called a query pair (or query) and designated as $({q_{I}},{q_{G}})$.
7. A complete algorithm must compute a (continuous) path, $\tau: [0,1] \rightarrow {\cal C}_{free}$, such that $\tau(0) = {q_{I}}$ and $\tau(1) = {q_{G}}$, or correctly report that such a path does not exist.

It was shown by Reif [817] that this problem is PSPACE-hard, which implies NP-hard. The main problem is that the dimension of ${\cal C}$ is unbounded.