⚡ electrical engineering

Online Data-Driven Reachability Analysis using Zonotopic Recursive Least Squares

This paper presents a data-driven reachability analysis framework that utilizes Exponentially Forgetting Zonotopic Recursive Least Squares (EF ZRLS) to recursively estimate time-varying system models from online noisy measurements, enabling the computation of less conservative forward reachable sets for both linear time-varying and nonlinear Lipschitz systems without requiring prior model knowledge or offline experiments.

Original authors: Alireza Naderi, Amr Hegazy, Amr Alanwar

Published 2026-08-12

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Alireza Naderi, Amr Hegazy, Amr Alanwar

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to predict where a runaway shopping cart will roll next. In the world of engineering and robotics, this is called reachability analysis. It's a safety check that asks: "If we start here, and the wind blows a little, or the wheels slip a bit, where could this object end up?" If we can draw a big, safe bubble around all those possible future spots, we can make sure the cart never rolls into a busy street or a fragile flower bed.

Traditionally, engineers tried to draw this bubble by writing down a perfect math formula for how the cart moves. They needed to know the exact weight of the cart, the friction of the wheels, and the strength of the wind. But in the real world, things change. A cart might get a new wheel, or the ground might get wet. If your math formula is even slightly wrong, your safety bubble might be too small, and disaster could happen. That's why scientists are looking for a smarter way: a method that learns the rules of the game just by watching the cart roll, without needing a perfect formula beforehand. This paper is about building that "watch-and-learn" safety bubble in real-time, even when the cart is changing its behavior on the fly.

The Paper's Big Idea: The "Forgetful" Safety Net

The authors, Alireza Naderi and his team, have developed a new method to draw these safety bubbles using only live data. Instead of trying to memorize the entire history of the cart's movement (which can be slow and rigid), their method uses a clever trick called Exponentially Forgetting Zonotopic Recursive Least Squares (EF-ZRLS).

Think of this method as a very smart, slightly forgetful detective. Imagine you are trying to guess the speed of a car that keeps changing its engine.

The Old Way (Batch Least Squares): The old detective would wait until the end of the day, collect every single speedometer reading from the morning, and then do a massive calculation to guess the speed. If the car swapped its engine at noon, the detective's calculation would be wrong because it's mixing morning data with afternoon data.
The New Way (EF-ZRLS): The new detective only looks at the last few minutes. If the car speeds up, the detective immediately updates their guess and "forgets" the old, slower speed. This allows them to track a car that is constantly changing its engine or driving on different roads.

The "Zonotopic" part of the name is just a fancy geometric shape (like a stretched-out, multi-dimensional diamond) used to draw the safety bubble. It's efficient and keeps the math from getting too heavy for computers to handle in real-time.

How It Works: The Sliding Window

The core of their discovery is a "sliding window" approach. As the system (like a robot or a car) moves, the method constantly grabs the most recent data points—say, the last 5 seconds of movement—and uses them to estimate the system's current "personality" (its mathematical model).

Because the system might be noisy (sensors might be a little fuzzy) or changing (the robot might pick up a heavy box), the method doesn't just guess one single number for the speed or direction. Instead, it calculates a set of all possible models that could explain what happened. It's like saying, "The car could be going anywhere between 10 and 12 mph, and it could be turning between 5 and 7 degrees." This set is guaranteed to contain the true behavior of the system, even with the noise.

Once they have this "set of possible models," they use it to predict where the system will go next. They draw a new safety bubble around the predicted future positions. If the system changes suddenly (like the robot picking up that heavy box), the "forgetting" part of their algorithm kicks in, discards the old data, and redraws the bubble to fit the new reality.

What They Found: Better Safety, Less Waiting

The team tested their idea in three different ways, and the results were promising:

The Changing Line: They simulated a system where the rules changed slightly over time. The old method (which uses all past data) failed to keep the safety bubble big enough, meaning it thought the system was safer than it actually was. The new method, however, kept the bubble perfectly sized, ensuring safety even as the system changed.
The Wobbly Robot: They tested it on a simulation of a chemical reactor (a complex, wobbly system). The new method created a safety bubble that was tighter and more accurate than the old method, meaning it wasted less space while still staying safe.
The Real Robot Car: They took a real autonomous racing robot (a JetRacer) and ran it around. In one test, they added a 2 kg weight to the car to simulate a sudden change. The old method got confused and failed to predict the car's path correctly. The new method, however, adapted instantly, recalculating the safety bubble as the car got heavier, and successfully predicted where the car would go.

