Richard Alligier
email: richard.alligier@enac.fr

David Gianazza
email: david.gianazza@enac.fr

Nicolas Durand
email: nicolas.durand@enac.fr

Xavier Olive
email: xavier.oliver@onera.fr

Dual-Horizon Reciprocal Collision Avoidance for Aircraft and Unmanned Aerial Systems

Keywords: Collision Avoidance, aircraft conflict resolution, self-separation, Optimal Reciprocal Collision Avoidance, Air Traffic Control, Unmanned Airborne Systems

The aircraft conflict detection and resolution problem has been addressed with a wide range of centralised methods in the past few decades, e.g. constraint programming, mathematical programming or metaheuristics. In the context of autonomous, decentralized collision avoidance without explicit coordination, geometric methods provide an elegant, cost-effective approach to avoid collisions between mobile agents, provided they all share a same logic and a same view of the traffic. The Optimal Reciprocal Collision Avoidance (ORCA) algorithm is a state-of-the art geometric method for robot collision avoidance, which can be used as a Detect & Avoid logic on-board aircraft or Unmanned Aerial Vehicles. However, ORCA does not handle well some degenerate situations where agents operate at constant or near-constant speeds, which is a widespread feature of commercial aircraft or fixed-winged Unmanned Airborne Systems. In such degenerate situations, pairs of aircraft could end up flying parallel tracks without ever crossing paths to reach their respective destination. The Constant Speed ORCA (CS-ORCA) was proposed in 2018 to better handle these situations. In this paper, we discuss the limitations of both ORCA and CS-ORCA, and introduce the Dual-Horizon ORCA (DH-ORCA) algorithm, where two time horizons are used respectively for short-term collision avoidance and medium-term path-crossing. We show that this new approach mitigates the main issues of ORCA and CS-ORCA and yields better performances with dense traffic scenarios.

Introduction

Automated conflict detection and resolution is a topic of major interest in the field of air traffic management [START_REF] Alligier | Constraint programming for air traffic management: a survey[END_REF]). The problem has been largely addressed from a centralized or decentralized point of view, using deterministic or stochastic algorithms and considering the problem from a strategical or tactical point of view.

Current research and advances around Urban Air Mobility (UAM), Unmanned Air Vehicles (UAV) and more generally Unmanned Airborne Systems (UAS) flying in the lower airspace lead researchers to study collision avoidance algorithms in order to separate UAS. The expected emergence in a near future of a large-scale, dense UAS traffic brings the focus on short-horizon self-separation methods in a multi-agent context.

Collision avoidance has been widely studied in the context of robots trajectory planning. Among the most efficient algorithms for multi-agent collision avoidance, the Optimal Reciprocal Collision Avoidance (ORCA) introduced (van den [START_REF] Van Den Berg | Reciprocal n-body collision avoidance[END_REF]) relies on a geometric approach where each agent modifies its velocity vector so that the relative velocity with any other agent falls outside the region where collision would occur in a given time horizon. This geometric approach is designed to guarantee conflict resolution for the next minutes in an autonomous manner, without explicit coordination among the agents. Provided all agents apply the same logic for the geometric algorithm and share the same view of the traffic situation (positions and velocities of the other agents), the maneuvers computed independently by each agent are implicitly coordinated.

Note that the term "optimal" in ORCA relates to the fact that the respective sets of collisionavoiding velocities from which two conflicting robots choose their optimal respective velocities are reciprocally-avoiding and maximal (see definition 1 in van den Berg et al ( 2011)): one cannot find a larger couple of velocity sets that is reciprocally-avoiding. With ORCA, the smallest change in the relative velocity is chosen so as to prevent collision in a given time horizon, and this relative velocity change is fairly shared among the two agents. However, ORCA does not provide optimal solutions in terms of overall trajectory deviations. In fact, it can be considered as a greedy heuristic: The relative velocity of each conflicting pair is chosen optimally at each time step in the set of conflict-free velocities, but without trying to minimize trajectory deviations over a whole time interval.

Although very efficient for robots which can modify their direction and speed at will, [START_REF] Durand | Constant speed optimal reciprocal collision avoidance[END_REF] showed that the ORCA algorithm has limitations for agents such as fixed-wing UAVs or aircraft that can only move at constant or nearly-constant speeds. The Constant-Speed Optimal Reciprocal Collision Avoidance (CS-ORCA) proposed by Durand showed improvements over the ORCA logic, with fewer pairs of flights ending on parallel paths without ever reaching their destination.

In this paper, we discuss the limitations of CS-ORCA and propose a further improvement on the ORCA and CS-ORCA algorithms. We introduce the Dual-Horizon Reciprocal Collision Avoidance (DH-ORCA) algorithm where a shorthorizon collision avoidance logic is complemented by a longer-horizon logic that helps agents to cross path with surrounding agents. We show that this dual-horizon logic provides improvements over the ORCA and CS-ORCA algorithms and has a significant impact on the residual separation losses and other safety and efficiency metrics.

We may expect that algorithms such as DH-ORCA could help tackle the problem of UAV Traffic Management in a safe, decentralized, autonomous way, even with the very large amounts of traffic expected in the near future. Such geometric algorithms are good candidates for possible airborne self-separation systems on-board commercial aircraft, or as the "Detect & Avoid" (D&A) logic envisioned for future Unmanned Aerial Systems.

After a short literature review on conflict detection and resolution methods in Section 2, we briefly discuss the context and the objectives of our study in Section 3. We then describe the ORCA algorithm in Section 4. The CS-ORCA variant is presented in Section 5, where its limitations are also discussed. Section 6 introduces the new dual-horizon method DH-ORCA. The experiment setup and traffic scenarios are presented in Section 7. Finally, the results are presented in Section 8, before the conclusion.

Literature Review

En-route conflict detection and resolution is currently managed by air traffic controllers who have a global view of traffic. They use a horizontal 2D representation of the traffic (a radar screen) and give different types of maneuvers (e.g. heading or flight level changes, small speed modifications) to maintain a minimum standard separation between aircraft. It has been known since the 90s that this task is highly combinatorial (see [START_REF] Granger | A traffic complexity approach through cluster analysis[END_REF] for a discussion on the subject). When more than two aircraft are involved, it is more efficient to consider the global situations than to solve conflicts by pairs. However, when the number of aircraft increases, a global approach may become too complex and autonomous algorithms can become a good alternative. Automatic conflict resolution methods can thus be divided in two categories: on one hand centralized approaches consider the whole situation and give instructions to every aircraft, on the other, autonomous approaches delegate the separation task to the different aircraft.

Centralized Approaches

Two types of centralized approaches can be found in the literature. In the first one, greedy methods [START_REF] Krella | Arc 2000 scenario (version 4.3)[END_REF]; [START_REF] Chiang | Geometric algorithms for conflict detection/resolution in air traffic management[END_REF]; [START_REF] Hu | Optimal coordinated maneuvers for three dimensional aircraft conflict resolution[END_REF]) use sequential algorithms to optimize trajectories one by one after ranking aircraft. The main challenge is then to find an appropriate ordering [START_REF] Archambault | Scheduling heuristics for on-board sequential air conflict solving[END_REF]). The second type of centralized approach considers the traffic situation as a global problem and tries to find a solution without prioritizing aircraft, using global optimization techniques such as evolutionary algorithms, mathematical programming, constraint programming, and making various assumptions on the traffic and/or the aircraft performances. [START_REF] Durand | Automatic aircraft conflict resolution using genetic algorithms[END_REF] showed that a genetic algorithm could efficiently solve multiple aircraft conflicts with simple maneuvers on real traffic data. The algorithm is all the more efficient when uncertainties on trajectory prediction can be reduced [START_REF] Alliot | A statistical analysis of the influence of vertical and ground speed errors on conflict probe[END_REF]). Other approaches used mathematical methods (semi-definite programming) [START_REF] Oh | Design and analysis of conflict resolution algorithms via positive semidefinite programming [aircraft conflict resolution[END_REF]; [START_REF] Frazzoli | Resolution of conflicts involving many aircraft via semidefinite programming[END_REF]), but solutions were only locally optimal, and the model required perfect trajectory prediction which is unrealistic. A perfect trajectory prediction was also used by [START_REF] Pallottino | Mixed integer programming for aircraft conflict resolution[END_REF][START_REF] Pallottino | Conflict resolution problems for air traffic management systems solved with mixed integer programming[END_REF] in the early 2000s in a mathematical model using Mixed Integer Linear Programming, which could be solved by CPLEX and ensure the global optimality of the solution. Christidoulou extended the model in 3D, but still required constant speed during climbing phases [START_REF] Christodoulou | Collision avoidance in commercial aircraft free flight via neural networks and non-linear programming[END_REF]). An improved version adding uncertainties to the trajectory headings was introduced by [START_REF] Gariel | 3d conflict avoidance under uncertainties[END_REF] in 2009 but all maneuvers needed to be executed at the same time. [START_REF] Omer | Hybridization of nonlinear and mixed-integer linear programming for aircraft separation with trajectory recovery[END_REF] introduced in the early 2010s a Mixed-Integer Linear Programming approach taking into account the trajectory recovery. Alonso-Ayuso et al (2016) used a Mixed Integer Non Linear Optimization model that also took the trajectory recovery into account. [START_REF] Peyronne | Solving air-traffic conflict problems via local continuous optimization[END_REF] introduced a trajectory model using unrealistic B-Splines trajectories and a semi-infinite programming formulation of the constraints. [START_REF] Rey | Complex number formulation and convex relaxations for aircraft conflict resolution[END_REF] recently proposed a new complex number formulation and convex relaxations for the centralized problem. [START_REF] Allignol | A new framework for solving en-route conflicts[END_REF] proposed to separate the model from the resolution algorithm. For each aircraft, a number of alternative trajectories and a matrix of pairwise conflicts were pre-calculated, taking various uncertainties into account, before the optimization process was performed. A similar approach was proposed by [START_REF] Lehouillier | Two decomposition algorithms for solving a minimum weight maximum clique model for the air conflict resolution problem[END_REF]. In [START_REF] Wang | Cooperation of combinatorial solvers for en-route conflict resolution[END_REF] different resolution methods were compared on the benchmark proposed in [START_REF] Allignol | A new framework for solving en-route conflicts[END_REF].

