PaperlayerView exact revision on arXiv

Source-linked AI summary

Deep Neural Network Compression for Aircraft Collision Avoidance Systems

Kyle D. Julian, Mykel J. Kochenderfer, Michael P. Owen

arXiv:1810.04240v1cs.LGstat.ML

TL;DR

ACAS Xu’s high-dimensional score table is too large for current avionics, motivating a compact representation that preserves advisory preferences and table values. The paper trains deep neural networks with asymmetric loss, refines their training, and uses multiple subnetworks to reduce runtime; simulation reports 1000-fold storage reduction and overall performance at least matching the original table.

  • Problem

    ACAS Xu’s high-dimensional collision-avoidance score table is too large for current avionics systems.

  • Method

    Deep neural networks approximate the table using asymmetric loss, gradient-based training, and multiple subnetworks representing subtables.

  • Results

    1000-fold storage reduction is achieved, while the final network outperforms the table on all reported metrics except a slight increase in P(Reversal).

  • Takeaways & Limitations

    The neural-network representation can replace the original table without degrading overall performance and enables use on existing avionics hardware.

Abstract

from arXiv · show

One approach to designing decision making logic for an aircraft collision avoidance system frames the problem as a Markov decision process and optimizes the system using dynamic programming. The resulting collision avoidance strategy can be represented as a numeric table. This methodology has been used in the development of the Airborne Collision Avoidance System X (ACAS X) family of collision avoidance systems for manned and unmanned aircraft, but the high dimensionality of the state space leads to very large tables. To improve storage efficiency, a deep neural network is used to approximate the table. With the use of an asymmetric loss function and a gradient descent algorithm, the parameters for this network can be trained to provide accurate estimates of table values while preserving the relative preferences of the possible advisories for each state. By training multiple networks to represent subtables, the network also decreases the required runtime for computing the collision avoidance advisory. Simulation studies show that the network improves the safety and efficiency of the collision avoidance system. Because only the network parameters need to be stored, the required storage space is reduced by a factor of 1000, enabling the collision avoidance system to operate using current avionics systems.

I. INTRODUCTION

ACAS X collision-avoidance logic is represented by a very large dynamic-programming score table, creating storage and avionics-deployment challenges. This paper investigates deep neural networks as a compact replacement while preserving performance and advisory preferences.

  • Dynamic programming produces a score table with millions of states and requires hundreds of gigabytes of floating-point storage.
  • Downsampling reduces the dynamic-programming table by a factor of 180, but the resulting baseline still requires over 2GB of storage.
  • Less than 120MB would be sufficient for legacy avionics, whose certification makes large storage requirements costly and time-consuming.
  • Prior compression methods exploit block structure, precision, or symmetry, but horizontal-maneuver ACAS Xu tables remain substantially larger.
  • Deep neural networks are explored as efficient nonlinear approximators that can preserve advisory decisions while compressing the score table.
  • Simulation evaluates safety and operational metrics across millions of encounters, finding 1000-fold memory reduction and improved performance on most metrics, with one slightly degraded.

II. SCORE TABLE

The ACAS Xu horizontal logic table maps a seven-variable aircraft encounter state to scores for five horizontal advisories. Its policy selects advisories from these scores, including under sensor uncertainty and multi-intruder encounters.

  • The five possible horizontal advisories are COC, weak left, weak right, strong left, and strong right.Weak and strong turns correspond to heading rates of 1.5 deg/s and 3.0 deg/s, respectively.
  • Seven discretized state variables form a 120 million-point grid describing encounter geometry, vertical timing, and the previous advisory.
  • The score table’s policy maps each state to the action with the highest score, using nearest-neighbor interpolation between grid points.
  • An unscented Kalman filter supplies weighted state samples so the system can compute advisories under uncertain sensor measurements.
  • Utility fusion extends the single-intruder score table to multiple intruders by combining action scores through worst-case or summed-score rules.

III. BASELINE TABLE REGRESSION METHODS

Baseline regression methods expose a tradeoff between compression and faithful policy reproduction. Decision trees are viable but require substantial storage, while the neural-network approach offers greater accuracy at much smaller size.

  • The original ACAS Xu score table contains 600 million floating-point numbers and requires over 2GB of storage.
  • Linear regression achieves an RMSE of 17.9 because a linear mapping is too simple for 120 million examples described by seven features.
  • SVMs are unsuitable because their regression process is too slow for the table’s large number of training examples.
  • Decision trees control storage through maximum depth, splitting by feature thresholds and predicting leaf-node average scores.
  • 100MB-or-smaller decision trees exceed RMSE 3.0 and 6% policy error, whereas the neural-network representation uses only 2.4MB.

