SURF 2024: Hierarchical Testing for Safety-Critical Autonomous Systems
2024 SURF Hierarchical Testing for Safety-Critical Autonomous Systems
- Mentor: Richard Murray
- Co-mentor: Apurva Badithela
Project Description
Automatically identifying failure cases of safety-critical autonomous systems is important for mainstream deployment of these systems. A few examples of such safety-critical robotic systems is illustrated on the right. Since autonomous robotic systems are complex and their domain of operation is very large, it is not possible to exhaustively verify correctness of the autonomous system with respect to safety specifications. Oftentimes, these systems need to reason over both discrete as well as continuous inputs and parameters.
State of the art methods include simulation-based falsification in which a simulator of the system (whose model is black-box) is queried with inputs until a failing trace is found. Current research in this area is in developing novel black-box optimization algorithms to query inputs in identifying these failing traces. However, most of these algorithms require the input vector to be continuous valued. Furthermore, these test inputs are often parameters that remain constant throughout the test, and are not reactive to system behavior. We wish to research the applicability of these methods to discrete-valued as well as mixed discrete-continuous inputs, and to reactive settings.
Problem Motivated via a Simple Example:
For example, consider a simple 2D double integrator system illustrated as a blue point mass as seen in the following .mp4 files. This system has two operating modes: north-south oscillating mode and east-west oscillating mode. The N-S and E-W poles are illustrated in red. When an external "switch" command is given to the system, it needs to safely switch to the other operating mode without entering the unsafe regions (shaded in blue).
The following video illustrates the system responding to a switch command. The system safely transitions from oscillating in the N-S mode to the E-W mode without entering the blue regions. Using black-box optimization, the time of the switch commanded is optimized to result in the worst-case possible trajectory (which is still far from the unsafe region). Observe that the switch is commanded when the system has gained a lot of momentum in transitioning to the other pole.
In the video below, two switches are commanded in quick succession, and once again, the time of the switches is optimized to result in the worst-case possible trajectory. In this run, however, the system enters the unsafe region, thus demonstrating a failure in the control design. Fundamentally, the decision to switch twice (and similarly three times, four times etc.) is a discrete variable. Currently, identifying these discrete inputs in combination with continuous inputs is not well-studied in the literature.
Therefore, we seek to identify a sequence of discrete inputs, that together with worst-case low-level inputs, leads to a violating system trajectory.
Desired:
- Experience programming in Python
- Coursework: CDS 110
- Interest in theoretical and computational research in topics such as: safety-critical systems, autonomous robotic systems, control theory, and optimization.
References:
[1] Annpureddy, Yashwanth, et al. "S-taliro: A tool for temporal logic falsification for hybrid systems." International Conference on Tools and Algorithms for the Construction and Analysis of Systems. Berlin, Heidelberg: Springer Berlin Heidelberg, 2011.
