Sarah Degaugue
email: sarah.degaugue@enac.fr

Nicolas Durand
email: nicolas.durand@enac.fr

Jean-Baptiste Gotteland
email: jean-baptiste.gotteland@enac.fr

Impact of Explicit Memory on Dynamic Conflict Resolution

Keywords: Air Traffic Control, Conflict Detection And Resolution, Dynamic Evolutionary Algorithm

Due to uncertainties in weather conditions, trajectory prediction and constant flight evolution, controlling traffic in a sector is a dynamic problem. Furthermore, when the traffic increases, Air traffic control can become a complex dynamic optimization problem difficult to handle by human operators. In the context of offering air traffic controllers intelligent decision support tools adapted to the dynamic nature of traffic, we compare two options to address this issue. Previous work has already used an evolutionary algorithm to solve conflicts at given time steps. In this paper, we compare two different approaches using this evolutionary algorithm. The first one periodically calls an automatic solver, and the second one uses a memory method to guide successive resolutions. In order to choose the more adapted, we test them on different scenarios of continuous traffic. The memory approach can handle higher densities by maneuvering fewer aircraft and inducing lower delays. It is also more stable over time as early planned maneuvers are more likely to comply to effective maneuvers.

I. INTRODUCTION

Dynamic evolutionary optimization is an active research topic and has many applications in real world. Dynamic problems are problems that change over time. Dynamic Optimization Problems (DOP) are dynamic problems solved by an optimization algorithm. In real life, most DOP involve uncertainties where changes occur over time in the objective function, environmental parameters or constraints [1]. These different changes can have consequences in the objective function, on the optimium solution and its evolution.

Many dynamic optimization algorithms are based on the principles of Artificial Evolution. Evolutionnary Algorithms (EAs) belong to this class of algorithms because they are inspired by the theory of species evolution. However, an adapted Dynamic Evolutionnary Algorithm (DEA) have to be able to follow a changing optimal solution and needs to take advantage of information gathered in previous generations to speedup the optimization search, even if the environment changes quickly.

Air traffic conflict resolution in a control sector can be defined as a DOP. The problem evolves because aircraft enter or exit the sector, their positions evolve and their trajectory prediction constantly change with time, because of uncertainties on speed and maneuver executions. Air traffic controllers manage the traffic by taking decisions on trajectories at specific time while the situation is permanently evolving.

In the literature, DOP are either defined as a sequence of static problems linked by dynamic rules ( [START_REF] Weicker | An analysis of dynamic severity and population size[END_REF], [START_REF] Aragon | A evolutionary algorithm to track changes of optimum value locations in dynamic environments[END_REF], [START_REF] Rohlfshagen | Dynamic evolutionary optimisation: An analysis offrequency and magnitude of change[END_REF]), or as a problem that has time-dependent parameters in its mathematical expression ( [START_REF] Bosman | Learning and anticipation in online dynamic optimization[END_REF], [START_REF] Woldesenbet | Dynamic evolutionary algorithm with variable relocation[END_REF]). Generally in stationary optimization, the only goal of optimization algorithms is to find the global optimum as quickly as possible. However, in Evolutionary Dynamic Problem (EDP) research where the considered problems vary over time, the goal shifts from finding the global optimum to detecting changes and then tracking the evolution of optima (local optima or ideally the global optimum) over time. Additionally, in the case where the problem after the change somehow correlates with the problem before the change, an optimization algorithm should also learn as much as possible from its previous search experience to hopefully move forward search more efficiently.

A. Naive approches

A basic approach consists in restarting the EA when a change happens in the system environment. In the Rerandomization PSO (RPSO) described by Hu and Eberhard [START_REF] Hu | Adaptive particle swarm optimization: detection and response to dynamic systems[END_REF], the entire or a part of the swarm is randomly relocated in the search space when a change occurs. The principal risk of this approach is to lose information from previous research and, consequently, to slow down the convergence.

B. Implicit memory

