Approximate 3D Visibility Graphs


Micro aerial vehicles operating outdoors must be able to maneuver through both dense vegetation and across empty fields. Existing approaches do not exploit the nature of such an environment. We have designed an algorithm which plans rapidly through free space and is efficiently guided around obstacles. In this paper we present SPARTAN (Sparse Tangential Network) as an approach to create a sparsely connected graph across a tangential surface around obstacles. We find that SPARTAN can navigate a vehicle autonomously through an outdoor environment producing plans 172 times faster than the state of the art (RRT*). As a result SPARTAN can reliably deliver safe plans, with low latency, using the limited computational resources of a lightweight aerial vehicle.

Related Publications

Autonomous Exploration and Motion Planning for an Unmanned Aerial Vehicle Navigating Rivers
Stephen T. Nuske, Sanjiban Choudhury, Sezal Jain, Andrew D. Chambers, Luke Yoder, Sebastian Scherer, Lyle J. Chamberlain, Hugh Cover and Sanjiv Singh
CMU-RI-TR- Journal of Field Robotics June, 2015
Sparse Tangential Network (SPARTAN): Motion Planning for Micro Aerial Vehicles
Hugh Cover, Sanjiban Choudhury, Sebastian Scherer and Sanjiv Singh
International Conference on Robotics and Automation May, 2013