David Gianazza

Dsna

Airspace configuration using air traffic complexity metrics

Flow regulation is a critical process in air traffic management, ensuring that the incoming traffic does not exceed the ability of air traffic controllers to handle it safely and efficiently. Currently, the european Flow Management Positions (FMP) use flight counts and sector capacities to assess the traffic load and build predicted opening schemes. These schemes, made of predefined airspace configurations, are used to detect potential overloads. Some past research undertaken at the Global Optimization Laboratory led to think that this process was not grounded on solid scientific notions, as concerns the quantification of the controllers workload. Consequently, it is proposed to stop using flight counts and sector capacities to predict this workload, and to use relevant air traffic complexity metrics instead. Another proposal is to explore all the possible combinations of elementary sectors, instead of the small subset of pre-defined configurations currently being used, so as to offer the maximum capacity to the incoming traffic.

In previous works, we assessed the relevance of complexity metrics by comparing their relative influence on the sector status prediction (merged, manned 1 , or split) made by a neural network. Real sector statuses issued from filed configurations were used to train the neural network 2 . A fairly simple relationship between the relevant metrics and the sector status was found. The main contribution of this paper is to use the relevant metrics and the sector status prediction to build realistic airspace configurations. The computed configurations are compared to the actual configurations archived by the ATC centers, and to the FMP opening schemes.

INTRODUCTION

Over the last years and with the increasing traffic demand, there has been a growing need for a better understanding of how the current air traffic management system is operated and how it could be improved. Quantifying the complexity of a given air traffic situation has become an issue for the assessment of ATC/ATFM performances, the benchmarking of new airspace structures, the design of new control tools, and other activities related to air traffic management. This paper focuses on the airspace configuration schedules made by the Flow Management Positions (FMP) of each Air Traffic Control center (ATCC), and sent to the european Central Flow Management Unit (CFMU) two or three days before the traffic actually enters the centre's airspace.

The work presented here is the continuation of previous research. In [START_REF] Gianazza | Optimization of air traffic control sector configurations using tree search methods and genetic algorithms[END_REF], [START_REF] Gianazza | Optimal combinations of air traffic control sectors using classical and stochastic methods[END_REF], and [START_REF] Gianazza | Optimisation des flux de trafic aérien[END_REF], we proposed several algorithms combining elementary sectors so as to offer the maximum capacity while making the best possible use of the available ressources. These algorithms used the same variables (flight counts in a period of time) and thresholds (sector capacities), as well as the same constraints (number of controllers on the duty schedule) than the FMP. However, the optimized schedules were still far from realistic when compared to real configurations. In [START_REF] Gianazza | Evaluation of air traffic complexity metrics using neural networks ans sector status[END_REF] and [START_REF] Gianazza | Selection and evaluation of air traffic complexity metrics[END_REF], we used the real sector status (merged, manned 3 , or split) to assess the relevance of several air traffic complexity metrics found in the litterature, assuming that the decision to split or merge sectors is somewhat related to the actual contoller's workload,. Neural networks were used for that purpose.

We will now see how the relevant air traffic complexity metrics and the sector status prediction made by the neural network can be used to produce more realistic schedules. In order to be closer to the real decision process than in our previous works ( [START_REF] Gianazza | Optimization of air traffic control sector configurations using tree search methods and genetic algorithms[END_REF], [START_REF] Gianazza | Optimal combinations of air traffic control sectors using classical and stochastic methods[END_REF]), the computed airspace configuration will be dynamically re-assessed every minute of the day.

If we were to implement this process within an existing decision support tool, we would have to compute the complexity metrics from the flight plans filed for the considered day, as the radar tracks are not yet available, two or three days before D-day. This issue is not adressed here and will be a further step of our research. In this paper, the metrics are computed from recorded radar tracks, in order to compare the computed configurations to the real configurations recorded by the ATCC. This is a first and necessary step in the validation of realistic airspace configurations schedules.

The current paper is organized as follows. Section I defines some vocabulary and gives the context and the motivation of our study, as well as some background on air traffic complexity. Section II describes the raw input data used to compute the air traffic complexity metrics. The neural network that predicts the sector status using the metrics values as input is shortly described in section III. Section IV introduces the algorithm building realistic airspace configuration schedules, according to the sector status predictions. Some results on the french air traffic centres are provided in section V, and section VI concludes the paper and gives the perspectives of future research.

I. BACKGROUND

A. Vocabulary

Before all, let us define a few terms of vocabulary used in this paper. The airspace of each center is made of several elementary sectors that may be merged (or collapsed) into larger sectors. In the rest of the paper, the term control sector, or simply sector, is used to denote a volume of airspace made either of one elementary sector or several elementary sectors merged together, and controlled by a team of usually two controllers (radar, and planning).

A configuration is a mapping of the set of elementary sectors onto a smaller number of control units, operated each by a radar and a planning controller. An airspace configuration schedule, also called opening scheme, shows the successive configurations for each time of the day.

We call incoming flow the number of aircraft entering the control sector within a period of time (30 or 60 minutes, for example). The incoming flows are sometimes called flight counts ( [START_REF] Verlhac | Improved configuration optimizer methodology to use a decision support tool[END_REF]), or traffic load in the CFMU handbook. The sector capacity is a threshold value on the number of flights that may enter the sector in a chosen period of time.

B. Context and motivation of the study

The current method used by the european FMP/CFMU to build airspace configuration schedules, or opening schemes, is fairly simple. A set of static airspace configurations defined by the FMP staff is filed in a database. When building a schedule, the FMP operator chooses for each time step (usually 30 or 60 minutes) the best configuration among those he or she thinks may be the most adequate for this time of the day. The subset of possible configurations at each time step is chosen according to the number of controllers listed on the duty schedule at that time of the day. Each configuration is evaluated by comparing the incoming flows to the sector capacities. This choice of the best configuration is subjective and based on the past experience of the operator. Of course, once the final schedule is built, there may remain some sectors for which the predicted incoming flow is higher than the capacity. This may be considered as a potential overload problem and signaled to the CFMU. Some regulations may be requested for one or several traffic flows crossing some sector boundaries or overflying some beacons 4 .

The Eurocontrol NCD (Network Capacity and Demand management) Research Area team has been working for several years on the optimization of this process (see [START_REF] Verlhac | Optimization of opening schemes[END_REF], [START_REF] Verlhac | Improved configuration optimizer methodology to use a decision support tool[END_REF], [START_REF] Verlhac | Improved configuration optimizer technical documentation[END_REF]), with the aim to propose new decision support tools for the flow management operators in a short-term future. The proposed methodology is strongly grounded on the current working method: it relies very much on the operators experience, and also uses predefined configurations as well as incoming flows and sector capacities (see [START_REF] Verlhac | Improved configuration optimizer methodology to use a decision support tool[END_REF], p. 12) to assess when a control sector is overloaded. One of the main concerns in this work seems to be the network effect affecting the set of regulations ( [START_REF] Pesic | Network effect: A possible model to highlight interdependencies between flow management regulations[END_REF]), and how it is connected with the building of opening schemes in several centres belonging to a same area of interest.

