Adaptive Stress Testing of Airborne Collision Avoidance Systems

Abstract

Verbatim from NASA NTRS. Not paraphrased, not summarized.

This paper presents a scalable method to efficiently search for the most likely state trajectory leading to an event given only a simulator of a system. Our approach uses a reinforcement learning formulation and solves it using Monte Carlo Tree Search (MCTS). The approach places very few requirements on the underlying system, requiring only that the simulator provide some basic controls, the ability to evaluate certain conditions, and a mechanism to control the stochasticity in the system. Access to the system state is not required, allowing the method to support systems with hidden state. The method is applied to stress test a prototype aircraft collision avoidance system to identify trajectories that are likely to lead to near mid-air collisions. We present results for both single and multi-threat encounters and discuss their relevance. Compared with direct Monte Carlo search, this MCTS method performs significantly better both in finding events and in maximizing their likelihood.

Authors

• Lee, Ritchie SGT, Inc.
• Kochenderfer, Mykel J. Stanford Univ.
• Mengshoel, Ole J. Carnegie-Mellon Univ.
• Brat, Guillaume P. Carnegie-Mellon Univ.
• Owen, Michael P. Massachusetts Inst. of Tech.

Keywords

• Verification and Validation
• Reinforcement Learning
• ACAS X