Minimum turns/shortest path problems: a framed-subspace approach

Abstract

The optimality of paths for motion planning is often judged purely on the lengths of the paths computed using an L/sub m/ metric. There are a number of other optimality criteria which are just as important, if not more so, for certain applications. In particular, determining paths of minimum turns is a very important problem in the area of robotic motion planning as well as VLSI design and IC layout. In this paper, we present efficient algorithms for finding the minimum turn paths, the minimum turn shortest paths, the shortest minimum turn paths, and the minimum cost paths. Our approach is based on propagating an artificial path planning wave through an environment represented by a framed-quadtree.