Ho, Florence, Goncalves, Artur, Salta, Ana, Cavazza, Marc ORCID: https://orcid.org/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

Preview

PDF (Author Accepted Manuscript) 23434 CAVAZZA_Multi-Agent_Path_Finding_for_UAV_Traffic_Management_2019.pdf - Accepted Version Download (1MB) | Preview

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 / School / Research Centre / Research Group:	Faculty of Engineering & Science > School of Computing & Mathematical Sciences (CMS) Faculty of Engineering & Science
Related URLs:	Organisation
Last Modified:	04 Mar 2022 13:06
URI:	http://gala.gre.ac.uk/id/eprint/23434

Actions (login required)

View Item

Downloads