Ensuring resolution completeness

Suppose that the discrete-time model is used. If $ {\alpha }$ is dense in $ X$, then each RDT vertex is visited a countably infinite number of times after it is constructed. By ensuring that the same motion primitive is never applied twice from the same vertex, all available motion primitives will eventually be tried. This ensures that the full reachability graph is explored for a fixed $ \Delta t$. Since the reachability graph is not necessarily finite, obtaining resolution completeness is more challenging. The scheme described in Figure 14.7 can be applied by periodically varying $ \Delta t$ during execution, and using smaller and smaller of values of $ \Delta t$ in later iterations. If $ U$ is finite, refinements can also be made to $ U_d$. This leads to a resolution-complete RDT.

Steven M LaValle 2012-04-20