Handling the goal region

Recall that backward value iterations start with the final cost-to-go function and iterate backward. Initially, the final cost-to-go is assigned as infinity at all states except those in the goal. To properly initialize the final cost-to-go function, there must exist some subset of $ X$ over which the zero value can be obtained by interpolation. Let $ G = S \cap {X_{G}}$. The requirement is that the interpolation region $ R(G)$ must be nonempty. If this is not satisfied, then the grid resolution needs to be increased or the goal set needs to be enlarged. If $ X_g$ is a single point, then it needs to be enlarged, regardless of the resolution (unless an alternative way to interpolate near a goal point is developed). In the interpolation region shown in Figure 8.21c, all states in the vicinity of $ {x_{G}}$ yield an interpolated cost-to-go value of zero. If such a region did not exist, then all costs would remain at infinity during the evaluation of (8.59) from any state. Note that $ \Delta t$ must be chosen large enough to ensure that new samples can reach $ G$.

Steven M LaValle 2012-04-20