Orientation-Aware Hierarchical, Adaptive-Resolution A* Algorithm for UAV Trajectory Planning

Abstract

Successful path planning for Unmanned Aerial Vehicles (UAVs) in challenging environments with narrow openings, such as disaster areas, requires attitude to be considered. State-of-the-art methods incorporate attitude only in the refinement stage. We introduce a first-of-a-kind global minimum cost path search method based on A* that considers attitude along the path. To make the problem tractable, our method exploits an adaptive and coarse-to-fine approach using global and local A* runs, plus an efficient method to introduce the UAV attitude in the process. We integrate our method with an SE(3) trajectory optimisation method based on a safe-flight-corridor, yielding a complete path planning pipeline. Extensive evaluation is undertaken using the AirSim flight simulator under closed loop control in a set of randomised maps, allowing us to quantitatively assess our method. We show that it achieves significantly higher success rates than the baselines, at a reduced computational burden.