An Efficient Snell's Law Method for Optimal-Path Planning across Multiple Two-Dimensional,Irregular,Homogeneous-Cost Regions

Abstract

We are exploring a new approach to high-level optimal-path planning when homogeneous irregularly shaped regions of a plane have different traversal costs per unit distance. It is based on the simple idea that optimal paths must be straight in homogeneous regions, and so those regions need not be subdivided for path planning. Our approach uses optics anal ogies, ray tracing, and Snell's Law and reduces the problem to an efficient graph search with a variety of pruning criteria. The time and space of our algorithm is O(V ²) in an intui tively average case, where V is the number of region vertices. In experiments in which space is held constant, an imple mentation of our algorithm was not only dramatically faster but also gave better cost solution paths than a representative implementation of the chief competing technique, grid-based wavefront propagation. This appears to be because of the quite different and considerably smaller search space required for our more intelligent algorithm.