Our research, which started at the Global Optimization Laboratory (LOG5 CENA/ENAC) some years ago, is a fairly different approach. We were initially interested in how to combine elementary sectors so as to offer a maximum capacity for a given trafic demand. To do that, we chose to explore the whole space of possible configurations that can be built from the set of elementary sectors, rather than the relatively small subset of predefined configurations that are currently being used by the FMPs. In [START_REF] Gianazza | Optimization of air traffic control sector configurations using tree search methods and genetic algorithms[END_REF] and [START_REF] Gianazza | Optimal combinations of air traffic control sectors using classical and stochastic methods[END_REF], we proposed several algorithms (tree search methods and stochastic methods) to compute optimal airspace configurations, using the same variables and thresholds that are used in the operational field (incoming flows and sector capacities).

In [START_REF] Gianazza | Optimal combinations of air traffic control sectors using classical and stochastic methods[END_REF], the potential profits provided by the optimized schedule showed a decrease of 69% of the cumulated delays, while using 20% less ressources, considering only one air traffic centre on one day of traffic. These results -too good to be true -together with the simple comparison of the registered schedule actually sent by the FMP to the CFMU with the real airspace configurations recorded the same day, led us to think that the incoming flows and sector capacities were really inadequate, or at least not sufficient for our purpose. In other words, the traffic load expressed as the number of flights entering the sector in the next M minutes may be useful for smoothing the traffic flows, but it is not enough to assess the actual controller's workload operating the sector. Strangely, this well-known fact seems completely forgotten in the current working method used to build opening schemes.

A general conclusion that can be drawn from these past studies is that the current traffic regulation process is not grounded on solid scientific notions, but highly depends on the operators experience (and of the feedback of experience from past situations): you know how to smooth the traffic using flow regulations, but you are unable to actually quantify the level at which it should be tuned. So, in order to build more realistic airspace configuration schedules, we propose to stop using the incoming flows and sector capacities to assess the controllers workload and to use relevant metrics instead. In order to be actually related to the controller's workload, such metrics should take account of the air traffic complexity within the sector.

C. Air traffic complexity

When considering air traffic complexity, we must be aware that it may be quantified in different ways, depending on the time and geographic scale involved, and on the intended application. It is one thing to compare several service providers over a year of traffic, taking account of aggregated complexity factors, and a very different thing to evaluate the controller's workload every few seconds, taking account of the traffic's complexity within the control sector. So there is no single universal complexity measure and all we may expect is a set of complexity metrics, useful and relevant only in a particular context and for a particular purpose. As a consequence, it is crucial to assess the relevance of the chosen metrics to the final goal.

In our study, the chosen time scale is one measure every minute, the geographic area is the set of control sectors usually operated in an ATC center, and the intended application is the airspace configuration process, with the final aim to find a realistic prediction of the opening scheme. The actual configuration of the control sectors depends on the controllers workload: overloads may lead to a decision to split a sector, and underloads lead to "merge" decitions. As we would rather avoid using (and tuning) a multitude of sector-specific parameters (like capacity values), we need to know how the actual controllers workload is related to the complexity of the sectors they are operating.

Several studies tried to find how the controller's workload is related to air traffic complexity. To do this, one usually tries to maximize the correlation of a set of complexity metrics with a quantifiable variable (called dependant variable) assumed to represent the actual controller's workload. Various methods have been used: linear ( [START_REF] Kopardekar | Measurement and prediction of dynamic density[END_REF]) or logistic ( [START_REF] Masalonis | Dynamic density and complexity metrics for realtime traffic flow management[END_REF]) regression, cross-sectional time series analysis ( [START_REF] Majumdar | The factors affecting airspace capacity in europe: A framework methodology based on cross sectional time-series analysis using simulated controller workload data[END_REF]), neural networks ( [START_REF] Chatterji | Measures for air traffic controller workload prediction[END_REF]),... A multitude of metrics have been proposed in the literature. The reader may refer to [START_REF]Cognitive complexity in air traffic control, a litterature review[END_REF] and [START_REF] Kopardekar | Dynamic density: A review of proposed variables[END_REF] for a review.

Whatever method is used, the choice of the dependent variable is crucial to determine how well complexity is actually measured. Many ways to quantify the controller's workload have been used in past studies: physical activity ( [START_REF] Laudeman | Dynamic density: An air traffic management metric[END_REF], [START_REF] Majumdar | The factors affecting airspace capacity in europe: A framework methodology based on cross sectional time-series analysis using simulated controller workload data[END_REF]), physiological indicators ( [START_REF] Crump | Review of stress in air traffic control: Its measurement and effects[END_REF], [START_REF] Averty | Evaluating a new index of mental workload in real ATC situation using psychological measures[END_REF]), simulation models of the controller's tasks ( [START_REF] Yousefi | Investigation of en route metrics for model validation and airspace design using the total airport and airspace modeler (TAAM)[END_REF], [START_REF]An evaluation of dynamic density metrics using RAMS[END_REF]), subjective ratings ([10], [START_REF] Chatterji | Measures for air traffic controller workload prediction[END_REF], [START_REF] Masalonis | Dynamic density and complexity metrics for realtime traffic flow management[END_REF]). The reader may refer to [START_REF] Gianazza | Evaluation of air traffic complexity metrics using neural networks ans sector status[END_REF] for a discussion on these variables. Let us just say that, in addition to being subject to noise and biases 6 , most of the above dependent variables require relatively heavy experimental setups to collect the data, usually with the active participation of controllers. Databases are often small and might exhibit low variability, which may in turn harm the statistical relevance of the results.

In order to avoid some of these drawbacks, we proposed a new dependent variable in [START_REF] Gianazza | Evaluation of air traffic complexity metrics using neural networks ans sector status[END_REF] and [START_REF] Gianazza | Selection and evaluation of air traffic complexity metrics[END_REF], for which a large amount of data is available from the ATCC databases, and which does reflect an operational reality. The basic idea, introduced in [START_REF] Gianazza | Optimisation des flux de trafic aérien[END_REF], is that the decisions to split (resp. merge) a sector are mostly taken when the controller is close to overload (resp. under-load). So the sector status (merged, manned, or split) is directly related to the controller's workload and may therefore provide an acceptable dependent variable. This data may also be biased or noisy, as we may not be sure that the splitting and merging decisions are always directly related to the workload. Other factors might distort data, such as the training of unexperienced controllers, technical incidents, real-traffic experimentations... However, we assume that the impact of these phenomena on the accuracy of the results is limited particularly because of the kind of complexity we are looking at here 7 . Moreover, we selected our data in a period of high traffic, so we may expect that most configuration changes were caused by the controllers workload.

The selection of the relevant metrics was done in collaboration with the Laboratory of Economy and Econometry of Air transport (LEEA8 ), within the S2D2 project 9 . In [START_REF] Gianazza | Evaluation of air traffic complexity metrics using neural networks ans sector status[END_REF] and [START_REF] Gianazza | Selection and evaluation of air traffic complexity metrics[END_REF] we proposed an original method to assess the metrics relevance, using neural networks and sector statuses obtained from the actual airspace configurations recorded by each ATC center. This method allowed us to select a subset of only 6 relevant indicators among the initial 28 chosen from [START_REF] Kopardekar | Measurement and prediction of dynamic density[END_REF], [START_REF] Chatterji | Measures for air traffic controller workload prediction[END_REF], [START_REF] Delahaye | Air traffic complexity: towards intrinsic metrics[END_REF], [START_REF] Averty | Conflit perception by ATCS admits doubt but not inconsistency[END_REF] and other sources.

