Supatcha Chaimatanan
email: supatcha@recherche.enac.fr

Daniel Delahaye
email: daniel@recherche.enac.fr

Marcel Mongeau
email: mongeau@recherche.enac.fr

Aircraft 4D trajectories planning under uncertainties

To sustain the rapidly increasing air traffic demand, the future air traffic management system will rely on a concept, called Trajectory-Based Operations (TBO), that will require aircraft to follow an assigned 4D trajectory (time-constrained trajectory) with high precision. TBO involves separating aircraft via strategic (long-term) trajectory deconfliction rather than the currently-practicing tactical (short-term) conflict resolution. In this context, this paper presents a strategic 4D aircraft trajectory planning approach aiming at minimizing interaction between aircraft trajectories for a given day. The proposed methodology allocates an alternative departure time, a horizontal flight path, and a flight level to each flight at a country and a continent scale. Uncertainties of aircraft position and arrival time on its curvilinear abscissa are taken into account in the 1 trajectory planning process. The proposed approach optimizes the 4D trajectory of each aircraft so as to minimize the interaction between trajectories. A hybrid-metaheuristic optimization algorithm has been developed to solve this large-scale mixed-variable optimization problem. The algorithm is implemented and tested with real air traffic data taking into account uncertainty over the French and the European airspace for which a conflict-free and robust 4D trajectory plan is produced.

Introduction

To ensure safety of aircraft traveling from an origin to a destination airport while minimizing delays and congestion, Air Traffic Management (ATM) system manages the air traffic to separate aircraft by some prescribed distance, noted N v for the vertical separation and N h for the horizontal separation. Current ATM regulations require aircraft operating in the terminal maneuvering area (TMA) 1 to be vertically separated by at least N v = 1,000 feet (ft) and horizontally separated by a minimum of N h = 3 nautical miles (NM). In the en-route environment, for aircraft operating up to (and including) FL2 410, the horizontal minimum separation is increased to 5 NM; for aircraft operating above FL 410, the vertical separation is increased to 2,000 ft [START_REF] Nolan | Fundamentals of Air Traffic Control[END_REF].

Aircraft are considered to be in conflict when these minimum separation requirements are violated. Such conflict situations would not necessary lead to a collision; however, it is a situation that controllers must avoid. One can consider that at any given time, each aircraft has a bounded and closed reserved block of airspace defined by a three-dimensional cylinder, as shown in Figure 1, in which other aircraft are not allowed to enter. Currently, the world's major ATM systems are being modernized in order to accommodate the increasing air traffic demand. The new ATM system will rely on a concept of Trajectory Based Operations (TBOs) which will focus more on managing each aircraft trajectory so as to adapt the airspace user's demand to the current airspace capacity. In this concept, an aircraft flying through the airspace will be required to follow a negotiated conflict-free trajectory, accurately defined in 4 dimensions (3 spatial dimensions and time). This 4D trajectory concept will significantly reduce the need of controller's intervention during the tactical phase. Therefore, a controller will be able to accommodate more flights in a given airspace at a given time.

In this paper, we propose a methodology to address such a strategic 4D trajectory planning at the country and continent scale. The proposed methodology separates aircraft trajectories by allocating alternative route, alternative flight level, and alternative departure time to each flight. Instead of trying to solve each conflict locally, we separate aircraft trajectory in the 3D space and in the time domain so as to minimize global interaction between them. The interaction is an indicator that defines a situation when two or more aircraft trajectories compete for the same space at the same period of time. This route, flight level, and departure time allocation problem is formulated under the form of mixed-integer optimization problem. The objective is to minimize interaction between aircraft trajectories.

As in reality, the aircraft may subject to external events such as wind, temperature, passenger delays, etc. These induce uncertainty on aircraft position and arrival time to a given point. To increase robustness to the 4D conflictfree trajectory, these uncertainty must be taken into account in the trajectory planning process. In this study, the proposed methodology takes into account uncertainty of aircraft position and in the time domain. A set of alternative 4D trajectories with minimum interaction are obtained through an optimization process that relies on a hybrid-metaheuristic optimization process. To our knowledge, no other research work addresses globally such a 4D strategic planning problem taking into account uncertainty in both 3D space and time domain for such large-scale problems (continental airspace).

The following section of this paper are organized as follows. Section 2 reviews previous related work on strategic trajectory planning problem. Section 3 presents the mathematical model of the 4D trajectory planning problem under uncertainty that we are considering. After that, a method to compute the value of the objective function under such uncertainties is detailed in section 4. In section 5, a resolution algorithm to solve this problem is discussed. Numerical results from computational experiments are presented in section 6. Finally, conclusions and perspectives are discussed in section 7.

Previous related works

Numerous researches on the ATM problem have been conducted in the past decades. We refer the reader interested by a survey on modeling and optimization in air traffic to the recent book [START_REF] Delahaye | Modeling and Optimization of Air Traffic[END_REF]. A survey on mathematical optimization models for air traffic management problems based on different air traffic management strategies is provided in [START_REF] Agustín | Mathematical optimization models for air traffic flow management: A review[END_REF]. A comparison of different optimization methods (deterministic and metaheuristic optimization approaches) used for ATM is provided in [START_REF] Lohn | A comparison of optimization approaches for nationwide traffic flow management[END_REF].

In the strategic planning (before takeoff) framework, aircraft trajectories can be separated by, for example, modifying the departure time of aircraft such as in [START_REF] Barnier | 4D -trajectory deconfliction through departure time adjustment[END_REF], [START_REF] Odoni | The flow management problem in air traffic control[END_REF], and [START_REF] Terrab | Strategic flow management for air traffic control[END_REF]. This method is effective since it absorb the delay on the ground without inducing extra fuel consumption. However, with increasing air traffic demand, significant delays still have to be assigned to a large number of aircraft to meet all airspace-sector and airport capacity constraints.

In [START_REF] Cafieri | Aircraft deconfliction with speed regulation: new models from mixed-integer optimization[END_REF] and [START_REF] Constans | Minimizing potential conflict quantity with speed control[END_REF], another idea to separate trajectories based on speed regulations is presented. This method is effective at the fine-grain level, however, it is irrelevant in the strategic trajectory planning context. Other strategies consider rerouting, or modifying the flight levels, or a combination of the above-mentioned methods, for example, in [START_REF] Gianazza | Separating air traffic flows by allocating 3D-trajectories[END_REF] and [START_REF] Barnier | Combining flight level allocation with ground holding to optimize 4D-deconfliction[END_REF]. In [START_REF] Bertsimas | The air traffic flow management problem with en-route capacities[END_REF][START_REF] Bertsimas | The air traffic flow management problem: An integer optimization approach[END_REF][START_REF]An integer optimization approach to large-scale air traffic flow management[END_REF] the authors show that the departure-time and alternative-route allocation problem is NP hard. However, these works propose improvements of air traffic at the airspace sector level but do not manage conflicts. In [START_REF] Oussedik | Reduction of air traffic congestion by genetic algorithms[END_REF][START_REF] Oussedik | Application de l'evolution artificielle aux problèmes de congestion du trafic aérien[END_REF], the authors focus on minimizing congestion in the airspace sectors by allocating to each flight optimal departure times and alternative routes using genetic algorithms (GA). Their results show that GA is very efficient in solving highly complex problems, however, it is not well adapted for the large-scale 4D trajectory planning problems that we are considering, due to excessive memory requirement intrinsic to population-based optimization algorithms.

The concept of 4D strategic deconfliction that aims to generate conflict-free trajectories for aircraft from origin to destination airports is introduced in the Innovative Future Air Transport System (IFATS) project [START_REF] Toebben | Innovative future air transport system: Simulation of a fully automated ATS[END_REF] and the 4 Dimension Contract-Guidance and Control (4D CO-GC) project [START_REF] Joulia | Aircraft 4D contract based operation: The 4DCO-GC project[END_REF]. In [START_REF] Chaimatanan | A methodology for strategic planning of aircraft trajectories using simulated annealing[END_REF][START_REF]Strategic deconfliction of aircraft trajectories[END_REF], preliminary studies on the optimization of individual 4D trajectories are presented. In these papers, optimal (conflict-free) 4D trajectories for individual flights are allocated by solving a combinatorial optimization problem using a non-population-based hybrid-metaheuristic optimization method. The numerical results presented in [START_REF]Strategic deconfliction of aircraft trajectories[END_REF] show advantages of the hybrid-metaheuristic optimization approach on ATFM problems. However, the discretization of the search domain (candidate departure times and trajectories) induces high combinatorics.

In [START_REF]A hybrid metaheuristic optimization algorithm for strategic planning of 4d aircraft trajectories at the continental scale[END_REF], the authors extend the works in [START_REF] Chaimatanan | A methodology for strategic planning of aircraft trajectories using simulated annealing[END_REF][START_REF]Strategic deconfliction of aircraft trajectories[END_REF] by introducing a method to consider uncertainties of aircraft position in the horizontal plane along the trajectory. The uncertainties are modeled as a disk around the nominal assigned position. Alternative route and departure time for each flight is obtained by solving a mixed-integer optimization problem through a hybrid-metaheuristic optimization algorithm. There exists several conflict detection and resolution methods. We refer the reader interested by a review of this subject to [START_REF] Kuchar | A review of conflict detection and resolution modeling methods[END_REF].