IV. NEURAL NETWORK COMPRESSION

The proposed representation stores a nonlinear neural function that maps encounter states to advisory scores instead of storing the full table. Its architecture and policy-oriented training are designed to preserve both score values and action preferences.

  • Only the parameters of a nonlinear function need to be stored, replacing explicit table storage with a compact deep neural-network representation.
  • Decision-tree policies are compared across 2.56MB, 19.4MB, and 126MB representations, with larger trees improving accuracy but retaining policy errors.
  • The network uses fully connected feed-forward layers with ReLU activations, seven inputs, and five outputs for the possible advisories.
  • One forward pass computes the score values for all five advisories.

B. Loss Function

The paper uses asymmetric MSE to preserve the original table’s advisory preferences while retaining accurate score estimates. Compared with nominal MSE, this approach substantially improves maintenance of turning advisories.

  • Standard MSE accurately approximates score values but can change the ordering of advisories, producing a different collision avoidance strategy.
  • Categorical cross entropy predicts optimal actions but does not represent score values needed to compute advisories over weighted states.
  • Asymmetric MSE combines numeric accuracy with action preservation by increasing penalties for underestimating optimal or overestimating suboptimal advisories.The penalty factor for optimal advisories is four times greater than that for suboptimal advisories.
  • 90–94% of turning advisories were maintained with asymmetric loss, compared with 72–74% using nominal MSE.These percentages are the on-diagonal entries of the normalized confusion matrices.

C. Model Architecture

The model architecture was selected through optimizer and depth experiments. AdaMax learned quickest without becoming stuck in local optima, followed by a five-hidden-layer architecture with roughly 600,000 parameters.

  • AdaMax learned quickest among the evaluated optimizers without becoming stuck in local optima.It also required relatively little parameter tuning because it uses gradient-moment estimates to anneal the step size.
  • The baseline architecture used five hidden layers with larger early layers and progressively smaller later layers.This tapering was intended to support increasingly abstract data representations.
  • The architecture was sized for approximately 600,000 total network parameters.
  • Training used normalized score-table data and inputs, shuffled batches of 216 samples, and 1200 epochs over four days.

E. Results

The neural-network representation closely approximates the original collision-avoidance table and improves three simulated safety and efficiency metrics, but initially increases runtime substantially. Smaller networks reduce this runtime cost without increasing storage requirements.

  • Network evaluation: The network provides a continuous approximation of the discrete table across multiple encounter geometries and preserves geometry-dependent policy behavior.Increasing τ shrinks the strong alerting region, while aprev = WR favors right turns to reduce reversals.
  • Operational performance: The neural network outperforms the original table on the three probability metrics evaluated in 1.5 million simulated 3D encounters.The metrics are P(NMAC), P(Alert), and P(Reversal); all four metrics are intended to be minimized.
  • Operational performance: The initial neural-network implementation increases relative runtime by a factor of 50 because computing its score values requires substantial additional computation.Runtime is normalized to the original score table.

A. Network Pruning

Network pruning removes low-impact connections iteratively, but substantial pruning eventually changes policies and increases errors. Multiple smaller networks provide the reported runtime solution without increasing storage.

  • A. Network Pruning: Sparse-network pruning removes connections iteratively and retrains after each step to adjust the remaining weights.This implementation removes 2% of connections at a time and targets low-magnitude weights first.
  • A. Network Pruning: 60% pruning doubles both RMSE and policy error rate, while 80% pruning causes drastic policy changes.Pruning 40% produces only minor policy changes, whereas further pruning increases network errors.
  • A. Network Pruning: Pruning can reach 60% before major policy changes, but sparse-representation overhead limits the resulting speedup.The result suggests ACAS Xu networks are denser than computer-vision networks.
  • B. Multiple Small Neural Networks: Partitioning the training data into 45 τ and aprev combinations enables separate smaller networks that evaluate only the relevant state-space subtable.Each network is trained on approximately 45 times less data and is made approximately 50 times smaller.
  • A. Network Pruning: With COC included in the penalty, the figure compares original-table COC scores, neural-network scores at table cutpoints, and COC score errors.The caption specifies the three plotted quantities but does not state their numerical outcome.
  • B. Multiple Small Neural Networks: The 45-network array uses approximately the same total parameter count as one large network and achieves a 3% runtime speedup over the original table.Each network has six hidden layers, 45 hidden units per layer, and approximately 11,000 parameters.

