# Game-theoretical approach to decentralized multi-drone conflict resolution
and emergent traffic flow operations

Serge Hoogendoorn, Victor L. Knoop,
Hani Mahmassani, and Sascha Hoogendoorn-Lanser

(August 1 2023)

##  1 Abstract

This paper introduces decentralized control concepts for drones using
differential game theory. The approach optimizes the behavior of an ego drone,
assuming the anticipated behavior of the opponent drones using a receding
horizon approach. For each control instant, the scheme computes the Nash
equilibrium control signal which is applied for the control period. This
results in a multi-drone conflict resolution scheme that is applied to all
drones considered.

The paper discusses the approach and presents the numerical algorithm, showing
several examples that illustrate the performance of the model. We examine at
the behavior of the ego drone, and the resulting collective drone flow
operations. The latter shows that while the approach aims to optimize the
operation cost of the ego drone, the experiments provide evidence that
resulting flow operations are very efficient due to the self-organization of
various flow patterns.

The presented work contributes to the state of the art in providing a generic
approach to multi-drone conflict resolution with good macroscopic flow
performance characteristics. The approach enables relatively straightforward
inclusion of error due to sensing and communication. The approach also allows
for including different risk levels (e.g., for malfunctioning of sensor and
communication technology), priority rules, regulations, and higher-level
control signals (e.g., routing, dynamic speed limits).

Keywords: drone traffic flow operations, differential game theory,
decentralized control, multi-drone conflict resolution

##  2 Introduction

Contemporary drone technology, including advanced monitoring and communication
systems, will provide a plethora of applications, for instance in delivery and
distribution, disaster relief, surveillance, but also personal mobility. As
the demand for drone transportation increases (e.g., [5]), multi-drone
conflict resolution becomes more and more important, as is the efficient use
of (scarce) airspace. We note that the term “drone” as used in this paper
encompasses unmanned VTOL vehicles of varying sizes and weights, including
eVTOL vehicles proposed for urban air mobility (UAM) services. We recognize
that airspace regulations differentiate between vehicles of varying sizes
(e.g. delivery drones are expected to operate at much lower altitudes than
multi-person UAM vehicles). The approach in this paper is intended as a
generic approach that does not make such distinctions, but might be applicable
to any and all subsets of such vehicles.

###  2.1 Multi-drone conflict resolution schemes

In the paper, we focus on the topic of multi-drone conflict resolution
schemes. Multi-drone conflicts are generally seen as problematic, and many
approaches aim to avoid situations in which these conflicts occur. Our view is
that as the demand for airspace is increasing, multi-drone conflicts cannot be
prevented and approaches allowing us to efficiently deal with them are needed.

An excellent overview of current conflict resolution (CR) schemes is given in
[15]. Here, a distinction is made between centralized and decentralized
schemes regarding both surveillance and trajectory propagation. In the review,
explicit attention is paid to the assumptions of predictability of the paths
of the opponent drones.

With the expected large number of drones, we argue that centralized planning
of all drone trajectories is not feasible nor practical, and we need to refer
to decentralized conflict resolution, also called “free flying” [9] in
unstructured airspace. This forms the basis for the approach presented in this
paper.

We argue that the scientific foundation of many of the relevant concepts lies
in traffic flow theory, as has been developed for (first) car traffic and
(later) pedestrian traffic. Later in the paper, we will show some of the
concepts used from that argument. Here, we will introduce the scientific
background of applying traffic flow theory to air traffic.

