Exploration of 2D and 3D Environments using Voronoi Transform and Fast Marching Method Articles uri icon

publication date

  • October 2009

start page

  • 55

end page

  • 86


  • 1


  • 55

International Standard Serial Number (ISSN)

  • 0921-0296

Electronic International Standard Serial Number (EISSN)

  • 1573-0409


  • Robot navigation in unknown environments requires an efficient exploration method. Exploration involves not only to determine towards the robot must to move but also motion planning, and simultaneous localization and mapping processes. The final goal of the exploration task is to build a map of the environment that previously the robot didn't know. This work proposes the Voronoi Fast Marching method, that uses a Fast Marching technique on the Logarithm of the Extended Voronoi Transform of the environment's image provided by sensors, to determine a motion plan. The Logarithm of the Extended Voronoi Transform imitates the repulsive electric potential from walls and obstacles, and the Fast Marching Method propagates a wave over that potential map. The trajectory is calculated by the gradient method. The robot is directed towards the most unexplored and free zones of the environment so as to be able to explore all the workspace. Finally, to build the environment map while the robot is carrying out the exploration task, a SLAM (Simultaneous Localization and Modelling)algorithm is implemented, the Evolutive Localization Filter (ELF) based on a differential evolution technique. The combination of these methods provide a new autonomous exploration strategy to construct consistent maps of 2D and 3D indoor environments.