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 or . The components are as follows:

- A
*world*in which either or . - A semi-algebraic
*obstacle region*in the world. - A semi-algebraic
*robot*is defined in . It may be a rigid robot or a collection of links, . - The
*configuration space*determined by specifying the set of all possible transformations that may be applied to the robot. From this, and are derived. - A configuration,
designated as the
*initial configuration*. - A configuration
designated as the
*goal configuration*. The initial and goal configurations together are often called a*query pair*(or*query*) and designated as . - A complete algorithm must compute a (continuous)
*path*, , such that and , 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 is unbounded.

Steven M LaValle 2012-04-20