The authors of [17] show how air traffic can be operated if there are no
specific flight paths. This can be further structured as shown in [16]. A
further insight is that especially in urban environments, some of the low-
altitude airspace is not available due to buildings. In that case, airspace
capacity is therefore limited by “intersections”. First studies on this, both
with simulations and analytically have been analyzed (e.g., [1].
Alternatively, dedicated space is available for various directions. That can
be in layers [6] or in tubes [4]. Also a fundamental diagram, or macroscopic
fundamental diagram, for has been shown for air traffic by simulation [2]. A
resulting control measure, a form of perimeter control, has subsequently been
presented and tested [7]. In [14] reinforcement learning is used to optimize
drone interaction rules to improve overall drone traffic operations. This is a
great example of how we can use decentralized schemes to achieve efficient and
safe flow operations.

###  2.2 Applications of game theory

This paper introduces control concepts for drones using differential game
theory. The approach is based on earlier approaches developed by the authors
for connected vehicles [13], vessels [12], pedestrians [10], and bicycle
modeling [11]. The motivation for applying these techniques is the emergent
phenomena that these decentralized approaches result in that we expect to be
beneficial for drone traffic operations.

Differential game theory has been applied to the control of drones before, but
to the best knowledge of the authors not for real-time cooperative control
purposes. Here, we propose a receding horizon approach in which each drone
determines the best trajectory for the coming period while reconsidering this
trajectory at chosen time instants.

In the remainder, we will present the mathematical formulation of the
differential game, which has been the focus of the presented research. We also
present the numerical solution scheme and show some of the characteristics of
the resulting decentralized multi-drone conflict resolution approach in terms
of drone traffic flow operation characteristics. We also provide first
insights into the sensitivity of these characteristics to the parameters of
the decentralized drone control scheme.

##  3 Mathematical problem formulation

In this section, we provide the mathematical problem formulation that forms
the basis for the numerical solution scheme presented in the next section. We
start by describing the simplified model capturing the drone dynamics,
followed by the objective function and necessary conditions for optimality of
the ego drone control.

###  3.1 A mathematical model for an ego drone in relation to its opponents

We consider drone $i$ the behavior of which will be described by a receding
horizon controller. The position of the drone is defined by a 3-dimensional
vector $\vec{r}_{i}(t)$. The velocity of the drone and the acceleration of the
drone are defined by $\vec{v}_{i}={d\over dt}\vec{r}_{i}$ and
$\vec{a}_{i}={d\over dt}\vec{v}_{i}$ respectively.

The dynamics of the ego drone are written down in the following state-space
formulation:

${d\over dt}\vec{x}=\vec{f}(t,\vec{x},\vec{u})$ (1)

where the state $\vec{x}$ is defined by the positions and velocities of the
ego drone $i$ and the other (opponents) drones $j\neq i$ with whom the ego
drone interacts, subject to the given initial state
$\vec{x}_{i}(t_{k})=\vec{x}_{k}$. The vector $\vec{u}$ denotes the control
signal - in this case, the acceleration vector $\vec{u}_{i}$.

For this paper, we consider a very simple model to relate positions,
velocities, and control signals. For the ego drone $i$ we have:

${d\over dt}\vec{r}_{i}=\vec{v}_{i}$ (2) ${d\over dt}\vec{v}_{i}=\vec{u}_{i}$
(3)

The same applies to the opponent drones $j$.

We emphasize that more advanced models for the dynamics of drones can be used,
and the methods presented in the ensuing can be applied without loss of
generality. Here, we have decided to keep the dynamics as simple as possible
to keep the mathematics as simple as possible.

###  3.2 Drone cost specification

The game-theoretical concept proposed here is based on the idea that the ego
drone minimises some cost function. We will use the following cost functional:

$J_{i}=\int_{t_{k}}^{t_{k}+T}e^{-\eta
s}L(s,\vec{x}(s),\vec{u}(s))ds+e^{-\eta(t_{k}+T)}\phi(t_{k}+T,\vec{x}(t_{k}+T))$
(4)

where $L$ denotes the running costs and $\phi$ denotes the terminal cost; note
that while we have omitted subscripts, both costs are specific for the ego
drone; $\eta$ denotes the discount factor showing that costs are discounted
over time; $T$ denotes the control (and prediction) horizon reflecting how far
the drone will plan ahead in time. For the sake of simplicity, we will assume
$\phi=0$ in the ensuing.

In assuming that the ego drone will minimize the cost during the planning
period $[t_{k},t_{k}+T)$, we determine:

$\vec{u}_{[t_{k},t_{k}+T)}^{*}=\arg\min
J_{i}(t,\vec{x}(t_{k}),\vec{u}_{[t_{k},t_{k}+T)})$ (5)

In other words, the ego drone determines the optimal acceleration vector
functional, which will be applied from $t_{k}$ onward. A new optimal
acceleration function will be computed at a new time $t_{k+1}<t_{k}+T$.

For this paper, we will use simple cost specifications to derive the desired
behavior of the ego drone. To this end, we split up the running costs into
three components: 1) the cost of straying from the desired direction and
speed; 2) the cost (risk) of getting too close to other drones, and 3) the
cost of acceleration. For more advanced specifications of the running cost,
other components can be added without loss of generality. We propose:

$L^{stray}={1\over 2}\left(\vec{v}_{i}^{0}-\vec{v}_{i}(t)\right)^{2}$ (6)
$L^{prox}=\sum_{j\neq i}e^{-d_{ij}/d_{0}}$ (7)

with $d_{ij}=||\vec{x}_{j}-\vec{x}_{i}||$, and

$L^{accel}={1\over 2}\vec{u}_{p}\cdot\vec{u}_{p}$ (8)

For combining the three factors, we propose a straightforward weighted linear
combination of the three cost components:

$L=\alpha L^{stray}+\beta_{0}L^{prox}+L^{accel}$ (9)

where $\alpha$ and $\beta_{0}$ are weights.

Next to opponent drones, in many situations obstacles also need to be
considered. Here, we assume that the location of obstacles (walls, ground,
etc.) are known. The obstacles are treated in the same way as the opponent
drones: costs $L^{obs}$ are determined for each obstacle $k$

$L^{obs}=\sum_{k}e^{-d_{ik}/d_{1}}$ (10)

Here, $d_{ik}$ is the minimum distance from the ego drone $i$ to the obstacle
$k$. The cost of being close to obstacles is added to the total cost specified
in Eq. (9) by adding $\beta_{1}L^{obs}$.

###  3.3 Mathematical model of the opponent drones

In the preceding subsection, we have formulated the optimization problem that
will yield the behaviour of the ego drone $i$, conditional on the behaviour of
the opponent drones $j$. Note that we assume that $i$ knows the expected
positions and velocities of all opponents for the prediction horizon and
optimises its flying behaviour accordingly. At the same time, the opponents
will behave in the same way, that is, optimise their behaviour under the
assumption that they know the behaviour of the other drones. The resulting
problem is a differential game, where we are looking for the Nash equilibrium.
In the remainder, we will show how we can determine this equilibrium state.