Autonomous Approaches

Autonomous approaches appeared in the 90s with the Free Flight debate motivated by Air Traffic Control cost reduction. The development of Unmanned Airborne Systems in the lower airspace recently gave a new interest to these approaches because the high traffic demand in the lower airspace [START_REF] Bulusu | Unmanned aviation: To be free or not to be free? a complexity based approach[END_REF]) might create dense situations that centralized approaches might not be able to handle, or at a greater cost. Sliding forces to coordinate maneuvers between aircraft [START_REF] Zeghal | A comparison of different approaches based on force fields for coordination among multiple mobiles[END_REF]) were one of the first autonomous approaches proposed in the late 90s. Potential or vortex fields [START_REF] Košecká | 2 1/2 d conflict resolution maneuvers for atms[END_REF]) as well as a model based on an analogy with electrical particle repulsion [START_REF] Eby | Free flight separation assurance using distributed algorithms[END_REF]) were also used. These algorithms took into account the aircraft speed constraints1 . For situations involving many aircraft, these approaches relied on the principle that forces or potential fields virtually generated by aircraft on each other would add up. There is no guarantee that this principle always leads to a conflict free solution. [START_REF] Eby | Free flight separation assurance using distributed algorithms[END_REF] inspired the Airborne Separation Assurance System (ASAS) approach developed by [START_REF] Hoekstra | Designing for safety: the 'free flight' air traffic management concept[END_REF]. ASAS used a Modified Voltage Potential (MVP) close to Eby's definition. It was tested in different contexts, such as the Mediterranean Free-Flight [START_REF] Ruigrok | Human factors evaluations of free flight: Issues solved and issues remaining[END_REF]). More recently, it was used to model airspace stability and capacity in a decentralized separation context [START_REF] Sunil | Modeling airspace stability and capacity for decentralized separation[END_REF]) and in a Capacity Assessment Model [START_REF] Sunil | Camda: Capacity assessment method for decentralized air traffic control[END_REF]). A geometric optimization approach solving complex situations by using an iterative process was proposed by [START_REF] Bilimoria | A geometric optimization approach to aircraft conflict resolution[END_REF] and used in the Future Air traffic management Concepts Evaluation Tool (FACET) project (D. [START_REF] Bilimoria | Facet: Future atm concepts evaluation tool[END_REF]). The Free-flight Autonomous and Coordinated Embarked Solver (Granger et al (2001b,a)) used a token allocation strategy to coordinate sequential maneuvers. Le [START_REF] Ny | Geometric programming and mechanism design for air traffic conflict resolution[END_REF] also used a geometric approach for scheduling crossing times of aircraft through a metering fix. [START_REF] Pallottino | Decentralized cooperative policy for conflict resolution in multivehicle systems[END_REF] proposed a model where coordination is ensured by protected stacking areas in which each aircraft can move without conflicting with other aircraft. The areas are headed to the flight destination. [START_REF] Schouwenaars | Decentralized cooperative trajectory planning of multiple aircraft with hard safety guarantees[END_REF] used a similar approach to plan safe trajectories in a decentralized way. Some approaches use a set of rules to coordinate the conflict resolution of multiple aircraft. For instance, D 'Amato et al (2020) use the Right of Way rules, as prescribed by the International Civil Aviation Organization (ICAO) for human piloted flights. This Right of Way rules creates constraints for each UAV. Then, considering these constraints, each UAV optimizes its own trajectory using constrained Model Predictive Control.

Geometric approaches using an implicit automated coordination were first introduced by van den [START_REF] Van Den Berg | Reciprocal velocity obstacles for real-time multiagent navigation[END_REF] with the Reciprocal Velocity Obstacles and then with the Optimal Reciprocal Collision Avoidance (ORCA) (van den Berg et al ( 2011)) algorithm used in the present paper. ORCA was initially built to simulate robots using self-separation logic in a 2D environment. In air traffic control, [START_REF] Snape | Navigating multiple simple-airplanes in 3D workspace[END_REF] have extended the model to the vertical dimension without segregating the horizontal and vertical maneuvers. More recently, geometric approaches have led to the definition of Solution Space Diagrams (SSD) that were used to analyze the dynamic of air traffic controller workload (d'Engelbronner et al (2015)) and were recently compared to the Modified Voltage Potential approach [START_REF] Balasooriyan | Multi-aircraft conflict resolution using velocity obstacles[END_REF] showing that the latter seemed to be more efficient in many situations. As opposed to ORCA which provides coordinated maneuvers for agents actively trying to avoid each other, SSD -which is actually a Velocity Obstacle (VO) algorithm with speed and turning rate constraints -does not provide coordinated maneuvers. In ORCA, a modification of the relative speed is computed for the considered pair of aircraft using a Reciprocal Velocity Obstacle (RVO). This relative speed modification is then split equally between the involved aircraft. In the Variable Responsibility ORCA (VR-ORCA) [START_REF] Guo | Vr-orca: Variable responsibility optimal reciprocal collision avoidance[END_REF]) the required relative speed modification is not shared equally, the relative speed modification is split between the two aircraft in order to minimize a cost function that takes into account all the aircraft visible by both aircraft.

ORCA maximizes the number of feasible velocities near the current speed vectors, whereas RORCA [START_REF] Wang | Repulsionoriented reciprocal collision avoidance for multiple mobile robots[END_REF]) maximizes the number of feasible velocities near the zero speed vector. It can be proved that the resulting speed constraints always contains the zero speed vector, ensuring a non-empty solution set for robots that can stop. Despite being useful for ground vehicles and multi-rotor UAVs, it does not provide useful guarantees for commercial air traffic or fixed-wing UAVs.

Durand ( 2018) highlighted an issue with the original ORCA algorithm when applied to commercial air traffic or fixed-wing UAVs flying at similar constant or nearly-constant speeds: aircraft could end-up flying parallel tracks without ever crossing paths to reach their respective destinations. In the same publication, they proposed a Constant-Speed ORCA algorithm (CS-ORCA) that can better handle these situations.

In this paper, we will discuss the limitations of CS-ORCA, then propose a new logic with two time horizons DH-ORCA that improves on ORCA and CS-ORCA.

Context and objectives

Potential context of application

Geometric algorithms such as ORCA, CS-ORCA, or the DH-ORCA algorithm introduced in this paper can be used in a variety of contexts, with different system architectures.

In a centralized architecture, the geometric algorithm could be implemented in a central computer with the positions and velocities of all traffic as input. The resulting modified velocity vectors would then be transmitted via data-link to the aircraft or UAVs. Using geometric algorithms in a centralized approach would be fast in terms of computation time, but less optimal in terms of overall trajectory deviations than global optimization methods such as the ones presented in the literature review.

Geometric algorithms are actually intended for a decentralized, autonomous approach. They could be of use either in the context of autonomous airborne separation assurance systems for commercial aircraft or in the detect & avoid logic that could be deployed in future Unmanned Airborne Systems. In such a context, each aircraft or UAV computes its own maneuvers on-board, and no explicit coordination among the agents is required. If the same ORCA logic is implemented aboard all agents, and if they all have the same view of the positions and velocities of the traffic, the velocity changes computed aboard each UAV or aircraft are implicitly coordinated (following the implemented logic) with the maneuvers of the other traffic. In other words, the resulting maneuvers are coordinated among all agents without passing or broadcasting any message.

This implies that all agents should apply the same logic, with the same look-ahead time (or time horizon) for the conflict detection. The time horizon parameter(s)2 should be pre-set before deployment. In section 7.5, we propose a method to tune these parameters, by choosing the values providing the best results on a set of random scenarios.

Handling the altitude

The original ORCA algorithm from van den Berg et al (2011) was initially designed for a 2Denvironment, to simulate robot collision avoidance. As will be detailed in section 4, it works by moving the 2D-vector of relative velocity outside a forbidden domain consisting of a blunt 2D-cone (see Fig. 1).

Aircraft and UAVs fly in a 3D-environment, and several ways have been proposed to adapt the 2D-ORCA algorithm to the 3D-space. The first one in Snape and Manocha (2010) considers a 3Dvector for the relative velocity and a blunt 3D-cone for the velocity obstacle -the head of the 3D-cone being a sphere around the other aircraft.

