PATH PLANNING AND NAVIGATION USING VORONOI DIAGRAM AND FAST MARCHING

A new Two Steps Voronoi Path Planning method is presented. 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 are reduced to almost an unidimensional map and this map represents the safest areas in the environment for moving the robot. The paper, also proposes an extended Voronoi Diagram using a new Voronoi Transform.