EvoDriver: Novelty-Search Driven Evolution of Behavioral Test Suites for Autonomous Vehicles

Abstract

In addition to environmental-based uncertainty conditions, self-adaptive Autonomous Vehicles (AVs) must be able to handle uncertainty posed by external human drivers sharing the operating environment. Existing search-based AV testing approaches have explored objective-oriented, top-down approaches to develop a range of test cases to assess whether the system satisfies functional and safety properties with respect to specific operational contexts. However, these techniques lack search pressure to identify test cases that may be obscured in unintuitive regions of the search space (i.e., edge cases). This paper introduces a bottom-up, exploratory approach to automatic test case generation for AVs, where test cases are evolved organically (i.e., in a more open-ended fashion) to reveal uncertainty posed by diverse and unexpected maneuvers from an external vehicle in the operating environment. Specifically, novelty search-based genetic programming is used to evolve controllers for an external vehicle that interacts with the AV under study in order to reveal the most diverse behavioral responses from the AV under study. By leveraging diversity as a metric through novelty search, our approach automatically discovers behaviors for an external vehicle that result in increasingly different interactions with the AV under study. Our approach overcomes challenges typically associated with traditional search-based AV testing, such as developer bias and high development costs of manually tuning search objectives. We demonstrate the efficacy of our proof-of-concept framework in several traffic scenarios, discovering diverse test cases that enable us to reveal undesirable behaviors in the AV under study, including many edge cases that might otherwise not be detected.