Oriented Visibility Graphs: Low-Complexity Planning in Real-Time Environments

Abstract

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