Automatic Testing and Falsification with Dynamically Constrained Reinforcement Learning

Xin Qin, Nikos Aréchiga, Andrew Best, Jyotirmoy V. DeshmukharXiv 2019 · OpenReview

TL;DR

This paper introduces a novel framework for automatically testing autonomous systems by modeling the system-under-design as an "ego" agent and its environment as "adversarial" (ado) agents. Using reinforcement learning, they train these ado agents to discover violations of the ego agent's specifications, demonstrating that these learned adversarial agents are more robust and generalizable than traditional testing methods.

What Problem Does This Paper Address?

Testing safety-critical autonomous systems, like self-driving cars, is incredibly challenging due to their operation in highly uncertain and dynamic environments. Traditional methods often rely on falsification or search-based techniques to find scenarios where the system fails. However, these methods are typically non-adaptive, meaning a discovered failure scenario is a fixed sequence of events that doesn't necessarily generalize to slightly different initial conditions or system dynamics. This necessitates re-running tests frequently during iterative design, which is time-consuming and inefficient. The paper aims to address this by developing a more robust and adaptive testing methodology.

Methods

The core of the paper's approach is an interactive multi-agent framework. The system-under-design is the "ego" agent, and its environment is composed of multiple "adversarial" (ado) agents. The goal is to synthesize controllers for these ado agents that can induce violations in the ego agent's behavior, based on a formal specification (using Signal Temporal Logic - STL).

Key methodological contributions include:

  • Multi-Agent Framework: Modeling the system and its environment as interacting ego and ado agents.
  • Reinforcement Learning for Adversarial Agents: Utilizing reinforcement learning (specifically Deep Q-learning and Proximal Policy Optimization) to train the ado agents. Instead of hand-crafting adversarial scenarios, the ado agents learn policies to generate them.
  • Formal Specification and Constraints: Using STL to formally define the ego agent's desired behavior and the constraints on the ado agents' behavior. This allows for automatic reward function generation for the RL training.
  • Reward Function Design: A novel reward function is proposed that hierarchically prioritizes ado constraints and penalizes violations of the ego specification. This ensures that adversarial agents behave reasonably while still trying to cause failures.
  • Generalizability Guarantees: Theoretical analysis and empirical demonstrations show that the learned adversarial policies can generalize to different initial conditions and even slightly altered ego agent dynamics without retraining. This is a significant improvement over static falsification methods.

Datasets

The paper does not introduce new datasets. Instead, it uses simulated environments for its case studies:

  • Grid-World Environment: A simulated grid-world for initial benchmarking and demonstrating generalizability across map sizes and ego agent step-sizes.
  • Autonomous Driving Simulators: The Carla simulator is used for two real-world case studies:
  • Adaptive Cruise Control (ACC): Simulating two vehicles in a single lane, where the lead vehicle is the ado agent.
  • Lane Change Maneuvers: Simulating two vehicles on a highway, where one vehicle attempts to merge into the ego agent's lane.

Key Insights and Ideas

  • Adversarial Agents as Learners: The most significant insight is treating adversarial agents not as pre-programmed scenarios but as learning entities. This allows them to discover more complex and subtle failure modes that might be missed by human-designed tests.
  • Generalizability is Key: The paper strongly emphasizes and demonstrates that learned adversarial agents are more robust and reusable. This is crucial for efficient development cycles, as it reduces the need for constant re-testing when the ego system is modified.
  • STL as a Unified Language: Using STL for both ego specifications and ado constraints simplifies the process. It allows for automatic reward generation, removing the burden of manual reward engineering, which is often a bottleneck in RL.
  • Hierarchical Constraints Matter: The proposed reward function's hierarchical structure for ado constraints is vital. It ensures that the adversarial agents don't resort to "trivial" or nonsensical behaviors (like driving backward) to cause a failure, making the testing more meaningful.

Key Results

  • Improved Success Rates: In the grid-world case study, the trained ado agent achieved success rates of 67.92% to 72.50%, significantly outperforming random ado agents (around 1-10%).
  • Generalization Across Parameters: The trained ado agent demonstrated generalizability across varying map sizes (up to 10x10 from training on 4x4) and ego agent step-sizes.
  • Robustness to Initial Conditions: The paper shows that trained ado agents can find counterexamples even for initial states not seen during training, with theoretical guarantees.
  • Autonomous Driving Success: In the ACC case study, the trained agent achieved a success rate of 54.8% (with DQN) in inducing collisions. In the yellow light scenario, success rates reached up to 75.76% after sufficient training.
  • Reduced Training Time: The use of DQN for training in the ACC case study was significantly faster (1.93 hours) compared to tabular Q-learning (4.83 hours).

Limitations and Future Work

  • Scalability of STL Encoding: While the paper uses STL for specifications and constraints, it acknowledges that more nuanced encoding of complex STL properties into reward functions could be an area for future work.
  • Convergence Guarantees: While deep RL algorithms are powerful, theoretical convergence guarantees can be challenging. The paper relies on empirical performance and theoretical results for approximate convergence.
  • Complexity of Multi-Agent Dynamics: The framework assumes a certain level of tractability in the multi-agent dynamics for RL to learn effectively. Highly complex or chaotic environments might pose further challenges.
  • Future Work: The authors suggest exploring more sophisticated STL encoding, extending the framework to handle stochastic agents, and applying it to a wider range of complex cyber-physical systems. They also highlight the potential for this approach to be integrated into formal verification tools.

Summary updated

Abstract

Autonomous systems such as self-driving cars and general-purpose robots are safety-critical systems that operate in highly uncertain and dynamic environments. We propose an interactive multi-agent framework where the system-under-design is modeled as an ego agent and its environment is modeled by a number of adversarial (ado) agents. For example, a self-driving car is an ego agent whose behavior is influenced by ado agents such as pedestrians, bicyclists, traffic lights, road geometry etc. Given a logical specification of the correct behavior of the ego agent, and a set of constraints that encode reasonable adversarial behavior, our framework reduces the adversarial testing problem to the problem of synthesizing controllers for (constrained) ado agents that cause the ego agent to violate its specifications. Specifically, we explore the use of tabular and deep reinforcement learning approaches for synthesizing adversarial agents. We show that ado agents trained in this fashion are better than traditional falsification or testing techniques because they can generalize to ego agents and environments that differ from the original ego agent. We demonstrate the efficacy of our technique on two real-world case studies from the domain of self-driving cars.
BibTeX
@misc{qin2019automatic,
  author = {Xin Qin and Nikos Aréchiga and Andrew Best and Jyotirmoy V. Deshmukh},
  title = {{Automatic Testing and Falsification with Dynamically Constrained Reinforcement Learning}},
  year = {2019},
  eprint = {1910.13645},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1910.13645},
}
Figure