Handling obstacles

A simple way to handle obstacles is to determine for each $x \in S$ whether $x \in {\cal C}_{obs}$. This can be computed and stored in an array before the value iterations are performed. For rigid robots, this can be efficiently computed using fast Fourier transforms [513]. For each $x \in {\cal C}_{obs}$, $G^*(x) = \infty$. No value iterations are performed on these states; their values must remain at infinity. During the evaluation of (8.59) (or a higher dimensional version), different actions are attempted. For each action, it is required that all of the interpolation neighbors of $x_{k+1}$ lie in ${\cal C}_{free}$. If one of them lies in ${\cal C}_{obs}$, then that action produces infinite cost. This has the effect of automatically reducing the interpolation region, $R(S)$, to all cubes whose vertices all lie in ${\cal C}_{free}$, as shown in Figure 8.21b. All samples in ${\cal C}_{obs}$ are assumed to be deleted from $S$ in the remainder of this section; however, the full grid is still used for interpolation so that infinite values represent the obstacle region.

Note that as expressed so far, it is possible that points in ${\cal C}_{obs}$ may lie in $R(S)$ because collision detection is performed only on the samples. In practice, either the grid resolution must be made fine enough to minimize the chance of this error occurring or distance information from a collision detection algorithm must be used to infer that a sufficiently large ball around each sample is collision free. If an interpolation region cannot be assured to lie in ${\cal C}_{free}$, then the resolution may have to be increased, at least locally.