A high-level open-loop plan,12.6
More generally, the particular motion command chosen need not be predictable, and may depend on the I-state during execution. In this case, the high-level feedback plan can be developed, in which a motion command is chosen based on the history I-state that results after the previous motion command terminates. Such variations are covered in [281,311,588].
The high-level planning problem can be solved using discrete planning algorithms from Chapters 2 and 10. The most popular method within the preimage planning framework is to perform a backward search from the goal. Although this sounds simple enough, the set of possible motion commands is infinite, and it is difficult to sample in a way that leads to completeness. Another complication is that termination is based on the history I-state. Planning is therefore quite challenging. It was even shown in , by a reduction from the Turing machine halting problem , that the preimage in general is uncomputable by any algorithm. It was shown in  that the 3D version of preimage planning, in which the obstacles are polyhedral, is PSPACE-hard. It was then shown in  that it is even NEXPTIME-hard.12.7
Steven M LaValle 2012-04-20