Navigation functions

Consider a (discrete) potential function, defined as $\phi : X \rightarrow [0,\infty]$. The potential function can be used to define a feedback plan through the use of a local operator, which is a function that selects the action that reduces the potential as much as possible. First, consider the case of a feasible planning problem. The potential function, $\phi$, defines a feedback plan by selecting $u$ through the local operator,

$$u^* = \operatornamewithlimits{argmin}_{u \in U(x)} \Big\{ \phi(f(x,u)) \Big\} ,$$ (8.4)

which means that $u^* \in U(x)$ is chosen to reduce $\phi$ as much as possible. The local operator yields a kind of greedy descent of the potential. Note that the action $u^*$ may not be unique. In the continuous-space analog to this, the corresponding local operator performs a descent along the negative gradient (often referred to as gradient descent).

In the case of optimal planning, the local operator is defined as

$$u^* = \operatornamewithlimits{argmin}_{u \in U(x)} \Big\{ l(x,u) + \phi(f(x,u)) \Big\} ,$$ (8.5)

which looks similar to the dynamic programming condition, (2.19). It becomes identical to (2.19) if $\phi$ is interpreted as the optimal cost-to-go. A simplification of (8.5) can be made if the planning problem is isotropic, which means that the cost is the same in every direction: $l(x,u) = l(x,u')$ for all $u,u' \in U(x) \setminus \{u_T\}$. In this case, the cost term $l(x,u)$ does not affect the minimization in (8.5). A common example in which this assumption applies is if the cost functional counts the number of stages required to reach the goal. The costs of particular actions chosen along the way are not important. Using the isotropic property, (8.5) simplifies back to (8.4).

When is a potential function useful? Many useless potential functions can be defined that fail to reach the goal, or cause states to cycle indefinitely, and so on. The most desirable potential function is one that for any initial state causes arrival in ${X_{G}}$, if it is reachable. This requires only a few simple properties. A potential function that satisfies these will be called a navigation function.^8.2

Suppose that the cost functional is isotropic. Let $x' = f(x,u^*)$, which is the state reached after applying the action $u^* \in U(x)$ that was selected by (8.4). A potential function, $\phi$, is called a (feasible) navigation function if

1. $\phi(x) = 0$ for all $x \in {X_{G}}$.
2. $\phi(x) = \infty$ if and only if no point in ${X_{G}}$ is reachable from $x$.
3. For every reachable state, $x \in X \setminus {X_{G}}$, the local operator produces a state $x'$ for which $\phi(x') < \phi(x)$.

The first condition requires the goal to have zero potential (this condition is actually not necessary but is included for convenience). The second condition requires that $\infty$ serves as a special indicator that the goal is not reachable from some state. The third condition means that the potential function has no local minima except at the goal. This means that the execution of the resulting feedback plan will progress without cycling and the goal region will eventually be reached.

An optimal navigation function is defined as the optimal cost-to-go, $G^*$. This means that in addition to the three properties above, the navigation function must also satisfy the principle of optimality:

$$\phi(x) = \min_{u \in U(x)} \Big\{ l(x,u) + \phi(f(x,u)) \Big\} ,$$ (8.6)

which is just (2.18) with $G^*$ replaced by $\phi$. See Section 15.2.1 for more on this connection.

Figure 8.3: The cost-to-go values serve as a navigation function.

Example 8..2 (Navigation Function on a 2D Grid)   Return to the planning problem in Example 8.1. Assume that an isotropic cost model is used: $l(x,u) = 1$ if $u \not = u_T$. Figure 8.3 shows a navigation function. The numbers shown in the tiles represent $\phi$. Verify that $\phi$ satisfies the three requirements for a navigation function.

At any state, an action is applied that reduces the potential value. This corresponds to selecting the action using (8.4). The process may be repeated from any state until ${X_{G}}$ is reached. This example clearly illustrates how a navigation function can be used as an alternative definition of a feedback plan. $\blacksquare$

Example 8..3 (Airport Terminal)   You may have found yourself using a navigation function to find the exit after arriving in an unfamiliar airport terminal. Many terminals are tree-structured, with increasing gate numbers as the distance to the terminal exit increases. If you wish to leave the terminal, you should normally walk toward the lower numbered gates. $\blacksquare$