Voronoi diagram and fast marching applied to path planning
Authors:
- S. GarridoS. Garrido
- L. MorenoLML. Moreno
- D. BlancoDBD. Blanco
- 10 July 2006
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 3049-3054
Abstract
This paper presents a new Path Planning method which operates in two steps. In the first step the safest areas in the environment are extracted by means of a Voronoi diagram. In the second step Fast Marching Method is applied to the Voronoi extracted areas in order to obtain the shortest path. In this way the trajectory obtained is the shortest between the safe possible ones. This two step method combines speed and reliability, because the map dimensions is reduced to a unidimensional map and this map represents the safest areas in the environment for moving the robot.Keywords
This publication has 9 references indexed in Scilit:
- A fast marching level set method for monotonically advancing fronts.Proceedings of the National Academy of Sciences, 1996
- Theory, algorithms, and applications of level set methods for propagating interfacesActa Numerica, 1996
- A Fast Level Set Method for Propagating InterfacesJournal of Computational Physics, 1995
- The Voronoi diagram of curved objects1995
- User’s guide to viscosity solutions of second order partial differential equationsBulletin of the American Mathematical Society, 1992
- Robot Motion Planning1991
- Fronts propagating with curvature-dependent speed: Algorithms based on Hamilton-Jacobi formulationsJournal of Computational Physics, 1988
- Viscosity Solutions of Hamilton-Jacobi EquationsTransactions of the American Mathematical Society, 1983
- Medial Axis Transformation of a Planar ShapeIEEE Transactions on Pattern Analysis and Machine Intelligence, 1982