Frustumbug: a 3D Mapless Stereo-Vision-based Bug Algorithm for Micro Air Vehicles

More Info


We present a computationally cheap 3D bug algorithm for drones, using stereo vision. Obstacle avoidance is important, but difficult for robots with limited resources, such as drones. Stereo vision requires less weight and power than active distance measurement sensors, but typically has a limited Field of View (FoV). In addition, the stereo camera is fixed on the drone, preventing sensor movement. For obstacle avoidance, bug algorithms require few resources. We base our proposed algorithm, Frustumbug, on the Wedgebug algorithm, since this bug algorithm copes with a limited FoV. Since Wedgebug only focuses on 2D problems, the Local-epsilon-Tangent-Graph (LETG) is used to extend the path planning to 3D. Disparity images are obtained through an optimised stereo block matching algorithm. Obstacles are expanded in disparity space to obtain the configuration space. Furthermore, Frustumbug has an improved robustness to noisy range sensor data, and includes reversing, climbing and descending manoeuvres to avoid or escape local minima. The algorithm has been extensively tested with 225 flights in two challenging simulated environments, with a success rate of 96%. Here, 3.6% did not reach the goal and 0.4% collided. Frustumbug has been implemented on a 20 gram stereo vision system, and guides drones safely around obstacles in the real world, showing its potential for small drones to reach their targets fully autonomously.