Enabling real-time execution: Runtime-efficiency improvements for the next-generation airborne collision avoidance algorithms

The Federal Aviation Administration is currently developing the Airborne Collision Avoidance System X (ACAS X), a critical safety system intended to be installed on all large aircraft to prevent mid-air collisions. We identify methods of speeding up the ACAS X algorithms in order to address concerns about ACAS X's ability to meet real-time constraints on practical avionics hardware. The approaches involve state- and grid-point combination, pre- and hierarchical interpolation, memory-locality maximization, and selected use of fixed-point computation. These modifications, which are mathematically equivalent to the original ACAS X design, improved the speed of ACAS X's primary runtime-contributing component by a factor of approximately 7.3 on a 32-bit x86 platform. Along with improved hardware, they enabled the system to meet execution-time objectives in flight testing. The techniques developed are general and potentially applicable to systems that approximate a continuous value function using multilinear interpolation over the values for discrete states and to systems that compute weighted sums of these values across multiple points.