# Towards Socially-Acceptable Multi-Criteria Resolution of the 4D-Contracts Repair Problem

## Extended Abstract

Youssef Hamadi

Tempero
Brando, Corsica, France
youssefh@tempero.tech

## ABSTRACT

We use multi-agent systems to solve conflicts between drone flight paths (4D contracts) in urban traffic, installing safety and service quality. Intuitive corrective actions are chosen considering delay, quality, and energy. We explore different algorithms based on graph search, auctions, and distributed optimization for decision-making and action evaluation. We test these in a simulated surveillance scenario with unforeseen emergency trajectories.

## KEYWORDS

Unmanned Air Traffic Management; UAV; Coordination; DCOP; SSI Auctions; Multi-Criteria Optimization

## ACM Reference Format:

Youssef Hamadi and Gauthier Picard. 2024. Towards Socially-Acceptable Multi-Criteria Resolution of the 4D-Contracts Repair Problem: Extended Abstract. In Proc. of the 23rd International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2024), Auckland, New Zealand, May 6 – 10, 2024, IFAAMAS, 3 pages.

## 1 INTRODUCTION

Urban Air Mobility (UAM) aims to integrate unmanned air vehicles (UAV) into urban environments, but faces challenges like infrastructure development, air traffic management, and public acceptance. Public acceptance hinges on safety, privacy, and environmental impact [12]. Achieving this requires technologies that prioritize clarity and understandability in conflict resolution. Unmanned Traffic Management (UTM) is key to safely integrating UAVs into airspace. It differs from traditional air traffic control due to the smaller, automated nature of UAVs operating at lower altitudes. The US Federal Aviation Administration (FAA) introduced the first global UTM concept in 2018, focusing on decentralized, automated systems and operator collaboration [2].

This paper focuses on the FAA's UTM proposal [3] and uses a scenario with unforeseen events (hovering, emergency) that disrupt pre-planned UAV 4D contracts [8], shown in Figure 1. These conflicts need corrective actions (without creating new conflicts or worsen service quality), involving direct communication between UAVs and operators, with access to real-time information. We consider various corrective actions for 4D contracts while mitigating

Gauthier Picard

ONERA/DTIS, Université de Toulouse
Toulouse, France
gauthier.picard@onera.fr

<figure><img src="image_1.png" /><figcaption>**Figure 1:** 3 UAVs following their trajectories handling some incidents (orange stars), a Medevac helicopter on its emergency trajectory (red), and conflicts (red circles) [8].</figcaption></figure>

potential drawbacks. We propose the 4D-contracts repair problem (4D-CRP) and solution methods that prioritize clarity and comprehensibility to build public trust in UAM systems.

PROBLEM (4D-CRP). Given a set of UAVs, the 4D-Contract Repair Problem (or 4D-CRP) amounts to find a set of corrective actions to solve all the conflicts between the trajectories of the UAVs, whilst minimizing the overall cost of the corrective actions.

UTM research has tackled similar problems to 4D-CRP using both centralized and decentralized approaches. Centralized approaches like [7] use optimization to resolve conflicts while considering future infrastructure, while [1] prioritizes passenger experience and battery life in large-scale operations. Decentralized approaches like [4] use airspace reservations and MAPF for pre-flight conflict resolution, while [6] tackles path planning with multiple operators and waypoints. Existing research has explored conflict management without horizontal maneuvers [9] and used DCOP for collective decision-making [8], but these lack considerations like energy limitations, multi-criteria decision-making or fairness. This highlights the need for our approach that prioritizes clarity, energy efficiency, and fairness in conflict resolution.

## 2 CORRECTIVE ACTIONS AND COST

To keep things simple and understandable for operators and monitors, we focus on three corrective actions: *postpone* (delay waypoints), *elevate* (change altitude to bypass conflicts), and *skip* (remove conflicting segment). These actions foster clarity, scalability, and predictability while ensuring safety by maintaining separation between UAVs. As to repair conflicting trajectories, sequenced corrective actions might be necessary, since any corrective action

<figure><img src="image_2.png" /></figure>

