The Exact Euclidean Distance Transform: A New Algorithm for Universal Path Planning. (7th June 2013)

• Record Type: Journal Article
• Authors: Elizondo-Leal, Juan Carlos; Parra-González, Ezra Federico; Ramírez-Torres, José Gabriel
• Is Part Of: International journal of advanced robotic systems. Volume 10:Number 6(2013)
• Publication Date: 2013-06-07
• Subjects: Path Planning -- Cell Decomposition -- Distance Transform; Robotics -- Periodicals; Robotics; Periodicals; 629.892
• DOI: 10.5772/56581
• Languages: English
• ISSNs: 1729-8806

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.