Frustumbug: a 3D mapless stereo-vision-based bug algorithm for Micro Air Vehicles

Obstacle avoidance is an important capability for flying robots. But for robots with limited resources, such as small drones this becomes particularly challenging. Bug algorithms have been proposed to solve path planning with only minimal resources. And stereo vision provides a rich description of the world for limited weight but typically has a limited Field of View (FoV) and is fixed to the drone frame to further reduce weight. Based on these, a computationally light 3D path-planning algorithm is proposed. The proposed algorithm is called Frustumbug and is based on the Wedgebug algorithm since this algorithm copes well with a limited FoV. Since Wedgebug only addresses 2D problems, the Local-ϵ-Tangent-Graph (LETG) is used to extend the path planning to 3D. Disparity images are obtained through an optimized stereo block matching algorithm. Frustumbug copes well with noisy range sensor data and includes 3D trajectories like reversing, climbing and descending maneuvers to avoid or escape local minima. The algorithm has been tested with 225 flights in two challenging simulated environments and achieved 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 was tested in the real world on a MAV. This shows the potential for small drones to reach their targets fully autonomously based on very limited resources.