Towards next-generation airport surface movement operations using hierarchical-distributed multi-agent planning

• Generalised architecture for hierarchical-distributed multi-agent system models to study new concepts of airport surface movement operations, allowing to instantiate models with differing operational/procedural concepts, levels of automation, and degrees of centralisation; • Elaborated MAS model for a novel concept of airport surface movement operations based on centralised planning and distributed, fully automated control; • AS-MAMP algorithm as two-level solver for conflict-free multi-agent motion planning that accounts for the heterogeneous fleet of agents, their shapes and kinodynamic constraints; • SIMP algorithm as SIPP-based solver accounting for finite acceleration as well as upper and lower speed bounds, thus enabling to plan kinodynamically feasible trajectories in complex, graph-based environments. Coordinating the movements of aircraft along the surface of busy airports is a complex task, involving both humans and machines. In response to the interrelated challenges of ever-increasing demand, emission reduction, and sustaining safety levels, technological advances are emerging which, in turn, necessitate novel concepts of operations (ConOps). To this end, diverse operational concepts with varying technological aspects, level of automation, and degree of control centralisation could potentially offer a solution. However, before such innovative ConOps are matured to be deployable at real-world airports, extensive evaluation based on computational modelling is necessary. To enable such detailed modelling and analysis of the large variety of concepts for next-generation airport surface movement operations, this paper proposes a generalised architecture based on the hierarchical-distributed multi-agent system modelling paradigm. We illustrate the generalised architecture by providing a specific model instance for a ConOps based on centralised planning and distributed, fully-automated control. As essential part of this model, we introduce the novel Multi-Agent Motion Planning on Airport Surfaces (AS-MAMP) algorithm to represent the decision-logic for coordinating all ground movements. The two-level solver builds on prominent prioritised planners such as Priority-Based Search (PBS) and its variant Greedy PBS. As current low-level solvers were insufficient to plan realistic 4D trajectories for ground movements, we developed the new Safe Interval Motion Planning (SIMP) algorithm. By defining activity sequences per agent, SIMP plans trajectories across the operational processes during taxiing such as pushback, tug coupling/decoupling, and engine-start. The motions of aircraft and ground vehicles are based on finite acceleration, and avoid dynamic obstacles in continuous space and time, necessitating to define states with feasible motion intervals . We benchmark AS-MAMP by varying its high-level prioritisation scheme, and exchanging SIMP with two existing low-level solvers, namely the Safe Interval Path Planning (SIPP) and A* algorithms. Based on scenarios on both a synthetic and a real-world airport layout, we demonstrate the efficacy of AS-MAMP to plan safe and efficient 4D trajectories. Moreover, we show that the model is able to handle runway throughput levels that match or exceed those of large European airports.