Exploration of a cluttered environment using Voronoi Transform and Fast Marching

The Extended Voronoi Transform and the Fast Marching Method combination provide potential maps for robot navigation in previously unexplored dynamic environments. The Extended Voronoi Transform of a binary image of the environment gives a grey scale that is darker near the obstacles and walls and lighter far from them. The Logarithm of the Extended Voronoi Transform imitates the repulsive electric potential from walls and obstacles. The method proposed, called Voronoi Fast Marching method, uses a Fast Marching technique on the Extended Voronoi Transform of the environment's image, provided by sensors, to determine a motion plan. The computational efficiency of the method lets the planner operate at high rate sensor frequencies. This avoids the need for collision avoidance algorithms. The robot is directed towards the most unexplored and free zones of the environment so as to be able to explore all the workspace. This method is very fast and reliable and the trajectories are similar to the human trajectories: smooth and not very close to obstacles and walls. In this article we propose its application to the task of exploring unknown environments. (C) 2008 Elsevier B.V. All rights reserved.