Skip navigation

Decentralized multi-agent path finding for UAV traffic management

Decentralized multi-agent path finding for UAV traffic management

Ho, Florence ORCID: 0000-0003-4703-7727, Geraldes, Ruben ORCID: 0000-0003-1339-382X, Gon, Artur ORCID: 0000-0001-8765-7387, Rigault, Bastien, Sportich, Benjamin, Kubo, Daisuke, Cavazza, Marc ORCID: 0000-0001-6113-9696 and Prendinger, Helmut ORCID: 0000-0003-4654-9835 (2020) Decentralized multi-agent path finding for UAV traffic management. IEEE Transactions on Intelligent Transportation Systems. pp. 1-12. ISSN 1524-9050 (Print), 1558-0016 (Online) (In Press) (doi:

PDF (Author Accepted Manuscript)
29605 CAVAZZA_Decentralized_Multi-Agent_Path_Finding_2020.pdf - Accepted Version

Download (2MB) | Preview


The development of a real-world Unmanned Aircraft System (UAS) Traffic Management (UTM) system to ensure the safe integration of Unmanned Aerial Vehicles (UAVs) in low altitude airspace, has recently generated novel research challenges. A key problem is the development of Pre-Flight Conflict Detection and Resolution (CDR) methods that provide collision-free flight paths to all UAVs before their takeoff. Such problem can be represented as a Multi-Agent Path Finding (MAPF) problem. Currently, most MAPF methods assume that the UTM system is a centralized entity in charge of CDR. However, recent discussions on UTM suggest that such centralized control might not be practical or desirable. Therefore, we explore Pre-Flight CDR methods where independent UAS Service Providers (UASSPs) with their own interests, communicate with each other to resolve conflicts among their UAV operations--without centralized UTM directives. We propose a novel MAPF model that supports the decentralized resolution of conflicts, whereby different `agents', here UASSPs, manage their UAV operations. We present two approaches: (1) a prioritization approach and (2) a simple yet practical pairwise negotiation approach where UASSPs agents determine an agreement to solve conflicts between their UAV operations. We evaluate the performance of our proposed approaches with simulation scenarios based on a consultancy study of predicted UAV traffic for delivery services in Sendai, Japan, 2030. We demonstrate that our negotiation approach improves the ``fairness'' between UASSPs, i.e. the distribution of costs between UASSPs in terms of total delays and rejected operations due to replanning is more balanced when compared to the prioritization approach.

Item Type: Article
Uncontrolled Keywords: Unmanned aerial vehicles, Delays, Aircraft, Standards, Trajectory, Cost function
Subjects: Q Science > QA Mathematics > QA75 Electronic computers. Computer science
Faculty / Department / Research Group: Faculty of Liberal Arts & Sciences
Faculty of Liberal Arts & Sciences > School of Computing & Mathematical Sciences (CAM)
Last Modified: 26 Nov 2020 22:34
Selected for GREAT 2016: None
Selected for GREAT 2017: None
Selected for GREAT 2018: None
Selected for GREAT 2019: None
Selected for REF2021: None

Actions (login required)

View Item View Item


Downloads per month over past year

View more statistics