⚡ electrical engineering

Predictive Zonotope Reduction: Precise Runtime Monitoring under Uncertainty

This paper introduces Predictive Zonotope Reduction (PZR), a dynamic approach that frames reducer selection as an optimal control problem and utilizes policy distillation to enable precise, resource-efficient runtime monitoring for robots operating under uncertainty, significantly reducing false-positive rates compared to static strategies.

Original authors: Vladimir Krsmanovic, Florian Kohn, Bernd Finkbeiner, Milan Simovic

Published 2026-09-04

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Vladimir Krsmanovic, Florian Kohn, Bernd Finkbeiner, Milan Simovic

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

Robots that move through the real world rely on sensors to understand their surroundings. These sensors, however, are never perfect. A camera might struggle in fog, or a distance meter might jitter due to electrical noise. When a robot makes a decision based on these imperfect readings, it risks taking an action that is either too cautious or dangerously reckless. To keep robots safe, engineers use a safety system called a runtime monitor. This system acts like a vigilant guard, constantly checking the robot's behavior against a set of rules to ensure it stays within safe boundaries. The challenge lies in representing the robot's uncertain position. If the monitor assumes the robot is in exactly one spot, it might miss a danger lurking just outside that point. If it assumes the robot could be anywhere in a vast area, it will sound the alarm too often, causing the robot to stop unnecessarily. The goal is to find a representation that is precise enough to be useful but simple enough to calculate quickly.

A mathematical shape known as a zonotope has become a popular tool for this job. Imagine a cloud of possible locations for the robot, shaped like a stretched, multi-dimensional balloon. As the robot moves and takes new sensor readings, this cloud grows and changes shape. The problem is that every new piece of information adds complexity to the cloud, making it harder and harder to compute. Eventually, the cloud becomes so large that the computer running the monitor cannot keep up, especially if the robot is running on a small, battery-powered device. To solve this, engineers must periodically shrink the cloud, a process called reduction. They do this by replacing the complex shape with a slightly larger, simpler one that still contains all the possible locations. The catch is that there are many different ways to shrink this cloud, and each method produces a different result. Some methods are better at keeping the shape tight in certain situations, while others work better in different ones. Traditionally, engineers have picked one method and stuck with it for the entire journey, even though the best choice changes as the robot moves.

Researchers at CISPA Helmholtz Center for Information Security and the Technical University of Munich have developed a new approach that changes how this decision is made. Instead of sticking to a single method, their system, called Predictive Zonotope Reduction, treats the choice of how to shrink the cloud as a sequence of decisions. It asks not just "what is the best way to shrink the cloud right now?" but "what is the best way to shrink it now, and then again in the next few steps, to keep the overall shape as tight as possible?" To answer this, the system uses a technique borrowed from robotics control, where a computer plans a few steps ahead to see the consequences of its current action. It simulates different paths, looking at how each choice of shrinking method would affect the cloud's shape in the near future. By looking ahead, the system can choose a method that might not be perfect for the immediate moment but sets up the cloud to be much more accurate later on.

However, running these complex simulations in real-time is too slow for many robots. To make the system fast enough for practical use, the researchers taught a small computer program to mimic the decision-making of the slow, careful planner. They used a process called policy distillation, where a neural network, acting as a student, learns from the "teacher" planner. The student network does not need to simulate the future; it simply looks at the current shape of the cloud and ranks the available shrinking methods from best to worst. This allows the system to make high-quality decisions almost instantly. To ensure the system remains robust, they combined several of these student networks into a group, letting them vote on the best choice. If the group is unsure, a backup planner steps in to make the final call. This combination of looking ahead, learning from experience, and voting for safety allows the system to run on very modest hardware, such as a Raspberry Pi 5, while maintaining high precision.

The researchers tested their new system on a simulated five-jointed robotic arm moving in a virtual environment. They programmed the arm to move while its sensors were subjected to realistic errors, mimicking the kind of noise found in real-world devices. They ran the arm through hundreds of different movements, comparing their new dynamic system against older methods that used a single, fixed way to shrink the uncertainty cloud. The results were striking. The new system reduced the number of false alarms by a significant margin. In the tests, the old fixed methods triggered unnecessary emergency stops nearly 30 percent of the time when the robot was actually safe. The new predictive system lowered this rate to less than 2 percent. This means the robot could move more freely and confidently, knowing that the safety monitor was not crying wolf. The system achieved this while running at a speed of 100 times per second, fast enough to keep up with the rapid movements of a real robot.

The study also revealed something surprising about how these shrinking methods work together. The researchers found that the method that performed best on its own was not always the one chosen most often by their smart system. In fact, the system frequently chose a method that was often poor when used alone. This happened because the smart system understood that using a different method first could reshape the cloud in a way that made the "poor" method work very well later. It was a lesson in timing and sequence: the best move is not always the strongest move in isolation, but the one that sets up the best future. By switching between methods dynamically, the system kept the uncertainty cloud much tighter than any single method could ever achieve on its own.

This work demonstrates that safety systems for robots do not have to be static. By treating the management of uncertainty as a dynamic, forward-looking problem, engineers can create monitors that are both safer and more efficient. The ability to run these advanced calculations on small, inexpensive hardware opens the door for more robots to operate safely in complex, unpredictable environments. The researchers showed that with the right approach, a robot can understand its own uncertainty better, leading to fewer mistakes and more reliable performance in the real world.

