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 over which the zero value can be obtained by interpolation. Let . The requirement is that the interpolation region 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 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 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 must be chosen large enough to ensure that new samples can reach .

Steven M LaValle 2012-04-20