As a result of [START_REF] Gianazza | Selection and evaluation of air traffic complexity metrics[END_REF], we also obtained a fairly simple equation (the trained neural network) allowing to predict the sector status from the six relevant metrics, which were the sector volume V , the number of aircraft within the sector N b, the average vertical speed avg_vs, the incoming flows with time horizons of 15 minutes and 60 minutes (F 15 , F 60 ), and the number of potential crossings with an angle greater than 20 degrees (inter_hori). We now propose to use these metrics and the neural network's prediction to build a realistic schedule of the airspace configurations operated in the ATC centre's control room.

II. INPUT DATA

The relevant metrics are computed every round minute of the day, using recorded radar data and environnement data (sector description) from the french ATC centers. Radar data is available in several forms: records made by each center, with one position every twelve seconds, in average, and a global record of the five french centers, with one position every three minutes. Several months of global records were available, whereas the centers local records were not readily available, at least for a sufficiently long period of time. So we used the global records (made by the IMAGE system), and interpolated the aircraft positions in order to get one position per minute. As many trajectory changes may occur within three minutes of flight, the computed positions are not highly accurate, and this may introduce a bias in the indicators values. However, this bias is most probably of small importance in our problem: we just want to predict when a sector will be merged into another one, or split in several smaller sectors. We are not considering the instant workload, which may require a higher level of accuracy on the aircraft positions, speed, and so on.

Several months of recorded traffic are available. We have restricted our choice, at least for the moment, to two days of traffic. We chose the 1st June 2003, that was previously used in [START_REF] Gianazza | Evaluation of air traffic complexity metrics using neural networks ans sector status[END_REF] and [START_REF] Gianazza | Selection and evaluation of air traffic complexity metrics[END_REF] to select the relevant metrics and train and test the neural network providing the sector status prediction. We also tried another day (June 2nd, 2003) that was not previously used.

Airspace configurations are built from elementary sectors that may be merged together into larger control sectors. So an airspace configuration is a partition of the set of elementary sectors. However, these partitions should only contain control sectors that are operationally valid. For example, a control sector should generally not be made of two sectors that are not neighbours. Once again, we referred to the ATC centers databases, which provide the list of elementary sectors of each center, and also the groups of sectors that can be merged together into a control sector.

III. SECTOR STATUS PREDICTION

Artificial neural networks are used to predict the sector status from the relevant complexity metrics. In previous works ( [START_REF] Gianazza | Evaluation of air traffic complexity metrics using neural networks ans sector status[END_REF], [START_REF] Gianazza | Selection and evaluation of air traffic complexity metrics[END_REF]), we trained such networks on real sector statuses in order to assess the relevance of a set of complexity metrics.

In the work presented here, we use the trained network and the most relevant metrics to predict the sector status on fresh input data. This allows us to decide when a given control sector is normally loaded, overloaded, or under-loaded, and when an airspace configuration should be recombined.

The reader unfamiliar with neural networks may refer to the the fairly wide literature on the subject. Let us just say that an artificial neural network is an algorithm inspired from the biological neurons and synaptic links, that may be represented as a graph with vertices (neurons, or units) and edges (connections) between vertices. There are many types of such networks, associated to a wide range of applications: pattern recognition (see [START_REF] Bishop | Neural networks for pattern recognition[END_REF] and [START_REF] Ripley | Pattern recognition and neural networks[END_REF]), control theory,... Beyond the similarities with the biological model, an artificial neural network may be viewed as a statistical processor, making probabilistic assumptions about data ( [START_REF] Jordan | KEYWORDS Air traffic complexity, airspace configuration, flow management, neural networks[END_REF]). Some train data is used to determine a statistical model of the process which produced this data. Once correctly trained, the neural network uses this model to make predictions on new data.

For our application, we use a fully connected feedforward neural network with three unit layers (or two weight layers), as shown on figure 1. For details on how this network was trained and tested, the reader may refer to [START_REF] Gianazza | Selection and evaluation of air traffic complexity metrics[END_REF]. We will just summarize its main features and give the equation of the relationship between the input and the output of the network.

The input variables are the relevant complexity metrics {V, N b, avg_vs, F 60 , F 15 , inter_hori}, normalized The neural network's equation is written as follows:

(y 1 , y 2 , y 3 ) T = Ψ( 15
j=1
w jk Φ(

6 i=1 w ij x i + w 0j ) + w 0k )
(1) where the output vector y = (y 1 , y 2 , y 3 ) T is a triple of posterior probabilities. This means that y 1 is the probability to fall in the merged class when the input vector is (x 1 , ..., x 6 ) T , and the same for y 2 and y 3 , with the manned (i.e. normal domain of operation) and split classes respectively. Ψ is the softmax function:

Ψ(z k ) = e z k 3 m=1 e zm (2)
Φ is the sigmoïd logistic function:

Φ(z) = 1 1 + e -z (3)
The adjusted weights w of the neural network are provided in the appendix 10 , together with some R code allowing to make the prediction.

It must be underlined that the output of the neural network is a triple of values that can be considered as probabilities, with each output y k comprised between 0 and 1. To emphasize this fact, we will denote (p merge , p man , p split ) the output of the neural network in the next section.

The network is unable to make complex recommendations such as to split the sector's volume in several parts and then to merge each of these parts with other sectors. It only recommends to merge the sector when the workload is low, or split it when the workload is high, or operate it normally when the workload is acceptable. As we are necessarily in one of the above three cases, the sum of the three probabilities y 1 , y 2 , and y 3 is always 1.

Let us note that, although these probabilities can be used to determine if a sector is normally loaded, overloaded, or under-loaded, they are not actually a numeric quantification of the workload.

IV. BUILDING AIRSPACE CONFIGURATIONS

A. General description of the process

Our aim is to compute at each time step of the day a realistic airspace configuration, so that each control sector has the highest possible probability to be in its normal domain of operation.

To do so, we start at time t=0 with a configuration where all elementary sectors are assigned to a single controller's working position. The situation is then reconsidered every minute of the day. The current configuration is re-assessed by considering the status prediction of each control sector.

Some of these sectors will remain unchanged: those for which the status is manned with a high probability. The others -which need either to be split or merged according to the neural network's prediction -will be entirely recombined as follows. We build every possible partition 11 from the elementary sectors composing these sectors. The best partition is then chosen (we shall see later what criteria are used to assess the partitions), and it replaces the initial set of sectors that needed to be recombined.

Let us now give a few details, first on the decision criteria which allows to decide when the airspace configuration must be changed, second on the algorithm used to explore all the combinations of sectors that need to be reconfigured, and third on the evaluation criterion used to select the best configuration.

B. Decision criteria

The decision to reconfigure sectors is driven by the prediction made by the neural network. The neural network's output is a triple (p merge , p man , p split ) of probabilities to belong to one of the classes (merged, manned, or split), with p merge + p man + p split = 1 (see section III).

The most straightforward decision criterion is to choose the class with the highest probability. Let us call D1 this decision criterion. This criterion may lead to many sectors reconfigurations: the highest probability may be only slightly higher than the others, and for short periods of time.

