DID YOU KNOW? DTIC has over 3.5 million final reports on DoD funded research, development, test, and evaluation activities available to our registered users. Click HERE
to register or log in.
Searching for Shortest and Safest Paths Along Obstacle Common Tangents
NAVAL POSTGRADUATE SCHOOL MONTEREY CA
Pagination or Media Count:
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. Dijkstras 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.
APPROVED FOR PUBLIC RELEASE