Mechanized Safety Proofs for Disc-Constrained Aircraft (CMU-CS-12-132)

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 (QdL) and the KeYmaeraD theorem prover for distributed hybrid systems. It represents an important step in formally verified, flyable, and distributed air traffic control. This research was sponsored by the National Science Foundation under grant numbers CNS-1054246, CNS-1035800, CNS0931985, CNS-0926181. Sarah M. Loos was supported by a DOE Computational Science Graduate Fellowship. The views and conclusions contained in this document are those of the authors and should not be interpreted as representing the official policies, either expressed or implied, of any sponsoring institution, the U.S. government or any other entity.