Path Planning for Mobile Robot Navigation using Voronoi Diagram and Fast Marching Articles uri icon

publication date

  • April 2011

start page

  • 42

end page

  • 64


  • 1


  • 2

Electronic International Standard Serial Number (EISSN)

  • 2180-1312


  • URL: For navigation in complex environments, a robot need s to reach a compromise between the need for having efficient and optimized trajectories and t he need for reacting to unexpected events. This paper presents a new sensor-based Path Planner w hich results in a fast local or global motion planning able to incorporate the new obstacle information. In the first step the safest areas in the environment are extracted by means of a Vorono i Diagram. In the second step the Fast Marching Method is applied to the Voronoi extracted a reas in order to obtain the path. The method combines map-based and sensor-based planning o perations to provide a reliable motion plan, while it operates at the sensor frequency. The m ain characteristics are speed and reliability, since the map dimensions are reduced to an almost uni dimensional map and this map represents the safest areas in the environment for moving the robot. In addition, the Voronoi Diagram can be calculated in open areas, and with all kind of shaped obstacles, which allows to apply the proposed planning method in complex environments wher e other methods of planning based on Voronoi do not work.


  • Robotics and Industrial Informatics


  • voronoi diagram; path planning; fast marching