The second one in [START_REF] Alligier | Constraint programming for air traffic management: a survey[END_REF] uses vertical cylinders instead of spheres around the aircraft. Each cylinder has a circular basis of radius, the horizontal separation standard, and its height is equal to the vertical separation standard. This model is more consistent with the current operational notion of separation loss in aviation: two flights are not separated when their horizontal distance is closer than the horizontal separation standard, and when their vertical separation is less than the vertical separation standard.

In this paper, we will focus on 2D-separation in the horizontal plane exclusively, and introduce a dual-horizon algorithm that improves on ORCA and CS-ORCA when applied to constant-speed aircraft flying in a horizontal plane. The extension of this dual-horizon algorithm to 3D-space could be made as in [START_REF] Snape | Navigating multiple simple-airplanes in 3D workspace[END_REF] or [START_REF] Alligier | Constraint programming for air traffic management: a survey[END_REF], without difficulty.

Objective of this paper

The limitations of ORCA in the context of airborne separation come from the fact that the speed range and acceleration of commercial aircraft are small. Whereas robots can reduce their velocity at will and can even stop completely, fixed-winged aircraft and UAVs cannot reduce their speed below the stall speed otherwise they fall to the ground, and their upper speed is limited by their airframe structure and motorization. Actually, fuel-efficiency dictates to operate within much tighter bounds than that. In the ERASMUS speed control project [START_REF] Bonini | How erasmus can support an increase in capacity in[END_REF]), the speed modification range for the cruising speed was set to [-6%; +3%] around the nominal speed.

When applying the original ORCA algorithm with a limited speed range, conflicting aircraft flying on converging tracks at similar speeds may end up on parallel tracks, postponing the crossing of their paths for a very long time and potentially never reaching their destination.

The objective of the research presented in this paper is to propose a new algorithm for selfseparation in the horizontal plane that is less subject to the parallel-track issue than ORCA or its constant-speed variant CS-ORCA and that helps converging flights to cross paths.

As the final intended application is a decentralized autonomous system where each aircraft computes its maneuver without explicit coordination with the others, the algorithm must use only the information available to the own aircraft: typically, the direction toward its own destination and the positions and velocities of the other aircraft obtained through the on-board radar. In particular, we assume that the intended destination of the other aircraft is not known by the own aircraft.

In our traffic scenarios, we will focus on pathological cases where all aircraft or UAVs fly at constant speeds that might differ from one another, but only in a limited range. These scenarios are more prone to exhibit the parallel tracks' behaviour. We here describe these cases as pathological, in the sense that the original ORCA algorithm was not intended to handle them, but such situations may actually occur very often in real life, typically for commercial aircraft flying at similar speeds in the upper airspace. This is not necessarily the case for UAVs flying in lower airspace, as there are a variety of UAVs (fixed-wing, rotor, etc) having different speed and acceleration characteristics. Nonetheless, the self-separation logic of these UAVs should be able to handle conflicts involving UAVs with similar speeds, for safety and efficiency reasons, as such situations may actually occur in the dense traffic situations envisioned in the near future.

Optimal Reciprocal Collision Avoidance (ORCA)

This section describes the Optimal Reciprocal Collision Avoidance (ORCA) algorithm developed in van den [START_REF] Van Den Berg | Reciprocal n-body collision avoidance[END_REF] in the specific case where speeds are constrained. First, the maneuver model is detailed for an aircraft pair, then, the maneuver calculation is explained when more than two aircraft are involved in a conflict. As explained in section 3, we focus on selfseparation in the horizontal plane for aircraft flying at a same altitude, so ORCA and its variants are applied in 2D and provide lateral maneuvers only, in the form of velocity changes. We will assume in this paper that only the direction of the velocity can be changed: the velocity domain is a circular arc (see Fig. 2). All the algorithms presented hereafter can easily be extended to nonconstant speeds by considering a velocity domain that is a portion of a disc limited by the minimum and maximum speed and by the turning rate.

Separation Constraint Model for Two Aircraft

Let us consider two aircraft A and B, as illustrated in Figure 1.a. Let d be the required minimum separation and τ be a time horizon (also called look-ahead time, or anticipation in the literature).

Let us denote A and B the respective positions of aircraft A and B at the current time (here t = 0 by convention), and # » v A and # » v B their respective velocity vectors.

Assuming both flights continue on their current course, the future position of aircraft A relative to aircraft B at a future time t ≥ 0 is given by the vector

# » BA(t) = # » BA + ( # » v A -# » v B ) t = # » BA + #» v r t,
∈ [t 1 , t 2 ] # » BA(t) < d. This can only happen if #»
v r lies inside the cone which extremity is A and which sides are the tangents to the circle C(B, d) passing through A (in grey on the figure). In the case where #» v r lies outside this cone of extremity A -which is not the case in Figure 1.b -there will never be a separation loss. To summarize, the fact that #» v r lies inside or outside the full cone of extremity A allows us to detect if there is a conflict within an infinite time horizon τ = +∞, or not.

In order to detect conflicts occurring within a finite time horizon τ , let us now consider in Figure 1

.b the smaller circle C(B , d τ ) of radius d τ centered at B such that # » AB = # » AB τ
. This small circle and the tangents to the big circle The two semi-planes P τ B→A and P τ A→B constraining the velocities of A and B respectively can be formally defined as follows:

A B a. A two-aircraft encounter #» v A #» v B A B b. Conflict detection #» v A #» v B B ′ 𝛿 𝜏 𝛿 + 𝜏 𝛿 - 𝜏 𝑑 𝑑/𝜏 #» v r A B c. Geometric construction #» v A #» v B B ′ 𝛿 𝜏 𝛿 + 𝜏 𝛿 - 𝜏 𝑑 𝑑/𝜏 #» v r #» c 𝜏 #» c 𝜏 2 - #» c 𝜏 2 A B d. Conflict resolution B ′ 𝛿 𝜏 𝛿 + 𝜏 𝛿 - 𝜏 𝑑 𝑑/𝜏 #» v ′ A P B→A #» v ′ B P A→B #» v ′ r
# » B A + λ #» v r < d τ or # » BA + λτ #» v r <
P τ B→A := # » v A ∈ R 2 | # » v A -# » v A + #» c τ 2 . #» η τ ≥ 0 P τ A→B := # » v B ∈ R 2 | # » v B -# » v B - #» c τ 2 . #» η τ ≤ 0
In the above definitions, #» η τ denotes a unit vector perpendicular to the curve δ τ at the point #» v r + #» c τ , and pointing towards the outside of δ - τ . Using these equations, we can prove that:

∀ # » v A ∈ P τ B→A , ∀ # » v B ∈ P τ A→B , # » v A - # » v B -( #» v r + #» c τ ) . #» η τ ≥ 0
This equation guarantees that d). Note that the constraints P τ B→A and P τ A→B are always enforced, whether a conflict is detected or not between A and B. When no conflict is detected at the current time step, these constraints guarantee that the next velocities chosen for A and B remain conflict-free.

#» v r = # » v A - # » v B is out- side the red zone δ - τ (Figure 1.
In our description of ORCA, we have chosen to consider the reciprocal velocity obstacle for the relative velocity

#» v r = # » v A -# » v B
, considering B fixed, but we could have reversed the roles of A and B and considered the velocity obstacle for # » v B -# » v A , considering A fixed. This would have given exactly the same semi-planes and the same result. This computation can be made on a central computer deciding the maneuvers for both aircraft, but more interestingly it can also be made separately onboard the two aircraft, with each aircraft deciding of its own maneuver within its conflict-free semiplane. If both aircraft share the same view of the situation and apply the same logic, their maneuvers will be implicitly coordinated, without having to exchange messages.

Speed and Turn Rate Constraints

Track changes are the only possible maneuvers for the aircraft or fixed-wing UAVs considered in this study. The aircraft speed remains constant throughout the conflict resolution process. This can be expressed as the following constraints on the velocities of aircraft A and B:

# » v A = # » v A # » v B = # » v B
In addition, the turn rate of every aircraft is limited to a maximum value, which can be specific to each aircraft. In the current study, it was limited to 3 degrees per second for all aircraft.

With the above constraints, the new velocity assigned by ORCA to an aircraft must be chosen so that the head of the velocity vector is on an arc of limited range, centered on the current aircraft

A B #» v A #» v B B ′ 𝛿 𝜏 𝛿 + 𝜏 𝛿 - 𝜏 𝑑 𝑑/𝜏 #» v r #» c 𝜏 #» c 𝜏 2 - #» c 𝜏 2
Figure 2: Conflicting aircraft model: the effort is shared by the two aircraft. The new velocities must be chosen on the green portion of the arc. position (see Figure 2). The arc range is limited by the maximum turning rate. If the time step is set to 5 seconds, for example, the arc range is ±15 degrees for the standard turning rate (3 degrees per second).

Considering the separation constraints P τ B→A and P τ A→B presented in the previous section 4.1, we see in Figure 2 that the velocity vectors must be chosen in the green portions of the arcs, inside these semi-planes, in order to move the relative velocity vector outside the red blunt cone δ - τ while satisfying the speed constraints.

Multiple-Aircraft Separation Constraints

