The shortest path problem in the plane with obstacles: a graph modeling approach to producing finite search lists of homotopy classes
Jenkins, Kevin Dean
Thornton, John R.
Query, Kim A.S.
MetadataShow full item record
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.
RightsThis 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.
Showing items related by title, author, creator and subject.
The shortest path problem in the plane with obstacles: bounds on path lengths and shortest paths within homotopy classes. Cuerington, Andre' M. (Monterey, California. Naval Postgraduate School, 1991-06);The problem of finding the shortest path between two points in the plane containing obstacles is considered. The set of such paths is uncountably infinite, making an exhaustive search impossible. This difficulty is ...
Quek, Henry C. (Monterey, California. Naval Postgraduate School, 2000-03-01);Up till today, the Internet only provides best-effort service, where traffic is processed as quickly as possible, with no guarantee as to timeliness or actual delivery. As the Internet develops into a global commercial ...
Parker, Gary B. (Monterey, California. Naval Postgraduate School, 1992-09);Search of an unknown space by a physical agent (such as an autonomous vehicle) is unique in search as the customarily most important goal (to reduce the computation time required to obtain the shortest distance) is not as ...