VI. IMPROVING NETWORK TRAINING

The training data is modified to address large score discontinuities that neural networks represent poorly, especially those caused by the COC penalty. Removing and later reapplied the penalty improves the network’s fit to the score table.

  • VI. IMPROVING NETWORK TRAINING: Large score discontinuities make the score table more error-prone for neural-network regression.Neural networks represent continuous functions, so discontinuities require additional weights and neuron activations.
  • VI. IMPROVING NETWORK TRAINING: The COC penalty creates a localized dark band with score values as low as -15.0, producing large representation errors.The penalty remains confined to the region where it is applied rather than spreading smoothly to neighboring states.
  • VI. IMPROVING NETWORK TRAINING: Removing the COC penalty from training data and applying it to network outputs separates the discontinuity from the function being approximated.The penalty is reapplied by computing dCPA and tCPA.
  • VI. IMPROVING NETWORK TRAINING: With the COC penalty removed, the low-score band disappears and the neural network fits the score table more accurately across the state space.The improvement includes more accurate neural-network values at close range.

B. Training with Online Costs

Online costs modify table values before advisories are selected, but the original asymmetric loss makes the neural-network policy too resistant to those changes. Training against the cost-adjusted policy improves agreement with the table.

  • B. Training with Online Costs: Online costs modify table values to tune performance, including reducing COC and weak-turning scores after strong-turning advisories.This cost helps prevent alerts from ending too early and thereby reduces split advisories and reversals.
  • B. Training with Online Costs: The asymmetric mean squared error widens the score gap between optimal and suboptimal actions, making online-cost policy changes harder to reproduce.The loss underestimates suboptimal actions and overestimates the optimal action.
  • B. Training with Online Costs: Training with the table’s online-cost-adjusted policy produces a neural-network policy that better matches the table policy.The comparison is shown in the right plot of Fig. 15.

VII. RESULTS

Simulation results show that successive compression updates make the neural-network policy more similar to the updated table. The final system performs well overall, runs slightly faster, and handles example multi-intruder encounters, while formal verification remains future work.

  • VII. RESULTS: 10 million 3D encounters with varied geometries and sensor noise were used to evaluate split-advisory probability and other performance metrics.Table II compares the different neural networks considered.
  • VII. RESULTS: The final neural-network compression outperforms the table on all evaluated metrics except P(Reversal), which increases slightly.Each compression update makes overall performance more similar to the updated table.
  • VII. RESULTS: The compressed system performs well overall and has a slightly faster runtime than the original table.The runtime comparison concerns the final neural-network system and original table.
  • VII. RESULTS: In two simulated encounters, the neural network alerts seven seconds earlier in one case and selects a different turn direction in another, avoiding near mid-air collisions.Its continuous function provides better interpolation than the table’s nearest-neighbor interpolation in some cases.
  • VII. RESULTS: A ten-aircraft simulated encounter illustrates that utility fusion can support safe maneuvering through multi-intruder scenarios.The example includes reversals in turning direction as different intruders become more imminent.
  • VII. RESULTS: Simulation over millions of states does not guarantee correct network behavior in every possible state.Formal methods such as Reluplex are identified as a possible route toward verification and certification.

VIII. CONCLUSIONS

The paper replaces the oversized ACAS Xu score table with deep neural networks that preserve advisory performance while reducing runtime and storage requirements. The resulting representation can run on existing avionics hardware and may support larger policies as storage capacity grows.

  • VIII. CONCLUSIONS: The neural-network representation approximates the ACAS Xu score table while maintaining optimal advisories and comparable performance.The paper concludes that the network can replace the original table without degrading performance.
  • VIII. CONCLUSIONS: Factoring the table into subtables and training multiple small networks reduces runtime to the level of the original table lookups.The approach also modifies training to improve representation of poorly fitted regions.
  • VIII. CONCLUSIONS: The compression approach enables the collision avoidance system to operate on existing avionics hardware.With greater storage capacity, it could represent a larger and more complex collision-avoidance policy.
Loading 1810.04240v1…