Implicit memory approach calls on redundant representations in order to memorize some good solutions which may be reuse later (redundant representations are representations containing more information than necessary to define a phenotype). Whereas Goldberg and Smith introduced a triallelic scheme in 1987 [START_REF] Goldberg | Nonstationary function optimization using genetic algorithms with dominance and diploidy[END_REF], where an allele can take "0," "recessive 1," or "dominant 1" values, Ng and Wong proposed in 1995 a new diploid [START_REF] Ng | A new diploid scheme and dominance change mechanism for non-stationary function optimization[END_REF] scheme using a diploid scheme with four possible alleles ("0 recessive," "1 recessive," "0 dominant," and "1 dominant"). In their experiments, diploid scheme seem better than haploid or triallelic schemes.

C. Explicit memory

Explicit memory approach uses external memory to store past elements population that may be useful in future steps of the evolutionary process. Contrary to implicit memory, with explicit memory we know how and when the specific information stored will be reused in later generations. An explicit memory was introduced by Louis and Xu in 1996 [START_REF] Louis | Genetic algorithms for open shop scheduling and re-scheduling[END_REF] on an open shop scheduling or re-scheduling problem as an example. When a change occurs during the simulation, a part of elements from previous generations of the EA are reused, and the other chromosomes are randomly initialized. The main limit encountered is when the environment changes are too much significant. As an example, in their case, a deleted task had an important repercussion on new good schedules and it was much more efficient to build a new solution from scratch. A similar method employed a short-term memory in order to recall, when a change occurs, individual's ancestors that have been evaluated good in last generations [START_REF] Trojanowski | Searching for optima in nonstationary environments[END_REF]. In [START_REF] Trojanowski | Adding memory to the evolutionary planner/navigator[END_REF], authors add a local memory on each chromosome about their ancestors solutions. Their conclusion is linked to Louis and Xu's approach because it highlights the fact that the method efficiency is correlated with the nature of environment changes.

D. Multiple Population Approaches

Multiple population approaches use multiple subpopulations to track multiple peaks in the landscape. A popular design proposed in ( [START_REF] Oppacher | The shifting balance genetic algo-rithm: Improving the ga in a dynamic environment[END_REF]), called a shifting equilibrium genetic algorithm, deployed a base population to exploit the best optimum found so far and multiple colonies to explore the search space. A measure of diversity, distance from the main population, was included in assessments of colony fitness. Interesting results have been obtained by the self-organizing scouts proposed by Branker in 2000 [START_REF] Branke | A multi-population approach to dynamic optimization problems[END_REF]. This algorithm use a mother population to explore research space, whereas daughter populations follow local optima, over the objective function changes.

II. ORIGINAL EVOLUTIONARY ALGORITHM

In this article we deal with traffic in the horizontal plane and only accept one maneuver per aircraft. In order to comply with air traffic controllers behavior, our model takes into account uncertainties in trajectory prediction, which increase over time. Many realistic uncertainty models have been presented in previous work [START_REF] Allignol | A new framework for solving en-routes conflicts[END_REF], [START_REF] Allignol | Large Scale 3D En-Route Conflict Resolution[END_REF]. In this article we use a simplified version of uncertainty described in [START_REF] Durand | Visualizing complexities: the human limits of air traffic control[END_REF] that increases the size of the separation standard linearly with time.

A. Maneuvers

Time is discretized into steps of duration τ to describe maneuvers. τ is small enough to detect every conflict in the application (in the simulations, τ = 3 s, [START_REF] Barnier | Trajectory deconfliction with constraint programming[END_REF] discusses the topic).

In the trajectory model chosen, maneuvers are heading changes of α degrees, starting at time t 0 and ending at time t 1 . Heading changes α take values that are discretized by steps of 5 degrees in order to comply with air traffic controllers practice. α is relative to the current heading. Figure 1 summarizes a current Air Traffic Control maneuver which can easily be implemented by pilots and current FMS technologies (cf. [START_REF] Granger | Optimal resolution of en-route conflicts[END_REF]). Uncertainty is added to the model by increasing the separation standard linearly with time. Using such a growing norm is very convenient for quickly calculating the conflicting zone, but it can only model an isotropic growth of uncertainty. For example a 5% of the mean speed increase on the separation standard models a 5% speed uncertainty and a 3 • heading uncertainty.

