Computer Science Department
School of Computer Science, Carnegie Mellon University


Mechanized Safety Proofs for
Disc-Constrained Aircraft

David Renshaw, Sarah M. Loos, André Platzer

August 2012


Keywords: Aircraft maneuvers, distributed hybrid systems, differential dynamic logic, theorem proving, formal verification.

As airspace becomes ever more crowded, air traffic management must reduce both space and time between aircraft to increase throughput, and on-board collision avoidance systems become ever more important. These systems and the policies that they implement must be extremely reliable. In this paper we consider implementations of distributed collision avoidance policies designed to work in environments with arbitrarily many aircraft. We formally verify that the policies are safe, even when new planes approach an in-progress avoidance maneuver. We show that the policies are flyable and that in every circumstance which may arise from a set of controllable initial conditions, the aircraft will never get too close to one another. Our approach relies on theorem proving in Quantified Differential Dynamic Logic (Qd&L) and the KeYmaeraD theorem prover for distributed hybrid systems. It represents an important step in formally verified, flyable, and distributed air traffic control.

16 pages

Return to: SCS Technical Report Collection
School of Computer Science

This page maintained by