This work is licensed under a Creative Commons Attribution International 4.0 License.

Proc. of the 23rd International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2024), N. Alechina, V. Dignum, M. Dastani, J.S. Sichman (eds.), May 6 – 10, 2024, Auckland, New Zealand. © 2024 International Foundation for Autonomous Agents and Multiagent Systems (www.ifaamas.org).
<figure><img src="image_3.png" /><figcaption>Figure 2: Average values over 30 instances for several performance metrics with increasing number of UAVs.</figcaption></figure>

potentially generate conflicts between segments after the conflict instant. In energy-unlimited settings, there always exists a sequence of actions that can solve any conflicting situation. In this paper, we will take into account limited energy resources, while also assuming that UAVs have the capability to safely land from their current positions if necessary [11]. We thus consider the following functions to assess the cost of an action *a* regardless of which UAV is performing it: $\kappa_c(a)$ is the difference between the initial number of conflict before *a* and the conflicts in the resulting set of trajectories; $\kappa_b(a)$ is the energy consumption resulting from performing action *a*, which requires assessing the extra energy required to perform new trajectory; $\kappa_d(a)$ is the delay resulting from performing the action *a*. For *postpone(c, d)* (resp. *skip(c)*) it is *d* (resp.0), and for *elevate(c, h)*, this is the time to flight up and to flight down by *h*; and $\kappa_w(a)$ is the number of missed waypoints, i.e. 1 for *skip*, 0 otherwise. To address potential unfairness where some UAVs make more concessions than others, we introduce criteria considering past actions: $\overline{\kappa}_b(u)$ the total energy conceded; $\overline{\kappa}_d(u)$ the total delay conceded; and $\overline{\kappa}_w(u)$ the total number of withdrawn waypoints. This allows us to favor actions that distribute concessions more equitably. For multi-objective evaluation, we prioritize lexicographically (e.g. minimize conflicts first, then break ties by minimizing skipped waypoints) and convert this into a weighted sum for optimization within our 4D-CRP framework. This allows for clear explanations of solution costs. As to ensure safety, we consider in our experiments lexicographic criteria with $\kappa_c$ as top-priority.

## 3 EXPERIMENTAL EVALUATION

Experiments are implemented as per [8]. We run 30 instances of randomly generated sets of trajectories and incidents for each fleet size $n = \{5, 10, 15, 20, 25\}$, and plot the average values, with [0.05, 0.95] confidence interval. We use the very same scenario generation parameters from [8], with an area of 1km by 1km, 10 emergency procedures and 5% per second an incident occurs.

We evaluate: ucs, which solves conflicts with a centralized solver based on graph search; ssi, which solves conflicts with sequential single item auctions [10]; scdcop, which solves conflicts (one by one) with AFB [5]. UAVs can perform the following actions: *postpone(c, d)* with $d \in \{20, 40, 60\}$, *elevate(c, \pm 20)*, and *skip(c)*. These actions are evaluated using some lexicographic criteria, which all have $\kappa_c$ first (to ensure safety), and always use random as a final tie-breaker. In the figure, we note them as follows: *wd* $\equiv \kappa_c > \kappa_w > \kappa_d$, *bwd* $\equiv \kappa_c > \kappa_b > \kappa_w > \kappa_d$, *b concession* $\equiv \kappa_c > \overline{\kappa}_b > \kappa_b$, *d concession* $\equiv \kappa_c > \overline{\kappa}_d > \kappa_d$, and *w concession* $\equiv \kappa_c > \overline{\kappa}_w > \kappa_w$.