B. Data

The EA used is similar to those described in [START_REF] Durand | Automatic aircraft conflict resolution using genetic algorithms[END_REF] and [START_REF] Durand | Optimal resolution of en route conflicts[END_REF]. It finds optimal maneuvers t 0 , t 1 , α for each aircraft of a scenario with the uncertainty model.

An example of a population element (chromosome) is given in figure 2 for a situation including n aircraft. Each value is coded by a positive float.

T0 1 𝜶 1 T1 1 T0 2 T1 2 𝜶 2 T1 n T0 n 𝜶 n chromosome Fig. 2: Structure of a chromosome
The algorithm receives as input the current time t c , the current flight plans of each aircraft, and their current maneuver (null if the aircraft is not maneuvered). If a maneuver has already started for an aircraft, its heading α and t 0 cannot be modified. However, if the end of maneuver t 1 is more than 60 seconds after t c , t 1 can still vary and will be optimized.

A lag (lag = 30 seconds in the experiments) was introduced to prevent any maneuver modification while the solver is optimizing the solution. For entering aircraft, another lag (lag b = 120 seconds in the experiments) was introduced. If t b is the entering time of an aircraft, a new maneuver cannot begin before t c + lag or before t b + lag b . This lag simulates the necessary time to take a new aircraft into account. We also make sure that the position at time t 1 allows an acceptable maneuver, i.e. a maneuver which respects the maximum turning rate toward the exit point. required (the 3 • per second standard rate was chosen).

The Evolutionary Algorithm chosen used is described in [START_REF] Durand | Automatic aircraft conflict resolution using genetic algorithms[END_REF]. An intelligent crossover operator is used to recombine the most promising maneuvers of each parent solutions. An intelligent mutation operator is also used to correct problematic maneuvers in the chromosome chosen for mutation. 100 generations are executed, the population is set to 150 elements. At each generation, 40% of the population is crossed and 40% of the population is muted. A σ = 2 truncation scaling is used and a simple sharing process is adopted to prevent convergence to local minimum. It divides the fitness of solutions that share the same characteristics by their occurrence numbers: two solutions share the same characteristics if they turn right or left or keep straight the same aircraft.

In the initial population and for both approaches, when a new maneuver is randomly defined, we chose to give one time out of 10 a direct route to the aircraft in order to favor solutions with the least number of maneuvers and shortest delay in the algorithm.

C. Fitness

The fitness function takes into account the four following criteria ranked by their criticality:

1) eliminate remaining conflicts (n conf the number of conflicts). Whenever a conflict remains, we try to delay it as late as possible because it could get a chance to be solved later. A parameter v tmin ∈ [0 : 1] measures the latest remaining conflict ; 2) minimize number of aircraft maneuvered (n man the number of maneuvered aircraft); 3) minimize delays caused by maneuvers (delay the sum of delays); 4) start maneuvers as late as possible (n b the sum of the differences between the maximum possible value of maneuver start t 0max and the actual maneuvering start t 0 ) : because of uncertainties, it is worth waiting as late as possible before maneuvering an aircraft. The EA first tries to eliminate every conflict, and then optimize trajectories resulting from maneuvers.

Finally, the resulting fitness of a chromosome is :

F = 1 1+n conf * v tmin if n conf > 0 1 + (n -n man ) + 1 1+2 * delay+n b else.

III. APPROACHES DESCRIPTION

In this section, we detail the two different approaches in order to continuously solve conflicts. The main difference between these approaches concerns the notion of memory defined in I-C.

A. Naive Approach (NA)

This approach is a naive version which launches the EA every ∆ s = 30 seconds. Maneuvers calculated by the solver are applied if they begin in less than 60 seconds, otherwise they are not sent to the aircraft because they may be applied at the next step.

B. Explicit Memory Approach (EMA)

With the Explicit Memory Approach, the idea is to keep information found from previous optimization to build new solutions. Unlike the Naive Approach, the EMA tries to build new solutions that are closer to the old ones. Indeed, after every resolution performed by the solver, we keep in an external file the last generation population in order to initialize the new population of the solver (∆ s = 30 seconds later). Only solutions that still comply with the current environment constraints are kept.

