Accession Number:

ADA247929

Title:

Searching for Shortest and Safest Paths Along Obstacle Common Tangents

Descriptive Note:

Master's thesis

Corporate Author:

NAVAL POSTGRADUATE SCHOOL MONTEREY CA

Personal Author(s):

• Crane, Jerry A.

Report Date:

1991-09-01

Pagination or Media Count:

196.0

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. 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.

Descriptors:

• *PATHS
• CONVEX BODIES
• GLOBAL
• OPTIMIZATION
• COMPUTATIONS
• PROCESSING
• ROBOTS
• ORIENTATION(DIRECTION)
• THESES
• SEQUENCES
• CONSTRUCTION
• GEOMETRIC FORMS
• PLANNING
• SEARCHING
• VISIBILITY
• BARRIERS
• SAFETY
• TANGENTS
• HEURISTIC METHODS
• POLYGONS
• CONCAVE BODIES
• ALGORITHMS
• CONTROL

Subject Categories:

• Cybernetics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE