CASSOS

POM : Planification, Optimization, and Modelization

Summary

• Acronym: CASSOS
• Project name: Computer-assisted sectors opening schedules
• Start date: 1999
• Suspended from 2002 to 2007, reactivated following S2D2 results
• End date: -

Description

The main objective of the project is to build realistic predictions of the airspace configuration, balancing the controllers workload, or the traffic load, as best as possible among the control sectors.

The airspace is currently divided in elementary sectors that may be merged (or collapsed) into larger sectors, and operated as control sectors assigned to controllers working positions. The way elementary sectors are combined into control sectors depends (at least in France) on the traffic flow through the airspace and on the workload of the controllers operating the sectors.

In the problem addressed here, the traffic is not considered as a variable which can be adjusted, but as input data. So the traffic demand is not regulated by assigning departure slots, but instead the elementary sectors are combined as best as possible so as to build the most adapted airspace configuration, taking into account various operationnal constraints.

CASSOS I

In a first period, we have tried to build optimal airspace configurations, using the same items as currently used by the Flow Management Positions (FMP) operators to build pre-tactical sectors opening schedules :

• the incoming flows, i.e. the flow of aircraft entering the control sector in a chosen time period,
• the sector capacities, i.e. a threshold value for the incoming flow, above which the sector is said to be overloaded,
• the maximum number of available controllers working positions at each time of the day,
• the flight plans filed by the airspace users, that are used to compute the incoming flows.

Today, FMP operators choose among a small number of pre-defined airspace configuration scenarios in order to build the predicted sectors opening schedules. The initial goal of the first phase of the CASSOS project was to explore all possible configurations, and to choose the optimal ones considering capacity constraints, and also the number of available controllers (taking into account the working schedule).

Several methods were tested, with either standard tree search algorithms (A*, Branch & Bound), or evolutionary algorithms. It was shown that standard methods were efficient enough when the airspace partitions were built only with usual control sectors (those described in the ATCC databases).

The above figure shows an optimal sectors opening schedule, where the incoming flow in each control sector is as close as possible to the nominal sector capacity, while satifying a constraint on the maximum number of available controllers working positions (in blue when the constraint is saturated, in black otherwise).

Each column represents an airspace configuration over a period of time. The number of control sectors is displayed at the top of each column. Each coloured box represents a control sector. The color code is the following:

• green when the value of the incoming flow is below, with a chosen tolerance, the sector capacity,
• yellow when the incoming flow is within chosen tolerance margins (+-10% on the example) defined around the nominal sector capacity,
• red when the flow value is above the nominal capacity plus the upper tolerance.

The potential profits provided by the optimized schedule have been assessed by simulating two different strategies of departure slots allocation:

• in the first one, the traffic is smoothed so as to satisfy the capacity constraints of the sectors opening schedule that was actually sent to the CFMU by the FMP operator on that day,
• in the second one, we shall first smooth the traffic demand considering that all elementary sectors were operated. In a second step, an optimal schedule is computed taking the smoothed traffic demand as input.

The aim of the second strategy is to ensure first that no elementary sector could be overloaded, before combining these elementary sectors in order to provide an optimized schedule.

The simulations were runned on a single day of trafic, over France only, and with no constraints on the maximum number of available working positions. The comparison of these two strategies showed a decrease of 69% of the cumulated delays, while using 20% less ressources (the ressources are represented by the cumulated time during which the control positions are armed) with the optimized schedule.

These unbelievalbly good results surely give an indication of the algorithms efficiency. However, they mainly show that the input variables (incoming flows) are not representative of the actual workload of the controllers operating the sectors.

This initial approach of the problem concluded that more relevant metrics should be used to assess the controllers workload.

CASSOS II

In a second period, CASSOS relied on results provided by the S2D2 project. The aim of S2D2 was to select the air traffic complexity metrics that were most correlated to the sector status (merged with another sector, operated, split into smaller sectors), considering that this status was closely related to the actual controllers workload.

In this context, the aim of CASSOS II is to build a realistic prediction of the airspace configuration, still exploring all possible combinations of sectors, but using relevant complexity metrics to assess the controllers worload. This time, the airspace configuration is re-assessed every minute, in order to be as realistic as possible.

A neural network is used to compute the sector status. This neural network takes the values of the relevant metrics as input and provides sector status probabilities as output. When a decision to reconfigure the airspace is taken, a Branch & Bound algorithm is used to recombine the sectors in order to find an optimal configuration, minimizing a cost assigned to each possible configuration.

The neural network is trained on filed data (past sectors openings), minimizing the error between the sector status probabilities computed with an input vector of complexity metrics, and the actual sector status.

As a first step, we have tried to assess the computed airspace configurations by comparing them to the actual configurations, using recorded radar tracks to compute the complexity metrics. The results show that the computed number of control sectors is fairly well correlated to the number of control sectors that were actually opened on the chosen day. However, we used raw complexity metrics, with high variations across time, as input. As a consequence, we observed much more airspace reconfigurations than in reality.

Two solutions to this problems are being explored:

• smooth the complexity metrics, using a moving average method
• use a reccurent neural network which would take several successive vectors of metrics (time series) as input.

The above figure illustrates the smoothing approach. The best compromise that was found in this case (Brest ATCC) is to smooth the metrics over 30 minutes. The number of controllers working positions that were operated that day is shown in blue, and the number of control sectors of the configurations computed by our algorithms is shown in magenta. The curve in blue above the two others shows the cumulated traffic (number of aircraft) within the centre's boundaries, smoothed with a moving average (30 minutes).

The main drawback of the smoothing approach is that more smoothing will give better results on average, but will be less accurate in the detection of the sector status transitions.

In future works, we shall:

• compute the complexity metrics from uncertain data (flight plans, trajectory predictions),
• improve the sector status prediction by using time series and reccurent neural networks.

The implementation of a HMI for trials and demonstrations has begun. Click on the image below to lauch the mock-up HMI, which is still very experimental and under developpment.

Perspectives

The algorithms developped within the CASSOS project may be used in several kinds of applications, depending on the chosen time horizon:

1. FMP sectors opening schedule (1 or 2 days ahead)
2. • the algorithms would provide a more realistic schedule than today, with a better prediction of the controllers workload,
   • provided the use of flight plans allows realistic predictions of the complexity metrics
3. Multi-sector planning / airspace management (1 or 2 hours ahead)
4. • the airspace configuration algorithms could be coupled with "what-if" functions: what would be the worlkoad, and the airspace configuration, if I modify these trajectories ?
   • provided we are able to improve the detection of the sector status transitions.

It must be emphasized that the CASSOS algorithms should not be used as decision support tools for the airspace configuration itself. They may only be used to forecast the future workload and configurations, given a traffic prediction as input (just like a weather forecast model). The reason is that the sector status prediction model is tuned on past data (recorded sector configurations). So using it in a decision support tool would freeze the whole system.

The work undertaken at DSNA/DTI/R&D within the CASSOS micro-project does answer some of the issues addressed by the SESAR R&D program. Let us cite the short description of the Complexity management in En Route project of the Work Package 4 (En-route operations): "procedures and tools to dynamically adjust En Route capacity to demand (e.g. planned complexity measurements, dynamic adjustement of sectorisation)".

Software

CASSOS is written in Objective Caml. The code is not public domain. A library of neural networks was implemented in Ocaml and may be soon available under L-GPL license (see the software page).

Main publications

---

Last Update: