Navigation function

Navigation function usually refers to a function of position, velocity, acceleration and time which is used to plan robot trajectories through the environment. Generally, the goal of a navigation function is to create feasible, safe paths that avoid obstacles while allowing a robot to move from its starting configuration to its goal configuration.

Potential functions as navigation functions

A potential function. Imagine dropping a marble on the surface. It will avoid the three obstacles and eventually reach the goal position in the center.

Potential functions assume that the environment or work space is known. Obstacles are assigned a high potential value, and the goal position is assigned a low potential. To reach the goal position, a robot only needs to follow the negative gradient of the surface.

We can formalize this concept mathematically as following: Let $X$ be the state space of all possible configurations of a robot. Let $X_{g}\subset X$ denote the goal region of the state space.

Then a potential function $\phi (x)$ is called a (feasible) navigation function if

1. $\phi (x)=0\ \forall 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)$.

Probabilistic navigation function

Probabilistic navigation function is an extension of the classical NF for static stochastic scenarios. Such a function is defined by introducing an additional permitted collision probability, which limits the risks (to a set value) during motion. The Minkowski sum used for in the classical definition is replaced with their respective Probability Density Functions, that represent their locations’ uncertainties. The probability for a collision is therefore the convolution of the geometries and the Probability Density Functionss of their locations.

Denoting the target position by $x_{d}$, the NF is defined at a point $x\in \mathbb {C}$ as: ${\varphi }(x)={\frac {\gamma _{d}(x)}{{\left[{\gamma _{d}^{K}(x)+\beta \left(x\right)}\right]}^{\frac {1}{K}}}}$ where $K$ is a predefined constant, which ensures the Morse nature of the function. $\gamma _{d}(x)$ is the distance to the target position ${||x-{x_{d}}|{|^{2}}}$, and $\beta \left(x\right)$ accounts for all obstacles and is independent of the target position $x_{d}$.

The numerator is defined in such a way to attracted to the target position, while the denominator ensures obstacle avoidance. Considering a stochastic scenario, one would like to minimize the probability for a collision while maintaining the shortest path to the target. Defining, $\beta \left(x\right)=\prod \limits _{i=0}^{N_{o}}{{\beta _{i}}\left(x\right)}$ where $\beta _{i}(x)$ is based on the probability for a collision at location $x$ for the deterministic scenario, $\beta _{i}\left(x\right)$ is a function of the distance between $x$ and the obstacle's boundary).

Since the pairwise separation constraint between the obstacles makes the obstacles’ locations dependent, the function $\beta (x)$ is not a probability function. A threshold value for collision probability is set by replacing the obstacles' geometric edges with the edges of that probability region. In a deterministic scenario, $\varphi (x)$ decreases the distance between $x$ and the target position while avoiding the obstacles. In a stochastic scenario, the probability for a collision is limited by a predetermined value $\Delta$. In order to do so, one defines $\beta _{i}$ as a function that encloses the risk for a collision at $x$ : $\beta _{i}(x)=\Delta -p_{tot}^{i}\left(x\right)$ and, $\beta _{0}(x)=-\Delta +p_{tot}^{0}\left(x\right)$

Thus, $\beta _{i}$ and $\beta$ vanish on the extended boundaries of each obstacle defined by $R_{\Delta _{i}}$, where the maximal probability for a collision is $\Delta$. Note that $p_{tot}^{0}\left(x\right)$ refers to the external boundary, computed on the PDF of the robot. Moreover, $\beta _{i}$ is computed for each obstacle, while the PNF integrates these for all obstacles throughout the workspace.

A map $\varphi$ 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 $\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 $J$. Formalized as an optimal control problem, we can write

${\text{minimize }}J(x_{1:T},u_{1:T})=\int \limits _{T}L(x_{t},u_{t},t)dt$

${\text{subject to }}{\dot {x_{t}}}=f(x_{t},u_{t})$

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

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

$\displaystyle \phi (x_{t})=\min _{u_{t}\in U(x_{t})}{\Big \{}L(x_{t},u_{t})+\phi (f(x_{t},u_{t})){\Big \}}$

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

1. $\phi (x)=0\ \forall 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)$.
4. $\displaystyle \phi (x_{t})=\min _{u_{t}\in U(x_{t})}{\Big \{}L(x_{t},u_{t})+\phi (f(x_{t},u_{t})){\Big \}}$

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 $J(x_{t},u_{t})$ and dynamics $f$. In the field of reinforcement learning the cost is replaced by a reward function $R(x_{t},u_{t})$ and the dynamics by the transition probabilities $P(x_{t+1}|x_{t},u_{t})$.

See also

• Control Theory
• Optimal Control
• Robot Control
• Motion Planning
• Reinforcement Learning

References

Sources

• LaValle, Steven M. (2006), Planning Algorithms (First ed.), Cambridge University Press, ISBN 978-0-521-86205-9
• Laumond, Jean-Paul (1998), Robot Motion Planning and Control (First ed.), Springer, ISBN 3-540-76219-1

External links

• NFsim: MATLAB Toolbox for motion planning using Navigation Functions.