Using Path Transforms to Guide the Search for Findpath in 2D

Abstract

This article will present a new approach to the 2D findpath problem for robots that have three degrees of freedom of move ment (3 DOF). This approach is based on a new extension to distance transform planning called the path transform. Path transforms have the desirable potential field property of taking into account clearance from obstacles without suffering the problem of local minima. Because path transforms guide the search for a 3-DOF path where solution paths are likely to lie, the computational burden of the new approach is low compared with that in previously reported results. The low computational burden is also due to efficient collision detection. A new hier archical collision checking based on distance space bubbles is presented. The new approach to findpath is guaranteed to find a solution path if it exists. Computer simulation results of solving the findpath problem in nontrivial environments are presented.