Searching for Shortest and Safest Paths Along Obstacle Common Tangents
Crane, Jerry Allen
MetadataShow full item record
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.
Approved for public release; distribution is unlimited
Showing items related by title, author, creator and subject.
Caldwell, James F., Jr. (1987-09);A moving target is detected at long range with an initial position given by a probability distribution on a grid of N cells. Also located on the grid is a searcher, constrained by speed, who must find an optimal search ...
Virgili-Llop, Josep; Costantinos Zagaris; Zappulla, Richard II; Bradstree, Andrew; Romano, Marcello (2017-02);This paper presents a convex optimization-based guidance algorithm for maneuvering a spacecraft equipped with a robotic manipulator. A local solution to the original optimization problem is found by solving a collection ...
Lee, Steve H. K. (Monterey, California. Naval Postgraduate School, 1995-09);A model is designed and implemented to construct a 'flyable,' least- risk route for strike aircraft from takeoff to target, through enemy radars, in a defined area of operations. A network is fust constructed by ...