The Exact Euclidean Distance Transform: A New Algorithm for Universal Path Planning

Abstract

The Path-Planning problem is a basic issue in mobile robotics, in order to allow the robots to solve more complex tasks, for example, an exploration assignment in which the distance given by the planner is taken as a utility measure. Among the different proposed approaches, algorithms based on an exact cell decomposition of the environment are very popular. In this paper, we present a new algorithm for universal path planning in cell decomposition, using a raster scan method for computing the Exact Euclidean Distance Transform (EEDT) for each cell in the map. Our algorithm computes, for every cell in the map, the point sequence to the goal. For each sequence, the sub-goals are selected near to the vertices of the obstacles, reducing the total distance to the goal without post processing. At the end, we obtain a smooth path up to the goal without the need for post-processing. The paths are computed by visibility verification among the cells, exploiting the processing performed in the neighbouring cells.