When an aircraft i is in conflict with more than two aircraft, the intersection of the semi-planar separation constraints P τ k→i with k = i creates a 2d polyhedral set C i . This 2d polyhedral set C i might be unbounded. This is the case for example in Figure 3 where A is conflicting with B and D. The conflict-free convex set C A for aircraft A is the intersection of the two semi-planes P τ B→A and P τ D→A .

The intersection of C i and the arc A i of possible turning angles for aircraft i (Section 4.2) defines an arc S i of admissible conflict-free velocities for aircraft i. If every aircraft selects its new velocity in this conflict-free arc, then no loss of separation will occur in the next τ seconds.

If, for a given aircraft i, the intersection of the semi-planes is empty, then every semi-plane is equally slightly moved until a non-empty intersection appears. The resulting convex C i does not guarantee a conflict-free maneuver anymore, but it remains close to the conflict-free domain. This

A B D # » v A # » v B # » v r B # » v D # » v r D P B→A P D→A

Summary of the ORCA algorithm applied to constant-speed aircraft

Algorithm 1 summarizes the ORCA algorithm applied to constant-speed aircraft (or UAVs). Time is discretized using a time step δt (see Table 1 in section 7.3 for the parameter values chosen in the experiments). As long as every aircraft has not reached its destination, every aircraft pair (i, j) is checked to calculate the semi-planes P j→i = P τ j→i and P i→j = P τ i→j . For every aircraft i, the convex C i is computed as the intersection of the semiplanes P k→i , with k = i. The admissible domain S i for the new velocity is then the intersection of C i and the arc A i of possible turning angles for aircraft i.

The new velocity #» v i is chosen as the closest vector to -→ v i pref in the admissible domain S i , where -→ v i pref is the preferred velocity vector for aircraft i, directed from the aircraft current position towards its destination.

Note that the admissible velocity domain S i can be empty for two reasons: either the convex C i is not empty but its intersection with A i is empty, or the convex C i is empty. In both cases, we select the new velocity #» v i that violates the constraints as little as possible. This is done by incrementally relaxing the constraints -as explained at the end of the previous subsection 4. 3 for every aircraft couple (i, j) do 3:

Define the semi-plane constraints P j→i and P i→j 4: end for 5:

for every aircraft i do

6: Calculate the convex intersection C i of every semi-planes C i = k =i P k→i 7:
Calculate the arc A i of possible aircraft i turning range.

8:

Calculate S i = C i A i 9:
Calculate the ideal velocity -→ v i pref 10:

Choose #» v i the velocity closest to -→ v i pref inside S i 11:
Change current velocity:

#» v i = #» v i 12:
Move aircraft i with current velocity #» v i 13:

end for 14:

increase current time t = t + δt 15: end while 5 Constant-Speed ORCA (CS-ORCA)

This section describes the Constant-Speed ORCA algorithm (CS-ORCA) introduced by Durand in [START_REF] Durand | Constant speed optimal reciprocal collision avoidance[END_REF]. This variant aims at correcting the pathological behaviour exhibited by the original ORCA algorithm when constant-speed aircraft converge at a small angle [START_REF] Durand | Does atm need centralized coordination? autonomous conflict resolution analysis in a constrained speed environment[END_REF]. In such cases, ORCA tends to postpone the conflict outside the time horizon τ , indefinitely, by setting the flights on parallel tracks.

We will first explain this behaviour in more detail in Section 5.1, then give a brief description of CS-ORCA (Section 5.2), before explaining in Section 5.3 why CS-ORCA does not completely solve the pathological cases it was designed to solve.

Pathological solutions where flights cannot cross paths

In Figure 1, we presented a conflict situation where #» v r lied deep within the forbidden zone δ - τ (the blunt cone in red), and the vector c τ computed by ORCA to move #» v r outside δ - τ was perpendicular to one of the cone sides.

Let us now consider Figure 4 showing a conflict in which the relative velocity #» v r is close to the circular part of the blunt cone δ - τ (in red). Such situations are more likely to occur at the beginning of a conflict.

A B d d/τ # » v A # » v B #» v r #» c #» c 2 - #» c 2 Figure 4:
Example where the tip of the relative velocity #» v r is projected onto the circular part of the reciprocal velocity obstacle (in red), leading to ORCA velocity constraints (semi-planes in green) that move the velocities of A and B apart, making them more parallel.

In such cases, the original ORCA algorithm computes a vector c τ joining the tip of #» v r to the closest point on the circular part of the frontier δ τ of the velocity obstacle. The direction of c τ is not perpendicular to either one of the cone sides, and the semi-planes defining the constraints for # » v A and # » v B -which are perpendicular to c τ -are not parallel to either one of the cone sides. They actually tend to move the velocities of A and B slightly apart. This move ensures that there will be no loss of separation within the next τ seconds. However, the conflict may reappear in the next time steps-and be solved in the same way-if the aircraft are still converging. This may typically occur when the aircraft must cross paths to reach their respective destination.

As a result, depending on the initial conditions, the two aircraft velocities tend to become parallel. Instead of solving the conflict by crossing the paths of the two aircraft, thus allowing them to reach their destination, the ORCA algorithm tends to postpone indefinitely the conflict outside the time horizon by setting them on parallel tracks. This is called the horizon effect in game theory.

The CS-ORCA algorithm

To deal with the problem described in the previous section, the semi-planes in CS-ORCA are computed differently than with ORCA, but the principle of the algorithm is the same. The finite time horizon τ is used to detect conflicts (i.e. future separation losses), exactly as in ORCA, by checking if the relative velocity #» v r lies inside the reciprocal velocity obstacle (the blunt red cone, on Fig. 4, with a circle of radius d τ at the head, and denoted δ - τ in Section 4.1). When no conflict is detected, i.e. when #» v r lies outside δ - τ , the semi-planes P τ A→B and P τ B→A are defined as in ORCA, by considering the orthogonal projection of the tip of #» v r onto the closest boundary of δ - τ . In this case, these semi-planes prevent from selecting new velocities that would lead to a conflict at the next time step. Depending on how #» v r is positioned outside δ - τ , the semi-planes P τ A→B and P τ B→A might be parallel to one of the straight sides of δ - τ , or parallel to a tangent to the round head of δ - τ . The difference between ORCA and CS-ORCA lies in how the semi-planes implementing the velocity constraints are computed when a conflict is detected, i.e. when #» v r lies inside δ - τ . This difference is illustrated in Figures 4 and5. Figure 4 shows how ORCA builds the semi-planes by projecting the tip of #» v r onto the closest boundary of δ - τ -which can be the round part at the head of the cone δ - τ , as in Fig. 4. Figure 5 shows how CS-ORCA builds the relative velocity deviation #» c by projecting the tip of #» v r onto the closest side of the full cone of extremity A, instead of the closest boundary of the blunt cone. Remembering from Section 4.1 that this full cone is in fact the reciprocal velocity obstacle corresponding to an infinite time horizon τ = +∞ 3 , we can denote P τ =+∞ B→A and P τ =+∞ A→B the semi-planes defined using this full cone δ - τ =+∞ . With these notations, the semi-plane implementing the constraint induced by aircraft B on the velocity of aircraft A can be mathematically summarized as follows for CS-ORCA:

A B d d/τ # » v A # » v B #» v r #» c #» c 2 - #» c 2
P CSORCAτ B→A := P τ =+∞ B→A if -→ v r ∈ δ - τ P τ =τ B→A otherwise
CS-ORCA is just Algorithm 1 with P i→j = P CSORCAτ i→j for all aircraft pairs (i, j) with i = j. As shown in Figure 5, with CS-ORCA the two aircraft turn left, as opposed to the choice made with ORCA in Figure 4. This allows both aircraft to reach their destination, without postponing the conflict beyond the time horizon.

Issue with CS-ORCA

Let us now explain why CS-ORCA does not always solve the pathological situations, exposed in section 5.1, that it was intended to solve. When aircraft have to cross one another, τ must be chosen large enough in order to avoid the parallel 3 One can also realize that by considering how the shape of δ - τ is modified when increasing τ to +∞: B moves to the position of A, and the radius of the round head of δ - τ tends to 0. (a) With τ = 1 min, CS-ORCA sets the two aircraft on parallel courses. The conflict is avoided, but the aircraft do not reach their destinations. Figure 6b depicts the first maneuver at t f irstman that led to this situation.

A B d/τ # » v A # » v B #» v r #» c #» c 2 - #» c 2 γ y x (b)
First maneuver performed at t f irstman , when -→ vr first enters the forbidden cone. Here, this happens when the aircraft are close. As a consequence, the cone angle is large. The resulting constraints (green semiplanes and arcs) tend to move the velocities toward parallel directions. The x and y directions are shown so that it is easier to relate this figure with Fig. 6a.

Figure 6: Example with τ = 1 min where CS-ORCA sets two aircraft on parallel tracks (Fig. 6a), by moving the velocities apart (Fig. 6b). Figure 6b is scaled to improve readability by choosing the minute as unit of time. This explains why B is here the center of both the circles of radius d and of radius d τ .

behaviour. To understand this, we can look at a situation with only two aircraft with the exact same speed converging at a small angle, as illustrated in Figure 6. If τ is too small, CS-ORCA chooses parallel tracks, the conflict is avoided, but aircraft do not

