User:Helptry/Sandbox

A Navigation Functions are a special type of Potential field used to navigate agents in environments containing obstacles. In particular, Navigation Functions possess special properties, which are very advantageous for navigation purposes. They have been initially introduced by the work of Koditschek and Rimon for guiding a single agent towards a desired destination and in the meantime avoid collisions with all obstacles in the workspace, assuming that the world is initially known. Since their introduction, Navigation Functions have been greatly extended to centralized and decentralized multi-agent systems, to non-holonomic systems, systems under constraints, unknown worlds, as well as more general tasks, as for example connectivity maintenance.

World definition

In order to define the concept of a Navigation Function, it is first essential to define the sets on which it is defined and with respect to which its desirable properties are expressed.

Navigation function definition

A Navigation Function is a map which is

• Analytic ($C^{2}$ suffices)
• Admissible: assumes its maximal value uniformly on the free space boundary;
• Polar: has a unique local minimum (which is obviously the unique global minimum);
• Morse: all critical points are non-degenerate, i.e., have non-singular Hessian matrix.

The above properties have been listed in order of increasing strictness. Although, analyticity (or merely twice continuous differentiability instead, which is sufficient) constitutes a relatively demanding requirement, in practice it is not. This is coupled with the fact that the manifold on which a Navigation Function is defined does not need to be analytic either, as the definition demands. This requirement can be relaxed by allowing non-smoothnesses (i.e., corners of the domain).

Admissibility is a reasonable property which ensures safety by implying that no gradient system can escape the free space system and collide with obstacles. By using implicit obstacle functions whose support is the obstacle boundary and negative coset preimage the obstacle's interior, admissible analytic functions can be easily constructed.

Polarity is a demanding property which is related to the model world's geometry (not on the geometry of that world in which the system is initially posed, e.g. the configuration space, since the model world does not necessarily coincide with that world, usually it does not).

The most demanding from all properties is non-degeneracy, in other words the Morse property. Nonetheless, it has been proved that non-degeneracy is not the necessary property for navigation purposes. Instead, it is avoidance of full degeneracy.

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.

See also

• Potential field
• Feedback motion planning
• Control theory
• Robot control

References

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

Category:Robot control