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:
It was shown by Reif  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