Planning with motion commands

A high-level open-loop plan,^12.6

$$\pi = ({\mu}_1,{\mu}_2,\ldots,{\mu}_k),$$ (12.34)

can be constructed, which is a sequence of $k$ motion commands. Although the precise path executed by the robot is unpredictable, the sequence of motion commands is assumed to be predictable. Each motion command ${\mu}_i$ for $1 < i < k$ must terminate with an I-state ${\eta}\in P({\mu}_{i+1},G_{i+1})$. The preimage of ${\mu}_1$ must include ${\eta_0}$, the initial I-state. The goal is achieved by the last motion command, ${\mu}_k$.

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 $\pi : {\cal I}_{hist}\rightarrow {\cal M}$ can be developed, in which a motion command ${\mu}= \pi ({\eta})$ is chosen based on the history I-state ${\eta}$ 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 ${\mu}$ 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 [311], by a reduction from the Turing machine halting problem [891], that the preimage in general is uncomputable by any algorithm. It was shown in [732] that the 3D version of preimage planning, in which the obstacles are polyhedral, is PSPACE-hard. It was then shown in [172] that it is even NEXPTIME-hard.^12.7