The actual sector configurations exhibit few fluctations in time. So we tried another decision criterion D2, considering how close the highest probability is from 1, and also the difference between the two highest probabilities. For example, a triple of probabilities (0.1, 0.1, 0.8) is a stronger incitation to split the sector than (0.1, 0.44, 0.46).

Let us consider our three probabilities sorted by decreasing values p 1 , p 2 , p 3 . The new decision criterion, that we will call D2, is expressed as follows, depending on which probability is the highest:

• if p 1 is the probability p merge to merge the sector: the decision to recombine the sector is taken only if 1p 1 < α and p 1p 2 > η, where α and η are chosen parameters. • if p 1 is the probability p split to split the sector: we decide to split only if 1p 1 < β, where β is a chosen parameter. In the other cases, the sector remains unchanged. We choose different criteria for the 'split' and 'merge' decisions, because we may need to be more reactive when the workload is increasing than when it is dropping down.

The decision criteria will provide us with a list of sectors that need to be recombined. The decision criterion D2, as described above, is bound to find a smaller list of sectors than D1, which may reduce the choices when recombining the sectors. A typical example is when only one sector needs to be merged, or several sectors that are not neighbours. So we will use D2 to decide when a configuration must be recombined, and use D1 to build the larger list of sectors that will be recombined.

The algorithm described in the next section will use this list as input, by building the subset of elementary sectors from which the initial control sectors are made, in order to compute all the possible partitions from these sectors. Let us now describe how this is done.

C. Searching sector configurations

The algorithm used to build all the valid sector configurations from an initial set of elementary sectors is a classical tree search algorithm. Figure 2 shows how to build all the partitions of a set of 5 elements: starting with element 1 in a single group, we have the choice to add the second element in the same group, or create a new group, and so on until all elements have been considered. We can use this algorithm to build all the partitions of a set of sectors. However, many of these partitions contain groups of sectors which are not valid, from the operational point of view. For example, it is most unlikely that a controller will handle a group of sectors which does not form a contiguous portion of airspace.

Hopefully, the airspace description found in the ATCC databases provides us, together with the list of elementary sectors, with the list of operationally valid groups of sectors. We just need to introduce this restriction in our tree search algorithm, as shown in figure 3 In this tree search, each node is a list of couples. The first item of a couple is a subset of sectors, and the second is the list of valid groups containing this subset, but which contain no sector from the other subsets of the node. When a list of valid groups is found to be empty, the branch is not explored: it will never lead to a valid configuration. The leaves of the tree are partitions made only of valid groups.

Let us now consider an hypothetic ATC centre of 20 elementary sectors for example. Let us imagine a situation at a time t where the airspace is configured in 4 large sectors, and with an increasing workload requiring that 3 of them be split in smaller sectors. Let us say that the 3 sectors are made of a combination of 15 elementary sectors. However steep the workoad's increase is, it is most unlikely in real life that the traffic will require to man all the 15 elementary sectors on separate control units at time t+1. Real traffic doesn't exhibit such drastic variations in one minute.

So it may be useless to compute all the partitions. We may focus on the partitions for which the number of groups does not exceed a chosen maximum. Typically, if p is the number of control sectors that need to be split, and q the number of sectors that need to be merged according to our decision criterion, we will search all the partitions comprising at most 2p + q + 1 groups. This will avoid to explore all possible partitions, without compromising our aim to find a realistic configuration.

D. Evaluation criterion

We have shown how to compute valid sector partitions that will replace the initial sectors that need to be split or merged. The tree search algorithm explores all possible airspace configurations, among which we must choose only one. Let us define the evaluation criterion used to select the best configuration.

Ideally, a good configuration is one for which all sectors (groups of elementary sectors) will have a probability to be in the manned status as close as possible to 1, according to the neural network's prediction.

However, we must also be able to evaluate configurations with overloaded sectors, for which the neural network issues a split recommendation, as well as underloaded sectors (merge recommendation).

Our evaluation criterion should be designed so as to penalize overloads more than underloads, which should themselves be more penalized than configurations with only normally loaded sectors.

When comparing two configurations with underloads or two configurations with normal workoad, we would rather choose the one with the less sectors, if they are otherwise equivalent. So the number of control sectors should also be included in the evaluation criterion.

Considering config(t) the configuration of the airspace at time t, let us call p merge (x, t), p man (x, t), and p split (x, t) the probabilities computed by the neural network for each sector x of the configuration, and N sect (x) the number of elementary sectors grouped together to form the sector x.

Let us define δ merge (x, t) the function such that δ merge (x, t) = 1 if p merge (x, t) is higher than the two other probabilities, and is equal to 0 otherwise. Two other functions δ man (x, t) and δ split (x, t) are similarly defined. In our evaluation criterion, we shall use:

• N units (t) the number of airspace units in the configuration at time t,

• C + (t) = x∈conf ig δ split (x, t).p split (x, t).N sect (x), • C(t) = x∈conf ig δ man (x, t).(1 -p man (x, t)), • C -(t) = x∈conf ig
δ merge (x, t).p merge (x, t).N sect (x).

We could have assigned a cost to the overloads, normal loads, and underloads, simply by cumulating the values of the probabilities in each case. For example, we could have chosen a cost x∈conf ig δ split (x, t).p split (x, t) for the overloads, and similar costs for the under-loads and normal loads. With such cost functions, however, a highly overloaded configuration with only one sector 12may well have a cost close to 1, as the probability p split (x, t) is likely to be high, while always remaining between 0 and 1. Considering a configuration where we split this single sector into two sectors, and supposing that these two sectors are still highly overloaded, the cost of such a configuration is likely to be close to 2, that is to say more than for the previous configuration.

This undesirable feature, due to the fact that we use status probabilities, and not actually a numeric quantification of the workload, is avoided by introducing the number of elementary sectors in the costs, so that an overloaded configuration with few control units controlling big sectors will have a higher cost than configurations with more control units with sectors of smaller sizes.

Finally, the evaluation criterion used to select the best configuration is:

eval conf ig = 10 k2+k3+k4 × N (k 1 , C + (t)) +10 k3+k4 × N (k 2 , N units (t)) +10 k4 × N (k 3 , C -(t)) +N (k 4 , C(t)) (4)
where N is a function such that

N (k, c) = ⌊max(0, (10 k -1) -c)⌋
and the exponents k 1 , k 2 , k 3 , and k 4 are chosen so that the term (10 k -1) is an upper bound of the corresponding cost c. This criterion is designed so that the k 1 digits of higher order represent the cost of overloads, the k 2 next digits are related to the number of units in the configurations, the k 3 next digits are assigned to the underloads cost, and the k 4 digits of lower order are related to the cost of normally loaded configurations.

V. RESULTS

Let us now present some results, and compare the configuration schedule computed with the complexity metrics to the real configurations recorded by the ATCC on the same day, and also to the FMP opening scheme.

Note that the comparison with the FMP opening scheme is not entirely fair: our configuration schedule is computed using recorded radar tracks, whereas the FMP scheme was built using the filed flight plans available two or three days before D-day. Still, it gives a good hint of the potential benefits of the method we propose, and the comparison with the real configurations remains fair: the actual merge/split decisions were taken with the same radar data as input.

