A Fast & Efficient Mission Planner for Multi-rotor Aerial Vehicles in Large, High-resolution Maps of Cluttered Environments

Abstract

Autonomous multi-rotor aerial vehicles have many potential applications in urban environments, such as inspecting infrastructure, creating 3D maps from the air, or delivering packages. However this involves flying close to obstacles like trees and buildings, or flying under overhanging structures like bridges, powerlines and doorways. Flying safely in environments like this will require perception and planning with respect to a full 3D world model.

Recent work has demonstrated that multi-rotor UAVs can robustly localize to static point cloud maps of urban environments using LiDAR- and VO-based methods. However it is difficult to plan directly in large 3D maps due to the memory requirements and size of the state space. We investigate the problem of planning paths in large high-resolution point clouds, for missions that include flying around obstacles and under overhanging structures.

Our approach is to plan offline a complete global mission path in the static map, that is collision-free and satisfies altitude constraints. We use a random-sample based planning algorithm to find approximate shortest paths, with rejection-sampling to satisfy constraints. We also introduce a novel approach for avoiding obstacles that may appear on the mission path by pre-planning a network of alternative paths.

We present results showing a comparison of various path planning algorithms and choose BIT* because it finds the approximate shortest path in the fastest time. For planning alternative paths, we use geometric path primitives based on splines or revert to BIT*. We also compare various data structures for storing the 3D world representation and use a sparse Octree to store occupied voxels because it offers the best trade-off between storage memory and collision-checking speed. We present qualitative results showing the resulting mission paths for multiple environments, including an industrial site and a tree-filled area.