Oriented visibility graphs: low-complexity planning in real-time environments

Abstract

(c) 2006 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other users, including reprinting/ republishing this material for advertising or promotional purposes, creating new collective works for resale or redistribution to servers or lists, or reuse of any copyrighted components of this work in other works.Digital Object Identifier : 10.1109/ROBOT.2006.1642054We show how the introduction of a fixed goal location allows us to lower complexity compared to reduced visibility graphs. The number of inter-polygonal edges is decreased from as much as square to not more than simply twice the number of polygons. By virtue of this restriction, we demonstrate how to deploy plan-based navigation strategies in highly unstructured, dynamic environments. This approach has been exercised extensively through numerous outdoor experiments. The vehicle used was the DARPA LAGR robot, and the various test environments included trees, ditches, bushes, tall and short grass, closed canopy, and varyingly-sloped terrain