Efficient Planning for High-Speed MAV Flight in Unknown Environments Using Sparse Topological Graphs

Abstract

Safe high-speed autonomous navigation for MAVs in unknown environments requires fast planning to enable the robot to adapt and react quickly to incoming information about obstacles within the world. Furthermore, when operating in environments not known a priori, the robot may make decisions that lead to dead ends, necessitating global replanning through a map of the environment. Many state-of-the-art approaches are limited to reduced velocities---precluding their usage in time-critical applications such as search and rescue---while those that do allow for high-speeds are myopic, restricting their success in large-scale, complex environments that require reasoning about the world outside of a local planning grid. This thesis proposes a computationally efficient planning architecture for safe high-speed operation in unknown environments that incorporates a notion of longer-term memory into the planner to enable the robot to accurately plan to locations no longer contained within the local map. A motion primitive based local receding horizon planner that uses a probabilistic collision avoidance methodology enables the robot to generate safe plans at fast replan rates. To provide global guidance, a sparse topological graph is created online from a time history of the robot's path and a notion of visibility within the environment that may be searched to find alternate pathways towards the desired goal if a dead end is encountered. The safety and performance of the proposed planning system is evaluated at speeds up to 10m/s, and the approach is tested in a set of large-scale, complex simulation environments containing dead ends. These scenarios lead to failure cases for competing methods; however, the proposed approach enables the robot to safely reroute and reach the desired goal.