In this paper, we put forward the work presented in [START_REF]A hybrid metaheuristic optimization algorithm for strategic planning of 4d aircraft trajectories at the continental scale[END_REF]. In addition to the uncertainties in the horizontal plane, we also consider uncertainties of aircraft altitude during climb and descent phase. Moreover, we introduce a method to take into account uncertainty in the time domain. At least to our knowledge, no other research work is able to address robustness of the resulting conflict-free 4D trajectory in presence of uncertainty in the time domain for a large problem (e.g. national and continent size air-traffic). In addition, we describe a method to The interaction to adapted the interaction detection method presented in [START_REF]A hybrid metaheuristic optimization algorithm for strategic planning of 4d aircraft trajectories at the continental scale[END_REF] in order to take into account such uncertainties. We also improve the hybrid-metaheuristics optimization algorithm proposed in [START_REF]A hybrid metaheuristic optimization algorithm for strategic planning of 4d aircraft trajectories at the continental scale[END_REF] by introducing new neighborhood function and new local search steps. Finally, we prove the viability of the overall methodology on large-scale air traffic data on the European continent airspace (≈ 30,000 trajectories) including the traffic in the TMA.

Mathematical model

This section describes the proposed strategic trajectory planning methodology in a mathematical framework. More precisely, the strategic trajectory planning problem under uncertainties that we are considering can be presented as follows:

• We are given a set of flight plans for a given day associated with a nationwide scale or continent-scale air traffic.

• For each flight, i, we suppose that the following elements are known:

a set of possible routes;

a set of possible flight levels;

a set of possible departure times;

the features of the uncertainties of aircraft position and arrival time.

• The goal is to separate the given set of aircraft trajectories in both the three dimensional space and in the time domain by allocating an alternative flight plan (route, departure time, FL) to each flight so as to minimize the global interaction between trajectories.

Uncertainty model

To consider the uncertainty of aircraft position and arrival time, we characterize the uncertainty sets as follows.

Uncertainty of aircraft position in the horizontal plane

Consider an initial 4D trajectory planning specifying that an aircraft must arrive at a given horizontal point (x, y) at time t. Due to uncertainties, we shall assume that the real horizontal position, (x r , y r ), of the aircraft at time t can be in an area defined by a disk of radius R h (defined by the user) around (x, y), as illustrated in Figure 2. Let hx = (x r -x) and hy = (y r -y) denote the uncertainties of aircraft position in the x and the y directions respectively.

The vector of uncertainty of aircraft position in the horizontal plane, denoted h = { hx , hy }, must belong to the set:

U h := { h : h 2 ≤ R h } (1)
In other words, the possible locations of the aircraft at time t are the elements of the set: {(x r , y r ) :

(x r -x) 2 +(y r -y) 2 ≤ R 2 h }.
To ensure horizontal separation of aircraft subjected to such uncertainties, the protection volume has to be enlarged by a radius of R h as illustrated in Figure 2. Thus, the robust minimum separation in the horizontal plane, N r h , is defined as:

N r h := N h + R h ,
where N h is the (usual) minimum horizontal separation of the case without uncertainty.

Uncertainty of aircraft position in the vertical dimension

Aircraft position may be subject to uncertainty in the vertical dimension mainly when the aircraft is not in its cruise phase, e.g. climb, descent.We shall assume that during such a non-level flight phase, the real altitude, denoted z r , of the aircraft at a given time t lies in a bounded interval defined by an uncertainty radius R v (set by the user) which reduces strongly when the aircraft reaches its requested flight level. The uncertainty of aircraft position in the vertical dimension, noted v = z r -z, must therefore belong to the set:

U v := { v : | v | ≤ R v } . (2)
In other words, the possible altitudes of the aircraft during non-level flight phase at time t are the elements of the set:

{z r : z -R v ≤ z r ≤ z + R v }.
To ensure vertical separation of aircraft subjected to such uncertainties, the vertical separation requirement has to be enlarged by R v as illustrated in Figure 2. Thus, the robust minimum separation in the vertical dimension, noted N r v , is defined as:

N r v := N v + R v ,
where N v is the (usual) minimum vertical separation of the case without uncertainty.

Uncertainty of aircraft arrival time

In addition to the uncertainty in the 3D space domain, aircraft may be subject to uncertainty so that it arrives at a given position with a time error. Let t be the maximum time error (defined by the user). For simplicity, to implement the interaction detection scheme, we shall assume that t is chosen so that it is a multiple of the discretization time step t s . The real arrival time, noted t r , of aircraft at the same trajectory point therefore lies in the time interval: [t-t , t+t ]. The uncertainty of the arrival time, noted t = t-t r , must therefore belong to the set:

x, y, z R v N v possible aircra, posi-on x r , y r , z r R h N h
U t := { t : | t | ≤ t } . (3)
We refer the reader interested by the modeling of uncertainties to [START_REF] Chaimatanan | Planification Stratégique de Trajectoires D'avions[END_REF].

Interaction between trajectories

The concept of interaction has been introduced in [START_REF]A hybrid metaheuristic optimization algorithm for strategic planning of 4d aircraft trajectories at the continental scale[END_REF]. To measure the interaction between aircraft trajectories taking into account the above-mentioned deterministic-type uncertainties, let us first consider two trajectories A and B illustrated in Figure 3, and let P and Q be any pair of sample points on the trajectories A and B respectively. Then, we must check whether the minimum separations, N r h and N r v is satisfied, between every possible pair of points such as P and Q (pair-wise comparisons). Let t r P be the real arrival time of aircraft A at point P , and let t r Q be the real arrival time at point Q, therefore:

A B R h P R h Q N r h N r h
t r P ∈ [t P -t , t P + t ],
and

t r Q ∈ [t Q -t , t Q + t ], respectively.
A potential conflict between trajectories A and B, taking into account uncertainties, can occur when the three following conditions are satisfied for a certain pair of sample points, P and Q, from each trajectory:

• d h := (x P -x Q ) 2 + (y P -y Q ) 2 < N r h . • d v := |z P -z Q | < N r v . • [t P -t , t P + t ] ∩ [t Q -t , t Q + t ] = ∅, i.e. |t P -t Q | ≤ 2t .
When the above conditions are satisfied, we say that point P is in conflict with point Q taking into account the deterministic-type uncertainty. Figure 4 illustrates the four possible scenarios of arrival time of two aircraft to the same 3D space region. Remark that a potential conflict between P and Q can occur only in cases a) and case b) where

|t P -t Q | ≤ 2t .
Let us define further

C D (P, Q) =        1 if point P is in conflict with point Q taking into account the uncertainty 0 otherwise. (4)
We defined the interaction, denoted Φ D i,k (u), at point P i,k (u i ) to be the sum of all the conflicts associated to point P i,k (u i ):

Φ D i,k (u) := N j=1 j =i Kj l=1 C D (P i,k (u i ), P j,l (u j )),
where K j is the number of sampling points for trajectory j.

Let us now denote to be the uncertainty of aircraft positions and aircraft arrival times, and let U = U h × U v × U t be the uncertainty set, where U h , U v , and U t are defined by (1), (2), and (3) respectively. The robust interaction associated to the point P i,k (u i ) considering the deterministic-type uncertainty, denoted Φ D i,k (u), can be defined as:

Φ D i,k (u) = sup ∈U Φ i,k (u, ) (5)
With the above definitions, we can perform implicitly the supremum computation involved in equation ( 5). Indeed, one can straightforwardly check that we have

Φ D i,k (u) = N j=1 j =i Kj l=1 C D (P i,k (u i ), P j,l (u j )). t t Q t Q + t ! t Q ! t ! t t t P t P + t ! t P ! t ! t t P ! 2t ! t P + 2t ! t a) b) c) d) aircra) A aircra) B t Q t Q + t ! t Q ! t ! t Q t Q + t ! t Q ! t ! t Q t Q + t ! t Q ! t !

Trajectory separation maneuvers

In this section, we describe three possible trajectory separation maneuvers, that we are considering in order to generate alternative 4D trajectories that minimize the total interactions.

Alternative departure time

The departure time of each flight, i, can be shifted by a positive (delay) or a negative (advance) time shift denoted by δ i . The departure time, t i , of flight i is therefore t i = t i,0 + δ i , where t i,0 is the initially-planned departure time of flight i. Following common practice in airports, the set of possible values for δ i will be discrete.

Alternative trajectory design

A method to generate an alternative trajectory that we consider in the paper is described in [START_REF]A hybrid metaheuristic optimization algorithm for strategic planning of 4d aircraft trajectories at the continental scale[END_REF]. To generate an alternative route, we modify the (given) initial horizontal flight profile, using a set of virtual waypoints.