##  4 Solving the differential game

Now that the mathematical problem has been specified, let us briefly look at
the solution approach. We describe the approach in two steps: the first step
derives the necessary conditions for optimality of the solution using
Pontryagin’s minimum principle. The second step shows how these are used to
determine the optimal solution using an iterative approach.

###  4.1 Necessary conditions for optimality

The differential game can be solved with the aid of Pontryagin’s minimum
principle. To do this, we first need to determine the co-state dynamics.
First, we define the Hamiltonian $H$ as follows:

$H=e^{-\eta t}L+\vec{\lambda}\cdot\vec{f}$ (11)

where $\vec{\lambda}$ denotes the shadow costs (or co-state) of the state
$\vec{x}$. This co-state describes the relative change in the optimal cost due
to a small change in the state.

The optimality conditions provide the necessary conditions for the optimal
acceleration:

$H(t,\vec{x},\vec{u}^{*},\vec{\lambda})\leq
H(t,\vec{x},\vec{u},\vec{\lambda})$ (12)

for all $\vec{u}$. For the model specification used in this paper, we can
easily show that the optimality condition provides the following expression:

$\vec{u}^{*}=-\vec{\lambda}_{v}$ (13)

This shows that the optimal acceleration is equal to minus the marginal cost
of the velocity $\vec{v}$. In other words, the ego drone applies the
acceleration which yields the steepest reduction in the cost of the velocity.

Pontryagin’s Principle states that the co-states $\vec{\lambda}$ satisfy the
following necessary conditions:

$-{d\over dt}\vec{\lambda}={\partial\over\partial\vec{x}}H$ (14)

For the co-states $\vec{\lambda}_{v}$ we have:

$-{d\over
dt}\vec{\lambda}_{v}=\alpha(\vec{v}^{0}-\vec{v}_{i})+\vec{\lambda}_{r}$ (15)

and for the co-states $\vec{\lambda}_{r}$ we have:

$-{d\over dt}\vec{\lambda}_{r}=-{\beta\over d_{0}}\sum_{j\neq
i}e^{-d_{ij}/d_{0}}\vec{n}_{ij}$ (16)

Instead of initial conditions, which are given for the states, co-states
satisfy terminal conditions that can be determined using the so-called
transversality conditions:

$\vec{\lambda}(t_{k}+T)={\partial\over\partial
x}\phi(t_{k}+T,\vec{x}(t_{k}+T))$ (17)

This in principle provides a complete system of unknowns and equations: we
have state dynamics with initial conditions, co-state dynamics with terminal
conditions, and optimality conditions providing an expression for the optimal
acceleration of the ego drone as a function of the co-state. This leaves us
with a system of ordinary differential equations with mixed initial and
terminal boundary conditions.

###  4.2 Iterative numerical solution

In this section, we briefly discuss the iterative numerical solution approach.
The algorithm is shown for one prediction period only; the receding horizon
generalization is straightforward and left to the reader. Moreover, for the
sake of simplicity, we have omitted obstacles, and terminal costs.

  1. 1.

