12.1.2 Algorithms for Nondeterministic I-Spaces

Now that the problem of planning in $ {\cal I}_{ndet}$ has been expressed using Formulation 10.1, the methods of Section 10.2 directly apply. The main limitation of their use is that the new state space $ {\vec{X}}$ is exponentially larger than $ X$. If $ X$ contains $ n$ states, then $ {\vec{X}}$ contains $ 2^n-1$ states. Thus, even though some methods in Section 10.2 can solve problems in practice that involve a million states, this would only be about $ 20$ states in the original state space. Handling substantially larger problems requires developing application-specific methods that exploit some special structure of the I-space, possibly by defining an I-map that leads to a smaller derived I-space.


Steven M LaValle 2012-04-20