The shortest path problem in the plane with obstacles: a graph modeling approach to producing finite search lists of homotopy classes

Abstract

The problem of finding the shortest path between two points in a plane containing obstacles is considered. The set of such paths is uncountably infinite, making an exhaustive search impossible. This difficulty is overcome by reducing the size of the search space. The search is first restricted to a countably infinite set by focusing attention on the set of homotopy classes. By applying simple optimality principles, a finite list of such classes is obtained whose union contains the shortest path. This process of simplification is accomplished by modeling the topology of the region with a graph. Optimality principles come into play during a graph traversal which is used to produce the finite search list. In addition, a computational investigation of two methods by which homotopy classes can be named is discussed, and properties of the graph models are investigated. The thesis of CPT Andre M. Cuerington, U.S. Army, calculates the actual shortest path using the search list produced here.