Planning with motion commands

A high-level open-loop plan,12.6

$\displaystyle \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

Steven M LaValle 2012-04-20