Why This Matters

The most exciting part of this paper is that it doesn't need a "training phase." You don't need to record hours of data before you can start using the safety system. It works online, meaning it learns and updates its safety bubble while the robot is actually moving.

This is a huge deal for things like self-driving cars or medical robots. If a self-driving car hits a patch of ice, or a robot arm picks up a heavy tool, the system needs to know right now that its movement rules have changed. This new method allows the computer to say, "Okay, the rules changed, let's redraw the safety bubble immediately," without needing to stop and re-calculate everything from scratch.

The authors proved their method works through simulations and real-world experiments, showing that it is robust, less conservative (meaning it doesn't waste space), and capable of handling systems that change their minds as they move. It's a step toward making autonomous systems that are not just smart, but also adaptable and safe in a messy, changing world.

Technical Summary: Online Data-Driven Reachability Analysis using Zonotopic Recursive Least Squares

1. Problem Statement

Modern cyber-physical systems (CPS) require formal safety verification to ensure they do not enter unsafe states. Reachability analysis is a primary technique for this, aiming to compute the set of all states a system can reach given uncertain initial conditions, inputs, and process noise.

Classical model-based approaches rely on accurate, pre-defined analytical dynamics. However, in many real-world scenarios, constructing an exact system model is non-trivial or impossible due to complex, unknown, or time-varying dynamics. Conversely, existing data-driven approaches often require large volumes of pre-collected offline data to construct a set of consistent models. These batch methods struggle when system models change over time (time-varying dynamics) or when offline data collection is infeasible. Furthermore, high-dimensional systems pose scalability challenges for methods solving Hamilton-Jacobi partial differential equations.

This paper addresses the challenge of computing over-approximated reachable sets for discrete-time systems where:

The system model is unknown.
Only online, noisy input-state measurements are available.
The system dynamics may be time-varying (Linear Time-Varying or LTV) or nonlinear (Lipschitz continuous).
No pre-recorded offline datasets are available for initial model identification.

2. Methodology

The proposed framework consists of two main components: a recursive parameter estimation method and a data-driven reachability propagation algorithm.

2.1 Exponentially Forgetting Zonotopic Recursive Least Squares (EF-ZRLS)

To estimate the unknown, time-varying system models from noisy data, the authors propose the EF-ZRLS method. Unlike standard Recursive Least Squares (RLS) that estimates a single point, EF-ZRLS estimates a set of models (represented as a matrix zonotope) that is guaranteed to contain the true system parameters.

Set-Based Estimation: The method maintains a time-varying matrix zonotope $\mathcal{M}_k = \langle C_k, G_k \rangle$ , where $C_k$ is the center matrix and $G_k$ is the generator matrix. The true parameter matrix $\theta_{tr,k}$ is guaranteed to lie within this set.
Handling Noise and Variations: The method accounts for:
- Measurement Noise ( $v_k$ ): Bounded by a known zonotope.
- Parameter Variations ( $\delta \theta_k$ ): The model is assumed to be slowly time-varying, with changes bounded by a known zonotope.
Exponential Forgetting: A forgetting factor $\lambda \in (0, 1]$ is introduced. This factor exponentially decreases the influence of past data on the covariance update, allowing the estimator to adapt to time-varying dynamics.
Optimal Gain: The authors derive an optimal correction gain $K_k^*$ that minimizes the trace of the covariance matrix (the size of the estimated set), ensuring the tightest possible over-approximation given the noise bounds.
Vector vs. Matrix Form: The method is formulated for multi-output regression models using matrix zonotopes, avoiding the computational overhead of converting to vector-permutation forms (which increases dimensionality via Kronecker products).

2.2 Data-Driven Reachability Analysis

Using the estimated time-varying set of models, the framework computes forward reachable sets for two system classes:

Linear Time-Varying (LTV) Systems:
- The system is modeled as $x_{k+1} = A_{tr,k}x_k + B_{tr,k}u_k + w_k$ .
- The algorithm (Algorithm 1) recursively updates the model set using EF-ZRLS.
- To handle the lack of new data during the prediction horizon, the method assumes the model variation is bounded by a known constant ( $\sigma_{AB}$ ) and expands the model set accordingly.
- A spatial generalization error term ( $Z_\epsilon$ ) is added to account for the density of the data relative to the continuous state-input space.
Nonlinear Lipschitz Systems:
- The nonlinear function $f(x_k, u_k)$ is approximated via a first-order Taylor expansion around a linearization point, resulting in a time-varying linear model plus a Lagrange remainder term $L(z_k)$ .
- The EF-ZRLS estimates the time-varying linearized model parameters.
- The remainder term $L(z_k)$ is over-approximated using a zonotope ( $Z_L$ ) derived from the data in a sliding window, leveraging the Lipschitz continuity assumption.
- An additional error term ( $Z_{\bar{\epsilon}}$ ) accounts for the Lipschitz constant and data density.

3. Key Contributions

The paper outlines four primary contributions:

EF-ZRLS Method: A novel set-based recursive estimator for time-varying multi-output regression models with bounded noise. The paper establishes the optimality of the estimator and derives the optimal correction gain (Theorem 1).
LTV Reachability Algorithm: An algorithm (Algorithm 1) to compute over-approximated reachable sets for discrete-time LTV systems subject to bounded process noise and model variations (Theorem 2).
Nonlinear Lipschitz Reachability Algorithm: An extension (Algorithm 2) to compute over-approximated reachable sets for a class of discrete-time nonlinear Lipschitz systems (Theorem 3).
Validation: Comprehensive validation through numerical simulations and a real-world experiment on an autonomous vehicle, contrasting the proposed method with existing batch Least Squares (LS) approaches.

4. Results and Evaluation

The authors evaluate the proposed method against a batch LS approach (from reference [2]) using three scenarios:

LTV System (Static Parameters): In a scenario with no parameter changes, the proposed EF-ZRLS converges to the same reachable set as the batch LS method after a sufficient number of iterations, validating the consistency of the recursive approach.
LTV System (Time-Varying Parameters): When system parameters change over time, the batch LS method fails to over-approximate the true reachable sets (as it relies on static offline data). In contrast, the proposed EF-ZRLS successfully tracks the changing dynamics and maintains a valid over-approximation.
Nonlinear Lipschitz System (CSTR): Applied to a Continuous Stirred Tank Reactor model, the proposed method yields less conservative reachable sets than the batch LS method. This is attributed to the recursive update of the linearized model and the localized estimation of the Lagrange remainder, whereas the batch method computes a global remainder over the entire offline dataset.
Real-World Experiment (Autonomous Vehicle): Using a JetRacer robot, the method was tested under two conditions:
1. Static Environment: The method produced less conservative sets than the batch LS method without requiring pre-collected data.
2. Dynamic Environment (Payload Change): A 2kg payload was added to the vehicle, simulating a model change. The proposed method remained robust and valid, while the batch LS method failed to over-approximate the reachable sets.

5. Significance and Claims

The paper claims that the proposed framework offers a significant advancement in safety analysis for systems where accurate models are unavailable or time-varying. Key significance points include:

Online Operation: The method operates solely on real-time data, eliminating the need for pre-recorded offline experiments, which is crucial for systems where dynamics evolve or offline data is difficult to collect.
Robustness to Time-Variance: By utilizing exponential forgetting and set-based estimation, the method remains robust under slowly varying dynamics, a limitation of static batch identification methods.
Reduced Conservatism: The approach produces less conservative reachable-set over-approximations compared to existing techniques, particularly for nonlinear systems, by utilizing local data updates rather than global offline approximations.
Scalability: The use of zonotopes and matrix formulations offers better scalability for higher-dimensional systems compared to methods solving Hamilton-Jacobi PDEs.

The authors conclude that while the method is effective, future work will focus on extending the EF-ZRLS to use adaptive forgetting factors ( $\lambda$ ) to further reduce the conservatism of the estimated model sets.