Project EET-B: Air Traffic Management
Manager: Prof Jan Maciejowski
Investigator: Prof Jan Maciejowski
Research Staff: Dr Alison Eele (RA1A)
Collaborators (Informal): University of Leicester, ETH Zurich, NLR Amsterdam, University of Bristol
Start date: 11 January 2010
Summary. The prolongation of air journeys due to air traffic congestion adds very significantly to aircraft fuel consumption. For this reason, the alleviation of air traffic congestion is an important means of improving fuel efficiency in transportation. According to emerging concepts, Air Traffic Management (ATM) assigns to each aircraft a Reference Business Trajectory (RBT) to achieve various goals, related mainly to arrival time and fuel use. The RBT will also take account of available information such as weather en-route and the RBTs of other aircraft. When aircraft are compelled to deviate from their RBTs they must obey conflict resolution rules to maintain a safe separation from other aircraft. It is often necessary to take account of random effects, due to weather conditions or unpredictable human behaviour.
The aim of this project is to provide new techniques for formulating conflict resolution rules, which relieve air traffic congestion and thereby improve aircraft fuel efficiency. Both decentralised and centralised frameworks for conflict resolution will be considered, according to whether aircraft themselves agree on the appropriate evasive action, or the ground controller acts as a 'centralised' controller. In either case, the conflict resolution problem will be formulated as a stochastic optimal control problem, which will be addressed using techniques from Projects UT-A, UT-B and UT-C.
Work carried out by the Society of British Aerospace Companies and NATS in the UK has identified areas where savings in CO2 emissions could be targeted. Of the planned savings 80% were to be gained from the climb and descent phases of each flight. Thus the greatest scope for improving fuel efficiency by improved air traffic control occurs in “Terminal Manoeuvring Areas” (TMA), namely in airspace close to airports, where there can be relatively high density of arriving/departing aircraft. This indicated that greater emphasis is likely to be needed on centralised rather than decentralised approaches – both because the problem requires such approaches, and because the availability of ground-based equipment implies that extensive computational resources can be assumed to be available.
Current Status. From focusing our approach on the TMA a few issues became apparent. Any methods used should have to be able to deal with: large numbers of aircraft; detailed three dimensional dynamics models, non-convex optimisation and have the capability to cope with uncertainty. These restrictions along with the potential computing resources available near a TMA suggested that a Stochastic Optimisation approach be investigated first. Stochastic Optimisation methods are those which employ probabilistic or random elements in either the problem data or optimisation algorithm. The class of methods focused on by our research to date has been Monte Carlo methods, specifically Markov Chain Monte Carlo (MCMC) and Sequential Monte Carlo (SMC). Both methods have previously been proposed and demonstrated on toy examples for vehicle avoidance, by others and by ourselves [CLM09], [KLM10], [YKLM10] and results permitting performance guarantees have been established [LLM10]. Our work has focused on adapting the methods specifically to the problem of air traffic control then comparing the methods by analysis of paths produced and required solution times. This has resulted in the publication [EM11], in which SMC was shown to be superior in handling the proposed problems, and simultaneous management of up to 20 aircraft was demonstrated.
Following on from our initial work in stochastic optimisation we focused attention on parallelisation opportunities for computational speed up. The underlying structure of SMC is very parallelisable, which could allow, through the use of parallel computer architectures such as graphics processor units (GPUs) or field programmable gate arrays (FPGAs), the majority of the speed-up required to enable real-time operation. To approach this aspect of the work a collaboration was established with Prof Wayne Luk and PhD student Thomas Chau from Imperial University's Computer Science department. The collaboration merged our own expertise on stochastic methods for MPC and ATM with their expertise in parallel computing for a variety of applications. As part of this collaboration a summer student project at Imperial was organised. In that project the SMC method for the ATM problem was translated directly to an FPGA. This showed promise for improved scaling at large vehicle numbers and reduction in energy usage compared to that of GPU computation [CKTHSEMCCCL14]. Further work by our collaborators has focused on improvements to the SMC algorithm for computational speed-up by varying particle numbers throughout the optimisation process itself [CNELCM13].
Continuing our own focus on stochastic optimisation with speed-up through parallelisation we adapted the SMC algorithm to act as an ‘embarrassingly parallelisable’ method. This meant that the inner loop of the algorithm could be run for multiple particles simultaneously on different computation cores without the need for interaction between the cores. Adopting this alteration and an alternative method of handling weights for vehicles within particles, a speed up of 98.5% was demonstrated between the standard sequential implementation of SMC and a parallelised approach on a GPU using NVIDIA’s CUDA programming environment. This large speed up was far higher than initially expected and has demonstrated the SMC method to be a feasible approach for real time (30 second update interval) optimisation of cruise-like trajectories for large numbers of aircraft (up to 20) [EMCL13].
With the significant speed-up from parallelisation the work has been able to adapt to far more complex ATM examples; specifically to modelling aircraft in the TMA. This required adoption of both a rolling window simulation where aircraft could now enter and leave the problem during the simulations and handling of both arrival and departure traffic. A single runway for both take-off and landing was adopted, similar to that of London Gatwick airport. The complexity of finding feasible landing paths for aircraft resulted in a necessary increase in particle numbers, which did result in a slow-down of optimisation. However scenarios handling up to 23 arrival aircraft in 15 minutes worth of airport time were demonstrated along with multiple cases of mixed arrival and departure traffic over similar time spans [EMCL13a], [ME14]. This work was presented to London Gatwick and NATS to gauge our realism and was very well received. Extensions suggested by their team included noise abatement as part of the trajectory costs (to potentially avoid flying over highly populated areas at inconsiderate times) and potentially adapting the method to optimising ground movements at the airport.
Current work is focusing on quantifying the fuel benefits from the SMC optimisation compared to real world data. Data has been obtained from www.flightradar24.com charting air traffic through the open ADS-B system. Roughly 60% of all passenger aircraft in the world are equipped with ADS-B transponders and broadcast their identity and state at regular intervals, which can be received by an informal public network of receivers. Coverage of these receivers is better in populated areas allowing frequent updates and a clearer view of aircraft locations. A study is currently underway of aircraft arriving and departing from Gatwick's TMA for a full 24 hour period, reverse engineering from the data, an estimate of fuel used and then using our own SMC simulations to solve the same arrival and departures problem to compare fuel use.
The work has attracted attention, with Prof Jan Maciejowski being invited to deliver a plenary lecture about it at the 1st IFAC Workshop on Advances in Control and Automation Theory for Transportation Applications in Istanbul, 16-17 September 2013.
Publications
[ME14]
J. Maciejowski and A. Eele,
Real-time optimisation-based planning and scheduling of vehicle trajectories,
17th IEEE Mediterranean Electrotechnical Conference - Control Systems, Beirut,
pp305-309 April 2014
[EMCL13a]
A. Eele, J. Maciejowski, T. Chau and W. Luk,
Control of Aircraft in the Terminal Manoeurving Area using Parallelised Sequential Monte Carlo,
Proc AIAA Guidance, Navigation and Control Conference, Boston,
Aug. 2013
[CNELCM13]
T. C. Chau, X. Niu, A. Eele, W. Luk, P. Y. Cheung, and J. Maciejowski,
Heterogeneous reconfigurable system for adaptive particle filters in real-time applications,
Proc. Int. Symp. Applied Reconfigurable Computing,
2013
[CKTHSEMCCCL14]
T. Chau, M. Kurek, J. Targett, J. Humphrey, G. Skouroupathis, A. Eele, J. Maciejowski, K. Cobden, B. Cope, P. Cheung and W. Luk,
Accelerating Sequential Monte Carlo Designs with Parameter Tuning,
22nd ACM/SIGDA International Symposium on Field-Programmable Gate Arrays, Monterey, California,
submitted Feb. 2014
[EMCL13]
A. Eele, J. Maciejowski, T. Chau, W. Luk,
Parallelisation of Sequential Monte Carlo for Real-Time Control in Air Traffic Management,
Proc Conference on Decision and Control, Florence,
Dec. 2013
[EM11]
A.Eele and J.M.Maciejowski,
Comparison of stochastic optimisation methods for control in air traffic management,
Proceedings of the 18th IFAC World Congress, Milan, Italy ,
Aug-Sept 2011
[LLM10]
A. Lecchini Visintini, J. Lygeros, J.M. Maciejowski,
Stochastic Optmization on Continuous Domains with Finite-time Guarantees by Markov Chain Monte Carlo Methods,
IEEE Transactions on Automatic Control, Vol 55, 12, pp 2858-2863,
Dec., 2010
[YKLM10]
Z.Yang, N.Kantas, A.Lecchini-Visintini and J.M.Maciejowski,
Stochastic model predictive control using open loop annealing and Monte Carlo methods,
Proceedings of the 19th International Symposium on Mathematical Theory of Networks and Systems (MTNS), Budapest Hungary,
Jul., 2010
[KLM10]
N. Kantas, A. Lecchini Visintini, J.M. Maciejowski,
Simulation Based Bayesian Optimal Design of Aircraft Trajectories for Air Traffic Management,
International Journal of Adaptive Control and Signal Processing, Special Issue on “Air traffic management: challenges and opportunities for advanced control”, Vol 24, 10 pp 882-899,
Oct., 2010
[CLM09]
E.Crisostomi, A.Lecchini-Visintini and J.M.Maciejowski,
Combining Monte Carlo and worst-case methods for trajectory prediction in air traffic control: a case study,
Automatic Control on Aerospace 2,1 (online journal at
http://www.aerospace.unibo.it/, ISSN 1974-5168,
Jun 2009
