Maximum clearance

One problem that typically arises in mobile robotics is that optimal motion plans bring robots too close to obstacles. Recall from Section 6.2.4 that the shortest Euclidean paths for motion planning in a polygonal environment must be allowed to touch obstacle vertices. This motivated the maximum clearance roadmap, which was covered in Section 6.2.3. A grid-based approximate version of the maximum clearance roadmap can be made. Furthermore, a navigation function can be defined that guides the robot onto the roadmap, then travels along the roadmap, and finally deposits the robot at a specified goal. In [588], the resulting navigation function is called NF2.

Assume that there is a single goal state, ${x_{G}}\in X$. The computation of a maximum clearance navigation function proceeds as follows:

1. Instead of ${X_{G}}$, assign $W_0$ to be the set of all states from which motion in at least one direction is blocked. These are the states on the boundary of the discretized collision-free space.
2. Perform wavefront iterations that propagate costs in waves outward from the obstacle boundaries.
3. As the wavefronts propagate, they will meet approximately at the location of the maximum clearance roadmap for the original, continuous problem. Mark any state at which two wavefront points arrive from opposing directions as a skeleton state. It may be the case that the wavefronts simply touch each other, rather than arriving at a common state; in this case, one of the two touching states is chosen as the skeleton state. Let $S$ denote the set of all skeleton states.
4. After the wavefront propagation ends, connect ${x_{G}}$ to the skeleton by inserting ${x_{G}}$ and all states along the path to the skeleton into $S$. This path can be found using any search algorithm.
5. Compute a navigation function $\phi_1$ over $S$ by treating all other states as if they were obstacles and using the wavefront propagation algorithm. This navigation function guides any point in $S$ to the goal.
6. Treat $S$ as a goal region and compute a navigation function $\phi_2$ using the wavefront propagation algorithm. This navigation function guides the state to the nearest point on the skeleton.
7. Combine $\phi_1$ and $\phi_2$ as follows to obtain $\phi$. For every $x \in S$, let $\phi(x) = \phi_1(x)$. For every remaining state, the value $\phi(x) = \phi_1(x') + \phi_2(x)$ is assigned, in which $x'$ is the nearest state to $x$ such that $x' \in S$. The state $x'$ can easily be recorded while $\phi_2$ is computed.

If ${\cal C}_{free}$ is multiply connected, then there may be multiple ways to each ${x_{G}}$ by traveling around different obstacles (the paths are not homotopic). The method described above does not take into account the problem that one route may have a tighter clearance than another. The given approach only optimizes the distance traveled along the skeleton; it does not, however, maximize the nearest approach to an obstacle, if there are multiple routes.