As detailed in [START_REF]A hybrid metaheuristic optimization algorithm for strategic planning of 4d aircraft trajectories at the continental scale[END_REF], we define for each flight i, a vector, w i , of virtual waypoints (our optimization variables) used to control the trajectory shape of flight i:

w i = (w 1 i , w 2 i , . . . , w M i )
, where M denotes the number of virtual waypoints that the user is allowed to introduce, where w m i = (w m ix , w m iy ) is the m th virtual waypoint of trajectory i, and where w m ix and w m iy are the normalized longitudinal and lateral components of w m i respectively. Figure 5, illustrates a possible alternative horizontal profile for a given trajectory constructed with M = 2 virtual waypoints.

Alternative flight level

We define another decision variable associated to each flight i: a flight-level shift l i . Therefore, the flight level, F L i , of flight i is given by:

F L i = F L i,0 + l i ,
where F L i,0 is the (given data) initially-planned flight level of flight i. Figure 6 shows a trajectory with two alternative flight levels. We shall denote by u i the components of u. It is a vector whose components are related to the modification of the i th trajectory, thereby our decision variable is: u := (δ, l, w).

Constraints

To minimize interaction between trajectories, we consider the following constraints:

Allowed departure time shift. Since it is not reasonable to delay or to advance departure times for too long, the departure time shift, δ i , is assumed to be limited to lie in the interval

[δ i a , δ i d ]. (6)
Common practice in airports conducted us to rely on a discretization of this time interval. Given the (user-defined) time-shift step size δ s , this yields N i a :=

∆ i :={-N i a .δ s , -(N i a -1).δ s , . . . , -δ s , 0, δ s , . . . , (N i d -1).δ s , N i d .δ s }. (7)
Maximum allowed flight-level changes. To limit the change of flight levels, the flight level shift is also bounded. The set, ∆F L i , of all possible flight-level shifts for flight i is:

∆F L i :=[F L i,0 -l i,max , . . . , F L i,0 -1, 0, F L i,0 + 1, . . . , F L i,0 + l i,max ], (8)
where l i,max is the (user-provided) maximum flight level shifts allowed to be allocated to flight i.

Maximal route length extension. The maximal route length extension should be limited so that it is acceptable by the airline. Let 0 ≤ d i ≤ 1 be the maximum allowed route length extension coefficient of flight i (model parameter to be set by the user). To restrain the route length extension, the alternative en-route profile of flight i must satisfy:

L i (w i ) ≤ (1 + d i ), (9)
where L i (w i ) denotes the normalized length of the alternative en-route profile determined by w i . The length L i (w i ) can be straightforwardly computed once the position of the waypoints (contained in the vector w i ) is known. Constraint can in fact be implicitly satisfied by restricting the set of possible waypoint locations (as will be described below). Allowed waypoint locations. As detailed in [START_REF]A hybrid metaheuristic optimization algorithm for strategic planning of 4d aircraft trajectories at the continental scale[END_REF][START_REF] Chaimatanan | Planification Stratégique de Trajectoires D'avions[END_REF], to limit the search space, to prevent undesirable sharp turns, and to restrain the route length extension, we bound the possible location of each virtual waypoint. To avoid sharp turns, the longitudinal position of the virtual waypoints should not be too close to each other.

Let W m ix be a set of all possible normalized longitudinal locations of the m th virtual waypoint on trajectory i. For each trajectory i, the normalized longitudinal component, w m ix , is set to lie in the interval:

W m ix := m 1 + M -b i , m 1 + M + b i . (10)
To obtain a regular trajectory, the normalized longitudinal component of two adjacent waypoints must not overlap, i.e.

m 1 + M + b i < m + 1 1 + M -b i ( 11
)
and hence the user should choose b i so that

b i < 1 2(M + 1) . ( 12
)
Let W m iy be a set of all possible normalized lateral locations of the m th virtual waypoint on trajectory i. Similarly, the normalized lateral component, w m iy , is restricted to lie in the interval:

W m iy := [-a i , a i ], ( 13
)
where 0 ≤ a i ≤ 1 is a (user-defined) model parameter chosen a priori so as to satisfy (9).

Objective function.

The objective is to minimize the total interaction between trajectories taking into account uncertainties. Therefore, the robust total interaction between trajectories, that we are minimizing, is:

Φ D tot (u) = N i=1 Ki k=1 Φ D i (u), ( 14
)
where N is the total number of trajectories.

To summarize, the strategic trajectory planning problem, based on deterministictype uncertainty set, can be represented by an interaction minimization problem formulated as a mixed-integer optimization problem as follows:

min u Φ D tot (u) subject to δ i ∈ ∆ i , i = 1, 2, . . . , N l i ∈ ∆F L i , i = 1, 2, . . . , N w m i ∈ W m ix × W m iy , m = 1, 2, . . . , M, i = 1, 2, . . . , N, (P3)
where Φ D tot (u) is defined by ( 14), and ∆ i , ∆F L i , W m ix , and W m iy are defined by ( 7), ( 8), [START_REF] Gianazza | Separating air traffic flows by allocating 3D-trajectories[END_REF], and ( 13) respectively.

Interaction detection method

The interaction between trajectories is measured using the method proposed in [START_REF]A hybrid metaheuristic optimization algorithm for strategic planning of 4d aircraft trajectories at the continental scale[END_REF][START_REF] Chaimatanan | Planification Stratégique de Trajectoires D'avions[END_REF]. To consider this deterministic-type uncertainty, one simply has to adjust the size of the (3D space) grid cells according to the (user-provided) robust minimum separation N r h and N r v (robust grid ). Then, to detect interactions, for each cell (I x , I y , I z , I t ) corresponding to each sampling point P i,k := (x P i,k , y P i,k , z P i,k , t P i,k ), one simply needs to check all the surrounding cells (in the robust grid) corresponding to the time period [t P -2t , t P + 2t ]. The algorithm used to compute the total interaction between N trajectories taking into account the deterministic-type uncertainty is described in detail in Algorithm 1.

Resolution algorithm

To solve the robust strategic 4D trajectory planning problem, we rely on the hybrid Simulated Annealing / Iterative Improvement Local Search (SA / IILS) algorithm proposed in [START_REF]A hybrid metaheuristic optimization algorithm for strategic planning of 4d aircraft trajectories at the continental scale[END_REF]. As we have introduced an additional decision variable, l i , to modify the flight level of any given trajectory i, some modifications to the neighborhood function are made as follows.

Consider a chosen flight i to be modified, we introduce here another userdefined parameter, noted P l , to control the probability to modify the flight level of flight i. This parameter P l must satisfy:

P w + P l ≤ 1,
where P w is the previously-defined (user-provided) probability to modify the location of waypoints. Finally, the probability to modify the departure time of Discretize the alternate trajectory i defined by ui into a sequence {P i,k } K i k=1 ;

4:

Initialize Φ D i (u) := 0;

5:

for k = 1 to Ki do (for each point P i,k of trajectory i)

6:
Initialize Φ D i,k (u) := 0;

7:

Compute the cell Ix, Iy, Iz, It corresponding to sample point P i,k ;

8: Compute Φ D i,k (u): 9:
for ix = Ix -1 to Ix + 1 do 10:

for iy = Iy -1 to Iy + 1 do 11:

for iz = Iz -1 to Iz + 1 do 12:
for it = It -2 t ts to It + 2 t ts do 13:

if ∃j = i such that j ∈ (ix, iy, iz, it) then