# » v A # » v B #» v r #» c #» c 2 - #» c 2 y x A d/τ # » v A #» v r #» c #» c 2 y x (b)
First maneuver performed at t f irstman . Here, the aircraft are far from each other when -→ vr first enters the forbidden cone. As a consequence, the cone angle is small. The resulting constraints (semi-planes and arcs in green) make both aircraft turn right, here increasing their relative closing speed, which helps them to cross paths. The x and y directions are shown so that it is easier to relate this figure with Figure 7a. reach their destinations as depicted in Figure 6a. As can be seen in Figure 6b, the first maneuver begins when -→ v r enters the forbidden zone δ - τ . With a small τ , aircraft are close when this happens.

As a consequence, the angle γ = 2 arcsin AB d made by the cone is large. Thus, the angle between the chosen semi-planes and -→ AB, equal to γ 2

, is large too. This results in constraints forcing a reduction of the velocity vectors' component along the vector -→ AB: the aircraft reduce their closing speed by making their velocities parallel, as plotted in Figure 6b.

Conversely, if τ is large enough, CS-ORCA makes them both turn right (or left), and both aircraft reach their destination as illustrated in Figure 7a showing the same example as in Fig. 6b, with a larger time horizon τ = 10 min. The maneuver begins when -→ v r enters the forbidden cone as depicted in Figure 7b. With a large τ , the aircraft are far from each other when this happens.

As a consequence, the angle between the chosen semi-planes and -→ AB is small, thus favouring maneuvers with a non-null closing speed and allowing aircraft to cross paths.

Ideally, one would want a large τ when aircraft have to cross one another, in order to avoid the parallel behaviour. When aircraft do not want to cross one another, a smaller τ would result in less restrictive constraints and be sufficient to avoid conflict efficiently.

6 Dual-Horizon ORCA (DH-ORCA)

We have seen in the previous section that CS-ORCA was initially meant to avoid the parallel behaviour when aircraft have to cross one another, but in order to work a large enough value of τ must be chosen. The drawback of having a large value of τ is that it will be used in all situations, even ones that do not require aircraft to cross paths. With a large τ , we have a loss of efficiency -as the constraints imposed on the velocity vectors are more restrictive than required -and with a small τ , the CS-ORCA algorithm exhibits the pathological behaviour we are trying to avoid.

With this in mind, we propose a new logic, called Dual-Horizon ORCA (DH-ORCA), with two time horizons. A small value τ conflict is used to enforce systematically the standard ORCA constraints. A larger value τ cross > τ conflict is used to enforce optional CS-ORCA-like constraints.

The optional constraint is enforced by an aircraft only when its preferred course towards its destination crosses the current trajectory of another aircraft, and is in conflict with it in the τ cross time horizon. Note that this logic does not require the aircraft to broadcast their preferred course to others: Each aircraft only needs its own intent to decide whether to enforce the optional constraint.

The DH-ORCA Constraints and Algorithm

The two constraints created by τ conflict , one for each aircraft, are always enforced. This guarantees that there will be no loss of separation within a time horizon τ conflict . These constraints are denoted P τ =τ conflict → . They are less restrictive than the P τ =+∞ → constraints of CS-ORCA.

The two constraints created by τ cross , one for each aircraft, are here to avoid the parallel behaviour and will be created using the cone side closest to -→ v r , as in CS-ORCA. Let us denote P τ =+∞ → these crossing constraints. Because the separation constraints P τ =τ conflict → created with the shortest time horizon τ conflict are sufficient to guarantee conflict-free trajectories-at least in the τ conflict time horizon-, the constraints created by τ cross are somewhat optional. In fact, each aircraft decides if it enforces or ignores the crossing constraint generated by the other.

Making the P τ =+∞ → constraint optional avoids to restrict the velocity choices when not necessary.

Here, the constraint will be enforced by an aircraft only when its preferred course towards its destination crosses the current trajectory of the other aircraft and if a loss of separation is predicted to occur in the τ cross time horizon when following this preferred course.

Let us denote Cross(A, B) this condition, allowing A to decide if it should enforce a P τ =+∞ B→A constraint because of aircraft B. This condition is expressed in the following equation, where d is the required minimum separation and -→ v A pref is the preferred velocity vector of aircraft A, directed toward its destination:

Cross(A, B) := ∃ t ∈ [0, τ cross ] s.t. -→ BA + ( -→ v A pref --→ v B ) t < d
Note that aircraft A assumes that B keeps following its current velocity vector -→

v B . Using -→ v B pref instead of -→ v B
would more accurately model a conflict between the intended paths of both aircraft, but would require aircraft B to share its intended velocity with A. Here -→ v B is used as a proxy of

-→ v B pref . If -→ v B is not close to -→ v B pref then Cross(A, B)
could be false despite aircraft A and B having to cross one another to go to their destination. Note also that the Cross(., .) criteria is not symmetric: Cross(A, B) might have a value different from Cross(B, A).

The constraint P τ =+∞ B→A generated by B is enforced by A if and only if Cross(A, B) is true.

The DH-ORCA constraints can be mathematically summarized as follows:

Geometrical Representation of the DH-ORCA constraints

A geometrical representation of the Cross(., .) criteria is also possible:

Cross(A, B) is true if and only if -→ v A pref --→ v B is inside the τ cross forbidden zone: -→ v A pref --→ v B ∈ δ - τcross .
Using the geometrical interpretation of this criterion, Figure 8 depicts the three possible cases for the P τ =+∞ → constraints:

1. Both aircraft ignore their P τ =+∞ → constraint as depicted in Figure 8a: only the classic constraints from ORCA with τ conflict are considered. This gives more freedom to the aircraft to modify their velocity. The new velocities are chosen as if only ORCA was used with τ = τ conflict . This case is typically encountered when the aircraft are far from each other, or when the direction of the preferred velocity of each aircraft diverges from the other aircraft's current velocity. 2. Only one of the two aircraft enforces the crossing constraint P τ =+∞ → , as depicted in Figure 8b: this crossing constraint is considered along with the classic ORCA-style separation constraints. See subsection 6.3 for a discussion on the effect of the asymmetrical enforcement of the DH-ORCA constraints. 3. Both P τ =+∞ → constraints are enforced as depicted in Figure 8c: Both aircraft must choose a velocity satisfying P τ =+∞ → . As a consequence, the new relative velocity #» v r shall fall outside the cone δ - τ =+∞ , allowing the aircraft to safely cross one another.

Discussion on the Asymmetry of DH-ORCA Constraints

When both aircraft enforce their P τ =+∞ → constraint, as on Figure 8c, both aircraft change their velocity vector to move #» v r outside the δ - τ =+∞ cone. The maneuver is equally split among the two aircraft and each aircraft do its part to avoid the other. If both aircraft do this, #» v r is guaranteed to be outside the cone δ - τ =+∞ and consequently no conflict will ever happen assuming all aircraft stay on their course.

In Figure 8b, where only one aircraft enforces its P τ =+∞ → constraint, we do not have such a guarantee: only one aircraft is actively maneuvering to avoid the other. However, it was experimentally observed that having only one aircraft maneuvering is sometimes enough to avoid the parallel behaviour. Roughly speaking, at each time step, the constrained aircraft takes half of the required speed change. It might not be enough to actually move -→ v r outside the δ - τ =+∞ cone, but it tries to move #» v r toward the edge of the cone: δ τ =+∞ . As aircraft are still far from each other, the enforced P τ =+∞ → constraint do not drastically reduce the aircraft's speed component along # » AB, thus avoiding the parallel behaviour. Furthermore, having -→ v r close to δ τ =+∞ somewhat pre-solves the crossing problem: as time goes by, -→ v r will eventually get inside δ - τ =τ conflict but as -→ v r is close to δ τ =+∞ , chances are that the minimal maneuvers to get #» v r outside δ - τ =τ conflict will be also maneuvers that get #» v r outside δ - τ =+∞ , allowing aircraft to cross one another.

Illustration of the Behavior of

ORCA, CS-ORCA and DH-ORCA on a simple example.

Let us consider the simple example shown in Figure 9a where 5 flights cruising at 230 kts at the same altitude must cross paths to reach their respective destinations. The separation standard d is 5 NM. The departure points (labeled "Start") are evenly spaced apart by a distance of 25 NM, as well as the arrival points (labeled "Goal").

When no Detect & Avoid algorithm is applied (Fig. 9a), all 5 aicraft fly directly to their destinations, but separation losses occur, with a total duration of 605 s.

A B d d/τ cross d/τ conflict # » v A # » v B #» v r #» c cross #» c conflict #» c conflict 2 - #» c conflict 2 P conflict B→A P conflict A→B -→ v A pref -→ v B pref -→ v r pref A -→ v r pref B
(a) In this example, the -→ vr pref are not inside the τcross forbidden zone, no P cross constraints are added.

- -

→ v B pref -→ v r pref B - #» c cross
→ v A pref -→ v r pref A #» c
→ v r pref A = -→ v A pref --→ v B and -→ v r pref B = -→ v A - -→ v B
pref . Reading from Figure 8a to Figure 8c, only the modified elements are labelled in order to improve readability. 4, no separation loss remains, whatever the chosen algorithm (ORCA, CS-ORCA, or DH-ORCA). However, we see that both algorithms ORCA (Fig. 9b) and CS-ORCA (Fig. 9c) exhibit the pathological parallel-tracks behavior described in section 5.1, whereas DH-ORCA does not (Fig. 9d)

