Exploratory Navigation based on 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 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 to 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 to be able to explore all the workspace. This method is very fast and reliable and the trajectories are smooth and not very close to obstacles and walls. In this article we propose its application to the exploration task of unknown environments.