There are three main cases :

• A new aircraft arrived in the sector : a new maneuver allele will be randomly initialized and added for each population element ; • An aircraft left the sector : the corresponding maneuver allele will be removed from each population element ; • An aircraft has been maneuvered since the last EA optimisation : population elements which suggested another maneuver for this aircraft (a different t 0 or a different α for example), will have this maneuver allele randomly initialized with a maneuver which respects the new constraints (same t 0 and same α).

IV. EXPERIMENTS

In this section, the air traffic generation scenario is described and the criteria used to compare the two approaches are presented.

A. Exercise generation

In order to generate continuous random traffic scenarios with different conflicts configurations, we consider a circular sector of 50 nautical mile radius (about 15 minutes of flying time for an aircraft), with 14 possible entry points regularly positioned on its circumference.

For our tests, the number of aircraft in the traffic situations is regulated using a Poisson law with variable λ depending on the scenario. Each aircraft is randomly assigned:

• a nominal speed, randomly chosen between 370 and 550 knots; • its entry point, in a rectangular area of 10 nautical miles around one of the sector's entry points; • an exit point on the opposite side of the sector, in a slice extending by plus or minus 30 degrees around the opposite point on the circle. Initially, each aircraft flies directly from its entry point to its exit point.

However, in order to build conflict scenarios and avoid unmanageable traffic situations, a minimal duration of 4 minutes is required before the first conflict of an aircraft entering the sector.

Finally, different density scenarios using increasing values of λ (see table I) are compared with both approaches. Each scenario last 3 hours and 20 minutes (12000 seconds).

B. Comparison parameters

1) The first objective, included in the EA fitness function, is to solve all conflicts. Because we only included one flight level and strong restrictions on maneuvers (only heading change per aircraft), some situations become difficult to solve when the density increases. We first compare the number of unsolved conflicts in both approaches. 2) Second, we compare the percentage of aircraft maneuvered for both approaches. 3) Third, we compare the percentage of delay due to maneuvers for both approaches. 4) Fourth, we compare the number of conflict pairs detected by both approaches. Because both approaches lead to different decisions and thus different trajectories, the number of conflict pairs detected at the end of each scenario is different. 5) Fifth, we compare the number of maneuver heading changes : this happens when the solution calculated 30 seconds before contains a maneuver in the opposite direction compared to the new one. These elements will impact controllers reactions and appreciation of the tool if such a tool is used to help them make decisions : the more stable the resolution over time, the more acceptable and the less stressful it is for air traffic controllers.

The last item (maneuver heading changes) deserves to be more explained. For an aircraft in particular, there is a heading change if it is in one of the following situations at time t, with t + lag > t 0 and t -∆ s + lag < t 0 :

• at time t -∆, the aircraft had a heading change α to the right and at time t the aircraft has heading change to the left; • at time t -∆, the aircraft had a heading change α to the left and at time t the aircraft has heading change to the right; • at time t -∆, the aircraft had no heading change (α = 0) and at time t the aircraft has a heading change (α ̸ = 0);

V. RESULTS

Results from simulations on each scenario are transcribed in table II.

A. Remaining conflicts

There is a big difference between the two approaches on the number of unsolved conflicts. For low densities, both approaches solve all the conflicts. Remaining conflicts for low densities are probably caused by the lack of coordination when aircraft enter the sector. Some significant number of unsolved conflicts appear when λ ≥ 1.9 for the naive approach, whereas the memory version keeps a low number of unsolved conflicts for λ ≥ 3. The number of maneuvered aircraft is for all experiments smaller with the Explicit Memory Approach than with the Naive Approach. For low traffic densities, there are more than 30% more maneuvers with the NA than with the EMA. This ratio tends to decrease when the density increases, which is due to the fact that in high densities, every aircraft tends to be maneuvered. The percentage of delay per aircraft increases with the traffic density for both approaches. However there is a big difference between the two approaches : the EMA approach induces a smaller delay to aircraft. For λ = 3.5, the delay observed with the NA is 70% higher than the delay observed with the EMA. The percentage of reused alleles increases with traffic density. It can be explained by the fact that the higher the traffic density, the more maneuvering constraints there are. When aircraft started a maneuver they cannot change the maneuver start time or heading angle, this information is kept in the next generation. It would be interesting in further work to separately count these cases.