Technical Summary: Predictive Zonotope Reduction for Precise Runtime Monitoring under Uncertainty

Problem Statement
Robots operating in physical environments rely on sensor measurements that inherently contain uncertainty due to environmental conditions and hardware limitations. To ensure safety, runtime monitors validate robot behavior against specifications. A common approach to soundly represent this uncertainty is using zonotopes (convex, point-symmetric sets). However, as new sensor measurements are continuously integrated during operation, the computational order of the zonotope grows unboundedly. To maintain feasibility on resource-constrained hardware, monitors must periodically apply zonotope reduction, an over-approximating step that limits the zonotope's order.

Existing approaches typically employ a fixed reduction method throughout the system's runtime. This is suboptimal because the ideal reduction strategy is state-dependent; a method that is precise at one moment may introduce excessive error at another. Furthermore, the choice of reduction method significantly impacts the precision of the monitor's verdicts. A lack of precision leads to false positives (unnecessary emergency stops or task aborts), which is particularly detrimental in scenarios like robot learning where exploration is required.

Methodology
The authors propose Predictive Zonotope Reduction (PZR), a framework that treats the selection of reduction methods as a sequential decision problem rather than a static configuration.

Optimal Control Formulation: PZR frames the selection of a reduction operator as an optimal control problem. The "state" is the current monitor state (including zonotope geometry), and the "action" is the choice of a sound reduction method from a predefined set. The objective is to minimize the Squared Hull Error (a metric estimating the false-positive rate) over a future horizon, rather than just optimizing the immediate reduction.
Model Predictive Control (MPC): The authors instantiate this formulation using MPC.
- MPC-F (Recorded-Future): Uses perfect knowledge of future inputs (offline or staggered decision scenarios) to roll out sequences of reductions and select the optimal path.
- MPC-B (Beam Search): To handle the exponential complexity of enumerating all method combinations, a beam search with a fixed width ( $W=4$ ) is employed to retain the most promising prefixes.
- MPC-L (Causal Predictive): For online settings where future inputs are unknown, future events are predicted via linear extrapolation of past inputs. This allows the system to operate causally without sacrificing soundness guarantees.
Policy Distillation for Real-Time Execution: While MPC provides high precision, its computational cost is prohibitive for real-time embedded systems. To address this, the authors distill the MPC control policies into lightweight neural ranking policies.
- Teacher-Student Setup: A neural network (student) is trained to rank reduction methods based on the rankings produced by the MPC "teacher."
- Ranking Objective: Instead of classifying a single "best" method, the network learns a pairwise ranking of all available reducers, providing a denser learning signal.
- Ensemble and Guarding: To mitigate covariate shift (where the distribution of runtime states differs from training data), multiple neural policies are combined into an ensemble that votes on the best method. A "Guard" mechanism (using a short-horizon MPC) intervenes when the ensemble lacks consensus or in ambiguous situations, ensuring robustness.

Key Contributions

Formulation of PZR: The paper formulates zonotope reduction as an optimal control problem, recognizing that reduction choices affect the future shape of uncertainty, not just the current state.
Receding-Horizon MPC Policy: The authors implement a policy that selects reduction methods by optimizing predicted future set tightness, removing the need for manual tuning of reduction strategies.
Neural Distillation and Ensemble: The work demonstrates that control policies can be distilled into neural networks that retain high accuracy while achieving real-time throughput. The integration of an ensemble with a control-policy guard enhances robustness against covariate shifts.
Implementation and Evaluation: The approach is implemented within the RLola runtime monitoring framework and evaluated on a 5-degree-of-freedom robotic arm simulated in MuJoCo, with sensor noise modeled according to ISO 5725.

Results
Experiments conducted on a Raspberry Pi 5 (16 GB RAM) demonstrate significant improvements over static reduction baselines (Girard, Scott, PCA, Combastel):

Precision: Dynamic selection produces significantly tighter zonotope approximations. At a transform bound of $b=150$ , the best fixed reducer yielded a False Positive Rate (FPR) of 29.68%, whereas the dynamic selectors (e.g., Vote3-Guarded) achieved an FPR of 1.79%.
Latency: While MPC-based policies are precise, they are computationally expensive. The distilled neural policies (e.g., G15, Vote3) achieve approximation losses comparable to MPC but with drastically lower latency, enabling 10 Hz monitoring throughput on the embedded hardware.
Method Complementarity: The analysis reveals that reduction methods are complementary. For instance, the Scott method is selected most frequently by the dynamic policies despite poor standalone performance, provided that Girard or PCA methods are used occasionally to condition the zonotope matrix for Scott's success.

Significance and Claims
The paper claims that Predictive Zonotope Reduction significantly improves the precision of runtime monitoring under uncertainty without compromising soundness. By dynamically selecting reduction methods, the approach reduces the rate of false positives (vacuous alarms), which is critical for preventing unnecessary system interruptions in safety-critical and learning-based robotic applications.

The authors emphasize that their method maintains formal safety guarantees by construction; the reduction methods selected are always sound over-approximations, ensuring that false negatives (missing a violation) are impossible. The primary trade-off addressed is between the tightness of the approximation (precision) and computational cost, which the proposed distillation strategy resolves for resource-constrained real-time systems. The work does not claim to invent new reduction algorithms but rather provides a framework for optimally sequencing existing ones.

Technical Summary: Predictive Zonotope Reduction for Precise Runtime Monitoring under Uncertainty

More like this