Multi-Agent Path Finding for UAV Traffic Management

Unmanned aerial vehicles (UAVs) are expected to provide a wide range of services, whereby UAV fleets will be managed by several independent service providers in shared low-altitude airspace. One important element, or redundancy, for safe and efficient UAV operation is pre-flight Conflict Detection and Resolution (CDR) methods that generate conflict-free paths for UAVs before the actual flight. Multi-Agent Path Finding (MAPF) has already been successfully applied to comparable problems with ground robots. However, most MAPF methods were tested with simplifying assumptions which do not reflect important characteristics of many real-world domains, such as delivery by UAVs where heterogeneous agents need to be considered, and new requests for flight operations are received continuously. In this paper, we extend CBS and ECBS to efficiently incorporate heterogeneous agents with computational geometry and we reduce the search space with spatio-temporal pruning. Moreover, our work introduces a “batching” method into CBS and ECBS to address increased amounts of requests for delivery operations in an efficient manner. We compare the performance of our “batching” approach in terms of runtime and solution cost to a “first-come first-served” approach. Our scenarios are based on a study on UAV usage predicted for 2030 in a real area in Japan. Our simulations indicate that our proposed ECBS based “batching” approach is more time efficient than incremental planning based on Cooperative A*, and hence can meet the requirements of timely and accurate response on delivery requests to users of such UTM services.

Authors

• Florence Ho
• Ana Salta INESC-ID and Instituto Superior Tecnico, Universidade Lisboa
• Ruben Geraldes National Institute of Informatics
• Artur Goncalves National Institute of Informatics
• Marc Cavazza
• Helmut Prendinger National Institute of Informatics

Keywords

• Unmanned Aircraft System Traffic Management
• Pre-Flight Conflict Detection and Resolution
• Multi-Agent Path Finding
• Heterogeneous Agents