Fast Marching Method: Theoretical Underpinnings and Applications to Robotics
September 22, Nice, France
Waves in the ocean and flames in the fireplace are two examples of dynamic boundaries in the nature. Some familiar problems in robotics, e.g. optimal path planning and visibility problems, can also be cast in the setting of evolving boundaries. We can use the Level Set Method to track such evolving interfaces. If the evolving interfaces always move forward, an efficient and accurate numerical scheme called Fast Marching Method (FMM) can be employed to efficiently track the interfaces by computing solutions to the non-linear Eikonal equation and related static Hamilton-Jacobi equations.
It is known that the FMM treats the underlying continuous domains more accurately compared with the standard discrete search techniques such as Dijkstra's algorithm commonly employed in path planning/robotics. While wavefront propagation based on potential field has been used in robot path planning, fast marching based on Eikonal equation provides more generalized (in that it can incorporate variety of costs including those based on velocity) and principled (solution to Eikonal equation) approach. The FMM's low computational cost (in order of O(N logN), where N is the total number of points in the domain) makes it applicable for real-time applications.
The objective of this tutorial is to introduce the theoretical and numerical underpinnings of the Fast Marching Method to the researchers in the field of robotics, and demonstrate its applications in some different areas in robotics.
Recent Updates
[2008-OCT-25] Program updated (with Dr. Clement Petres' slides)
[2008-OCT-10] Program updated (with slides & videos)
[2008-SEP-10] Program updated (with schedule)
[2008-JUL-10] Program added
[2008-JUN-12] New speaker: Dr. Roland Philippsen
[2008-JUN-12] New tool: E* Interpolated Graph Replanner
[2008-MAY-12] Organization tab added
[2008-MAY-01] Preliminary website up