Figure 2 illustrates the difference between the analyzed solution methods. ssi triggers far more corrective actions of any type. This is due to its way of solving each conflict by using a sequence of actions, using a local version of ucs, that may be useless in the future. While very fast on smaller settings, it requires almost 8 times less information sharing than scdcop. Oddly, ssi struggles on some settings (size 10): it generates many *skip* actions. That means that ssi cannot find mono-agent action sequences able to save waypoints, using *elevate* or *postpone*; this is most probably due to the fact that agents cannot find good sequences of *postpone*, since they are already all struggling with surveillance delay impact, they cannot balance. scdcop tends also to trigger more actions than ucs, but in a limited order compared to ssi. Indeed, scdcop only triggers one action per detected conflict in an sequential manner. scdcop saves as many waypoints as ucs on larger settings. Interestingly, with larger fleets, scdcop runtime grows linearly compared to ssi and ucs, since only considering mono-action sequences. Finally, it is particularly interesting that all algorithms improve delay and battery fairness: more agents there are, more actions permits to balance delay allocation (max delay) and energy expenses (min battery level) when facing event (while these ones are proportional to the number of agents).

## 4 CONCLUSION

This paper explored solution methods for resolving conflicts between planned drone trajectories in Urban Air Mobility (UAM). We investigated various solvers and decision criteria, prioritizing understandable solutions. Stakeholders can choose from flexible mechanisms with trade-offs in communication, computation, and airspace impact. More research is needed for larger-scale scenarios, diverse fleets, and market-based approaches. This work lays the groundwork for adaptable and socially acceptable conflict resolution algorithms in future UAM systems.

## ACKNOWLEDGMENTS

This work has been partly conducted as part of the PARHéRo ANR project, funded by the French Ministry of Defence's Innovation Agency (AID), under Grant Agreement ANR-21-ASRO-0004.
REFERENCES

[1] Mehdi Bennaceur, Rémi Delmas, and Youssef Hamadi. Passenger-centric urban air mobility: Fairness trade-offs and operational efficiency. *Transportation Research Part C: Emerging Technologies*, 136:103519, 2022.

[2] Federal Aviation Agency. Utm concept of operations version 2.0. Technical report, Federal Aviation Agency, 2022.

[3] Federal Aviation Agency. Unmanned aircraft systems traffic management (utm) implementation plan. Technical report, Federal Aviation Agency, 2023.

[4] Florence Ho, Rúben Geraldes, Artur Gonçalves, Bastien Rigault, Atsushi Oosedo, Marc Cavazza, and Helmut Prendinger. Pre-flight conflict detection and resolution for uav integration in shared airspace: Sendai 2030 model case. *IEEE Access*, 7:170226–170237, 2019.

[5] Thomas Léauté, Brammert Ottens, and Radoslaw Szymanek. FRODO 2.0: An open-source framework for distributed constraint optimization. In *Proceedings of the IJCAI’09 Distributed Constraint Reasoning Workshop (DCR’09)*, pages 160–164, Pasadena, California, USA, July 13 2009. https://frodo-ai.tech.

[6] Rafael Papa, Ionut Cardei, and Mihaela Cardei. Generalized path planning for utm systems with a space-time graph. *IEEE Open Journal of Intelligent Transportation Systems*, 3:351–368, 2022.

[7] Mercedes Pelegrín, Claudia D'Ambrosio, Rémi Delmas, and Youssef Hamadi. Urban air mobility: from complex tactical conflict resolution to network design and fairness insights. *Optimization Methods and Software*, pages 1–33, 08 2023.

[8] Gauthier Picard. Trajectory coordination based on distributed constraint optimization techniques in unmanned air traffic management. In *International Conference on Autonomous Agents and Multiagent Systems (AAMAS-22)*, pages 1065–1073. IFAAMAS, 2022.

[9] Valentin Polishchuk. Centralized and distributed utm in layered airspace. 2018.

[10] Adrian Schoenig and Maurice Pagnucco. Evaluating sequential single-item auctions for dynamic task allocation. In Jiuyong Li, editor, *AI 2010: Advances in Artificial Intelligence*, pages 506–515, Berlin, Heidelberg, 2011. Springer Berlin Heidelberg.

[11] Md Shah Alam and Jared Oluoch. A survey of safe landing zone detection techniques for autonomous unmanned aerial vehicles (uavs). *Expert Systems with Applications*, 179:115091, 10 2021.

[12] Pavan Yedavalli and Jessie Mooberry. An assessment of public perception of urban air mobility (uam). *Airbus UTM: Defining Future Skies*, pages 2046738072–1580045281, 2019.