A. A full example

As a first example of the results provided by the algorithms proposed in section IV, let us consider Brest Air Traffic Control Centre, on the 1st june, 2003. The decision criterion is D2, with the following parameters values: α = 0.5, η = 0.2, and β = 0.5. Figure 4 shows an example of the final ouput of our algorithm. The time t is given in minutes after 00h00. Only a short period of time is presented, roughly between 04h20 and 07h00. The airspace configurations actually used on the same day for the same period are shown on figure 5.

When comparing these two schedules, we observe some differences in the choice of the control sectors composing the configurations. This is not a surprise. For a same traffic situation, there are often several ways to split the airspace in order to balance the workload among the control sectors. And in a same situation, different control room's managers may make different arbitrary choices. So it is not surprising that we do not find exactly the same configurations.

From the author's past experience in Brest ATCC, the configurations of the computed schedule seem realistic, although this would have to be confirmed by experienced FMP operators. At a more macroscopic level, we may compare the number of control units in the computed schedule and in the real configurations. It is also interesting to compare these two schedules with the FMP opening scheme made two days before D-day. Figure 6 shows the evolution of the number of control units for the three configuration schedules. The horizontal axis shows the time, expressed in minutes after 00h00, and the vertical axis the number of control units.

[AOUS J Q RFX RNG Z] t= 283 [AOUS FBRT J Q RNG RZX] t= 304 [AOUS FBRT J Q RNG X Z] t= 317 [AOUS J Q RFX RNG Z] t= 324 [A FBRT J O Q RNG RZX] t= 328 [A FBRT J O Q RNG X Z] t= 332 [AOUS FBRT J Q RNG X Z] t= 335 [AOUS FBRT G J N Q X Z] t= 337 [AOUS J Q RFX RNG Z] t= 338 [AOUS FBRT G J N QS QU X Z] t= 342 [AOUS FBRT J QS QU RNG X Z] t= 343 [AOUS J QS QU RFX RNG Z] t= 344 [AOUS FBRT J QS QU RNG X Z] t= 347 [AOUS FBRT J QS QU RNG ZXIU ZXS] t= 354 [AOUS FBRT J Q RNG ZXIU ZXS] t= 356 [AOUS FBRT J Q RNG XIU ZIU ZXS] t= 360 [AOUS FBRT J Q RNG X ZIU ZS] t= 363 [AOUS FBRT J Q RNG X Z] t= 370 [A FBRT J O Q RNG X Z] t= 381 [AOUS FBRT J Q RNG X Z] t= 394 [AOUS FBRT J Q RNG X ZIU ZS] t= 409 [A FBRT J O Q RNG X ZIU ZS] t= 426 [AOUS FBRT J Q RNG X ZIU ZS ...

and so on

On this figure, we see that the prediction using complexity metrics shows more variations in time than the real configurations. The reason is that, with our algorithms, some overloads or under-loads lasting only a few minutes will lead to configuration changes, whereas in the real world, they are disregarded and the resulting curve is smoother. If we go a little further in the explanation, it may be that, apart from the incoming flows which use an anticipation window of 15 or 60 minutes, most of the metrics used as input of our neural network give only a snapshot of the situation at time t. These metrics are subject to high variations in time, which may account for the many changes we observe in the number of configurations. It may have been useful to smooth the metrics values on a chosen time window before using them as input, or to use the anticipated values of these metrics, predicted for a short period ahead the current time t.

Another and more simple way to get a more realistic airspace configuration schedule would be to introduce an anticipation window in the process described in IV. This would allow to detect and discard the configuration changes that last only a few minutes. Despite these variations, our prediction stays fairly close to the real configurations. There is however an exception between 1110 minutes (18h30) and 1240 minutes (20h40), where our computation shows between two and three more control sectors than what was actually manned. The detailed outputs of our algorithms showed several consecutive configurations where two or three non-adjacent sectors (Q, ZX, and GS for example) were given a "merge" decision by the neural network, and the others had a "no change" decision. The list of sectors to recombine was only made of sectors that were not neighbours, so it was not possible to merge them, and they remained opened.

We tried to avoid this problem when designing the decision criterion D2 but it seems this was not enough, and we will have to improve our algorithm by extending the recombination to neighbouring sectors, even if it was not initially decided to merge or split them.

Although there remains a few points that need to be improved, the results shown on figure 6 are already fairly good, especially if we compare with the FMP opening scheme. Of course, in order to be in the same context as the FMP, we should use the flight plans of the final traffic demand as input instead of the recorded radar tracks. We could then check if our prediction would remain so close to reality. The work presented here was only intended to show that the use of complexity metrics allows to simulate how a control's room is operated, with a high degree of realism. This is a necessary step towards realistic predictions that could be used in the FMP/CFMU flow regulation process. Figure 8 shows the results for the same day and the same center, but using criterion D2 with α = 0.5, η = 0.2, and β = 0.5. The curve of the computed configurations is slightly different from figure 7. This is not surprising, as the sequence of merge/split decisions is different. However, the curve still exhibits many variations. The use of criterion D2 with the chosen values of α, η and β does not succeed in smoothing the variations in the number of control sectors.

We tried different values of these parameters. Figure 9 shows the best compromise that we found, with α = 0.10, η = 0.2, and β = 0.3. These values were chosen so that our algorithms is more reactive when the workload increases than when it drops down. This seems to reflect the actual controllers behaviour.

The results may again be improved through more extensive parametric tests to tune the criterion D2, by minimizing the quantified difference between the com- Evolution of the number of control sectors (computed schedule, real configurations, and FMP opening scheme) for Reims ATCC (2003, June 2nd), with decision criterion D2 (α = 0.1, η = 0.2, and β = 0.3) puted schedule and the real configurations. There could be other alternative methods than the use of criterion D2 to smooth the schedule. We could smooth the values of the metrics taken as input, and use metrics that better reflect the anticipation of future workoad. We could also introduce an anticipation window in the decision process.

On the real configurations of that day, we observe four peaks in the number of control sectors which are not found in the computed schedules, whatever the chosen decision criterion. The first two are in the morning from 09h37 (t=577) to 10h08 (t=608), and from 11h16 (t=676) and 12h06 (t=726). The two others are in the afternoon, from 14h28 (t=868) to 14h37 (t=877), and from 16h13 (t=973) to 16h50 (t=1010). There may be several explanations to this. The population of controllers is not homogeneous, and some may accept more complex and heavy traffic than others whereas the neural network provides only an averaged prediction.

However, these peaks are more probably caused by "split" decisions which are not related to the controllers workload. On the opposite, the decisions to split sectors in the early morning are clearly related to a workload increase, and the correlation of the computed schedule with the real configurations is fairly good.

VI. CONCLUSION

To conclude, let us summarize the main ideas that were developped during our research on airspace configuration schedules and complexity metrics, with the aim to ground the FMP/CFMU flow regulation process on more objective and quantified variables.

First, we introduced algorithms exploring the whole space of possible configurations that can be built from the center's elementary sectors, rather than the small subset of pre-defined configurations currently used by the FMP.

Second, we proposed to stop using flight counts and sector capacities to assess the overloads or underloads, and to use relevant air traffic complexity metrics instead.

The original idea for selecting these relevant metrics was to use the real sector status (merged, manned, or split) of the control sectors as a new dependent variable to assess the actual controller's workload. This data, issued from the real airspace configurations recorded by the ATCCs, is available in large quantities and does not require heavy experimental setups to be collected. In addition, it does reflect an objective operational reality, directly related to the intended application.

In this paper, we showed how the selected metrics could be used to build airspace configuration schedules. The results presented in section V are an important step towards a realistic prediction of airspace configurations. When using recorded radar data as input, our algorithms compute opening schemes which seem realistic, with a number of control sectors close to the real configurations recorded by the ATC center.

However, before considering a possible future use of our method in the operational context, it remains to be checked if such a realistic prediction could be made with the flight plans of the final traffic demand as input, instead of the radar tracks. It may be so, considering that the relevant complexity metrics are not so sophisticated, and that smoothed values of these metrics may be even more relevant. If the existing flight plan data is not accurate enough, we may expect that future 4Dtrajectory planning requirements will allow to compute a good prediction of the opening scheme, two or three days before D-day.

Apart from the FMP/CFMU opening schemes, there are many potential applications to the neural network's sector status prediction. As it is representative of how the current control sectors are being operated today, it could be used, for example, in real-time simulations to benchmark new working methods, new control tools, or changes in the airspace structure.

A more extensive testing and tuning of our algorithms is required first. In future research, we shall explore several ideas that could improve our method, like smoothing the computed schedule by introducing an anticipation window, or recombining sectors on a larger scale when merging decisions are issued. We could also try other complexity metrics that would exhibit less variations than the ones we used, as in real life the decision to split or merge sectors is not taken so often in a day. Such metrics could be obtained by averaging existing metrics over a short period of time. It may be useful to reflect the anticipation of future workload by using the predicted values of some metrics as input. Other types of neural networks, or other techniques, more adapted to dynamic discrete choices could also be tried.

Fig. 1 .

 1 Fig. 1. Feed-forward network for sector status prediction

{1, 2 Fig. 2 .

 22 Fig. 2. Searching the partitions of a set of 5 elements

  ... t= 258 [AOUS FZX RNG RQJ] t= 261 [AOUS RFX RNG RQJ Z] t= 265 [AOUS FZX RNG RQJ] t= 266 [AOUS RFX RNG RQJ Z] t= 281

Fig. 4 .

 4 Fig. 4. Example of computed airspace configurations for Brest ATCC (2003, June 1st)

Fig. 5 .

 5 Fig. 5. Example of real airspace configurations for Brest ATCC (2003, June 1st)

Fig. 6 .

 6 Fig. 6. Number of control sectors (computed schedule, real configurations, and FMP opening scheme) for Brest ATCC (2003, June 1st), with decision criterion D2

Fig. 7 .Fig. 8 .

 78 Fig. 7. Number of control sectors (computed schedule, real configurations, and FMP opening scheme) for Reims ATCC (2003, June 2nd), with decision criterion D1

  Fig. 9. Evolution of the number of control sectors (computed schedule, real configurations, and FMP opening scheme) for Reims ATCC (2003, June 2nd), with decision criterion D2 (α = 0.1, η = 0.2, and β = 0.3)

  .

	Valid groups of sectors :
	a: {2,3} b: {3,4}
	c: {4,5} d: {1,5}
	e: {1,2,3,4,5}				({1},{s,d,e})
	s: generic term for a singleton
	{1},{2},{3},{4} or {5}
			({1,2},{e})			({1},{s,d}) ({2},{s,a})
		({1,2,3},{e})	({1,2},{}) ({3},{s,b})	({1,3},{}) ({2},{s})	({1},{s,d} ({2,3},{a})	and so on...
	({1,2,3,4},{e}) ({1,2,3},{}) ({4},{s,c})	({1,4},{}) ({2,3},{a})	({1},{s,d}) ({2,3,4},{})	({1},{s,d}) ({2,3},{a}) ({4},{s,c})
	({1,2,3,4,5},{e})	({1,2,3,4},{}) ({5},{s})			({1,5},{d}) ({2,3},{a}) ({4},{s})
		Fig. 3. Searching all valid airspace configurations

A control sector may be manned (or operated, or armed) by a team of two controllers when the workload is normal, or split , when this is possible, into smaller sectors operated separately if the traffic is high, or merged (or collapsed) with other sectors to form a larger sector when the traffic is low.

Irrelevant statuses, such as when a part of the initial sector is merged with one control sector, and the other part with another control sector, were discarded in the neural network's training.

From now on, we will prefer the term manned instead of armed that was used in previous works, to denote that the sector is in its normal domain of operation.

such regulations are called "traffic-volume" in some Eurocontrol documentations ([START_REF] Verlhac | Improved configuration optimizer methodology to use a decision support tool[END_REF])

http://www.recherche.enac.fr/opti/

such as the subjective ratings recency effect denounced in[START_REF] Averty | Evaluating a new index of mental workload in real ATC situation using psychological measures[END_REF], or raters errors in the case of "over-the shoulder workload ratings"[START_REF] Mannings | The relationship between air traffic control events and measures of controller taskload and workload[END_REF]

Pre-tactical applications do not ask for as much details as studies of instantaneous workload would. On the opposite, benchmarking of ATC centers would require an even coarser granularity, as indicators are averaged on wide temporal and geographical horizons ([START_REF] Flynn | Traffic complexity indicators and sector typology analysis of U.S. and european centres[END_REF],[START_REF]Note de synthèse sur l'indicateur de complexité PRU[END_REF],[START_REF]Complexity metrics for ANSP benchmarking analysis[END_REF])

http://www.enac.fr/recherche/leea

http://www.recherche.enac.fr/opti/S2D2/

although not with the full range of decimals, due to presentation constraints.

A partition is a mapping of the elementary sectors on a number of controller's working positions.

All elementary sectors merged as a single control unit.

The POM team was formerly part of the Global Optimization Laboratory LOG CENA/ENAC

APPENDIX A: FULL DESCRIPTION OF THE NEURAL NETWORK USED FOR SECTOR STATUS PREDICTION

This appendix details the adjusted weights of the neural network that was found in [START_REF] Gianazza | Selection and evaluation of air traffic complexity metrics[END_REF], and also provides some R code allowing to predict the sector status. Due to presentation constraints, the full range of decimals is not written.

The R code providing the triple of probabilities (y1, y2, y3) (see equation III) is written on figure 10. In this code, Mh and Mo are the matrices of parameters (weights and biases) assigned to the connections between the input layer and the hidden layer, and between the hidden layer and the output layer, respectively. Biases are handled in the network by adding special units returning a constant value 1. The biases are the weights assigned to the connections between such an unit and the next layer.

f.softmax <-function(z) {exp(z)/sum(exp(z))}; f.logistic <-function(z) {1/(1+exp(-z))} f.predict <-function(input) { f.softmax(Mo %*% c(1, f.logistic(Mh %*% (c(1,input))))) } Fig. 10. R code for the prediction of sector status Table I details the values of Mh. The first column contains the biases w0j . The second gives the weights of the connections between the input x1 (volume V ) and the 15 hidden units, and so on with the other columns.

Table II describes the transpose matrix Mo T (the matrix has been transposed in order to fit in the page). The first column of Mo also contains biases, and the 15 others give the weights of the connections between the hidden units and the output units.


Pierre-Selim Huard
email: huard@recherche.enac.fr

Nicolas Barnier
email: barnier@recherche.enac.fr

Cédric Pralet
email: cpralet@onera.fr

Automated mission planning for a fleet of micro air vehicules

The ENAC University is using and developping the Paparazzi UAV system, which aims to provide a free and fully autonomous autopilot for a fleet of MAV, including fixed wing and rotary wing MAVs. The Paparazzi project has now succeeded in providing a fully autonomous navigation system for multiple fixed-wing aircraft system. One of the main concern of the project is the development of autonomous decision making algorithms and cooperative behaviour between the different MAV of a fleet to increase the level of autonomy of the system. We can distinguish 4 different levels of autonomy: the manual level, the augmented stability level with or without pilot through video, the flight plan level where the mission is described in terms of trajectories and waypoints, and the mission level where the mission is described in terms of goals. In this paper, we focus on the latter, which implies to solve the automated mission planning problem for a fleet of MAV. We first present a formal model for this problem inspired by the MAV06, EMAV2006 and MAV07 contests, then we propose two different approaches to solve it.The first one is based on dynamic programming and computes a policy which gives the action to take for each state, regardless of prior history and taking the uncertainties into account, whereas the second one is a real-time planning and replanning algorithm based on the A* algorithm.

I. A formal model of a mission

Automated planning 1 is a branch of Artificial Intelligence which aims to provide algorithms which can compute policies or plans to realize a set of fixed goals performed by agents such as ground robots or UAV. To modelize classic planning problems we use restricted state-transition systems (see figure 1). These systems are determinist (there is no uncertainty), finite (there is a finite number of state and action), and completely observable (there is no uncertainty on the state observation). We denote this system Σ = (S, A, γ) where S is a finite set of states, A is a finite set of actions, γ : S × A → S is a transition function.

A planning problem is then defined as a triple P = (Σ, s 0 , g) with Σ a restricted state-transition system, s 0 the initial state, and g a set of final states. Solving the mission planning problem consists in finding a valid sequence of action which permits to go from an initial state to a final state. In our case, the final states are defined as a state where all MAVs are either at home or on ground (or out-of-order).

Definition 1 A plan is sequence of action π = (a i ) i∈ [1..n] where n is the size of the sequence. A solution to P is a plan π(a i ) i∈ [1..n] that satisfies: s n ∈ g where s n = γ(γ(. . . γ(s 0 , a 1 ) . . . , a n-1 ), a n ) 1) go (2) go (1) go( 1) go (2) go (1) go (2) go( 1) go (2) go(0) go(0) Figure 1. A state transition system that describes a mission with 1 vehicle and 2 drop zones. 0 is home, 1 is the first drop zone, 2 is the second drop zone.

I.A. States description

Each state can be described with first-order logic or with variables representation. In this paper we only use the variables representation. We define each state as a set of variables which represents the state of each MAV of the fleet, and the achievement of each goal. Moreover, for a fleet of MAVs we need to synchronize the actions of the various aircraft. To do this synchronization, we add a variable for each MAV describing the time left to the end of the current action.

For each MAV i we have the following variables at decision step t:

• position[i, t] ∈ [0, ..., n -1] is the position of the MAV and n is the number of waypoints in the mission.

• ball[i, t] ∈ [0, . . . , balls max ] is the number of paintballs left in the airframe.

• video[i, t] ∈ [0, 1] is set to 1 if the MAV has a video camera sensor. This variable is constant if we consider that the video camera won't fail during the mission.

• f lying[i, t] ∈ [0, 1] represents if the MAV is flying or not.

• time[i, t] ∈ [0, ..., time max ] is the time to the end of the current action and time max is the maximum time of an action.

• action[i, t] ∈ {nop, takeof f, go(x), eight, drop, land, nop}, x ∈ [0, . . . , n -1] is the current action.

For each goal k we have : goals[k, t] ∈ [0, 1], deepending whether the goal k is achieved or not.

At the initial state all MAVs are on ground.

I.B. Actions and transitions description

The transition function γ describes the constraints, 2 i.e. the preconditions and postconditions of an action that bind two successive states. Therefore, we use the language of constraints to express γ. An action for a fleet of MAVs is the vector a = (a 1 , a 2 , . . . a i . . . , a nb aircraf t ) of the actions of each MAV. In this paper we consider for each MAV the following actions: Takeoff, Land, Move, Eight a and Drop b .

I.B.1. The preconditions

A MAV has to finished its current action before it begins a new one, therefore for each action we have the following precondition: time[i, t] = 0.

In this paper we consider the following constraints:

Takeoff The MAV is on the ground and Takes off, which gives the following constraint:

(f lying[i, t] = 0)
Land The MAV is flying and lands on the ground:

(f lying[i, t] = 1)
Move The MAV is flying and move to a waypoint x :

(f lying[i, t] = 1)
Eight The MAV does a eight figure centered over the target x to identify it:

(f lying[i, t] = 1)∧(postion[i, t] = x)∧ (video[i, t] = 1)
Drop The MAV drops a ball on the target x:

(f lying[i, t] = 1) ∧ (position[i, t] = x) ∧ (ball[i, t] > 0)
Nop The MAV is on the ground and does no action:

((time[i, t] = 0) ∨ (action[i, t] = nop))∧(f lying[i, t] = 0)

I.B.2. Action in progress

Additional other constraints need to be met as well by the following variables.

If time[i, t] > 1 the current action is not finished, so the state variables are constants except for the time variable:

position[i, t + 1] = position[i, t] ball[i, t + 1] = ball[i, t] f lying[i, t + 1] = f lying[i, t] action[i, t + 1] = action[i, t]
The evolution of the time to the end:

time[i, t] > 0 ⇒ time[i, t + 1] = time[i, t] -1 time[i, t] = 0 ⇒ time[i, t + 1] = duration(action[i, t + 1]) -1

I.B.3. The effects

If time[i, t] = 1, the constraints translating the effects of actions are applied to the state variables:

• After taking off the aircraft is flying, the f lying variable is set to 1 (see equation ( 1)).

• After landing the aircraft is on the ground, the f lying variable is set to 0 (see equation ( 2)).

• After moving to x the aircraft position is x (see equation ( 3

action[i, t] = takeof f ⇒ f lying[i, t + 1] = 1 (1) action[i, t] = land ⇒ f lying[i, t + 1] = 0 (2) action[i, t] = move(x) ⇒ position[i, t + 1] = x (3)
Let k be the goal corresponding to the realisation of action[i, t] at position[i, t]. If time[i, t] = 1 then:

action[i, t] = eight ⇒ goal[k, t + 1] = 1 action[i, t] = drop ⇒ (goal[k, t + 1] = 1) ∧ (ball[i, t + 1] = ball[i, t] -1) goal[k, t] ≤ goal[k, t + 1]

I.C. Optimisation

To compare the quality of different solutions we use a criterion, also called utility function (U : S → R). This criterion permits to choose the best solution. In some cases, finding the optimal solution can be too expensive computationaly speaking. In those cases we use the criterion to find a "good" solution (but not the best).

In this paper, we chose to first maximize the amount of goal achieved (or the sum of the utilities if some goal are more important than others) within a given time and then to minimize the duration of the mission.

II. Mission planning under uncertainty

In the first part we have not modelised the uncertainties in the problem. We write it as if it traduces the reality of operations. However, the result of an action is not always deterministic. Markov Decision Processes 3 are a frequently used model to take into account the uncertainty of the effects of an action. It introduces the probability of transition between two states as a function T : S × A × S → [0, 1]. In this paper we choose to use a formalism based on Uncertainties, Feasibilities c , and Utilities 4 which is better suited to our problem because we have already describe feasibilities and utilities in the previous section. Therefore we only need to describe uncertainties.

We suppose the result of an action does not depend on the prior history, it depends of the current state and of the enviroment only.

II.A. The uncertainties

We assume that only the achievement of a goal is uncertain. We define the probability of identification of a target at the end of the eight figure by the MAV i:

P id (i) = P (goal[k, t + 1] = 1 | goal[k, t] = 0, action[i, t] = eight, time[i, t] = 1, position[i, t] = pos(k)) Let {i 1 , . . . , i m } be a set of MAV verifying action[i, t] = eight, time[i, t] = 1, position[i, t] = pos(k).
The event "MAV i identify the target k" does not depend of the event "MAV j identify the target k", therefore using the Poincaré formula we have:

P id = P (goal[k, t + 1] = 1 | goal[k, t] = 0) = m j=1 (-1) j-1 1≤i1<•••<ij ≤m [P id (i 1 ) × P id (i 2 ) × • • • × P id (i j )]
c Feasibilities corresponds to the transition constraints.

3rd US-European Competition and Workshop on Micro Air Vehicle Systems (MAV07) & European Micro Air Vehicle Conference and Flight Competition (EMAV2007), 17-21 September 2007, Toulouse, France

And if P id (i) = p does not depend of the MAV i we have:

P id = m j=1 (-1) j-1 j l=1 j l p l (4)
We can define the probability of dropping a ball close to the target using the same properties as in (4).

II.B. Solving

To solve a planning mission with uncertainty, we propose to generate an optimal policy π : S → A which will maximize the expected utility after each step of decision. We use Bellman's optimality equations (see equations 5 and 6) and dynamic programming [START_REF] Putterman | Markov Decision Processes: Discrete Stochastic Dynamic Programming[END_REF][START_REF] Bellman | Dynamic Programming[END_REF] to compute the optimal value V * n (s) at each step of decision n for each state s and the corresponding action π n (s).

V * n (s) = max a∈A s ′ ∈S P (s, s ′ , a) (U (s ′ ) -U (s)) + V * n+1 (s ′ ) (5)
π n (s) = argmax a∈A s ′ ∈S P (s, s ′ , a) (U (s ′ ) -U (s)) + V * n+1 (s ′ ) (6)
However some problems cannot be solved within acceptable computation times (e.g. a mission with 3 targets, 1 MAV and 120 decision steps can take as much as 3 hours to solve on a PIV 3GHz). Moreover, it might be impossible to know the probabilities of transition between state, or to a long time before the mission the field conditions such as wind.

III. Real time mission planning and replanning

Our second method is a real-time planning and replanning algorithm. It permits to solve problems that cannot be modelled with probabilities. The algorithm we use to compute the plan is based on the classic A* algorithm. 6 We build a plan offline assuming all actions are deterministic and will succeed. During the execution of the plan we check whether an action fail or does not end in the forecasted state, and replan when necessary.

We define three different stages of the real-time planning [START_REF] Paolucci | Interleaving planning and execution in a multiagent teamplanning environment[END_REF] and replanning algorithm. The A* planner which builds a new plan from current state, the execution which runs the plan, and the controller which checks if the plan needs to be corrected (see figure 2).

3rd US-European Competition and Workshop on Micro Air Vehicle Systems (MAV07) & European Micro Air Vehicle

Conference and Flight Competition (EMAV2007), 17-21 September 2007, Toulouse, France

III.A. Planning

The A* algorithm is a pathfinding algorithm d often used in IA planning because of it simplicity and efficiency due to the fact that it expands estimated best nodes first. To estimate the cost of the best solution that goes through state n we use:

f (n) = g(n) + h(n)
Where g(n) is the time to go from initial state to n. and h(n) is an estimated time to the solution from n. The A* algorithm usually stores partial solutions into a priority queue using a function f to estimate the cost of a partial solution. It expands the node with the best priority, and store the new partial solutions into the same priority queue. To minimize the cost of the mission we include a penality in g for solution state where a goal is not done. Let G be the set of goal that are not achieved, the penality for a solution state is:

penality = k∈G U [k] × time mission cost = g + penality
Where time mission is the maximum time allocated to the execution of the mission.

III.B. Execution Control and replanning

The planner sends to the execution module of the MAV a plan π = (a k ) 1≤k≤n and the predicted resulting states p = (s k ) 1≤k≤n . After each step of the plan, we enter a decision process where the controller decides whether to continue with the execution of the plan or to build a new plan to cope with an unpredicted state, i.e. if γ(s t-1 , a t ) = s t . In those cases, the planner needs to give a new plan as soon as possible. The online computing time ct of a new plan needs to be very small compared to the decision time step time step. We choose the following condition:

ct < time step 10 (7)
In case the previous condition fails, we repair the previous plan thus If the last action of MAV i failed, the MAV i redo this action before resuming his plan. The condition 7 is likely to fail when few goals have been achieved.

d Pathfinding = find the shortest path.

IV. Results and Further works

We have successfully written a formal model of mission for a fleet of MAVs. We have also proposed and implements two different algorithms to solve the mission planning problem using this model. Our Dynamic Programming based algorithm, which takes into account uncertainties, is an offline algorithm (computed on ground before the mission), and the resulting policy could be airborne in a paparazzi equiped MAV as a conditional flight plan. We successfully solved a 2 MAVs mission with 4 targets and 120 decision steps. Our real-time planning and replanning algorithm successfully solved a 2 aircrafts mission with 8 targets. Our first results show that for it is harder to solve problems if the fleet of MAVs is homogenous (i.e. all the MAVs have the same sensors), it makes the problem highly symmetrical. The next step is to work on symmetry breaking and goal allocation to tackle the complexity of the problem.

Figure 2 .

 2 Figure 2. Execution / planning scheme.

Figure 3 .

 3 Figure 3. Estimated cost of a partial solution.

  3rd US-European Competition and Workshop on Micro Air Vehicle Systems (MAV07) & European Micro Air VehicleConference and Flight Competition (EMAV2007), 17-21 September 2007, Toulouse, France

		go(0)
	go(1)	drop	drop	go(0)
	s0		go(	go(2)
		go(1)
				go(0)
	go(2)	go(2)
		drop	drop
	Transition	go(0)
	a
	State

  MAV does a eight figure centered on a target b Drop: MAV drops a paintball on a target3rd US-European Competition and Workshop on Micro Air Vehicle Systems (MAV07) & European Micro Air VehicleConference and Flight Competition (EMAV2007), 17-21 September 2007, Toulouse, France

))

a Eight: