Counter-example Guided Learning of Bounds on Environment Behavior

Yuxiao Chen, Sumanth Dathathri, Tung Phan-Minh, Richard M. Murray

TL;DR

This paper introduces a novel data-driven framework for verifying autonomous systems that interact with complex, unmodeled environments. It learns a "reactive bound" on the environment's behavior, which is then used to formally verify the system's safety and performance guarantees, even without a perfect environmental model. This approach has been successfully demonstrated on multi-robot navigation and autonomous driving scenarios.

What Problem Does This Paper Address?

Building autonomous systems that operate safely in complex, real-world environments is a significant challenge. A key difficulty is the inability to create accurate, comprehensive models of these environments, which are often dynamic, unpredictable, and influenced by external agents (like other vehicles or robots). Without such models, it's hard to formally guarantee that an autonomous system will behave as intended and avoid unsafe situations. Traditional formal verification methods rely heavily on precise environment models, which are often infeasible to obtain. This paper tackles this gap by proposing a method to verify system behavior without needing a perfect environmental model, instead learning a conservative approximation of the environment's possible actions.

Methods

The core of the proposed approach is a Counter-example Guided Learning of Bounds framework. Here's a breakdown of the key techniques:

  • Falsification: The system uses a falsifier (specifically, the S-Taliro tool) to search for scenarios where the system violates its safety specification. This falsifier works with the current controller and a learned "reactive bound" of the environment.
  • Reactive Bound Learning: When the falsifier finds a violation (a "negative trace"), this trace, along with positive traces of desired behavior, is fed into a reactive modeling module. This module learns a function, $h(x, d) \ge 0$, that defines the set of possible environment actions ($d$) given the system's state ($x$). This bound is "reactive" because it depends on the current system state.
  • L₁ Piecewise SVM: To learn this reactive bound, the paper proposes an "L₁ piecewise SVM" (Support Vector Machine). This is a specialized SVM designed to:
  • Provide a low probability of false negatives (i.e., incorrectly classifying a dangerous environment action as safe).
  • Have an analytic form for its decision boundary, which is crucial for verification.
  • Handle piecewise environmental behavior by using multiple separating hyperplanes and automatically tuning the regions using membership functions.
  • Iterative Refinement: The process is iterative: the falsifier searches for violations using the current reactive bound. If violations are found, they are used to refine the bound. This continues until the falsifier can no longer find any violations under the learned bound, at which point the system is considered verified with high probability.
  • Random Convex Programs (RCP) Theory: The reliability of the learned bounds and the verification process is grounded in the theory of Random Convex Programs, which provides probabilistic guarantees on the accuracy of the learned model based on the amount of data.

Datasets

The paper utilizes real-world data for its case studies:

  • Multi-robot navigation: Data was generated through simulations of a multi-robot system.
  • Lane Change: The paper uses data from the "safety pilot model deployment (SPMD) database," which contains over 50 million miles of naturalistic driving data. This is a significant real-world dataset for autonomous driving research.

Key Insights and Ideas

  • Verification without a Perfect Model: The most significant insight is the demonstration that formal verification of complex systems can be achieved even when the environment is not fully modeled. By learning a conservative approximation of the environment's behavior, we can still gain strong guarantees.
  • Reactive Bounds are Key: The concept of "reactive bounds" is crucial. Instead of a static model of the environment, the bound adapts to the system's current state, making it more expressive and useful for dynamic scenarios.
  • Counter-examples Drive Learning: The iterative process where falsifying traces directly inform the learning of the environment model is a powerful feedback loop. This ensures that the learned bound is specifically tailored to capture the types of behaviors that could lead to system failure.
  • Piecewise SVM for Expressiveness: The development of a piecewise SVM allows the framework to capture more complex, non-linear environmental behaviors that a standard SVM might miss. This is particularly relevant for scenarios with distinct operational modes or regions.

Key Results

  • Successful Verification: The framework successfully verified controllers for both the toy multi-robot system and the autonomous vehicle lane-change scenario.
  • Multi-robot Navigation: After 5 iterations, the falsifier could no longer find violating traces for the multi-robot system under the learned reactive bound. The learned bound was shown to be close to the actual threshold of the environment's behavior.
  • Lane Change: For the lane change scenario, the framework verified an MPC controller. Without the reactive bound, the falsifier could easily find scenarios to block the AV. With the learned bound, the falsifier could not find such scenarios, demonstrating the controller's safety. The paper also shows how removing a collision avoidance constraint led to a collision, highlighting the framework's ability to identify critical failure modes.
  • Runtime: The mean run times were reported as 4977s for the robot problem and 29.6s for the lane change problem, indicating reasonable computational cost for the verification process.

Limitations and Future Work

  • Data Requirements: The reliability of the learned bound is dependent on the quality and quantity of the data. While the paper uses real-world data, obtaining sufficient data for all possible states and environmental interactions can still be a challenge.
  • Computational Cost: While the runtimes are presented, the iterative nature of the falsification and learning process can still be computationally intensive, especially for highly complex systems or long horizons.
  • Generalizability of SVM: While the piecewise SVM increases expressiveness, there might still be environmental behaviors that are difficult to capture with this model class.
  • Future Work: The authors suggest extending the framework to handle more complex dynamics, explore different learning algorithms for the reactive bound, and investigate its application to a wider range of autonomous systems and interaction scenarios. The paper also mentions the possibility of using the learned bounds for controller synthesis, which is a natural next step.

Summary updated

Abstract

There is a growing interest in building autonomous systems that interact with complex environments. The difficulty associated with obtaining an accurate model for such environments poses a challenge to the task of assessing and guaranteeing the system's performance. We present a data-driven solution that allows for a system to be evaluated for specification conformance without an accurate model of the environment. Our approach involves learning a conservative reactive bound of the environment's behavior using data and specification of the system's desired behavior. First, the approach begins by learning a conservative reactive bound on the environment's actions that captures its possible behaviors with high probability. This bound is then used to assist verification, and if the verification fails under this bound, the algorithm returns counter-examples to show how failure occurs and then uses these to refine the bound. We demonstrate the applicability of the approach through two case-studies: i) verifying controllers for a toy multi-robot system, and ii) verifying an instance of human-robot interaction during a lane-change maneuver given real-world human driving data.
BibTeX
@inproceedings{chen2019counter,
  author = {Yuxiao Chen and Sumanth Dathathri and Tung Phan-Minh and Richard M. Murray},
  title = {{Counter-example Guided Learning of Bounds on Environment Behavior}},
  booktitle = {Conference on Robot Learning},
  year = {2019},
  url = {https://openreview.net/forum?id=V9KaX-kqkAW},
}

Loading related content...

Figure