The shortest path problem in the plane with obstacles: a graph modeling approach to producing finite search lists of homotopy classes
Loading...
Authors
Jenkins, Kevin Dean
Subjects
Path planning
Finding the shortest path in the plane with obstacles
Finding the shortest path in the plane with obstacles
Advisors
Thornton, John R.
Date of Issue
1991-06
Date
June 1991
Publisher
Monterey, California. Naval Postgraduate School
Language
en_US
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.
Type
Thesis
Description
Series/Report No
Department
Department of Mathematics
Organization
Naval Postgraduate School
Identifiers
NPS Report Number
Sponsors
Funder
Format
117 p.
Citation
Distribution Statement
Approved for public release; distribution is unlimited.
Rights
This publication is a work of the U.S. Government as defined in Title 17, United States Code, Section 101. Copyright protection is not available for this work in the United States.