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 

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  be the state space of all possible configurations of a robot. Let  denote the goal region of the state space.

Then a potential function  is called a (feasible) navigation function if 
 
 if and only if no point in  is reachable from . 
For every reachable state, , the local operator produces a state  for which .

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 Functionss of locations.  Denoting the target position by , the Probabilistic navigation function is defined as:

where  is a predefined constant like in the classical navigation function, which ensures the Morse nature of the function.  is the distance to the target position , and  takes into account all obstacles, defined as 

where  is based on the probability for a collision at location . The probability for a collision is limited by a predetermined value , meaning:

and,

where  is  the probability to collide with the i-th obstacle. 
A map  is  said to be a probabilistic navigation function if it satisfies the following conditions:
 It is a navigation function.
 The probability for a collision is bounded by a predefined probability .

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 . Formalized as an optimal control problem, we can write

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

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

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

 
 if and only if no point in  is reachable from . 
For every reachable state, , the local operator produces a state  for which . 

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  and dynamics . In the field of reinforcement learning the cost is replaced by a reward function  and the dynamics by the transition probabilities .

See also 

Control Theory
Optimal Control
Robot Control
Motion Planning
Reinforcement Learning

References

Sources

External links
 NFsim: MATLAB Toolbox for motion planning using Navigation Functions.

Robot control