An algorithm for computationally lightweight simulation of automated airtraffic control (ATC) at a busy airport has been derived. The algorithm is expected to serve as the basis for development of software that would be incorporated into flight-simulator software, the ATC component of which is not yet capable of handling realistic airport loads. Software based on this algorithm could also be incorporated into other computer programs that simulate a variety of scenarios for purposes of training or amusement.
The ATC simulation problem that the algorithm is meant to solve can be summarized as follows: ATC is responsible for all aircraft that enter an arbitrarily specified hemisphere, denoted the flight-simulator bubble, that is centered at the airport. ATC must guide all the aircraft to safe landings in a sequence that is as fair as possible under the circumstances. Information about the airport that is taken into account includes the lengths, directions, and locations of end points of runways. Information about each aircraft that is taken into account includes the current three-dimensional position and velocity, maximum and minimum speeds, and mathematical relationships among turning times and the starting and ending points of turns between specified headings. The solution generated by the algorithm must be a set of instructions to the aircraft that enable all aircraft to land without violating any constraints.
The algorithm consists of four components denoted the controller, the plan, the vector generator, and the constraint verifier. The controller is event-driven and relatively simple: It responds to any of three events, as follows:
- An aircraft enters the bubble. The controller tries all vector options in a shortest-path-first order, checking each by use of the constraint verifier. When a solution is found, the controller issues instructions to the appropriate pilots.
- An aircraft leaves the bubble. The controller removes the aircraft from the plan.
- An aircraft changes location as prescribed by the plan. The controller causes the plan to be updated with the new location and time of arrival of the aircraft at the location. If necessary, it gives instructions to the appropriate pilot.
Thus, the controller is the input/output interface for the ATC.
The plan is a data structure that is used to verify current and hypothetical routing for each aircraft. The plan consists of a simple temporal network (STN) augmented by labeling of time points with identities of aircraft and of other time points with which overlaps must be prevented. The approach followed by an aircraft is represented as a directed path in the STN. Inasmuch as each aircraft has its own unique path, the overlap labels are used to enforce the fundamental constraint that no two aircraft may be in the same place at the same time. If two time points overlap in space, then it is necessary to ensure that they do not overlap in time. This is done by introducing temporal constraints. Operations on the plan include insertion of an aircraft, deletion of an aircraft, and updating of the position and time of an aircraft. An aircraft is inserted into the plan by inserting its approach.
The approach generator generates a series of time points and temporal constraints that represent a hypothetical approach for an aircraft. It also generates the information for the overlaps for each time point of the plan. The approach generator includes a vector generator that iterates over options from most preferred (a full-procedure approach) to least preferred (one or more turns in a holding pattern, ending in a direct approach). Once a vector is generated, it must be verified as described in the next paragraph. If verified, it is incorporated into the plan.
The constraint verifier checks a plan and introduces temporal constraints where necessary to maintain veracity. The constraint verifier identifies time points that lack temporal ordering between themselves and members of their overlap set. It then incrementally inserts ordering constraints and verifies that each constraint is possible using temporal propagation. It can preferentially schedule new points either before or after pre-existing points, according to the preferences of the designers of the ATC system. Once a verified plan is found, the verifier returns “true.” If a verified plan cannot be found, the verifier returns “false” and removes any extraneous temporal constraints it inserted.
This work was done by Russell Knight of Caltech for NASA’s Jet Propulsion Laboratory. For further information, access the Technical Support Package (TSP) free on-line at www.techbriefs.com/tsp under the Information Sciences category.
The software used in this innovation is available for commercial licensing. Please contact Karina Edmonds of the California Institute of Technology at (818) 393-2827. Refer to NPO-40445.
This Brief includes a Technical Support Package (TSP).
Computationally Lightweight Air-Traffic-Control Simulation
(reference NPO-40445) is currently available for download from the TSP library.
Don't have an account?
Overview
The document titled "Computationally Lightweight Air-Traffic-Control Simulation" describes a novel approach to automating air traffic control (ATC) for lightweight simulations, such as computer games. Developed by the Jet Propulsion Laboratory and sponsored by Microsoft Corporation, this system utilizes a Simple Temporal Network (STN) to manage the timing and routing of aircraft as they enter an air traffic control bubble around an airport.
The ATC algorithm operates by generating flight plans for incoming aircraft, which include their coordinates, vectors, and speed constraints. As aircraft enter the bubble, the algorithm assesses their positions and speeds, issuing commands to ensure safe landings without violating any constraints. The system is designed to be responsive and fair, accommodating multiple aircraft while maintaining safety and efficiency.
Key components of the ATC algorithm include the plan, vector generator, constraint verifier, and controller. The plan serves as a data structure that verifies current and potential flight paths, ensuring that no two aircraft occupy the same space at the same time. The controller is event-driven, responding to three main events: the entry of an aircraft into the bubble, the exit of an aircraft, and changes in an aircraft's location as dictated by the flight plan.
The document illustrates the algorithm's functionality through a series of scenarios, demonstrating how it manages the landing of multiple aircraft with varying speeds and trajectories. For instance, when a faster aircraft enters the bubble, the algorithm may place it in a holding pattern if no safe landing vectors are available. Additionally, if an aircraft deviates from its planned speed, the system can detect this during propagation and issue new instructions as necessary.
Overall, the document emphasizes the importance of computational efficiency in air traffic control simulations, particularly for applications in gaming and other lightweight environments. By leveraging heuristics and a structured approach to flight path management, the proposed system aims to enhance the realism and safety of simulated air traffic control, making it a valuable contribution to both aerospace technology and simulation development.
