UAV fleet management for humanitarian operations

Unmanned Aerial Vehicles (UAVs) are experiencing increasing use in many applications and are expected to operate in Beyond Visual Line of Sight (BVLOS) conditions. Due to the volume of UAVs and types of aircraft expected to share the airspace, novel approaches for path planning are necessary to ensure their safe integration.

TSL has developed a bi-level fleet management heuristic for UAV operations that consists of two main components: a dynamic clustering algorithm and a path planning heuristic. The dynamic clustering procedure discretises the airspace into distinct segments considering traffic, weather and geography. This way, the number of conflicting vehicles and trajectories to consider during trajectory planning is reduced by limiting the analysis to obstacles within the cluster. Vehicles are given a location and approximate allowable time window to enter and/or exit a cluster that allows for modifications in their trajectories if required.

The trajectory planning heuristic creates UAV paths and modifies routing decisions based on the level of activity in an area, battery levels and demand requirements. A battery consumption minimisation is proposed whilst ensuring safety by maintaining minimum separation with other vehicles in accordance with PBN and RNP requirements.

A hybrid K-means Particle Swarm Optimisation (PSO) technique is utilised to create the airspace clusters considering projected demand. The K-means approach is used to produce an intial custlering, which is then modified by the PSO meta-heuristic by controlling its vertices.

The airspace clusters serve as inputs to the path planning algorithm to generate feasible flight trajectories. The procedure initially generates a general path based on a modified A* algorithm, where the path score is based on the number of cluster crossings, the workload at each cluster and the travel distance. Based on this initial corridor, a tree-based algorithm creates a detailed path sequentially as the UAV completes its travel.

Model Features

The developed models are tested based on the humanitarian operation in the aftermath of the 1999 Chi-Chi Earthquake and have shown to produce viable operational plans with reduced computational requirements. The next steps of the project is to obtain UAV trajectory data to further improve the path planning algorithms, and determine adequate safety requirements for humanitarian applications.