Backward Reachability Analysis of Neural Feedback Loops: Techniques for Linear and Nonlinear Systems

Nicholas Rober, Sydney M. Katz, Chelsea Sidrane, Esen Yel, Michael Everett, Mykel J. Kochenderfer, Jonathan P. How

TL;DR

This paper introduces a new framework for safety certification of systems controlled by neural networks (Neural Feedback Loops) using backward reachability analysis. By developing efficient algorithms for both linear and nonlinear systems, the authors demonstrate how to calculate "backprojection sets"—the regions of state space that lead to a target set—enabling safety guarantees for complex systems like 6D quadrotors over 100 times faster than previous methods.

What Problem Does This Paper Address?

Neural networks (NNs) are increasingly used to control safety-critical systems, such as autonomous vehicles and robots, because they handle complex nonlinearities better than classical controllers. However, NNs are "black boxes" that lack the formal safety guarantees required for deployment in the real world.

Researchers often use reachability analysis to certify safety. Forward reachability asks: "Given where I am, where could I end up?" Backward reachability asks: "What starting positions lead to this dangerous region?"

Backward reachability is often superior for safety certification because it can be less conservative in scenarios where a robot might branch left or right around an obstacle. However, it is mathematically difficult because NNs are generally non-invertible and contain nonlinear activation functions (like ReLU), making it hard to "run the network in reverse" to find the set of inputs that lead to a specific output.

FIGURE 1: Collision avoidance scenario. Backward reach- ability correctly guarantees safety whereas forward reacha- bility fails.

Methods

The authors propose a framework that avoids the need to invert the NN. Instead, they leverage standard forward NN analysis tools (like CROWN) to find over-approximations of backprojection (BP) sets. Their approach is split into two main tracks:

  1. HyBReach-LP (Linear Systems): This algorithm uses Linear Programming (LP) to find BP sets for systems with linear dynamics. It introduces Guided Partitioning, which uses Monte Carlo sampling to identify which regions of the state space are most likely to reach the target. It then prioritizes partitioning those areas to reduce conservativeness without wasting time on irrelevant regions.
  2. BReach-MILP (Nonlinear Systems): For systems with nonlinear dynamics, the authors use the OVERT tool to create piecewise-linear over-approximations of the dynamics. They then solve the problem using Mixed-Integer Linear Programming (MILP), which allows for an exact encoding of the NN's ReLU activations.

The general workflow for both involves four steps: over-approximating the dynamics, finding a rough "backreachable" set ignoring the NN, encoding the NN constraints over that set, and finally solving an optimization problem to find the tightest possible bounding box for the BP set.

FIGURE 3: A summary of our approach for computing backprojection sets for both linear and nonlinear dynamical systems.

Datasets

The algorithms were evaluated on several control-relevant models rather than static datasets:

  • Double Integrator: A standard benchmark for control systems.
  • Linearized Ground Robot: A unicycle model used to demonstrate obstacle avoidance.
  • Nonlinear Ground Robot: A version of the unicycle model using trigonometric dynamics (sine/cosine) to test the MILP approach.
  • 6D Linearized Quadrotor: A high-dimensional system used to test the scalability and speed of the new algorithms.

Key Insights and Ideas

  • Forward Tools for Backward Problems: The core "aha" moment is that you don't need to invert a neural network to perform backward reachability. By embedding forward relaxation techniques (like affine bounds) into an optimization loop, you can effectively bound the input space that leads to a specific output set.
  • Guided Partitioning is a Game Changer: Uniformly splitting the state space to improve accuracy is computationally expensive. By using a "guided" approach that focuses on the boundary of the estimated BP set, the authors achieve convergence much faster.
  • Revealing Hidden Vulnerabilities: In the nonlinear robot experiment, the backward analysis revealed a "bug" caused by angle wraparound ($0$ to $2\pi$). The BP sets "marched" in an unexpected direction, showing that certain control inputs near the x-axis could inadvertently drive the robot into an obstacle—a vulnerability that might be missed by standard testing.
Visualizing the Guided Partitioning process

Key Results

  • Massive Speedups: For the 6D quadrotor system, the combination of Guided Partitioning, Disciplined Parametric Programming (DPP), and a "SkipLP" strategy reduced the computation time from 3,796 seconds to just 28 seconds—a 135x improvement.
  • Reduced Conservativeness: The HyBReach-LP algorithm consistently produced tighter (less conservative) set estimates than previous methods like BReach-LP, while remaining computationally efficient.
  • Nonlinear Certification: The BReach-MILP approach successfully certified safety for a nonlinear 2D robot, proving the framework's versatility across different dynamics.

Limitations and Future Work

  • Hyper-rectangular Bounds: The current method produces axis-aligned boxes (hyper-rectangles) to bound the sets. While efficient, these can be conservative if the true BP set is slanted or curved. The authors suggest exploring other set representations (like polytopes or zonotopes) in the future.
  • Scalability to Higher Dimensions: While 6D is a significant step, real-world systems (like full humanoid robots) have much higher dimensionality, which remains a challenge for reachability analysis.
  • Dynamics Approximation: For nonlinear systems, the accuracy depends on the piecewise-linear approximation of the dynamics; tighter approximations lead to better results but increase the number of integer variables in the MILP, slowing down the solver.

Summary updated

Abstract

As neural networks (NNs) become more prevalent in safety-critical applications such as control of vehicles, there is a growing need to certify that systems with NN components are safe. This paper presents a set of backward reachability approaches for safety certification of neural feedback loops (NFLs), i.e., closed-loop systems with NN control policies. While backward reachability strategies have been developed for systems without NN components, the nonlinearities in NN activation functions and general noninvertibility of NN weight matrices make backward reachability for NFLs a challenging problem. To avoid the difficulties associated with propagating sets backward through NNs, we introduce a framework that leverages standard forward NN analysis tools to efficiently find over-approximations to backprojection (BP) sets, i.e., sets of states for which an NN policy will lead a system to a given target set. We present frameworks for calculating BP over approximations for both linear and nonlinear systems with control policies represented by feedforward NNs and propose computationally efficient strategies. We use numerical results from a variety of models to showcase the proposed algorithms, including a demonstration of safety certification for a 6D system.
BibTeX
@article{rober2023backward,
  author = {Nicholas Rober and Sydney M. Katz and Chelsea Sidrane and Esen Yel and Michael Everett and Mykel J. Kochenderfer and Jonathan P. How},
  title = {{Backward Reachability Analysis of Neural Feedback Loops: Techniques for Linear and Nonlinear Systems}},
  journal = {IEEE Open Journal of Control Systems},
  year = {2023},
  doi = {10.1109/ojcsys.2023.3265901},
}
Figure