Navigation function

Probabilistic navigation function

Probabilistic navigation function is an extension of the classical navigation function for static stochastic scenarios. The function is defined by permitted collision probability, which limits the risk during motion. The Minkowski sum used for in the classical definition is replaced with a convolution of the geometries and the Probability Density Functions of locations. Denoting the target position by ${\displaystyle x_d}$, the Probabilistic navigation function is defined as: ${\displaystyle \phi (x)=\frac{{\gamma }_d(x)}{{\left[{\gamma }_d^K(x)+\beta \left(x\right)\right]}^{\frac{1}{K}}}}$ where ${\displaystyle K}$ is a predefined constant like in the classical navigation function, which ensures the Morse nature of the function. ${\displaystyle {\gamma }_d(x)}$ is the distance to the target position ${\displaystyle ||x-x_d|{|}^2}$, and ${\displaystyle \beta \left(x\right)}$ takes into account all obstacles, defined as ${\displaystyle \beta \left(x\right)=\prod _{i=0}^{N_o}{\beta }_i\left(x\right)}$ where ${\displaystyle {\beta }_i(x)}$ is based on the probability for a collision at location ${\displaystyle x}$. The probability for a collision is limited by a predetermined value ${\displaystyle \mathrm{\Delta }}$, meaning: ${\displaystyle {\beta }_i(x)=\mathrm{\Delta }-p^i\left(x\right)}$ and, ${\displaystyle {\beta }_0(x)=-\mathrm{\Delta }+p^0\left(x\right)}$

where ${\displaystyle p^i(x)}$ is the probability to collide with the i-th obstacle. A map ${\displaystyle \phi }$ is said to be a probabilistic navigation function if it satisfies the following conditions:

1. It is a navigation function.
2. The probability for a collision is bounded by a predefined probability ${\displaystyle \mathrm{\Delta }}$.

Navigation Function in Optimal Control

While for certain applications, it suffices to have a feasible navigation function, in many cases it is desirable to have an optimal navigation function with respect to a given cost functional ${\displaystyle J}$. Formalized as an optimal control problem, we can write

${\displaystyle \text{minimize }J(x_{1:T},u_{1:T})=\underset{T}{\int }L(x_t,u_t,t)dt}$

${\displaystyle \text{subject to }\dot{x_t}=f(x_t,u_t)}$

whereby ${\displaystyle x}$ is the state, ${\displaystyle u}$ is the control to apply, ${\displaystyle L}$ is a cost at a certain state ${\displaystyle x}$ if we apply a control ${\displaystyle u}$, and ${\displaystyle f}$ models the transition dynamics of the system.

Applying Bellman's principle of optimality the optimal cost-to-go function is defined as

${\displaystyle {\displaystyle \varphi (x_t)=\underset{u_t\in U(x_t)}{min}\{L(x_t,u_t)+\varphi (f(x_t,u_t))\}}}$

Together with the above defined axioms we can define the optimal navigation function as

1. ${\displaystyle \varphi (x)=0\mathrm{\forall }x\in X_g}$
2. ${\displaystyle \varphi (x)=\mathrm{\infty }}$ if and only if no point in ${\displaystyle X_G}$ is reachable from ${\displaystyle x}$.
3. For every reachable state, ${\displaystyle x\in X\setminus X_G}$, the local operator produces a state ${\displaystyle x^{\prime }}$ for which ${\displaystyle \varphi (x^{\prime })<\varphi (x)}$.
4. ${\displaystyle {\displaystyle \varphi (x_t)=\underset{u_t\in U(x_t)}{min}\{L(x_t,u_t)+\varphi (f(x_t,u_t))\}}}$

Even if a navigation function is an example for reactive control, it can be utilized for optimal control problems as well which includes planning capabilities.

Stochastic Navigation Function

If we assume the transition dynamics of the system or the cost function as subjected to noise, we obtain a stochastic optimal control problem with a cost ${\displaystyle J(x_t,u_t)}$ and dynamics ${\displaystyle f}$. In the field of reinforcement learning the cost is replaced by a reward function ${\displaystyle R(x_t,u_t)}$ and the dynamics by the transition probabilities ${\displaystyle P(x_{t+1}|x_t,u_t)}$.