8.4.4.3 Navigation function in the sense of Rimon-Koditschek

Now consider constructing a navigation function from which a vector field can be derived that satisfies constraints motivated by the acceleration-based control model, (8.47). As usual, the definition of a navigation function begins with the consideration of a potential function, $\phi : X \rightarrow {\mathbb{R}}$. What properties does a potential function need to have so that it may be considered as a navigation function as defined in Section 8.4.1 and also yield a vector field that satisfies an acceleration bound? Sufficient conditions will be given that imply that a potential function will be a navigation function that satisfies the bound.

To give the conditions, it will first be important to characterize extrema of multivariate functions. Recall from basic calculus that a function $f : {\mathbb{R}}\rightarrow {\mathbb{R}}$ has a critical point when the first derivative is zero. At such points, the sign of the second derivative indicates whether the critical point is a minimum or maximum. These ideas can be generalized to higher dimensions. A critical point of $\phi$ is one for which $\nabla \phi = 0$. The Hessian of $\phi$ is defined as the matrix

$$H(\phi) = \begin{pmatrix}\displaystyle\strut \frac{\partial^2 \ph... ...& \displaystyle\strut \frac{\partial^2 \phi}{\partial x_n^2} \end{pmatrix} .$$ (8.48)

At each critical point, the Hessian gives some information about the extremum. If the rank of $H(\phi)$ at $x$ is $n$, then the Hessian indicates the kind of extremum. If (8.48) is positive definite,^8.13 then the $\phi$ achieves a local minimum at $x$. If (8.48) is negative definite,^8.14 then the $\phi$ achieves a local maximum at $x$. In all other cases, $x$ is a saddle point. If the rank of $H(\phi)$ at $x$ is less than $n$, then the Hessian is degenerate. In this case the Hessian cannot classify the type of extremum. An example of this occurs when $x$ lies in a plateau (there is no direction in which $\phi$ increases or decreases. Such behavior is obviously bad for a potential function because the local operator would not be able to select a direction.

Suppose that the navigation function is required to be smooth, to ensure the existence of a gradient at every point. This enables gradient descent to be performed. If $X$ is not contractible, then it turns out there must exist some critical points other than ${x_{G}}$ at which $\nabla \phi(x) = 0$. The critical points can even be used to infer the topology of $X$, which is the basic idea in the subject of Morse theory [701,234]. Unfortunately, this implies that there does not exist a solution navigation function for such spaces because the definition in Section 8.4.1 required that the integral curve from any state that can reach ${x_{G}}$ must reach it using the vector field derived from the navigation function. If the initial state is a critical point, the integral curve is constant (the state remains at the critical point). Therefore, under the smoothness constraint, the definition of a navigation function should be modified to allow critical points at a small number of places (only on a set that has measure zero). It is furthermore required that the set of states from which the integral curves arrive at each critical point (i.e., the domain of attraction of each critical point) has measure zero. From all possible initial states, except from a set of measure zero, the integral curves must reach ${x_{G}}$, if it is reachable. This is ensured in the following definition.

A function $\phi : X \rightarrow {\mathbb{R}}$ is called a navigation function in the sense of Rimon-Koditschek if [829]:

1. It is smooth (or at least $C^2$).
2. Among all values on the connected component of ${\cal C}_{free}$ that contains ${x_{G}}$, there is only one local minimum, which is at ${x_{G}}$.^8.15
3. It is maximal and constant on $\partial{\cal C}_{free}$, the boundary of ${\cal C}_{free}$.
4. It is a Morse function [701], which means that at each critical point $x$ (i.e., $\nabla \phi \vert _x = 0$), the Hessian of $\phi$ is not degenerate.^8.16 Such functions are known to exist on any smooth manifold.

If $\phi$ is smooth in the $C^\infty$ sense, then by Sard's Theorem [234] the set of critical points has measure zero.

Methods for constructing navigation functions are outlined in [829] for a general family of problems in which ${\cal C}_{free}$ has a semi-algebraic description. The basic idea is to start with simple shapes over which a navigation function can be easily defined. One example of this is a spherical subset of ${\mathbb{R}}^n$, which contains spherical obstacles. A set of distorting transformations is then developed to adapt the navigation functions to other shapes while ensuring that the four properties above are maintained. One such transformation extends a ball into any visibility region (in the sense defined in Section 8.4.3). This is achieved by smoothly stretching out the ball into the shape of the visibility region. (Such regions are sometimes called star-shaped.) The transformations given in [829] can be combined to define navigation functions for a large family of configuration spaces. The main problem is that the configuration space obstacles and the connectivity of ${\cal C}_{free}$ are represented only implicitly, which makes it difficult to correctly apply the method to complicated high-dimensional problems. One of the advantages of the approach is that proving convergence to the goal is simplified. In many cases, Lyapunov stability analysis can be performed (see Section 15.1.1).