Navigation algorithm for a nested hierarchical system of robot path planning among polyhedral obstacles

Abstract

An algorithm NAVIGATOR for robot path planning in a 2D world with polygonal obstacles is presented. The method employs A* search in a subset of the visibility graph of obstacle vertices. A procedure is given for finding this subset of the visibility graph without computing line intersections. The NAVIGATOR module is part of a complete hierarchical system for control and world representation for a robot which operates in an unkown and unstructured environment.