Initialization of control variables (prediction horizon $T$, time step $h$;

  2. 2.

Initialization of parameters (weights, desired speed; relaxation parameter
$a$, cut-off error $eps$

  3. 3.

For each drone, initialization of initial position $\vec{r}(0)$ and velocities
$\vec{v}(0)$ and target position $\vec{r}_{\infty}$

  4. 4.

Initialize co-states for the positions $\vec{\Lambda}_{r}(t)=\vec{0}$ and
velocities $\vec{\Lambda}_{v}(t)=\vec{0}$ for all $t=0:\Delta t:T$

  5. 5.

While $error>eps$ do

    1. (a)

Set $\vec{\lambda}_{r}(t)=\vec{\Lambda}_{r}(t)$ and
$\vec{\lambda}_{v}(t)=\vec{\Lambda}_{v}(t)$

    2. (b)

For $t$ = $0:\Delta t:T-\Delta t$

      1. i.

For $i=1:n$

        1. A.

$\vec{u}(t|i)=-\vec{\lambda}_{v}(t|i)$

        2. B.

$\vec{v}(t+\Delta t|i)=\vec{v}(t|i)+\Delta t\cdot\vec{u}(t|i)$

        3. C.

$\vec{x}(t+\Delta t|i)=\vec{x}(t|i)+\Delta t\cdot\vec{v}(t|i)$

    3. (c)

For $t$ = $T:-\Delta t:\Delta t$

      1. i.

For $i=1:n$

        1. A.

Compute desired velocity $\vec{v}_{i}^{0}(t)$

        2. B.

$\vec{\lambda}_{r}(t-\Delta t|i)=\vec{\lambda}_{r}(t|i)+\Delta
t\cdot{\beta\over d_{0}}\sum_{j\neq i}e^{-d_{ij}/d_{0}}\vec{n}_{ij}$

        3. C.

$\vec{\lambda}_{v}(t-\Delta t|i)=\vec{\lambda}_{v}(t|i)+\Delta
t\cdot\left(\alpha(\vec{v}_{i}^{0}-\vec{v}(t|i))+\vec{\lambda}_{r}(t|i)\right)$

    4. (d)

Relaxation
$\vec{\Lambda}_{r}(t)=(1-a)\cdot\vec{\Lambda}_{r}(t)+a\cdot\lambda_{r}(t)$ and
$\vec{\Lambda}_{v}(t)=(1-a)\cdot\vec{\Lambda}_{v}(t)+a\cdot\lambda_{v}(t)$

    5. (e)

$error=||\vec{\Lambda}-\vec{\lambda}||$

It is beyond the scope of the paper to analyze the performance of the
numerical solution in detail. For illustration purposes, Fig. 1 shows the
convergence properties of the scheme for a one-on-one drone interaction
scenario, with a time horizon of 10 s (discussion in the following section for
more details) for different values of the relaxation parameter $a$. The
picture clearly shows how $a$ affects the rate of convergence. We also note
that for this case, larger values of $a$ lead to non-convergence of the scheme
(not shown in the figure). Convergence issues already occur for $a=0.05$,
where oscillations are observable due to over-correction of the stable
solution $\vec{\Lambda}$. While further investigation into the convergence
properties is an important direction for future research, it is out of the
scope of this paper.

Figure 1: Convergence behavior of iterative scheme for 50 iterations and
different values of $a$

##  5 Experiments

In this section, we present the results of applying the multi-drone conflict
resolution approach presented in this paper to different scenarios. We
emphasize that the objective is to gain first insights into the properties of
the scheme first and foremost, and not to present real-life scenarios. This
implies that results would need to be scaled (in terms of time and spatial
scale) to realistic values upon true-life application. Moreover, the number of
scenarios presented is limited as they serve to illustrate the emerging
properties of the multi-drone conflict resolution scheme.

###  5.1 One-on-one drone interaction

Fig. 2 shows results from solving the game theoretical problem for a one-on-
one drone conflict. The situation shows how two drones try to reach opposite
destinations (the asterix ’*’). The figure shows the planned trajectory from
the current position at $t_{k}$. The planned trajectory is the trajectory that
minimizes the cost of the ego drone. The figure shows the situation as a
projection on the $x-y$ plane and the $x-z$ plane.

Figure 2: Example of model behavior for head-on interaction between two drones
for $v^{0}=1$, $T=10$, $\alpha=1$, and $\beta_{0}=10$.

Note that in this example, the interaction takes place in plane $z=1$. This is
not necessarily the case, but a consequence of the slightly perturbed initial
conditions in the $x$ and $y$ position of the drones. In fact, there are
infinite optimal solutions for a head-on interaction as considered in this
scenario: the algorithm will compute only one.

To test the influence of the different parameters numerically, have considered
the head-on drone interaction scenario for different parameter values. For
each of the considered scenarios, the impacts of the speeds of the drones
turned out to be negligible. We therefore only show the impact of the minimum
distance between the passing drones in relation to the parameter values. Table
1 shows an overview of the impacts of some of the key parameters that can be
used in designing the drone scheme.

First of all, the prediction (or look-ahead) time $T$ determines the minimum
distance between the two drones (in a non-linear way). The table shows that
the larger the look-ahead time, the larger the minimum distance between the
two drones is. This is in line with our expectations, as looking further ahead
allows for earlier changes in the direction and speed of the drone.

Second, the interaction scaling parameter $R$ has been considered. Its impact
is also as expected: the minimum distance scales approximately linearly with
$R$. The parameter hence provides a good way to design the minimum distance
allowed between two interacting drones.

Finally, the table shows the impact of the weight $\beta_{0}$ of the proximity
costs. Again, the parameter influences the minimum distance as expected: a
larger value yields more emphasis on maintaining sufficient distance at the
cost of changing course and speed.

Parameter | Value | Minimum distance
---|---|---
$T$ | 2.5 | 0.21
| 5 | 0.34
| 10 | 0.41
$R$ | 0.05 | 0.18
| 0.1 | 0.34
| 0.2 | 0.68
$\beta_{0}$ | 1 | 0.16
| 10 | 0.34
| 100 | 0.55
Table 1: Minimum distance sensitivity for head-on scenario with $v^{0}=1$,
$\alpha=1$, $\beta_{0}=10$, $T=5$, and $R=0.1$; and $\Delta t=1s$

###  5.2 Self-organization in multi-drone conflict resolution

In this subsection, we consider multi-drone conflict resolution scenarios,
focusing on the self-organization characteristics of the scheme. To this end,
we look at a head-on interaction scenario and a crossing scenario. We use the
same parameter values as in the one-on-one interaction case unless stated
differently.

####  5.2.1 Head-on interactions and lane formation

The first multi-drone scenario considered is a scenario where two groups of
drones are meeting head-on. To this end, we generated two groups of drones in
two rectangular boxes of 5 by 2 by 1 meter around $x=12.5$ and $x=-12.5$,
$y=0$ and $z=1$ respectively. In each box, $n$ drones are generated. For the
right box, drones move towards the left (desired direction
$\vec{e}^{0}=(-1,0,0)$), while for the left box, drones move towards the right
(desired direction $\vec{e}^{0}=(1,0,0)$). The locations of the $n$ drones are
drawn from a 3D uniform distribution, assuming equal mean distances in each
direction. The initial speeds of the drones are equal to zero.

To illustrate the performance of our decentralized approach, we will perform a
range of analyses and show different visualizations. To start, Fig. 3
illustrates the results of the head-on interaction experiment, by showing
three consecutive snapshots of the drone positions and their intended paths
(for 1 s ahead). The figure shows the projection on the x-y plane (left column
of pictures) and on the x-z plane (right column of pictures). Although more
difficult to discern than in the case of a 2D pedestrian flow, we can clearly
see that clusters are formed by drones that are moving in the same direction.
This cluster-formation resembles the formation of bi-directional lanes in a
pedestrian flow [8], but is more complex as the drones have more freedom to
move. As a result, patterns are not always easily identifiable.

Figure 3: Example showing self-organization in bi-directional drone flow
operations for head-on scenario (100 drones) with $v^{0}=1$, $\alpha=1$,
$\beta_{0}=10$, $T=5$, and $R=0.1$; and $\Delta t=1$

Next, let us consider the result statistics shown in Tab. 2, showing the
impact of the parameters of the algorithm on the minimum distance and the
average speed in the direction of the destination. Regarding the latter, the
table shows that the speed is not strongly affected by the parameters, but the
minimum distance observed is. This shows that the scheme results in very
efficient multi-drone conflict resolution.

For the prediction horizon $T$, we see that the minimum distance increases
when the prediction horizon becomes larger. This is expected as looking ahead
further improves the possibilities for more efficient interactions with other
drones. The improvement reduces substantially when going from $T=5$ to $T=10$,
at the expense of increased computational complexity. For this case, we could
argue that $T=5$ is a good trade-off between efficiency and complexity.

The minimum distance scales linearly with the distance scaling $R$. Similar to
the one-on-one interaction, this shows that $R$ is an important design
parameter that directly influences interaction characteristics. To an extent,
the same applies to the parameter $\beta_{0}$: increasing the weight of the
proximity costs results in a higher importance of keeping sufficient distance
between the interacting drones, at the expense of a slight reduction in
efficiency.

Parameter | Value | Minimum distance | Average speed
---|---|---|---
$T$ | 2.5 | 0.33 | 0.99
| 5 | 0.44 | 1.00
| 10 | 0.46 | 1.00
$R$ | 0.05 | 0.22 | 1.00
| 0.1 | 0.42 | 1.00
| 0.2 | 0.85 | 0.99
$\beta_{0}$ | 1 | 0.27 | 1.00
| 10 | 0.47 | 1.00
| 100 | 0.59 | 0.99
Table 2: Minimum distance and average speed sensitivity for head-on scenario
(100 drones) with $v^{0}=1$, $\alpha=1$, $\beta_{0}=10$, $T=5$, and $R=0.1$;
and $\Delta t=1$

Overall, we can conclude that the interactions are highly efficient, even in
the case of high numbers of interacting drones. This has two reasons. First,
as the interactions occur in free space, the swarm expands as more drones are
present. Later in this section, we will consider restricted airspace to
showcase the impact on efficiency by introducing bottleneck scenarios. Second,
as we have already seen by looking at a single simulation outcome, self-
organized patterns are formed that enable efficient interaction of the drone
groups.

To visualize the self-organized patterns, we consider the spatial distribution
of the drones from the two groups near the point where the head-on interaction
occurs (i.e., at $x=0$). To this end, we collected the points at which the
drones of both groups passed the $x=0$ cross-section. The picture shows these
points clustered based on direction. For the clustering, the ’natural’
interpolation function for irregularly gridded data of Matlab 2023b was used
(for visualization purposes only). Fig. 4 shows the patterns that are formed
for a 200-drone interaction experiment. The figure clearly shows the clusters
that are formed for the two example situations, where we emphasize that the
points shown reflect different passing times. Clearly, the scheme results in a
structure where drones moving in the same direction form groups that are
spatially and temporarily close, as to reduce the number of close-range
interactions with drones moving in the opposite direction.

Figure 4: Two examples of the spatial distribution of drone groups for head-on
interaction scenario near $x=0$. The two pictures show two random simulation
outcomes from the same scenarios, resulting from different initial spatial
distributions of the drones.

####  5.2.2 Crossing flows and self-organized patterns

Here, we briefly discuss the results of a crossing drone flow experiment.
Again, two groups of drones are considered. Instead of meeting heads-on, the
drone flows cross at a 90-degree angle. Group 2 moves along the x-axis (from
right to left), while group 1 moves along the y-axis (from top to bottom). In
line with the formation of diagonal striped patterns in pedestrian flow (see
[8]), we expect specific patterns to be formed for this scenario that resemble
structures formed in pedestrian flow operation; see [8].

Figures 5 and 5 show the results of two randomly chosen experiments, where
random means that, in line with the head-on interaction case, initial
positions of the 200 drones were randomly generated in two bounding boxes.
Both pictures show that forms of self-organization are present. While the
diagonal patterns, which we know from pedestrian flow operations, are not
directly transferred to the 3D drone flow, we do see similar emergent
patterns. For instance, in Fig. 5, we see that group 1 forms two diagonal
shapes in the z-direction. The patterns formed in Fig. 6 are different, yet
clusters are clearly identifiable.

Figure 5: Illustration of drone behavior for crossing experiment 1. The left
column shows the projections of the drone positions on the $x-y$ plane; the
middle and left columns show the projections of groups 1 and 2 on the $x-z$
and $y-z$ plane respectively. We plotted the current position, and the
1-second ahead planned trajectory. Figure 6: Illustration of drone behavior
for crossing experiment 2.

To gain insight into the sensitivity of the efficiency and the risk levels of
the flow operations of the parameter values, we repeated the sensitivity
analysis of the head-on scenario to the crossing flow scenario. Tab. 3 shows
the result of this sensitivity analysis for the crossing flow scenario.

Let us first look at the impact of the prediction horizon $T$. Interestingly,
we see that while increasing $T$ from 2.5 to 5 yields an increase in the
minimum distances, increasing it further causes a reduction (i.e., an increase
in the risk). This counterintuitive outcome shows that what is optimal from
the perspective of an individual drone, may not per se yield a system
improvement for specific cases. While further investigations are needed, we do
remark that similar results are reported in [11].

Looking at the impact of the interaction distance $R$, we see similar results
as in the head-on scenario. First of all, it is remarkable to see that average
speeds are insensitive to the value of $R$, meaning that the increased spacing
requirements have a very limited impact on the average operation speed of the
drones. It again needs to be stressed that in this scenario, there are no
spatial constraints and airspace capacity is - in a sense - unlimited. From
the table, we can clearly see how the minimal distance between the drones
scales with increasing $R$: as with the head-on scenario, $R$ can be
effectively used to ensure that drone operations meet safety requirements
expressed in the distances the drones maintain from each other. Again, the
same applies to the parameter $\beta_{0}$: as for the head-on scenario,
increasing the weight of the proximity costs results in a higher importance of
keeping sufficient distance between the interacting drones.

Parameter | Value | Minimum distance | Average speed
---|---|---|---
$T$ | 2.5 | 0.31 | 0.99
| 5 | 0.43 | 0.99
| 10 | 0.37 | 1.00
$R$ | 0.05 | 0.27 | 0.99
| 0.1 | 0.43 | 0.99
| 0.2 | 0.80 | 0.99
$\beta_{0}$ | 1 | 0.22 | 1.00
| 10 | 0.45 | 0.99
| 100 | 0.47 | 0.99
Table 3: Minimum distance and average speed sensitivity for crossing-flow
scenario (200 drones) with default settings $v^{0}=1$, $\alpha=1$,
$\beta_{0}=10$, $T=5$, and $R=0.1$; and $\Delta t=1$

###  5.3 Bottlenecks and multi-drone conflict resolution

In this subsection, we consider multi-drone conflict resolution scenarios for
bottleneck scenarios. To this end, we reconsider the head-on interaction
scenario discussed in the previous subsection. In this case, however, we
restrict the amount of airspace available by positioning two large static
obstacles with a radius of $2m$ located at $(x,y)$ $(0,-2.5)$ and $(0,2.5)$
respectively. While the drones are able to fly around the obstacles (and may,
in particular for longer prediction horizons), the shortest path is to
navigate between the 1-meter passage between the cylinders.

Also in this scenario, we see self-organization occurring, leading to
efficient flow operations. Fig. 7 showcases this by looking at the operations
in three consecutive time instants. The pictures show the current position of
the drones (circle or triangle) and the planned optimal trajectory determined
using the multi-drone conflict resolution scheme presented in this paper. Note
that we have used $T=2.5s$ to make pictures somewhat clearer. The figure shows
that before the drones arrive at the bottleneck, they have formed two clusters
for each direction. When the drones arrive at the bottleneck, the flocks
funnel to form a narrow stream, which is clearly observable from the top view
(left column of pictures). At the same time, they start to form dynamic lanes
when navigating through the bottleneck. The separation between the two
directions occurs in the $z$-direction mostly, although in other simulations
(and with other parameters) other patterns occur as well.

Figure 7: Illustration of cluster formation process inside the bottleneck;
left pictures show top view; right pictures show side view.

Fig. 8 shows the self-organization in a different way, by providing the cross-
sectional projection of the passing drones at $x=0$ for two random simulation
experiments. It again shows how the bi-directional flows are separated in the
z-direction. It also shows how in different situations, a different number of
lanes are formed (top: 4 lanes, bottom: 3 lanes).

Figure 8: Two examples of the spatial distribution of drone groups for the
bottleneck scenario near $x=0$. The two pictures show two random simulation
outcomes from the same scenarios, resulting from different initial spatial
distributions of the drones.

To get some insight into the impact of the parameter values, Tab. 4 shows the
sensitivity of the minimum distance (as a measure for risk) and average speed
(as a measure of efficiency) to different parameter settings (i.e., $R$ and
$\beta_{0}$). From the table, we can conclude that the parameters have the
expected results. First of all, we see that changing the distance scaling
parameter $R$ impacts the minimum distance in an approximate linear fashion.
While the minimum distance that drones maintain increases with increasing $R$,
the average speed starts to reduce. This is caused by the fact that due to
increased spatial requirements, bottleneck capacity is insufficient and drones
need to reduce their speed before being able to pass through the bottleneck
(congestion). The impact of the weighting parameter $\beta_{0}$ is also as
expected given the outcomes of the previous experiments. While increasing the
weight increases the minimum distances between the drones, the average speed
reduces signifying forms of congestion occuring due to the bottleneck.

Parameter | Value | Minimum distance | Average speed
---|---|---|---
$R$ | 0.05 | 0.22 | 0.98
| 0.1 | 0.35 | 0.92
| 0.2 | 0.67 | 0.73
$\beta_{0}$ | 1 | 0.17 | 0.99
| 10 | 0.16 | 0.86
| 100 | 0.24 | 0.62
Table 4: Minimum distance and average speed sensitivity for head-on scenario
(100 drones) with $v^{0}=1$, $\alpha=1$, $\beta_{0}=10$, $T=5$, and $R=0.1$;
and $\Delta t=1$

##  6 Discussion, conclusions and future work

This paper presents a novel approach to multi-drone conflict resolution based
on differential game theory, which has been successfully used in modeling
pedestrian, cyclist, and vessel dynamics, as well as controlling CAVs. The
problem formulation and numerical solution approaches were adapted here for
multi-drone conflict resolution.

Based on the results presented in this paper, we conclude that the proposed
game-theoretical approach shows potential for real-time application in multi-
drone conflict resolution and decentralized management of drone traffic. While
showing promise, several aspects require further investigation before
practical applications can be considered. Some of these required
investigations are theoretical in nature, others are more technical in the
sense that insights in (the limits of) communication and sensing technology.
Below, we provide an overview of our findings as well as the required further
studies.

####  6.0.1 Main findings

First of all, the numerical properties of the solution scheme are sufficient
to warrant further investigation: the scheme converges to solutions close to
the optimal solution within a limited number of iterations, and computation
times are acceptable for real-time application. However, further analyses are
required, especially when considering realistic scenarios with accurate update
times, prediction horizons, and interactions with other drones. Such analyses
were out of the scope of this paper, which aimed to show the concept rather
than the practical details of real applications.

Secondly, the emergent drone flow operations prove to be highly efficient
while maintaining safety requirements. This efficiency is attributed to the
self-organized structures that occur when different groups of drones interact.
These patterns are similar to those observed in pedestrian and, to a lesser
extent, bicycle flows, which motivated the application of differential game
theory to drones. The experiments demonstrate that even in the presence of
airspace restrictions, self-organized processes occur, resulting in efficient
drone operations. However, in situations of limited capacity, average drone
speeds decrease as queuing forms in front of the bottleneck. Furthermore, the
limiting behavior of the system as density increases and conflicts
correspondingly increase, losses in productivity are likely to be experienced
providing an upper bound to the system’s practical capacity, as illustrated in
the fundamental diagrams observed in [2].

####  6.0.2 Further investigations

From a scientific perspective, further investigation of the various phenomena
observed in three-dimensional space is of key interest. One of the crucial
issues is the limit of efficient and safe self-organization, including the
role of heterogeneity in reducing this efficiency of self-organization. For
pedestrian flow operations, we know that self-organization breaks down when
densities become too high. Furthermore, heterogeneity, expressed in terms of
the free speeds $\vec{v}_{i}^{0}$ of the drones, or other differences in drone
performance characteristics, has a negative impact on self-organization
leading to the so-called ’freezing by heating’ effect that is observed in
different self-driven systems. For instance, in [8] it is shown how
heterogeneity in pedestrian flows leads to failing self-organization of bi-
directional lanes and consequently to blockages. The limits in self-
organization will result in the need for more centralized interventions in
terms of air traffic management, structuring the airspace, etc. These could
pertain to the prioritization of specific types of drones, management measures
such as speed homogenization, virtual intersection controllers, etc.

Our enhanced insight into drone flow properties will also form the basis for
aggregate (macroscopic) modeling approaches that may be suitable to capture
the dynamics of swarms of drones driven by game-theoretical control
principles. Understanding the conditions under which self-organization
collapses can provide insights for designing drone traffic management control
principles, including the redistribution of capacity to specific groups of
drones if needed and possible airspace architectures in areas where
restrictions are called for by land use and environmental considerations as in
[3]. Hierarchical approaches have been successful in the past in the CAV
domain [13].

The impact of sensing and communication errors needs to be studied. Different
strategies proposed in [11] express the level of cooperation among traffic
participants. We argue that risks arising from high probabilities of sensing
and communication failure can be mitigated by considering the opponent drones
as potentially hostile (the ’demon drone’ scenario). This approach ensures
that the ego drone adopts risk-averse strategies. At the same time, more
complex drone dynamics models are to be investigated to understand the gains
(in terms of e.g. reduction of model error) and losses (increased computation
complexity) of including more involved drone dynamics.

In addition to analyzing technical limitations, it will be crucial to consider
compliance with existing or future drone traffic regulations (e.g., European
regulations for airspace use, U-space), as well as priorities for different
types of drones. These rules will often imply more structured airspace, where
drones with specific functions or destinations will move in specific airspace
layers. They furthermore may involve priorities for specific functions.
Examples of how to include traffic rules in a differential game theoretical
approach to conflict resolution and interaction modeling can be found in [11].

##  7 Author contributions

The authors confirm their contribution to the paper as follows: study
conception and design: Hoogendoorn; simulation preparation and execution:
Hoogendoorn; data analysis and interpretation of results: Hoogendoorn, Knoop,
Mahmassani; draft manuscript preparation: Hoogendoorn, Knoop, Mahmassani,
Hoogendoorn-Lanser. All authors reviewed the results and approved the final
version of the manuscript.

## References

  * [1] Michiel JM Aarts, Joost Ellerbroek and Victor L Knoop  “Capacity of a constrained urban airspace: Influencing factors, analytical modelling and simulations”  In _Transportation Research Part C: Emerging Technologies_ 152 Elsevier, 2023, pp. 104173
  * [2] Christopher Cummings and Hani Mahmassani  “Emergence of 4-D System Fundamental Diagram in Urban Air Mobility Traffic Flow”  In _Transportation Research Record_ 2675.11 SAGE Publications Sage CA: Los Angeles, CA, 2021, pp. 841–850
  * [3] Christopher Cummings and Hani S. Mahmassani  “Comparing Urban Air Mobility Network Airspaces: Experiments and Insights”  In _Transportation Research Record_ , 2023  DOI: 10.1177/03611981231185146
  * [4] Christopher Cummings and Hani S. Mahmassani  “Measuring the Impact of Airspace Restrictions on Air Traffic Flow Using Four-Dimensional System Fundamental Diagrams for Urban Air Mobility”  In _Transportation Research Record_ 2677.1, 2023, pp. 1012–1026  DOI: 10.1177/03611981221103237
  * [5] Malik Doole, Joost Ellerbroek and Jacco Hoekstra  “Estimation of traffic density from drone-based delivery in very low level urban airspace”  In _Journal of Air Transport Management_ 88 Elsevier, 2020, pp. 101862
  * [6] Malik Doole, Joost Ellerbroek, Victor L Knoop and Jacco M Hoekstra  “Constrained Urban Airspace Design for Large-Scale Drone-Based Delivery Traffic”  In _Aerospace_ 8.2 Multidisciplinary Digital Publishing Institute, 2021, pp. 38
  * [7] Jack Haddad, Boris Mirkin and Kfir Assor  “Traffic flow modeling and feedback control for future Low-Altitude Air city Transport: An MFD-based approach”  In _Transportation Research Part C: Emerging Technologies_ 133 Elsevier, 2021, pp. 103380
  * [8] Dirk Helbing, Illés J. Farkas and Tamás Vicsek  “Freezing by heating in a driven mesoscopic system” Cited by: 374; All Open Access, Green Open Access  In _Physical Review Letters_ 84.6, 2000, pp. 1240–1243  DOI: 10.1103/PhysRevLett.84.1240
  * [9] J Hoekstra, RNHW Van Gent and R Ruigrok  “Conceptual design of free flight with airborne separation assurance”  In _Guidance, Navigation, and Control Conference and Exhibit_ , 1998, pp. 4239
  * [10] S. Hoogendoorn and P.H.L. Bovy  “Simulation of pedestrian flows by optimal control and differential games” cited By 203  In _Optimal Control Applications and Methods_ 24.3, 2003, pp. 153–172  DOI: 10.1002/oca.727
  * [11] S. Hoogendoorn, A. Gavriilidou, W. Daamen and D. Duives  “Game theoretical framework for bicycle operations: A multi-strategy framework” cited By 2  In _Transportation Research Part C: Emerging Technologies_ 128, 2021  DOI: 10.1016/j.trc.2021.103175
  * [12] S. Hoogendoorn, W. Daamen, Y. Shu and H. Ligteringen  “Modeling human behavior in vessel maneuver simulation by optimal control and game theory” cited By 11  In _Transportation Research Record_ , 2013, pp. 45–53  DOI: 10.3141/2326-07
  * [13] M. Liu, J. Zhao, S. Hoogendoorn and M. Wang  “A single-layer approach for joint optimization of traffic signals and cooperative vehicle trajectories at isolated intersections” cited By 12  In _Transportation Research Part C: Emerging Technologies_ 134, 2022  DOI: 10.1016/j.trc.2021.103459
  * [14] Marta Ribeiro, Joost Ellerbroek and Jacco Hoekstra  “Improving Algorithm Conflict Resolution Manoeuvres with Reinforcement Learning” Cited by: 1; All Open Access, Gold Open Access  In _Aerospace_ 9.12, 2022  DOI: 10.3390/aerospace9120847
  * [15] Marta Ribeiro, Joost Ellerbroek and Jacco Hoekstra  “Review of conflict resolution methods for manned and unmanned aviation”  In _Aerospace_ 7.6 MDPI, 2020, pp. 79
  * [16] Emmanuel Sunil et al.  “The influence of traffic structure on airspace capacity”, 2016
  * [17] Emmanuel Sunil, Joost Ellerbroek, Jacco M Hoekstra and Jerom Maas  “Three-dimensional conflict count models for unstructured and layered airspace designs”  In _Transportation Research Part C: Emerging Technologies_ 95 Elsevier, 2018, pp. 295–319