Metalevel Motion Planning for Unmanned Aircraft Systems: Metrics Definition and Algorithm Selection

Abstract

A diverse suite of manned and unmanned aircraft will occupy future urban airspace. Flight plans must accommodate specific aircraft characteristics, including physical volume with safety zone clearance, landing/takeoff procedures, kinodynamics, and a wide range of flight environments. No single motion planner is applicable across all possible aircraft configurations and operating conditions. This dissertation proposes the first motion planning algorithm selection capability with application to small Unmanned Aircraft System (UAS) multicopters operating in and over a complex urban landscape.

Alternative data-driven fail-safe protocols are presented to improve on contemporary ``fly-home'' or automatic landing protocols, focusing on rooftops as safe urban landing sites. In a fail-safe direct strategy, the multicopter identifies, generates, and follows a flight plan to the closest available rooftop suitable for landing. In a fail-safe supervisory strategy, the multicopter examines rooftops en route to a planned landing site, diverting to a closer, clear landing site when possible. In a fail-safe coverage strategy, the multicopter cannot preplan a safe landing site due to missing data. The multicopter executes a coverage path to explore the area and evaluate overflown rooftops to find a safe landing site. These three fail-safe algorithms integrate map generation, flight planning, and area coverage capabilities.

The motion planning algorithm selection problem (ASP) requires qualitative and quantitative metrics to inform the ASP of user/agent, algorithm, and configuration space preferences and constraints. Urban flight map-based, path-based, and software-based cost metrics are defined to provide insights into the urban canyon properties needed to construct safe and efficient flight plans. Map-based metrics describe the operating environment by constructing a collection of GPS/Lidar navigation performance, population density, and obstacle risk exposure metric maps. Path-based metrics account for a vehicle's energy consumption and distance traveled. Software-based metrics measure memory consumption and execution time of an algorithm. The proposed metrics provide pre-flight insights typically ignored by obstacle-only planning environment definitions.

An algorithm portfolio consisting of geometric (Point-to-Point: PTP), graph-based (A* variants), and sampling-based (BIT* variants) motion planners were considered in this work. Path cost, execution time, and success rate benchmarks were investigated using Monte Carlo problem instances with A* "plus" producing the lowest cost paths, PTP having the fastest executions, and A* "dist" having the best overall success rates. The BIT* variant paths typically had higher cost but their success rate increased relative to altitude. The problem instances and metric maps informed two new machine learning solutions for urban small UAS motion planning ASP. Rule-based decision trees were simple to construct but unable to capture both complex cost metrics and algorithm properties. The investigated neural network-based ASP formulations produced promising results, with a hybrid two-stage selection scheme having the best algorithm selection accuracy, laying the seeds for future work.

The most significant innovation of this dissertation is motion planning ASP for UAS. Non-traditional open-source databases also advance the field of data-driven flight planning, contributing to fail-safe UAS operations as well as ASP. Path planning algorithms integrated a new suite of diverse cost metrics accompanied by a novel multi-objective admissible heuristic function. Neural network and decision tree ASP options were presented and evaluated as a first-case practical approach to solving the motion planning ASP for small UAS urban flight.