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.