Searching for Shortest and Safest Paths Along Obstacle Common Tangents
Loading...
Authors
Crane, Jerry Allen
Subjects
Advisors
Kanayama, Yutaka
Date of Issue
1991-09
Date
September 1991
Publisher
Monterey, California. Naval Postgraduate School
Language
en_US
Abstract
This thesis describes a method for computing globally shortest paths for a point robot in a two-dimensional, orthogonal world composed of convex and concave polygons through the construction of obstacle common tangent visibility graphs. Visibility and intersection testing are based on the orientation of three or more points in the plane, and complex obstacle tangent visibility graphs are constructed using only these orientation relationships. Obstacle common tangents for convex and concave polygonal obstacles are implemented as a computational representation of locally shortest paths. A series of tangent sequences form global paths which equate to global path equivalence classes, effectively reducing the path finding problem to that of finding the shortest path in the path equivalence class. A simple and logical approach for processing concave polygons using convex subpolygons is implemented, allowing common tangent construction and path searching algorithms to process complex geometrical shapes in an efficient and symbolically unique fashion. Dijkstra's algorithm is implemented using heuristic control for optimal path searching. The framework for utilizing constant clearance strips for safe path planning along obstacle common tangents is presented but not fully implemented.
Type
Thesis
Description
Series/Report No
Department
Organization
Naval Postgraduate School (U.S.)
Identifiers
NPS Report Number
Sponsors
Funder
Format
189 p.;28 cm.
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.