Skip navigation

Multi-agent path finding for UAV traffic management: Robotics track

Multi-agent path finding for UAV traffic management: Robotics track

Ho, Florence, Goncalves, Artur, Salta, Ana, Cavazza, Marc ORCID: 0000-0001-6113-9696, Geraldes, Ruben and Prendinger, Helmut (2019) Multi-agent path finding for UAV traffic management: Robotics track. In: Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems (AAMAS 2019). Association for Computing Machinery (ACM), pp. 131-139. ISBN 978-1-4503-6309-9 ISSN 2523-5699

[img] PDF (Author Accepted Manuscript)
23434 CAVAZZA_Multi-Agent_Path_Finding_for_UAV_Traffic_Management_2019.pdf - Accepted Version
Restricted to Registered users only

Download (1MB) | Request a copy

Abstract

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.

Item Type: Conference Proceedings
Title of Proceedings: Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems (AAMAS 2019)
Additional Information: Conference held at Montreal, Canada, May 13-17, 2019.
Uncontrolled Keywords: Unmanned Aircraft System Traffic Management; Pre-Flight Conflict Detection and Resolution; Multi-Agent Path Finding; Heterogeneous Agents
Subjects: Q Science > QA Mathematics > QA75 Electronic computers. Computer science
Faculty / Department / Research Group: Faculty of Architecture, Computing & Humanities
Faculty of Architecture, Computing & Humanities > Department of Computing & Information Systems
Last Modified: 31 May 2019 11:02
Selected for GREAT 2016: None
Selected for GREAT 2017: None
Selected for GREAT 2018: None
Selected for GREAT 2019: None
URI: http://gala.gre.ac.uk/id/eprint/23434

Actions (login required)

View Item View Item

Downloads

Downloads per month over past year

View more statistics