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:
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.
Personal Autonomy Rehabilitation in Home Environments by a Portable Assistive Robot
IEEE Transactions on Systems, Man, and Cybernetics.. num. 2 , vol. 42 , pages: 561 – 570 , 2011
A. Jardon Juan G. Victores S. Martinez A. Gimenez
Task-Oriented Kinematic Design of a Symmetric Assistive Climbing Robot
Short paper, IEEE Transactions on Robotics. num. 6 , vol. 27 , pages: 1132 – 1137 , 2011
M.F. Stoelen F. Bonsignorio A. Jardon
Usability assessment of ASIBOT: a portable robot to aid patients with spinal cord injury
Disability & Rehabilitation: Assistive Technology. , pages: 1 – 11 , 2010
A. Jardon C.A. Monje A. Gil A. Peña
Metodología de diseño óptimo para la construcción de robots de servicio.
Anales de Ingeniería Mecánica, ESPAÑA.. num. 1 , vol. 2 , pages: 1041 – 1046 , 2008
A. Gimenez A. Jardon Rubio, H. García Prada, A. Castejón, C.
Robots applications against gravity
IEEE Robotics & Automation magazine. num. 1 , vol. 13 , pages: 5 – 6 , 2006

Entries:
A. I. de la Peña González, A. M. Gil Agudo, Functional Evaluation of ASIBOT, a Portable Robot to Aid Disabled Persons
In Proceedings II International Congress on Domotics, Robotics and Remote‐Assistance for All DRT4all 2007, 2007, Madrid, SPAIN
A. Jardon
Human-Robot Coexistence in Robot-Aided Apartment
The 23rd International Symposium on Automation and Robotics in Construction (ISARC 2006), Tokyo, Japan
R. Cabas R. Correal A. Gimenez S. Martinez A. Jardon
Asibot, robot de asistencia a discapacitados y personas mayores
drt4ALL. Congreso Internacional sobre Domótica, Robótica y Teleasistencia, Madrid, Spain
R. Cabas R. Correal A. Gimenez A. Jardon
A portable light-weight climbing robot for personal assistance applications
8th International Conference on Climbing and Walking Robots (Clawar'05). ?The Best Paper Award?, London, UK
R. Cabas R. Correal A. Gimenez A. Jardon
Live experimentation of the service robot applicationselderly people care in home environments
IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS'2005), Edmonton, Canada
R. Cabas R. Correal A. Gimenez A. Jardon
Service robot applications for elederly people care in home environments
2nd International workshop on advances in service robotics, Sttugart, Germany
R. Cabas R. Correal A. Gimenez A. Jardon
The MATS robotic system to assist disableb people in their home environments
Intl. Conference on Intelligent Robots and Systems, IROS'03, Las Vegas, USA
A. Gimenez
Light weight autonomous service robot for disable and elderly people help in their living environment
Procedings of the 11th International Conference on Advanced Robotics (ICAR 2003), Coimbra, Portugal
A. Gimenez A. Jardon
Light weight autonomous robot for elderly and disabled persons’ service
4th International Conference on Field and Service Robotics, Yamanashi, Japan
R. Cabas R. Correal A. Gimenez P. Staroverov A. Jardon
MATS: An assistive robotic climbing system for personal care & service applications
1st Internatinal Workshop on advances in service robotics, Bardolino, Italy
A. Gimenez A. Jardon

Entries:
M. Ferre, M. Buss, C. Melchiorri (Editors). Advances in Telerobotics
pages: 1 – 500. Springer Tracts in Advanced Robotics (STAR), vol. 31 , ISBN: 978-3-540-71363, 2007
ADVANCES IN TELEROBOTICS
chapter: Proprio & Teleoperation of a robotic system for disabled people assistance in domestic environments <a target="_blank" href="http://link.springer.com/chapter/10.1007/978-3-540-71364-7_25">[online]</a> pages: 325 – 338. Springer Tracts in Advanced Robotics (STAR), vol. 31 SPRINGER NETHERLANDS EDITORIAL , ISBN: 978-3-540-71363, 2007
R. Correal A. Gimenez S. Martinez A. Jardon
M. Ferre, M. Buss, C. Melchiorri. Advances in Telerobotics
chapter: Introduction to Advances in Telerobotics pages: 1 – 10. Springer Tracts in Advanced Robotics (STAR), vol. 31 , ISBN: 978-3-540-71363, 2007
CLIMBING AND WALKING ROBOTS
chapter: A PORTABLE LIGHT-WEIGHT CLIMBING ROBOT FOR PERSONAL ASSISTANCE APPLICATIONS pages: 961 – 968. CLAWAR 05 , ISBN: 978-3-540-26413, 2006
A. Gimenez A. Jardon

Entries:

Previous Research topics

next Research topics