Efficient Planning for High-Speed MAV Flight in Unknown Environments Using Online 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 outside of a local planning grid. This work 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 enabling the robot to accurately plan to locations no longer contained within a 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 memory-efficient sparse topological graph is created online from a time history of the robot's path and a geometric notion of visibility within the environment to search for 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.