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.

Fleet management heuristic workflow

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.

Airspace modification 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.

Sequential trajectory optimisation

Model Features

Scalability

The techniques developed in this study have been applied to simulations large UAV fleets.

Demand Management

The model evaluates projected demand trends and structures the path planning algorithm accordingly.

Sequential Trajectory Design

Flight paths are reassessed during the flight to reduce processing requirements.

Hazard Isolation

The airspace clustering approach can be used to isolate no-fly zones and areas where weather precludes UAV operation.


Flight path testing

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.

Airspace managment results


Project Details

Team

Panagiotis Angeloudis   Supervisor
Washington Ochieng   Co-supervisor
Jose Escribano   Lead Researcher

Related Talks

(2019). Sequential Trajectory Optimisation Using Dynamic Airspace Sectorisation. Transportation Research Board 98th Annual Meeting (TRBAM 2019). PDF
(2018). Integrated Trajectory-Location-Routing for Rapid Humanitarian Deliveries using Unmanned Aerial Vehicles. 2018 Aviation Technology, Integration, and Operations Conference. DOI