Publication:
The shortest path problem in the plane with obstacles: bounds on path lengths and shortest paths within homotopy classes.

Loading...
Thumbnail Image
Authors
Cuerington, Andre' M.
Subjects
Path Planning
Finding the Shortest Path in the Plane With Obstacles
Advisors
Thornton, John R.
Date of Issue
1991-06
Date
Publisher
Monterey, California. Naval Postgraduate School
Language
en_US
Abstract
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 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, we obtain a finite list of such classes whose union contains the shortest path. This process of simplification is discussed in the thesis of CAPT Kevin D. Jenkins, U.S. Marine Corps. In this thesis we first discuss a computational investigation of two methods by which homotopy classes can be named. Next, a computational heuristic is presented that finds the lower bound for a path in a class. Finally, the true shortest path is found by searching these classes in order of increasing lower bound. One application of this study is in the area of robotic path planning.
Type
Thesis
Description
Series/Report No
Department
Applied Mathematics
Other Units
Naval Postgraduate School
Identifiers
NPS Report Number
Sponsors
Funder
Format
109 p.;28 cm.
Citation
Distribution Statement
Approved for public release; distribution is unlimited.
Rights
Collections