VI. CONCLUSION AND FURTHER WORK

In this article, we compared two approaches for conflict resolution in the evolving environment of a sector. Results globally show that an explicit memory approach is better than a naive approach in terms of number of maneuvers, delays, unsolved conflicts, conflict pairs and heading changes.

Indeed, the memory-based approach allows to keep the number of unsolved conflicts smaller for higher densities. It reduces significantly the number of maneuvered aircraft, which is a very important factor for building manageable solutions. The delays per aircraft during the simulations are also significantly reduced which probably impacts the number of conflict pairs. The percentage of heading changes measures the number of times a solution is drastically changed over time. It measures the stability of the solutions planned in advance. This percentage is also much lower with a Memory approach. A maneuver predictor should be as stable as possible if it were to be used as an aid for air traffic control. We can notice that on the average, 70% to 90% percent (according to the traffic density) of previous alleles are used in the memory process.

In future work, we should add a vertical dimension to the problem, which would make it more realistic and allow to explore a bigger range of maneuvers and higher densities of traffic.

Another memory approach could be imagined by keeping alive a population of solutions and picking regularly in this evolving population the best solution to decide the maneuvers to assign to aircraft. Sarah Degaugue is a PhD student at the École Nationale de l'Aviation Civile (ENAC). She graduated from ENAC as an engineer with a double master's degree in Operational Research (OR) in 2021.

Nicolas Durand is a professor at the École Nationale de l'Aviation Civile (ENAC). He graduated from the École Polytechnique de Paris in 1990 and from ENAC in 1992. He has been a design engineer at the Centre d' Études de la Navigation Aérienne (then DSNA/DTI R&D) from 1992 to 2008, holds a PhD in Computer Science (1996) and got his HDR (French tenure) in 2004.

Jean-Baptiste Gotteland is an assistant professor at the École Nationale de l'Aviation Civile (ENAC). He graduated from ENAC as an engineer in 1995, and received a PhD (2004) in computer science from the University of Toulouse.

Fig. 1 :

 1 Fig. 1: Maneuver model.

Fig. 3 :

 3 Fig. 3: Number of unsolved conflicts

Fig. 4 :

 4 Fig. 4: Percentage of maneuvered aircraft

Fig. 5 :

 5 Fig. 5: Delay (in %)

Fig. 6 :

 6 Fig. 6: Number of conflict pairs detected

Fig. 7 :

 7 Fig. 7: Percentage of heading changes

Fig. 8 :

 8 Fig. 8: Percentage of reused alleles

TABLE I :

 I Scenarios

	λ	Number of aircraft
	1.1	97
	1.2	102
	1.3	103
	1.4	105
	1.6	113
	1.9	123
	2.0	128
	2.5	136
	3.0	151
	3.5	161

TABLE II :

 II Results

	λ	Approach	Remaining conflicts	Percentage of	Delay	Conflict pairs	Percentage of
				maneuvered aircraft	(%)	detected	Heading changes
	1.1	EMA NA	0 0	46 62	2 3	101 114	26 37
	1.2	EMA NA	1 1	48 73	5 9	135 160	34 47
	1.3	EMA NA	0 0	49 66	3 5	126 143	32 43
	1.4	EMA NA	1 0	53 69	3 8	148 171	23 30
	1.6	EMA NA	0 0	53 73	5 8	194 204	16 37
	1.9	EMA NA	0 4	63 80	5 15	237 302	30 36
	2	EMA NA	0 6	60 84	5 14	235 332	27 48
		EMA	0	65	7	291	36
		NA	6	90	17	380	51
	3.0	EMA NA	3 7	80 91	11 19	455 525	31 46
	3.5	EMA NA	6 11	83 92	13 23	572 685	35 35