Of course, we cannot draw general conclusions from this simple illustration and DH-ORCA does not guarantee that the pathological solutions will never occur. In the following, we will show experimentally in Section 8 that DH-ORCA drastically reduces the occurrences of pathological solutions when compared with ORCA and CS-ORCA on hours of random scenarios, described in next Section 7, especially for aircraft flying at the same speed.

7 Traffic Scenarios, Simulation, and Experiment Setup 7.1 Traffic Scenarios (Flight Plans)

In our experiments, we compare the different methods described in the previous sections on random traffic scenarios. We consider a circular area of chosen radius R. A new flight enters the area at a random location on the boundary, taken in the admissible domain determined by exclusion zones around the positions of the preceding flights, so as to avoid conflicting situations on entry. More precisely, as illustrated in Figure 10, we extrapolate the positions of the flights already in the area at the time t when the new flight is scheduled to enter the area, assuming each flight follows its initial straight route toward its destination. We then define a circular exclusion zone of chosen radius (greater than the separation standard d) around each extrapolated position. The admissible entry domain (in green on Figure 10) is obtained by removing the intersections between the outer boundary and the exclusion zones.

Let us denote ∆ entry the separation that we wish to enforce between an entering aircraft and the aircraft already in the area. To account for the fact that the traffic is simulated with a userchosen time step δt, the exclusion zones defined around the positions of these other aircraft must have a radius ∆ entry + V δt, where V is the speed of the entering flight. The additional margin V δt accounts for the fact that the entering aircraft actually enters the area at a time t start between t Once the entry point is chosen, the flight will follow a straight route at a random angle θ from the direction towards the center of the area (see Fig. 11). This random angle θ is drawn from a uniform distribution U ([-α, α]). The destination of each flight is the intersection of this straight route and the circular boundary opposite to the entry point. It can be easily shown that the average crossing distance of the circular area is 2R sin α α when α > 0 and 2R when α = 0.

The aircraft speed V is randomly chosen between a minimum value V min and a maximum value V max . We assume no wind.

The average crossing time is then 2R sin α α / V min + V max 2 .

In all random scenarios, the flight entry times follow a Poisson distribution of parameter λ (the desired average number of flight entries per unit of time). By definition of the Poisson distribution, the average number of flights entering the area over a given period of time T is λT and the variance of this number of entering flights is also λT .

We are interested in measuring some performance metrics at a given average traffic density. The traffic density is the number of aircraft or drones within the area at a given moment. This number depends on the inbound and outbound flows. Assuming the circular area is supplied in flights between t start and t end following the Poisson distribution, there will be a transition period at the beginning of the scenario, when the traffic density increases while the outbound flow remains at zero. After this transition period, the traffic density remains approximately stable -with some variations mainly due to the Poisson distribution of the inbound flow and also to the distribution of the crossing times -before decreasing after t end until it reaches zero at time t f , the end of the simulation. Figure 12 illustrates the typical evolution of the traffic density when the incoming flow follows a Poisson distribution, over a period of 24 hours.

To summarize, a scenario is characterized by several parameters: radius of circular area considered in the experiment, average number of flights entering the circular area per unit of time, duration of the scenario, upper and lower bounds for the ground speed, angle α defining the angular bounds for the route, radius ∆ entry of the exclusion zones for the entry conflicts.

Note that the scenarios are designed so that all flights reach their exit point before the end of the simulation t f when the flights follow their initial straight route as initially planned (when no D&A maneuver is performed).

Traffic Simulation with a Detect and Avoid (D&A) module

We have developed a small generic fast-time traffic simulator to execute the traffic scenarios and evaluate several detect and avoid algorithms such as the ones described in previous sections. Any D&A algorithm or conflict resolution algorithm can be easily plugged in the generic simulator to provide maneuvering instructions to the flights every δt seconds, where δt is the user-chosen time step of the simulation.

A D&A algorithm may modify the trajectory of a flight by changing the norm and/or the direction of its velocity at any time step of the simulation. However, in the current experiment, the norm is kept constant, and we only change the direction of the velocity vector. Note that whatever the trajectory modifications, the objective of a flight still remains to reach the exit point that was initially planned, so the D&A algorithm should at some point allow it to resume its navigation towards this exit point, unless it is unable to because of other traffic.

The random scenarios described in section 7.1 are designed such that no flight should conflict with others when entering the airspace, if all flights follow their initial route. When a D&A algorithm is used, some trajectories may be deviated to avoid conflicts. These modified trajectories may conflict with entering flights, with not enough anticipation for the D&A algorithm to find solutions to these conflicts. Such conflicts on entry are solved by the simulator by delaying the entering flight until it is separated from the other traffic by a distance greater than ∆ entry . These delays are measured during the simulations. A large amount of delay, as well as large trajectory deviations, will indirectly result in less flights reaching their destination before the end of the simulation. This will in turn result in a lower traffic throughput than with no D&A. The traffic throughput is measured by the throughput metric presented in Section 7.4.

Experiment Setup and Scenario Parameters

In this paper, some parameters will be the same for all scenarios. The values of these common parameters can be found in Table 1. The aircraft speed is constant during the simulation; only course changes are possible. However, each aircraft might have a different speed. Each aircraft speed is drawn in a uniform distribution U ([V min ; V max ]). Different speed ranges will be tested as the speed diversity has a great impact on the observed performance metrics. However, the speed ranges [V min ; V max ] will be chosen so that (V min + V max ) /2 is set to a constant value for all scenarios, so that the traffic density is not impacted by the choice of the speed range. This way, the traffic density is only controlled through the average number of flights entering the circular area per unit of time λ. We will use random scenarios with different values of this incoming flow λ in our experiments, as we want to test the algorithms on various traffic densities. Table 2 gives the values of λ tested in this paper as well as the measures of the traffic density and overall duration of separation loss for each of the three scenarios (low, medium, and high density). These metrics are measured without applying any D&A algorithm in order to characterize the difficulty of each scenario. The cumulated duration of separation loss is simply the sum over all flights of the time during which an aircraft was separated by less than the required minimum separation d from another aircraft.

Performance Metrics

Executing avoidance maneuvers during the simulation of a scenario has an impact on the traffic that can be measured through a number of metrics: number and/or duration of remaining separation losses, delays at entry, trajectory lengthening, number of flights not terminated-i.e. that could not reach their exit point before the end of the simulation because they were maneuvered-and distance remaining to be flown to destination for these flights4 .

In this paper, we propose to assess the performance of D&A algorithms through five metrics only: Two safety metrics measuring the duration and severity of separation losses respectively; Three efficiency metrics, the first measuring the total duration of the degenerate situations with parallel tracks not reaching their destinations, the second measuring the trajectory lengthening due to the D&A maneuvers, and the third the traffic throughput, which is directly related to the amount of delay assigned to entering flights.

Because we want to assess the D&A algorithms performances at a given average traffic density, these safety and efficiency metrics are measured only for the flights that are scheduled to enter the simulation in the time interval corresponding to the stationary regime of the scenario (see Figure 12). So we consider only the flights departing between t statio i = t i + T transition and t statio f = t f -T transition where t i and t f are the beginning and end times of the scenario with no detect and avoid, and T transition is the transition time at the beginning or at the end of the scenario. The other flights can be of use when computing some of the metrics, however. For example, a separation loss involving a flight in the selected list and another one that is not in the list will still be counted.

In our experiments, we have taken a transition time T transition = T max +2σ where T max = 2R V min and σ = √ λ T max , in order to be safely within the stationary regime interval.

The performance metrics used to assess the three methods (ORCA, CS-ORCA and DH-ORCA) on scenarios of low, medium and high traffic densities are listed below. The separation loss metrics and the one measuring the parallel tracks duration consider only the trajectory points in the stationary regime of each scenario. The trajectory lengthening metric considers only the trajectory parts starting after the beginning of the stationary regime. Most metrics are normalized so that we can compare their values on scenarios of various traffic densities.

• normalized LoS: This metric quantifies the duration of the separation losses. In order to avoid scenario-related variations, we normalize this total duration. The normalized LoS metric is the total duration of the separation losses observed in the simulation when using the evaluated D&A algorithm divided by the total duration of separation losses when no D&A algorithm is used. This can be summarized by the following formula, where LoS is the total duration of separation losses:

normalized LoS(scenario, algo) = LoS(simu(scenario, algo)) LoS(simu(scenario, without D&A))

• normalized LoS Severity: This metric quantifies the severity of the separation losses by considering the minimum distance min LoS dist between aircraft over all separation losses, and normalizing using the separation standard d (i.e. the minimum required separation). This metric is 0 when no separation loss occurs, and is otherwise computed using the following formula:

normalized LoS Severity(scenario, algo) = 1 -min LoS dist(simu(scenario, algo)) d

The closer to 1 this metric is, the worst the closest separation loss is. • normalized length: With this metric we quantify the trajectory deviations due to the D&A maneuvers. A simple way to do this could be to compute the ratio of the length of the actual trajectories over the length of the initial planned routes. However, for the flights that do not reach their destination before the end of the simulation, it makes no sense to measure the ratio between the length of the incomplete trajectory and the length of the initial planned route. Thus, we consider the distance between the last point of the flown trajectory and the destination, and add it to the length of the flown trajectory, before computing the ratio between this total length and the length of the planned route. This can be summarized by these formulas:

