Fast Marching

base_f

Description

Introduction to Fast Marching

The FM algorithm was introduced by J. Sethian in 1996 and is a numerical algorithm that approximates the viscosity solution of the Eikonal equation which represents, among other,
The FM method is used to solve the Eikonal equation and is very similar to the Dijkstra algorithm that finds the shortest paths on graphs, though it is applied to continuous media.

Fast Marching and Motion Planning

To get a Motion Planner for mobile robots with desirable
properties, such as smoothness and safety, we can think of
attractive potentials. In Nature, there are phenomena with a
similar behaviour, e.g., the electromagnetic waves. If there
is an antenna in the goal point that emits an electromagnetic
wave, then the robot can drive to the destination by tracing
the waves back to the source. In general, the concept of
electromagnetic waves is especially interesting, since the potential and its associated vector field have the good properties
desired for the trajectory, such as smoothness and the absence
of local minima.

This attractive potential still has some problems. The most
important one that typically arises in mobile robotics, is
that optimal motion plans may bring robots too close to
obstacles or people, which is not safe. To obtain a safe
path, it is necessary to add a component that repels the robot
from obstacles. In addition, this repulsive potential and its
associated vector field should have good properties such as
those of electrical fields. If we consider that the robot has
an electrical charge of the same sign as obstacles, then the
robot would be pushed away from obstacles. The properties
of this electric field are very good because it is smooth and
there are no singular points in the interest space.



To help understand the Fast Marching Path Planning basis method, let us suppose a two dimensional wave propagating in a homogeneous medium. The front wave is then a circle propagating outwards the initial point. If an additional axis is added to represent the time, the results is as shown in the next figure:

Now, if the initial point of the wave propagation are all those points which represents obstacles in a binary occupancy map, we obtain a map in which the value for each cell is proportional to the distance to the nearest obstacle, as shown in the next figures:


An the path obtained over this new “distances” map, applying the gradient method is:

FM2: Fast Marching Square

The path obtained applying Fast Marching directly is non-smooth and runs too close to obstacles, being not safe at all. The solution we propose is to use the “distances” map obtained applying Fast Marching as a slowness map. This means that the lower is the value for a given cell the closer it is to an obstacle (or wall) thus the velocity has to be slower.

Then, a wave is propagating from the goal point until it reaches the current position of the robot. For this propagation, the velocity of the wave for each cell is proportional to the value of the slowness map for that cell. Then it is obtained a map in which each cell has a value for the time the wave lasts to reach that cell. This map will never have local minima, since the velocity of the wave is always non negative.

The map with the time values applying Fast Marching over the previous slowness map is:

And applying the gradient method from the goal point to the initial point the path obtained is:

The result is a path much more smooth, safer and optimal in time.

We already proposed other alternatives such as Voronoi Fast Marching. Please, see the publications list below to find more information.

FM Applications

This proposed path planning has been applied successfully to:

– 2D and 3D path planning.
– Exploration and SLAM.
– Robot formations.
– Outdoor path planning.

Entries:
High-Accuracy Global Localization Filter for Three-Dimensional Environments
Robotica, http://dx.doi.org/10.1017/S0263574711000701. num. 3 , vol. 30 , pages: 363 – 378 , 2012
F. Martín S. Garrido D. Blanco L. Moreno
Diseño y simulación de un actuador de rigidez variable
Anales de Ingeniería Mecánica: Revista de la Asociación Española de Ingeniería Mecánica; ISSN: 0212-5072. num. 18 , vol. 1 , pages: 154 – 161 , 2012
A. Gimenez A. Jardon López, J. García, D.
Compact modeling technique for outdoor navigation
IEEE Transactions on Systems, Man, and Cybernetics-Part A (ISSN: 1083-4427). num. 1 , vol. 38 , pages: 9 – 24 , 2008
D. Blanco L. Moreno
Desarrollo de un sistema de percepción de una plataforma móvil para entornos exteriores
Revista Iberoamerica de Ingeniería Mecánica (ISSN : 1137-2729). num. 3 , vol. 8 , pages: 3 – 23 , 2004
D. Blanco L. Moreno

Entries:
Topographical analysis for Voronoi-based modelling
28th Annual Conference of the IEEE Industrial Electronics SocietyIECON 2002, 2002, Seville, Spain
L. Moreno
Voronoi Extraction of Free-way Areas in Cluttered Environments
2005 IEEE/RSJ Int. Conf. on Intelligent Robots and Systems (IROS2005), Edmonton, Canada
D. Blanco L. Moreno
Traversability analysis technics in outdoor environments: a comparative study.
11th International Conference on Advanced Robotics, ICAR 2003, 2003, Coimbra, Portugal
D. Blanco L. Moreno
Traversable regions model for outdoor robots.
11th International Conference on Advanced Robotics, ICAR 2003 , 2003, Coimbra, Portugal
D. Blanco L. Moreno
Estimación de Suelos Navegables para Interiores
11th Workshop Robocity 2030: Robots personales y asistenciales, 2013, Madrid, Spain
J.V. Gomez D. Alvarez L. Moreno
Localization in 3D Environments Using DifferentialEvolution
2009 IEEE International Symposium on Intelligent Signal Processing (WISP'2009), Budapest, Hungary
F. Martín S. Garrido D. Blanco L. Moreno
Accelerated Localization in Noisy 3D Environments usingDifferential Evolution
The 2010 International Conference on Genetic and Evolutionary Methods, Las Vegas, USA
C. G.Uzcategui F. Martín D. Blanco L. Moreno
Differential Evolution approach to the grid-based Localization and Mapping problem
2007 IEEE International Conference on Intelligent Robots and Systems (IROS'2007), California, USA
F. Martín S. Garrido L. Moreno
L1-norm global localization based on a Differential Evolution Filter
2009 IEEE International Symposium on Intelligent Signal Processing (WISP'2009), Budapest, Hungary
M.L. Muñoz F. Martín S. Garrido D. Blanco L. Moreno
Modelado de zonas cruzables para la navegación segura de robots en entornos exteriores
2º Workshop de RoboCity 2030, Robot de exteriores, 2007, Ávila, España
D. Blanco L. Moreno
Evolutionary Filter for Mobile Robot Global Localization
2007 IEEE International Symposium on Intelligent Signal Processing (WISP'2007), 2007, Alcala Henares, Spain
F. Martín S. Garrido L. Moreno
E-SLAM solution to the grid-based Localization and Mapping problem
2007 IEEE International Symposium on Intelligent Signal Processing (WISP'2007), 2007, Alcala Henares, Spain
F. Martín S. Garrido L. Moreno
Rh-0 Humanoid Robot Bipedal Locomotion and Navigation Using Lie Groups and Geometric Algorithms
International Conference on Intelligent Robots and Systems (IROS'2005), Edmonton, Canada
J. M. Pardos-Gotor

Entries:
Innovations in Robot Mobility and Control
chapter: Voronoi-based outdoor traversable region modelling pages: 201 – 250. Springer-Verlag , ISBN: 3-540-26892-8, 2005
D. Blanco L. Moreno

Previous Research topics

next Research topics