The shortest path problem in the plane with obstacles: bounds on path lengths and shortest paths within homotopy classes.
Loading...
Authors
Cuerington, Andre' M.
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
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
Organization
Naval Postgraduate School
Identifiers
NPS Report Number
Sponsors
Funder
Format
109 p.;28 cm.
Citation
Distribution Statement
Approved for public release; distribution is unlimited.