Navigation function

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

Then a potential function ϕ ( x ) is called a (feasible) navigation function if

1. ϕ ( x ) = 0   ∀ x ∈ X g
2. ϕ ( x ) = ∞ if and only if no point in X g is reachable from x .
3. For every reachable state, x ∈ X ∖ X g , the local operator produces a state x ′ for which ϕ ( x ′ ) < ϕ ( x ) .

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

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

ϕ ( x t ) = min u t ∈ U ( x t ) { L ( x t , u t ) + ϕ ( f ( x t , u t ) ) }

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

1. ϕ ( x ) = 0   ∀ x ∈ X g
2. ϕ ( x ) = ∞ if and only if no point in X G is reachable from x .
3. For every reachable state, x ∈ X ∖ X G , the local operator produces a state x ′ for which ϕ ( x ′ ) < ϕ ( x ) .
4. ϕ ( x t ) = min u t ∈ U ( x t ) { L ( x t , u t ) + ϕ ( f ( x t , u t ) ) }

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 ) .