L:= list of all trajectory sample point in (ix, iy,

for l = 1 to length(L) do 16:

P := L(l);

17:

Check conflict, C := C D (P i,k , P ) using (4);

Φ D i,k (u) := Φ D i,k (u)
Φ D i (u) := Φ D i (u) + Φ D i,k (u); 30: end for 31: Φ D tot (u) := Φ D tot (u) + Φ D i (u); 32: Return Φ D tot (u).
Algorithm 2 Neighborhood function considering flight level shifts Require: probabilities P w , P l , trajectory i.

1: Generate random number, r := random(0,1); 2: if r < Pw then 3:

Choose randomly one virtual waypoint w m i to be modified.

4:

Choose randomly new w m ix from W m ix ;

5:

Choose randomly new w m iy from W m iy ; 6: else

7: if r < (Pw + P l ) then 8:
Choose randomly new flight level shift li from ∆F Li; Two additional local search algorithms to intensify the search on each particular trajectory in different solution spaces are introduced as follows:

Intensify the search in the Time Domain (TD). This local search module intensifies the search by modifying only the departure time of a given trajectory i. The algorithm repeats until a pre-defined number of local-search iterations is performed.

Intensify the search in the Flight-level Domain (FD). This local search module intensifies the search by modifying the flight level of a given trajectory i. If the change of flight level yields an improvement of the objectivefunction value, the module further intensifies the search on the current flight level by applying a local change from the neighborhood structure to trajectory i (using the PT local search of [START_REF]A hybrid metaheuristic optimization algorithm for strategic planning of 4d aircraft trajectories at the continental scale[END_REF]). The algorithm repeats until a pre-defined number of local search iterations is performed.

Numerical results

The strategic 4D trajectory planning methodology addressing the deterministic type uncertainty is implemented on an AMD Opteron 2 GHz processor with 128 Gb RAM. It is tested with the national-size and continent-size air traffic over the French and the European airspace.

National-size en-route air traffic

First, we test the proposed methodology on the full-day national-size en-route air traffic over the French airspace, involving 8,836 trajectories. Simulations are performed with different values for the parameters R h , R v , and t , defining the size of the uncertainty sets.

The parameter values chosen to specify the optimization problem are given 1. The parameter values specifying the resolution algorithm are empirically set and given in Table 2. The initial and final total interaction between trajectories, the computation time, and the number of iterations performed to solve the problems considering different levels of uncertainty are reported in Table 3 (the vertical uncertainty radius, R v , is used only when aircraft are climbing and descending).

The size of the uncertainty set affects the resolution time and the final total interaction between trajectories. When uncertainties are not considered (case 1), the algorithm reaches interaction-free solution in short computation time.When increasing the time uncertainty, the initial interaction increases significantly (cases 2, 4, 5 and 6), and the algorithm requires more computation time to converge. The algorithm reaches an interaction-free solution for the case 3. It solves up to 99.7% of the initial interactions in the remaining cases (2, 4, 5, and 6), within computation times that are still compatible in a strategic planning context.

Continent-size air traffic

To test the proposed methodology on continent-size air traffic, simulations were performed on the en-route traffic scenario as well as on traffic involving the TMAs. The data set is a full day of air-traffic over the European airspace on July 1, 2011. It consists of 30,695 trajectories simulated with optimal vertical profiles and with direct route However, due to the lack of data, alternative flight levels for these two continent-size instances are not available. To solve these problem instances, we limit the maximum flight level change, l i,max , to zero, for all flight i (l max = 0). The uncertainty of aircraft position in the TMA is not taken into account (R T M A h = 0, and R T M A v = 0), since during this phase of flight, aircraft are usually required to follow a given path with very high precision. The user-defined input parameters of the optimization algorithm are all set to the same values as those for the national-size en-route air traffic (Table 1), except for l max which is set to zero as explained above.

The user-defined parameter values specifying the hybrid SA / IILS algorithm to solve these problem instances are given in Table 2. The only difference with those for the national-size instance (Table 2) is that the number of iterations at each temperature step is increased from 200 to 4,000, P l is set to zero, and P w is consequently increased from 1/3 to 1/2.

The initial and final total interaction between trajectories, and the computation time to solve the problem considering different levels of uncertainty are reported in Table 4. Although the trajectories can be separated only by modifying the horizontal flight profile and the departure time of each flight, the resolution algorithm finds an interaction-free solution, taking into account uncertainty of aircraft positions, for both problem instances in cases 3 and 6. When time uncertainty is considered (case 2 and 5), there remains less than 15% of the initial interaction between trajectories. This could be improved by introducing more degrees of freedom to the solution space, e.g. alternative flight levels, or speed regulation in the TMA. The most remaining interactions are located in the TMA. In compare with the methodology proposed in [START_REF]A hybrid metaheuristic optimization algorithm for strategic planning of 4d aircraft trajectories at the continental scale[END_REF], the methodology proposed in this paper yields solution that is more robust to uncertainties in the vertical and in time domain.

Conclusions

In this paper we have presented a methodology to consider uncertainty of aircraft position and arrival time in the strategic 4D trajectory planning process. The uncertainties have been modeled with deterministic sets. The algorithm therefore tries to minimize the interaction between trajectories considering all possible scenario implicitly described by the uncertainty sets (worst-case approach). The algorithm developed for the case without uncertainty was adopted via a modification of the way the objective function is evaluated. The modified algorithm was tested on national-size and continent-size air traffic. It was able to find interaction-free solutions for some uncertainty set sizes. There remains less than 15 % of the initial interactions when the size of the uncertainty set is larger.

The level of uncertainty to be considered is a trade-off between the desired robustness of the solution obtained and the associated trajectory modifications costs, to be decided by the user. Considering too important uncertainty in strategic planning will, indeed, results in a lost of capacity, since large portions of airspace have to be cleared for a given aircraft for a long period of time. Instead, the user can consider lower uncertainty levels, and iteratively solve the remaining interactions during pre-tactical and tactical phases.

When the traffic in the TMA is included, result may be improved by adding speed control variable in the state space to reduce interaction in such area which is not the case in the above-presented algorithm (in all benchmark with TMA, the remaining interaction are mainly located in such area).

Figure 1 :

 1 Figure 1: The cylindrical protection volume

Figure 2 :

 2 Figure 2: Possible aircraft position in the 3D space domain in presence of deterministic uncertainty.

Figure 3 :

 3 Figure 3: Evaluating the interaction between two continuous trajectories A and B in presence of deterministic-type uncertainty.

Figure 4 :

 4 Figure 4: Possible scenarios of arrival time of two aircraft to the same 3D space region.

Figure 5 :

 5 Figure 5: An alternative horizontal profile for a given trajectory, i, constructed with M = 2 virtual waypoints.

Figure 6 :

 6 Figure 6: Two alternative vertical profiles for a trajectory (two alternative flight levels).

3. 4 Mixed-integer programming formulation 3 . 4 . 1

 4341 Decision variables.Let us set the compact vector notation:δ := (δ 1 , δ 2 , . . . , δ N ), w := (w 1 , w 2 , . . . , w N ),and l := (l 1 , l 2 , . . . , l N ).

  slots of flight i. Therefore, we define the set, ∆ i , of all possible departure time shifts of flight i by

Algorithm 1

 1 Interaction computation algorithm in presence of deterministic-type uncertainty Require: value of the decision variables u = (δ, l, w), and the time sequence of 3D robust grids (taking into account the N r h and N r v minimum separations. 1: Initialize Φ D tot (u) := 0; 2: for i= 1 to N do (for each trajectory i) 3:

10 :

 10 Choose randomly new departure time shift δi from ∆i; 11: end if 12: end if flight i is 1 -(P w + P l ). The new neighborhood function considering flight level shifts is summarized in Algorithm 2.

Table 1 :

 1 Chosen (user-defined) parameter values specifying the robust optimization problem for the national-size air traffic.

	parameter	value
	t s	20 seconds
	δ s	20 seconds
	-δ i a = δ i d := δ 120 minutes
	d i	0.20
	l i,max := l max 2
	M	3

Table 2 :

 2 Empirically-set (user-defined) parameter values of the resolution methodology to solve the national-size air traffic.

	parameter	value
	Number of iterations at each temperature step, N I 200
	Initial rate of accepting degrading solutions, τ 0	0.3
	Geometrical temperature reduction coefficient, β	0.99
	Final temperature, T f	(1/500).T 0
	Inner-loop interpolation sampling time step, t interp 5 seconds
	Probability to modify horizontal flight profile, P w 1/3
	Probability to modify flight level, P l	1/3
	Threshold value, Φ τ	0.5 Φ avg
	in Table

Table 3 :

 3 Initial and final total interaction between trajectories for the nationalsize air traffic, considering different dimensions for the uncertainty set (the vertical uncertainty radius, R v , is relevant only when aircraft are climbing or descending).

	case uncertainty set	initial	solved	CPU	no. of
	dimensions	Φ D tot	interactions time (minutes) iterations
	R h = 0 Nm.
	1 R v = 0 feet.	83,044	100.0 %	18.3	18,259
	t = 0 s.
	R h = 0 Nm.
	2 R v = 0 feet.	2,282,436	99.7%	1,093.8	1,083,215
	t = 180 seconds.
	R h = 1 Nm.
	3 R v = 100 feet.	765,448	100.0%	101.1	97,400
	t = 60 seconds.
	R h = 1 Nm.
	4 R v = 100 feet.	1,425,384	99.7%	1,809.0	1,791,000
	t = 120 seconds.
	R h = 1 Nm.
	5 R v = 100 feet.	2,821,706	98.7 %	2,213.3	2,191,970
	t = 240 seconds.
	R h = 2 Nm.
	6 R v = 100 feet.	5,000,430	97.9%	2,289.8	2,266,956
	t = 240 seconds.

Table 4 :

 4 Initial and final total interaction between trajectories for the continentscale air traffic with different dimensions for the uncertainty set.

	case	traffic	uncertainty	initial	solved	CPU time	no. of
		scenario set dimensions	Φ D tot	interactions (minutes) iterations
		only	R h = 0 Nm.
	1	en-route R v = 0 feet.	142,144	100.0 %	43.1	49,000
			t = 0 s.
		only	R h = 3 Nm.
	2	en-route R v = 200 feet. 5,142,632	87.7 %	2,756.2	2,728,776
			t = 60 s.
		only	R h = 3 Nm.
	3	en-route R v = 200 feet. 430,234	100.0 %	347.6	345,528
			t = 0 s.
			R h = 0 Nm.
	4 with TMA R = 0 feet.	235,632	100.0 %	478.1	473,345
			t = 0 s.
			R h = 0 Nm.
	5 with TMA R v = 0 feet.	3,874,402	85.5 %	2,652.1	2,625,714
			t = 120 s.
			R h = 3 Nm.
	6 with TMA R v = 200 feet. 487,698	100.0 %	578.4	572,648
			t = 0 s.

A terminal control area (also known as a terminal maneuvering area) is a controlled airspace surrounding major airports, generally designed as a cylindrical or up-side-down wedding-cake shape airspace of 30 to 50 mile radius and high of 10,000 feet.

Flight level (FL) is a pressure altitude, expressed in hundreds of feet, e.g. and altitude of

32,000 feet is referred to as FL 320.

Acknowledgment

This work has been supported by 4 Dimension Contract Guidance and Control (4D CO-GC) project, and by the French National Research Agency (ANR) through JCJC program (project ATOMIC n • ANR 12-JS02-009-01).


"A linguistic approach to David Mitchell's science-fiction stories in Cloud Atlas" Sandrine Sorlin Aix-Marseille University, LERMA / IUF Style is not specific to an author but to a particular narrative. Nobody shows this better than David Mitchell in Cloud Altlas published in 2004. This novel is composed of six different stories linked by a diegetic thread but set at different times, from the 19 th century to a distant post-apocalyptic future. These six stories have stylistic, rhythmic, semantic and grammatical structures of their own, perfectly suited to their content matter. The reader just has to follow the rhythm to take a plunge in the atmosphere of the narrated story. In other words, Cloud Altlas seems to illustrate a truism: the same language can create different worlds. However, it must be acknowledged that David Mitchell is more than "using" language to that effect, he re-moulds standard English to fit the world he has in mind. The subject matter is carved into existence through a carefully sharpened language.

It can therefore be said that this finally-worked language does not merely mirror the story it narrates, it gives shape to it, it makes it possible. Standard English would not have been up to the task. This makes him akin to writers such as Anthony Burgess (A Clockwork Orange) or Russell Hoban (Riddley Walker) who indulge in similar alterations of the English language. To illustrate this, we shall focus on the two stories that take place in the future in Cloud Atlas1 : "An Orison of Sonmi ~ 451" (Sonmi) and "Sloosha's Crossin' an' Ev'rythin' After" (Sloosha). These two opposite worlds-the first one portrays a genetically-engineered world in the 22 nd century, the other depicts humanity back to an Iron Age after the explosion of the nuclear bomb-are produced by two languages which could not be further apart in their structures and rhythms. Mitchell manages this tour de force of making language speak completely differently from one story to the next.

We shall first see how in both stories, language acquires a defamiliarizing strangeness, reflecting the new context. We shall then analyse in what sense language can be said to create the story. The writing of these two stories follow different patterns: following Gilles Deleuze's terminology, we shall call it an "arborescent" writing as regards "Sonmi" and a "rhyzomatic" one in the other story. Lastly, we will examine how far language has gone in its evolution in both stories. In "Sonmi", language seems to be the result of a political manipulation that has tampered with its natural evolution. As for "Sloosha", on the opposite, the bomb appears to have liberated it from the grammatical shackles that used to stifle it: the new language is powerfully alive and appears to have come back to its "essential" state.

Worlds apart, the two stories yet produce a similar defamiliarizing effect on the reader. In "Sonmi" we are presented with an exceedingly modern world composed of "purebloods", "xecs", "genomicist", "syntaxists", "aides", "tellers, "archivist" and "fabricants" given mathematical names (Yoona-939, Wing-027, or Sonmi-451, the interviewed fabricant in the story), in the purest science-fiction tradition (we need only think of Zamyatin's We). The text is strewn with unfamiliar technological and medical words (kalodoxalyn, stimulin, amnesiads, xenon, neon, carbdiox, ascension catalysts, soporifix, medics, aircon inflows, Medicorp, biocosmeticians, healant), sometimes in the form of abbreviations or capital letters ("sync, EyeSats, Xultation, AdV"). It is permeated with signifiers belonging to the rigorous field of science ("portion, encompass, approx, milligrams"), drawing sometimes on the French language which adds to the scientific effect ("de rigueur"; "I shall précis it"). The contrast is striking with the other story where English seems to have regressed just as humanity has. The linguistic fabric has become threadbare; some letters have completely disappeared, replaced by apostrophes, making it sometimes hard to read. The nuclear disaster has brought about some kind of linguistic entropy, finding a perfect illustration in the signifier "hole" standing for "whole"; the loss of this <w> reveals a bigger loss: people have been literally plunged into a big bang from which they painfully try to recover. There are two contradictory forces in this post-apocalyptic writing, reflecting the atoms at work as they are engaged in activities of fusion and fission. The reading is both axed by the apostrophes: they indeed tend to make the reader halt, as it sharply cuts the rhythm. At the same time the sounds are sometimes so close that they seem to blend into a kind of fusing whole, to the point of being almost unreadable. The alphabetical atoms are indeed getting into fusion, creating new, unfamiliar linguistic entities: "'n'kin'n'age'n'all". Besides, the survivors of the Apocalypse try to grasp what ancient technological words used to refer to, by translating them into familiar words: "a tel'scope" is thus defined as "the furthest seeing eye"; "'lectric" has to be comprehended in known words: "Smart magic like a heart works the body". The survivors attempt to make do with what remains: they are "bricoleurs" in Lévi-Strauss's meaning of the term and the activity of "bricolage":

[The bricoleur's] universe of instruments is closed and the rules of his game are always to make do with "whatever is at hand", that is to say with a set of tools and materials which is always finite and is also heterogeneous because what it contains bears no relation to the current project, or indeed to any particular project, but is the contingent result of all the occasions there have been to renew or enrich the stock or to maintain it with the remains of previous constructions or destructions. (Lévi-Strauss 1992: 17) Like in Russell Hoban's post-apocalyptic story (Riddley Walker), the survivors make the most of the fragmented words that have lost their previous referents, trying to re-member what there was before the blast and to make sense out of the incoherent and heterogeneous.

By contrast, the language of "Sonmi" could be the tool of "the engineer", as it seems to be perfectly designed to serve the new reality. In Lévi-Strauss's dichotomy indeed, unlike the "bricoleur", the engineer "subordinate[s] each of the [diverse tasks] to the availability of raw material and tools conceived and procured for the purpose of the projects" (Lévi Strauss 1992: 17). In this dystopian near future Korea (Nea So Copros) run by corporations, what is a brand in our reality has now become a common name without any capital letters: "traffic jams" are now called "fordjams". People are equipped with their "sony", they wear "nikes" and "rolex". The Media use "nikons". In this "consumerdom", everything has been desacralized, or rather, only one thing is sacred: business. Even the contents of the Encyclopaedias have been translated into the new consumerist language : there are now only "encyclopaedia of consumable". Music takes the form of scientific programming: "programmable violin". Commitment is now synonymous with "Investment". Alienated to the consumer society, human feelings and expressions have changed meaning. One father complains about his inability to look at his neighbours "in the eye", not because he has made a mistake involving his honesty and dignity as we would have expected, but because he could not get his daughter the most fashionable doll: "How am I supposed to look our neighbours in their faces if our daughter is the only girl in our carousel to not have a Zizzi?" (Mitchell 2004: 355). We then understand we have gone a great deal down the consumerism line. People are asked to "work, spend, work" (Mitchell 316). What is the most sacred, giving birth, has turned into a real market: you can "sell baby quota". As in Huxley's book, in this brave new world too, life-giving has been taken over by the State. It produces genetically-engineered slave-workers called "fabricants" whose life and death are entirely controlled. The scientist has become all powerful in this bypassing of natural reproduction: the human body no longer constitutes a limit; the border has been crossed, as evidenced by the new word "wombtank", bringing together a most natural place of birth and an artificial container. The era of the posthuman has already begun.

Man has taken total control of nature. Natural elements only exist in so far as they are human-engineered. For instance, science takes care of the dissemination of seeds, as the now "sterile" wind cannot carry out this function any more ("the sole sound was a sterile wind swishing blunted needles" [Mitchell 328]). Irrational uneven nature has been dealt with: the mountains are being "processed". The trees have been planted in a mathematical, rigid order so that they look like a military corps: "The Norfolk pine-rubberwood hybrids were planted in rank and file and created the illusion that trees were marching past our ford in a billionstrong regiment" (Mitchell 328). Science has infiltrated the natural world to the point that nature can no longer be described in its own terms: the "natural" world has been subordinated to the engineer's language and vision. Even the moths are described as "electron-like". In the living-room the old "aquarium" has been superseded by a "dysneyrium" (displaying films): natural elements have been taken over by culture linguistically too. In the latest linguistic software the Party has installed, the new cultural files have indeed deleted the old natural ones. There thus can be no such thing as a comparison between the two worlds any more since there is only one left. As a matter of fact, there are very few comparisons in "Sonmy" as opposed to the other story where nature seems to have regained its rights after the nuclear disaster. In "Sloosha", nature appears to be coming back unexpectedly through the linguistic door. For instance, what used to be scientific and therefore exclusively human ("observatories") is now written "observ'trees". Most comparisons take nature as its comparing element: "my eyes got owlier", "slipp'ry as cave fish, heavy as a cow, cold as stones", "she din't b'have like no queeny-bee", "lornsomer'n a bird in a box in a well". Nature proves to be a rich linguistic source for the survivors in their description of human movements for instance: "hawkeyeing me", "to spider up the crumbly ridge". The process of "life-giving" is following natural rhythm and evolution here, as the images make clear: "I planted my first babbit up Jayjo from Cutter Foot Dwelling", "when Jayjo plumped up ripe" (Mitchell 243). Living in complementarity with nature, the post-apocalyptic survivors communicate with their environment. This harmony is linguistically rendered by the indifferent use of the genitive form for human and non-human elements, showing that now humans are just one category among others. This form is not the preserve of animate beings any more: "this busted world's fault". As we shall proceed to see, the choice of semantic and grammatical structures is determining in both stories.

The two stories are produced by two radically opposed languages. The language in "Sonmi" has the rigour of mathematical writing, the sentences being often introduced by a very scientific colon: "Therefore: we must be vigilant against evil", "some: but yet more surprises", "Not really: an enforcer escorted me". Although this narrative is actually an interview of Sonmi before her execution-Sonmi is a "fabricant", that is to say a clone created to serve as a dutiful worker, who has rebelled against the lot reserved to her species by the State-, there is absolutely no contracted forms, every word is as fully pronounced as it would be in a very formal speech. In this paratactic way of writing, there is no link between the short sentences, creating a very sharp, chopped-up rhythm. The long words of Latin and Greek origins sound like linguistic fossils, adding to the deadly and cold rhythm: "obscured, chauffeur, reverted, ricocheted, alternated, curtail, acute, soporifix, quandary, simulacrum, malfunction, requartered, morphed". A preference is given to nouns, which contributes to the impression of a reified language: "Her aloofness was in fact watchfulness", "Her sullenness hid a subtle dignity", "Their drunkenness had a recklessness that nite". The following sentence supposed to explain Mr Rhee's emotional reaction and behaviour sounds like a cold medical diagnosis: "Seer Rhee should be understood in the context of his wife". Similarly, the technocratic-sounding expressions "in the face of" ("Why did the entire conurb not grind to a halt and give praise in the face of such inevitable beauty?"), or "for the comfort of" ("This fallacy is propagated for the comfort of purebloods"), tend to technicize language. In fact, beneath the seemingly rich linguistic surface of this "engineered" piece of writing lies a poor language based on a simple mechanical construction. Signifiers can indeed be articulated or disarticulated as you connect or disconnect a computer. The pervasive use of a negative prefix is symptomatic of a language lacking variety and colours: "un-censored, unconscionable, disconnecting, underbelly unmet, unlatched, untouched, unfiltered, unlit, unhood, unflaggingly, unmaled, unpleasantness, uncritical, unthinking, unaided, unsouled, malfunctioned, ill-advisedly, unresponding, uninfluential". It can make us think of Orwell's Nineteen Eighty-Four in which zealous linguists try to "[cut] the language to the bone" (Orwell 54), exterminating superfluous words: "If you have a word like "good", what need is there for a word like "bad"? "Ungood" will do just as well-better, because it's an exact opposite, which the other is not" (Orwell 54). In "Sonmi", a good "investment" or devotion of your life to the Juche (the charismatic father of the Corpocracy) has its own technical language: it can be rebuilt in any way whether you are at the top of the hierarchy "twelvestarred" or on the verge of being "destarred", as everybody is "destarrable" until you're left with nothing ("to zerostar somebody"). This language-machine creates a mechanical world that has in fact more to do with "bricolage" than creativity.

In "Sonmi" indeed, sentences strictly conform to the canonical order: a subject is invariably complemented by its verb, abiding by the ideological standards underlined and denounced by Benjamin Lee Whorf. For the linguist indeed, the old Greek grammatical structures have unquestioningly been governing our way of making sense of the world: And, pursuant again to grammar, the notion became ingrained […] that the verb class cannot exist without an entity of the other class, the "thing" class, as a peg to hang on. "Embodiment is necessary", the watchword of this ideology, is seldom STRONGLY questioned. (our italics; Whorf 1956: 241) A sentence like "Ascension merely frees what Soap represses" complies with this linguistic ideology. In Nea So Copros, no deviation from the "right" order is tolerated. The extensive reference to spatial directions (upstrata, instreamed, coerced into, untermensh, downcurved to, switchbacked up into, parallel to, etc.) contributes to creating the image of a rigidly hierarchized world where everything is "orientated". Space is linguistically mastered; each social stratum is addressed to with a particular language ("Papa Song's upstrata lexicon that Matins support this theory" [Mitchell 196]), ensuring everybody remains in the place they occupy on the social and linguistic tree. Indeed like the scientists in Nineteen Eighty-Four who are given just the amount of words that would be needed in their trade, fabricants have to follow their "Catechisms", ready-made or ready-thought expressions learnt in a training called "Orientation"; for example "the verb remember is outside servers' lexicons" (Mitchell 230). Natural acquisition is tampered with through the use of a drug called Soap that erases all the new words they have learnt during the day: "Orientation teaches us the lexicon we need for our work, but Soap erases xtra words we acquire later".

Through its semantic and grammatical structures, language in "Sonmi" would correspond to the "arborescent" structure Deleuze and Guattari speak of in A Thousand Plateaus, which they describe as a pre-defined structure where everything is already known and planned-here quoting Jean Petitot and Pierre Rosenstiehl: "The channels of transmission are preestablished; the arborescent system preexists the individual, who is integrated into it at an allotted place" (Deleuze and Guattari 2004: 18). The mechanical and articulated language of "Sloosha" is modelled on the tree image in so far as "the tree articulates and hierarchizes tracings" (Deleuze and Guattari 13). We indeed have the feeling words are here at the end of the linguistic chain, labelled like manufactured goods at the end of the assembly line. Language in "Sonmi" addresses itself directly to the reader's brain: it has to do with semantics, with the signified, rather than the signifier; the linguistic process is terminated: words have been processed and deposited on paper, ready-to-be-understood. The abundance of -ed forms in the text conveys the idea of a stabilized language describing a passive, arrested movement: "well-oriented, genomically modified, unholstered, upended, a rainstained, sun-crackled overhang, deadlanded, Huamdonggil is not gridnumbered or charted". Besides, the text is strewn with verbs in the passive voice, depriving the subjects of the sentences of any active part: "are entitled to 'rests'", "every minute must be devoted to", "these individuals will be named later", "Festivities were cancelled", "The other half was decidedly muted", "servers are genomed for gruelling nineteen-hour workdays", "a body genomed for service", "it was poorly dijied". With the passive form, we are presented with the result of an active process that seems to have been accomplished on its own, the agents being rarely mentioned. The grammatical structure here produces this idea of a puppet language being activated by invisible strings. Similarly, the subjects of the verbs in the active voice are often inanimate, creating a situation in which things are going on around Sonmi without her being able to exert any control over them: "an eyehole blinked, bolts unclacked", "The planked ceiling thumped and creaked, a hatch flipped open, and Ma Arak Na's face appeared" "the streets funnel the morning wind to high speeds" "the rear door hissed open".

The contrast is thus striking with the second story which is littered with -ING forms, conversely giving the impression of a movement in endless suspension. Nouns, which usually tend to immobilize processes, have been turned into -ing verbs. We do not speak of trips, folly, adventures or choices but of "journeyin's", "follyin's", "adventuring's", "choosin'". The numerous adjectives ending in <y>-mostly absent in "Sonmi"-convey a similar idea of movement: "breathy, selfy, runty, mythy, southly, summery, melty, knotty'n'rooty, waxy'n'silty". Such a sentence as "there wasn't no scalin' it" would be rendered by "escalation was impossible" in "Sonmi", the noun ("escalation") putting an end to the movement-in-process embodied by the -ing form ("scalin'"). Far from being a linguistic lawobedient writing, the language of "Sloosha" deranges the "ideological" rules: it is a "delinquent" language flouting the canonical order, as in the following sentences: "so hushly hushly up I was", "snailysome goin' was them rockfields", "Coneys'n'roasted taro we was eatin'". Words have changed categories. Onomatopoeias accede to the level of verbs: "They was padddooomin". The spelling and grammatical borders have been disrupted, giving birth to a new lexical and grammatical layout: "Pa'n'me" is a novel one-word signifier including words previously separated.

Reading "Sloosha" can carry you out of breath, the accumulated signifiers linked by "'n" accelerating the rhythm as if it were never going to end: "She's fuggin" your b'liefs'n'all up'n'down'n'in'n'out", "Magicky ruby welled'n'pumped an' frothed on the fleece an' puddle on the stone floor". As opposed to the regular tree-like linguistic structures in "Sonmi", we can here convene the image of the nomadic rhizome Deleuze and Guattari speak of, which has the distinctive feature of never taking roots. Unlike the rooted tree indeed, the rhizome does not settle anywhere or conform to any already articulated hierarchical structure:

A rhizome has no beginning or end; it is always in the middle, between things, interbeing, intermezzo. The tree is filiation, but the rhizome is alliance, uniquely alliance. The tree imposes the verb "to be", but the fabric of the rhizome is the conjunction, 'and…and... and…'. This conjunction carries enough to shake and uproot the verb 'to be. (Deleuze 27) Through its abundant use of the conjunction "and" accelerating the rhythm of the sentences, the language in "Sloosha" is indeed characteristic of the rhizome, always on the run, taking speed in the middle: "The middle is by no means an average; on the contrary, it is where things pick up speed" (Deleuze 2004: 28). It confers the impression of a "stammering" process that will not finish. The idea of rapidity is also rendered by verbs that are now immediately followed by a direct object complement: "She sorried losing", "she looked spikers at me". The text here is not addressed to the reader's brain but to their senses. Indeed, to a technical language ("Sonmi") succeeds a very concrete, figurative language that appeals to our emotions. Rather than semantics, what is at stake here is semiotics. The percept is substituted for the concept. The onomatopoeic sounds replace the finished linguistic goods; "cockadoodlydooing", "an'blissweed'll lead you b'tween the whack-crack an'boom-doom an' pan-pin-pon till we…", "an' suddenwise whoah a whip binded my legs t'gether an' whoah up I flew an' whoah down my head dropped an 'aieee the pavestones smashed my skull" (Mitchell 289). In "Sloosha", language is not conceptual: it is a language "in the making", describing things as they occur without any prior structuring. Thus you do not "sob your eyes out" in "Sloosha" but "sobbed'n'sobbed'n'sobbed". Likewise, "an 'up Old Georgie's'closure we scaled hand by hand by hand" (p. 275).

This very concreteness of language makes it a good candidate for humorous remarks that would be impossible in the other language (where "Humor is the ovum of dissent, and the Juche should fear it"). Funny jokes are possible because language has crossed the barriers of decency. It tends indeed to be more colloquial: "fear pissin'in my blood". Such expressions as "ass-belched", "my voice was jus a duck fart in a hurricane" cannot but trigger a smile. Far from the obscure, alien-sounding words in "Sonmi", language here is as close it can get to the thing itself: "he spoke knuckly like savages", "blissweed" or "no mornin' for sluggybeddin'" need no translation. Words are on a par with things anyway: "stones'n'shapes'n'words". There are no fossilized words; language here is expressive, striking and vivid; simple answers and questions have become verbs: "to yay", "to howzit" (how are you / is it with you), "to say-so somebody" (to order), "to naysay", "there's no but whying". There is something very "practical" in the expression "to coldwater the plan" and its exact opposite "it fired hot" to refer to the success or failure of a project. "To hesitate" has a more expressive and "natural" translation in the language of the future: "to donkey 'bout with it". "Going back to some place very fast" is expressed by the metaphor of a rapid animal: "to back rabbit". Our complicated words have been replaced by signifiers clearly expressing their meaning; thus if you are a "veterinarian", what you do is indeed "animal doctoring"; the concept "nonsense" tends to be more "vividly" rendered in the new language: "animal farting". The numerous comparisons of the text conjure up colourful images that makes language all the more transparent and clear. Such sentences as these are very visual: "wriggling like eels on the sand", "I was hooded like a goat b'fore slaught'rin'", "helpless as a strung-up lardbird bein' bled from the hook", "but the gone-lifes outnumber the now-lifes like leaf outnumber trees".

If language is so different in both stories, it is because its very essence, its very substance has been "manipulated" in two radically opposed ways.

In both stories, language has taken different evolutionary paths. More particularly in "Sonmi", it reveals the manipulation it has been subjected to. Indeed, the English language of the 22 nd century should be more corrupted than it is here, had it followed its natural evolution. In fact the Unique Party of the Corporation has mastered not only nature but also what is the most natural to man, that is to say their language. The irregular verbs for instance have been maintained. The natural process of simplification at work in any language has been curbed here through intervention. The linguistic DNA has been fixed once and for all: it is a "genomed" language. Repetitions, synonyms, superfluous or deviant elements are not seen in a good eye by the Party as regards fabricants. The fabricant Yoona-939 became a suspect when she started using "irregular speech" and "finer-tuned" words. Language must conform to the mould sanctioned by Papa.

The absence of metaphors or any figure of speech in this language ("Sonmi") is the symptom of a dispassionate language. It has reached the final stage Rousseau talked about in his Essai sur l'origine des langues, moving further away from its passionate, metaphorical initial state. For the French thinker indeed, language was metaphorical in its origin because it was born of man's passions: "As the first motives which brought man to speak were passions, his first words were tropes. The figurative language was the first to arise, the 'proper' meaning was found last […] We started reasoning a long time after" (Rousseau 1993: 63, our translation). The language of Sonmi is a rationalized language that has done away with human passions and emotions. Vowels are rare in this consonant-dominated language devoid of any imaginative power; for instance, "ex" is systematically replaced by a simple X: "we xited the overway at xit two" (Mitchell 323). In "Sonmi" the earth is poisoned, compelling the remaining citizens to keep to the cities run by a power obsessed with property. This cleaning process has affected words too: language has been made "proper". What belonged before to the abstract, metaphysical sphere has now been brought down to the level of material elements. A "Soul" is the new word for a microchip. Hence the disappearance of metaphors or similes whose main function, according to Lakoff and Johnson, is to enable us to grasp abstract elements (Lakoff 1980: 115). Indeed metaphors permit us to put things in relation and open perspectives so as to create meaning and understand the world: "because so many of the concepts that are important to us are either abstract or not clearly delineated in our experience (emotions, ideas, time) we need to get a grasp on them by mean of other concepts that we understand in clearer terms (spatial orientations, objects…)". For instance, "love" can only be defined with the help of other concepts: "Love is madness", "Love is a journey", "Love is war" (Lakoff 115). By contrast, in the other story, metaphors are plentiful, which is understandable among survivors who try to grasp the world around them. Besides, the narrator, Zachry, is narrating the story of his life as a child when he tried to face and understand the adult world. For instance he resorts to a metaphor in his attempt to describe what lies are: "Lies are Old Georgie's vultures what circle on high lookin' down for a runty'n'weedy soul to plummet'n'sink their talons in".

Sonmi comes close to reintroducing metaphors, as she moves away from Papa's catechism. The spheres she is bringing together are far apart and create a surprising vision: "The statue itself assumed a comic majesty", or "Snow is bruised lilac in half-lite". She is reintroducing some kind of tension inherent to metaphors according to Paul Ricoeur. Indeed, for the French philosopher this trope always displays a tension between the "is" and the "is not" of a metaphorical sentence. In the expression "this man is a lion", he is not (literally) and is (metaphorically) a lion. The literal meaning yields to the new impertinent meaning while resisting to it. Both meanings cohabit in a way. The State would not allow such resisting and impertinent tension in the meaning of words. Just like the Inner Party in Orwell's novel, it has taken hold of the identity of things and determines what is and what is not. Tension or dual cohabitation is unthinkable for the Party of "Unanimity". The opposition they are fighting (Union) is non-metaphorically called "Cancer". It literally embodies a disease to be fought by the Party of cleanliness and health, as the vocabulary reveals: "The Juche's rounds of new Enrichment Statutes are sticking band aids on hemorrages and amputations". All that used to be abstract now corresponds to something very physical in the 22 nd century. "Evil" has taken up a very concrete embodiment: Papa Song told us a gas called evil xists in the world; purebloods called terrorists breathe in this evil, and this gas makes them hate all that is free, orderly, good and corpocratic; a group of terrorists called Union had caused yesterday's atrocity by infecting one of our own sisters, Yoona-939 of the Chongmyo Plaza Dinery, with evil. (Mitchell 196).

In this literal, orientated language, words have been reduced to one smoothed-out semantic layer with one fixed meaning. The Party has indeed tampered with the paradigmatic axis of language, condemning it as a lively and changing organism. This impossibility for language to deviate from its pre-assigned form has an equivalent at the diegetic level: indeed, we learn that the story Sonmi is narrating had a pre-planned outcome. Its end was contained in the beginning and Sonmi was aware of it from the start: she knew that the people supposed to be her accomplices in her "ascension" have always been part and parcel of the Party's conspiracy to take her down, with this aim in mind: "To generate the show trial of the decade. To make every last pureblood in Nea So Copros mistrustful of every last fabricant. To manufacture downstrata consent for the Juche's new Fabricant Xpiry Act. To discredit Abolitionism. You can see, the whole conspiracy has been a resounding success" (Mitchell 349). The idea of circularity and impossible escape is in keeping with the stifling language of the story, too mechanical and paralysing to allow any escape in the unknown or to let imagination grow. Similarly, no escape in the past is possible; the latter is a "forbidden zone" (Mitchell 233). The Party has indeed eliminated all the elements belonging to Pre-consumer times: "An abbey had stood there for fifteen centuries, until Corpocracy dissolved the preconsumer religions after the Skirmishes" (Mitchell 329). No cohabitation of elements belonging to different periods of time is thinkable: it would introduce some kind of dissemblance or dissymmetry in which tension and dualism could reappear. Language guarantees this erasure of the past, as old words have been discarded and forgotten. The new signifiers having one and only meaning, they cannot hide any other. Linguistic "palimpsests"2 are impossible since hypotexts have been deleted, washed clean.

Yet some hope remains and it is paradoxically to be found in language itself. Indeed if Sonmi played the game all the way till her preplanned arrest and condemnation, it is because she knew that her testimony would be read. Whether it is seen as "the ugliest wickedness in the annals of deviancy" does not matter. This piece of writing will somehow make its way through people's minds and start "germinating" there:

We see a game beyond the endgame. I refer to my Declarations, Archivist. Media has flooded Nea So Copros with my Catechisms. Every schoolchild in corpocracy knows my twelve "blasphemies" now. My guards tell me there is even talk of a statewide "Vigilance Day" against fabricants who show signs of the Declarations. My ideas have been reproduced a billionfold. […] As Seneca warned Nero: No matter how many of us you kill, you will never kill your successor. (Mitchell 349) Linguistic seeds can grow some kind of rebellious feelings when and where least expected. In the long run this germinating language will get the better of the genomed language, starting the "-ing process" again. Sonmi seems to think that, like nature, language is resilient enough to counter any manipulative action. Like the genomed moth whose "wings'logos had mutated over generations into a chance syllabary" and thus represents "a small victory of nature over corpocracy" (Mitchell 328), language may deviate from the linguistic route laid out by the Party. This is precisely this linguistic resistance which is at stake in "Sloosha". As opposed to the other story, language has not been tempered with here. It is in the state it is in because of the circumstances. Apparently diminished, it has in fact found the strength to rebuild itself on demolished grounds. In the process, grammar has simplified itself: most verbs have lost their irregularities ("I knowed, she thinked, I'd bringed, he finded, forbidded"), the plural is marked by a simple "s" for all nouns now ("foots"); "was" applies invariably to singular as well as plural subjects ("we was eatin'", "our bodies was"). The same simplification applies to comparatives, sometimes operating on the irregular forms ("badder, bestest"). It has a powerfully poetic aspect: far from the perfect, military sounds of the first language (as in "the crush of consumers cleared in an instant" for instance), it seems to follow the rhythm of life. Hence the numerous superfluous elements; "'n all" punctuates many phrases: "wise up my people'n'kin to the Prescient's truesome plannin'n'all". As life is, the text is full of useless repetitions: "mocking us mocksome". A binary rhythm gives the tempo to most phrases, making them sound as light as childish songs: "Ma was flappin'n'anxin'", "Pa was still lyin'n'bobbin'", "Dawn fogged waxy'n'silty", "bumpy'n'thorny", "runty'n'weedy", "not lazy'n'spotty", "over knotty'n'rooty ground". The childish-sounding words give a lively turn to the signifiers: "umb'licky word", "nothin' to be gained by dillyin'", "a squeezywheezy", "he snaky-snuck up a leafy hideynick".

Far from being a one-layered language, words in "Sloosha" can sometimes be multilayered. They indeed carry the burden of the Old Civilisation. The signifiers convey several meanings, dragging some remains of the past, forming a real palimpsest. They are sometimes funny (when we get what the "kole kole" girl refers to for instance), but they sometimes contain more scathing overtones. Just like in Riddley Walker, language seems to know things its speakers ignore: the word "Civ'lize" for instance insists on the sounds "lize" or "lies", as if the most civilised and scientific of all countries had lied to its fellow-citizens not telling them everything about the bomb. Many portmanteau words offer an acrid denunciation of our civilization: the term "trespyin" mixes two ideas "to trespass / to spy". Death seems to show through the new version of skeleton "skellyton" mixing such words as "skull/shell/hell/y". "P'mission" seems to insist on the mission any permission gives rise to. But unlike what happens in Riddley Walker where people blindly trust language-in which they are sure to find the secret of the bomb-, Zachry is conscious of the power of language and thus of the necessity to denounce it, as he mistrusts people's nice words: "You can't go trustin' folks what lassoop words so skillsome as him" "No un but me seen the arrow o'flatt'ry them words fired" (Mitchell 252), "her words was slipp'ry wrestlers they jus' flipped your nay into a yay" (Mitchell 254). This is a real germinating language (in the form of the rhizome) that is growing here. Not taking root anywhere, it simply follows the flow of life. As compared with the flat line on the electroencephalogram the one-layered language in "Sloosha" could represent, the accumulated 'n'n'n'n'n'n'n'n'n'n'n' could be an image of the heart oscillations signifying life. Yet, things are not as clear-cut. They tend to permanently oscillate between life and death, right and wrong. The wise prescient Meronym-a member of the remaining technologically-advanced civilisation who is visiting the primitive tribe the narrator belongs to-teaches Zachry that every single thing has two sides to it; it never can be one-sided and clear-cut:

List'n, savages an' Civ'lizeds ain't divvied by tribes or b'liefs or mountain ranges nay, ev'ry human is both, yay. Old Uns'd got the Smart o' gods but the savagery o'jackals an'that's what tripped the Fall. Some savages what I knowed got a beautsome Civ'lized heart beatin' in their ribs. Maybe some Kona. Not'nuff to say-so their hole tribe. (Mitchell 303) "Unanimity" is impossible: there always are and must be some counterbalancing elements. Thus Meronym reinstates the dualism and the dichotomies put down in the first language, and claims the possibility to stand in-between. The "Sloosha" language itself, as a rhyzomatic one, grows in the middle. Thus within the new spelling of "Hawai" can be read the questions of the survivors in regard to their lot: "Ha Why". A "lullaby" is now a "babbybye" oscillating between life (baby) and death (bye).

Zachry and his tribe still have the possibility to imagine a different future from the one they have, a possibility linguistically blocked in the other story: "an' 'magin' flyin' kayaks an' no-horse carts wheelyin' here'n'there" (Mitchell 285). But the term "'mazement" expresses people's ambivalent feelings concerning their future, oscillating between hope and loss: people are both ready to be "amazed" and yet are lost in a "maze" where they can not see very far ahead. Language conveys this ambivalent wish to go forward and the inability to do so. Likewise, the signifier "f'got" in its new spelling seems to hesitate between to get / to have and to forget / to abandon. Language does not exhaust itself in one fixed meaning: like the people, it has become nomadic, refusing to settle itself anywhere. Rhyzomatic words can thus disseminate themselves on unknown territories and experiences, where everything is not rigorously planted for them in advance. Language has been set free. On the whole, it seems to have come back to the time when it was at its most natural and this seems possible only because nature has regained its genuine place and function.

Conclusion

What can be said of the "Sloosha" story can also be said of Mitchell's novel as a whole, as it seems to refuse to follow a straight chronological line: the six stories are indeed embedded in a Matryoshka doll fashion; the whole structure thus forms concentric spheres that does not allow the readers to settle anywhere; when they become familiar with a story, they are indeed suddenly "deterritorialized"-to use Deleuze's term-and plunged into a new spatio-temporal universe. We never know where the next story is going to take us, just like the clouds in Sloosha's last image: "Who can say where the cloud's blowed from or who the soul'll be 'morrow? Only Sonmi the east an' the west an' the compass an' the atlas, yay, only the atlas o' clouds" (Mitchell 308).

The stories themselves are a palimpsest, drawing on very well-known literary styles (from the typical 19 th century epistolary mode to the futuristic world and language that Huxley, Zamyatin, Orwell or Hoban have made us familiar with). The mosaic image Mitchell is building out of fragmented heterogeneous elements compels us to take a look at humanity's social, literary and linguistic history from a distance. At first sight very pessimistic-all the stories depict characters in a stifling situation, and the embedded structure of the stories adds to the impression-, Cloud Atlas nourishes hope of some rhyzomatic germination in the middle. And precisely the middle story, the only one which is uninterrupted, is the postapocalyptic "Sloosha" story, where language is paradoxically at its most lively and essential, as if language and mankind needed to undergo such a trauma to be brought back in line with nature. Luckily, writers reinvigorate language for us before any catastrophe takes place. But Mitchell's writing, like Orwell's or Hoban's, remains a warning.

Works Cited CARROLL, John B. (ed.). Language, Thought and Reality: Selected Writings of B.L. Whorf, Cambridge Mass.: The MIT Press, 1956.

The first four stories take us from the South Pacific in the 19 th century to 1931 Belgium, moving on to the seventies in California, and lastly today's England, before focussing on

th -century Korea (Sonmi) and Hawaii in a distant future (Sloosha).

We here refer to the title ofGérard Genette's book, Palimpsestes (Paris: Seuil, 1982), by which he means that a literary text can always hide another that it never manages to conceal entirely, so that the text often lends itself to a double reading where hypertext and hypotest are superposed.