The shortest path problem in the plane with obstacles
Subtitle: a graph modeling approach to producing finite search lists of homotopy classes
Contributors: Thornton, John R.
Publisher: Naval Postgraduate School; Available from the National Technical Information Service
Published: 1991
Place of publication: Monterey, Calif; Springfield, Va
Language: eng
Number of pages: 117
Description: 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.
Notes: Thesis advisor, John R. Thornton.

Thesis (M.S. in Applied Mathematics) Naval Postgraduate School, June 1991.

Bibliography: p. 116.