UC Santa Cruz

A Geometric Combinatorial Satisfiability Approach to Automating Free Flight in the Airspaceby James W. Herriot

This dissertation details a research project whose aim is to contribute to research on automating and optimizing the aggregate trajectories of arriving aircraft flights in the terminal airspace inspired by the principles of free flight. A software simulation was designed and developed to model dynamic generation of airspace flight paths from top-of-descent to landing. Although this research is conceived to apply generally to automatically generating safely separated flight paths in the wider airspace, this work focuses on airspace local to a particular airport with one or more runways available for landing arriving aircraft. This approach is robust within a dynamic airspace which is frequently changing due to weather, runway reversals, miss approaches, and aircraft traffic.

The methodology described here employs a trio of geometry, combinatorics, and satisfiability. The unique uniform triangular/hexagonal geometry enables the generation of a large number of similar flight path segments (analogous to pixels), which when joined together form the vast combinatorics of all possible 4DT flight paths for aircraft headed to these runways. In this combinatoric form, these numerous flight path candidates are then handed off to a satisfiability solver, searching for a suite of overall optimal flight paths. This approach generalizes solving for an ensemble of efficient flight paths within a dynamic changing airspace, making way for efficient optimization and automation of aircraft routes.