length(scenario, algo) = pref and A are on the same side of # » v B . The parallel total duration metric is the total duration of the parallel behavior observed in the simulation when using the evaluated D&A algorithm.

D&A Parameter Selection

Each D&A algorithm has parameters that we must calibrate before comparing the methods: the time horizon τ for ORCA and CS-ORCA and (τ conflict , τ cross ) for DH-ORCA. To select the best parameter values for each method, we perform a grid search: The best parameter value (or combination of values) is selected from a grid of values evaluated on a set of scenarios. For each D&A algorithm, each parameter is tested on 3 traffic densities with 20 random scenarios for each traffic density.

Table 3 gives the grid of values tested for each method. For DH-ORCA, note that we try all couples of parameter values such that τ conflict < τ cross .

D&A algorithm

Grid of parameters to be tested ORCA τ ∈ {212 When choosing the best parameter value(s), one wants to minimize both the separation losses normalized LoS and the trajectory length normalized length, with a higher priority on the safety metric. Considering Figure 13, we see that Figure 13: For the ORCA method, normalized length is plotted as a function of the normalized LoS. Each point is the result obtained by using ORCA with a specific τ value. Each point is obtained by computing the metrics average over the 20 × 3 calibration scenarios. The red point is the selected parameter value τ = 500 s for the ORCA method.

there is a trade-off to be found between the two conflicting objectives (safety and efficiency), when selecting the value of the time horizon parameter τ . This figure plots the normalized trajectory length as a function of the normalized separation loss duration, averaged over the 3 × 20 calibration scenarios, here for the ORCA method. Each point on this figure represents a parameter value from the selection grid.

As the primary objective is to ensure safety, we could simply select the value of τ minimizing the normalized LoS metric. However, we can see on Figure 13 that there is a range of τ valuesnear the y-axis -that perform very well in terms of safety, but show different performances in terms of efficiency.

In order to take also the efficiency criteria into account, we will select the τ parameter value having the minimum value of normalized length among all the τ -values for which the normalized LoS measure is less than 5% above the minimum normalized LoS. This 5% safety threshold is materialized, for ORCA, on Figure 13 by the vertical line close to the y-axis. This selection process is applied for all the time horizon parameters of the three D&A methods tested in this paper (ORCA, CS-ORCA and DH-ORCA).

As stated in section 5.3, when aircraft have to cross one another, a large τ is required to avoid the parallel behavior. In DH-ORCA, we have two horizons, one to avoid the parallel behavior (τ cross ) and one to avoid conflict (τ conflict ). As a consequence this allows τ conflict to be much smaller than τ cross and the τ values CS-ORCA. This interpretation seems to be confirmed by the best parameter values obtained with the grid search, shown in Table 4.

D&A algorithm

Best performing parameters ORCA τ = 500 s CS-ORCA τ = 308 s DH-ORCA τ conflict = 52 s τcross = 372 s The time horizon parameter values of Table 4 are the ones used in section 8 when comparing the three D&A methods (ORCA, CS-ORCA, DH-ORCA). Please note that the 3 × 20 scenarios used to select the time horizon parameter values are not used in section 8, where the performances of each method are assessed on new, unseen scenarios, using the metrics presented in section 7.4. This avoids any overly optimistic bias. To draw a parallel with Machine Learning, one can see these 3 × 20 scenarios as a training set to learn the time horizon parameters. Likewise, the scenarios used in Section 8 can be seen as the test set used to evaluate the performance with new traffic instances.

Note also that the time horizon parameter values found in this section are specific to the context of the current study, and that more realistic traffic conditions -with a different mix of aircraft speeds -might require another selection of these parameters before deploying the chosen D&A algorithm.

Results

Let us now compare ORCA, CS-ORCA and DH-ORCA on traffic scenarios of low, medium and high densities (see section 7.3 for a description of the scenarios). In subsection 8.1, we compare the three methods using a same aircraft speed distribution for all the scenarios. Then, in subsection 8.2, we examine the influence of the aircraft speed distribution on the results, considering several speed distributions. As we will see, these two scenario parameters (traffic density, speed distribution) have an impact on the results, although the performance ranking of the three methods remains the same.

For each tested traffic density and speed distribution, 100 random scenarios are simulated. For each simulation, we measure the performance metrics described in section 7.4. The 100 values obtained for each metric are summarized in a boxplot or by their mean value, depending on the considered figure.

The results were computed using only one core of an AMD Ryzen Threadripper 1920X. Computation time is not an issue for geometric D&A algorithms: For instance, it takes 355 s of CPU user time, on average, to simulate 6 hours of traffic using DH-ORCA with the largest incoming flow of 160 flights/hour. Out of these 355 s, the time spent computing the new velocities (i.e. the execution time of DH-ORCA) is 262 s.

Comparison on low, medium, and high traffic density scenarios

In this section, the aircraft speeds in all scenarios are drawn from a same uniform distribution U ([200 kts; 260 kts]).

Let us first see how the ORCA, CS-ORCA and DH-ORCA methods fare in terms of safety, considering the normalized duration of separation losses on Figure 14, and the severity of separation losses on Figure 15. We see that ORCA is the less safe among the three methods, showing the longest and most severe separation losses in all types of scenarios, whereas DH-ORCA outperforms both ORCA and CS-ORCA on these two safety metrics. results, with ORCA performing worst and DH-ORCA performing best among the three methods.

Figure 16 shows the total duration of the parallel tracks occurrences for the three methods. ORCA performs worst, by far. We also see that CS-ORCA does actually improve very significantly over ORCA on the parallel-tracks issue. DH-ORCA performs best, significantly improving over both ORCA and DH-ORCA. We will see in the next sub-section that the improvement is even more significant when the speed range is tighter. The left part of Figure 17 shows that the trajectory lengthening due to the D&A algorithm is really large for ORCA, and much smaller for CS-ORCA and DH-ORCA. This was expected, considering the issues that were raised in section 5.1 concerning ORCA when applied to aircraft flying at constant or near-constant speeds. The right part of Figure 17 zooms on the results of the two best methods, and shows a clear advantage for DH-ORCA.

The better performance of DH-ORCA on both the parallel tracks duration (Fig. 16) and the trajectory lengthening metric (Fig. 17) confirm that the dual horizon actually performs as expected, helping aircraft to cross paths more efficiently than with the two single-horizon methods.

The normalized throughput shown on Figure 18 is closely related both to the additional time spent by aircraft in the area due to maneuvering, and to the delays assigned to entering aircraft, due to other traffic maneuvering close to their entry point. Remind that the scenarios are designed such that no conflict occurs at entry when no D&A algorithm is used, but that delays may be assigned when a D&A algorithm modifies the trajectories. When the cumulated delays are important, this reduces the throughput of the system. We see on Figure 18 that both CS-ORCA and DH-ORCA are able to maintain a nearly constant throughput ratio, whatever the traffic density, whereas the throughput drastically decreases with the traffic density (which is controlled through the incoming flow) when ORCA is used.

Influence of the aircraft speed distribution

In all the scenarios in this paper, every aircraft flies at a constant speed: only course changes are possible. The individual aircraft speeds are drawn in a uniform distribution centered on a same average speed (see Table 1 in section 7.3). In the current section, we investigate the influence of the speed range of the uniform distribution on the results. As seen in Section 5.3, it may happen that the D&A algorithm solves a conflict by postponing it, setting the two involved aircraft on parallel courses. If the aircraft fly at different speeds, one will eventually overtake the other, and both aircraft will resume their navigation towards their respective destination. However, if they fly at the same speed, the relative position of the aircraft will stay the same: they are interlocked. This situation is more likely to occur when the speed diversity is low.

Let us now confirm that DH-ORCA actually mitigates this issue. When comparing DH-ORCA with CS-ORCA on a variety of speed ranges, DH-ORCA should perform better than CS-ORCA when the speed diversity is low. This is actually the case, as can be seen on Figures 19,20,21,22,and 23 showing the evolution of the metrics with the speed range. In these figures, the mean values of the metrics are plotted along with 95% confidence intervals for the estimated means.

Figures 19 and20 show that the trajectory lengthening and the parallel behavior total duration remain approximately constant with DH-ORCA, whatever the speed range, whereas with CS-ORCA they both dramatically increases when the speed diversity is low. Likewise, the throughput in Figure 21 is stable for DH-ORCA whereas it slightly drops for CS-ORCA as speed diversity decreases. We can conclude that he pathological behavior for aircraft flying at similar constant speeds-i.e. aircraft being set on parallel tracks-that occurred when using ORCA is still observed with CS-ORCA and the more so with low speed diversity. Although it still exists with DH-ORCA, this pathological behavior is significantly mitigated by the use of a dual horizon.

Concerning the safety metrics (duration of separation losses and separation loss severity), we see on Figures 22 and 23 that DH-ORCA consistently fares better than CS-ORCA on all traffic densities and speed ranges. On Figure 22, we can also observe that DH-ORCA is somewhat less sensitive to the speed diversity than CS-ORCA, in terms of conflict duration.

Looking at Figure 23, we can see that the remaining separation losses are less severe with DH-ORCA than with CS-ORCA for the normalized LoS Severity metric. Considering the evolution of the severity with the speed range, we see that the advantage of using DH-ORCA is even more apparent when aircraft fly at very similar speeds.

Conclusion

To conclude, we have seen that the original Optimal Reciprocal Collision Avoidance (ORCA) algorithm, initially proposed in van den [START_REF] Van Den Berg | Reciprocal n-body collision avoidance[END_REF] for robot collision avoidance, exhibits a pathological behavior when applied for Detect & Avoid purposes to aircraft or UAS flying at similar constant speeds. The Constant-Speed ORCA (CS-ORCA) variant of the algorithm introduced in Durand (2018) was designed as a way to solve this issue.

In the current paper, we have exposed why CS-ORCA might still exhibit the undesired behavior where two flights converging at a small angle might be set on parallel tracks by the algorithm, preventing them to cross paths to reach their respective destinations. We have shown that CS-ORCA is less subject to this issue when using a large value of the time horizon parameter τ . However, our results in section 8.2 show that this issue still remains when using CS-ORCA, even though we selected the τ value in section 7.5 to get the best possible results on the kind of scenarios considered in this study.

We have proposed a new algorithm Dual-Horizon ORCA (DH-ORCA) combining a shortterm ORCA-like logic with a longer-term CS-ORCA-like logic with optional constraints. In DH-ORCA, a relatively small time horizon τ conflict is used to enforce separation, and a larger time horizon τ cross is used to help aircraft (and/or UAVs) to cross paths. The optional constraints computed with the larger time horizon τ cross are designed so that each aircraft only requires its own intent to decide to enforce the constraint or not: There is no need for any aircraft to broadcast its destination to the others.

Our results show that DH-ORCA outperforms both ORCA and CS-ORCA on scenarios of various traffic densities. They also show that the gain in safety and efficiency of DH-ORCA is most important when the speed diversity is low, as expected.

The results of our study were obtained on traffic scenarios where all aircraft fly at similar, constant speeds, in order to make the undesired behavior described above more likely to occur. Aircraft flying at similar speeds within a very limited speed range is actually a common feature of the commercial traffic in the upper airspace, although these aircraft usually fly at greater speeds than in our study. In the lower airspace, the air traffic that we may envision in the future will probably also include a number of UAVs and/or aircraft operating at similar speeds-closer to the speed ranges of our scenarios-and for which a speed modification is either of very limited range (e.g., large fixed-wing UAVs) or costly in terms of energy budget (e.g., multi-rotor or hybrid UAVs).

So the Detect & Avoid logic that could be deployed in the future on these aircraft or UAVs should be safe and efficient in all situations, including when aircraft and/or UAVs flying at similar speeds converge at a small angle. We have shown that DH-ORCA can fulfill this objective with greater safety and efficiency than ORCA or CS-ORCA.

However, none of the geometric algorithms studied in this paper provides a formal guarantee to avoid the parallel tracks degenerate situations. Although they are much less likely to occur with DH-ORCA than with ORCA or CS-ORCA, these situations still happen in dense traffic and we cannot be sure they will never occur even with low traffic.

Further research could focus on finding an algorithm that would provide such formal guarantees. One could also examine the robustness of geometric algorithms such as ORCA or its variants CS-ORCA and DH-ORCA, and possibly other D&A logics, in more realistic operational conditions where all aircraft and/or UAVs might not share the exact same representation of the traffic, and might have slightly different implementations of the Detect & Avoid logic.

Figure 1 :

 1 Figure 1: Conflicting aircraft model: a loss of separation will occur within time τ if and only if the relative velocity #» v r lies in the red forbidden zone.

  d which means that A and B are in conflict at time λ τ ≤τ . Consequently, a conflict will occur within time τ if and only if #» v r lies in this zone δ - τ . Note that the reciprocal velocity obstacle δ - τ lies in the space of relative velocities. When a conflict occurs, it can be avoided simply by modifying the velocities # » v A and # » v B such that the relative velocity is moved outside the reciprocal velocity obstacle. The ORCA (Optimal Reciprocal Collision Avoidance) algorithm is based on the principle that the effort to keep #» v r outside the reciprocal velocity obstacle should be minimal and shared by the two agents A and B. In its original version, the necessary minimal relative velocity change, here denoted #» c τ , is split equally between the two agents, as shown in Figure 1.c. The vector #» c τ is simply obtained by connecting the tip of #» v r with its orthogonal projection on the closest boundary of the reciprocal velocity obstacle δ τ . The half-vector #» c τ 2 is added to # » v A in order to define a semi-plane P τ B→A perpendicular to #» c τ , and this same half-vector is subtracted from # » v B to define a semi-plane P τ A→B . Both semi-planes are shown in light green on Figure 1.c. If the new velocities # » v A and # » v B are chosen in the semi-planes P τ B→A and P τ A→B respectively, as illustrated in Figure 1.d, the new relative velocity #» v r falls outside δ - τ and the conflict is solved, at least for a time horizon τ and assuming both aircraft stay on their new course.

Figure 3 :

 3 Figure 3: Multi-Conflicting aircraft model: for aircraft A, a conflict will occur within time τ with aircraft B (resp. D) if and only if the relative velocity # » v r B (resp. # » v r D ) lies in the forbidden zone in red associated with aircraft B (resp. D).

Figure 5 :

 5 Figure 5: CS-ORCA velocity constraint model: the relative speed #» v r is now projected on the closest side of the cone instead of the circular part, only when #» v r is inside the forbidden zone (in red).

  With τ = 10 min, CS-ORCA makes both aircraft turn right, the conflict is avoided, and the aircraft reach their destinations. Figure7bdepicts the situation at t f irstman that explains this choice.

Figure 7 :

 7 Figure 7: Example with τ = 10 min where CS-ORCA makes both aircraft turn right and reduce their relative closing speed, allowing them to cross paths and reach their destination.

  pairs (i, j) with i = j.

  this example, -→ vr pref B is inside the τcross forbidden zone, P τ =+∞ A→B is added.

Figure 8 :

 8 Figure 8: Three examples with different preferred velocities are considered. They illustrate the three possible cases concerning the P cross constraints. Let us note -→ v r pref A = -→ v A pref --→ v B and -→ v r pref B = -→ v A --→ v Bpref . Reading from Figure8ato Figure8c, only the modified elements are labelled in order to improve

  ORCA algorithm is used, no loss of separation and two parallel behavior are observed on this simple scenario. CS-ORCA algorithm is used, no loss of separation and one parallel behavior are observed on this simple scenario. DH-ORCA algorithm is used, no loss of separation and no parallel behavior are observed on this simple scenario.

Figure 9 :

 9 Figure 9: An example in which the parallel behavior is observed with ORCA and CS-ORCA but not with DH-ORCA.

Figure 10 :Figure 11 :

 1011 Figure 10: Admissible domain for an entry point (in green), and exclusion zones around flights already in the area.

Figure 12 :

 12 Figure 12: Typical evolution of the traffic density in a random scenario where flight entry times are sampled from a Poisson distribution. The stationary regime is shown by the horizontal orange segment.

Figure 14 :Figure 15 :Figure 16 :Figure 17 :

 14151617 Figure 14: Normalized duration of the separation losses with aircraft speed randomly drawn in U ([200 kts; 260 kts]) for different incoming flows.

Figure 18 :

 18 Figure 18: throughput with aircraft speed randomly drawn in U ([200 kts; 260 kts]) for different incoming flows.

Figure 19 :Figure 20 :

 1920 Figure 19: Evolution of the parallel behaviour total duration with the speed range.

Figure 21 :Figure 22 :Figure 23 :

 212223 Figure 21: Evolution of the normalized throughput with the speed range.

  -until S i is not empty.

	Algorithm 1 ORCA algorithm, applied to
	constant-speed aircraft
	Input: simulation time step δt, time horizon τ ,
	and a scenario with the planned origin, destination,
	cruising speed and scheduled entry time of each air-
	craft
	Output: aircraft trajectories

1: while every aircraft has not reached destination do 2:

Table 1 :

 1 Common parameters for all scenarios

	Parameter Description

Table 2 :

 2 Low, medium, and high density scenarios. The traffic density is controlled by the value of the incoming flow parameter λ. LoS here means Loss of Separation.

Table 3 :

 3 Time horizon (τ ) values tested for each D&A algorithm.

Table 4 :

 4 Best values of the time horizon parameter(s) for each D&A algorithm. The τ -values are selected from the parameter grid shown in Table3, considering the average performance over 3 × 20 calibration scenarios.

When cruising, an aircraft can easily change its direction while respecting a maximum turning rate, but it can only slightly modify its speed, within a narrow speed range.

There is only one time horizon for ORCA and CS-ORCA, but the new logic we propose DH-ORCA uses two different time horizons.

Remember that a full simulation with the D&A off will show no delay and have all flights reaching their destination, although it will certainly have many separation losses, whereas with the D&A on we may expect much less separation losses, but some flights might be delayed at entry because of maneuvering aircraft, and some other flights might not reach their destination before the end of the simulation.

Declarations

• Funding The authors declare that no funds, grants, or other support were received during the preparation of this manuscript.