Robust monitors reduce false alarms in uncertain autonomous systems
Anytime-Valid Monitoring of Robust Stochastic Models
Logic in Computer Science
Summary
Safety methods for autonomous systems need accurate models of how agents interact with their environment, but these models are often imperfect or incomplete. The authors present a new way to watch these models while the system is running, to quickly spot when the model is wrong compared to the real world, without falsely raising alarms too often. They use a strategy based on sequential betting rules that helps decide when to signal a problem and prove their method is theoretically optimal within a certain class of monitors. Their tests show these new monitors detect issues faster and handle more detailed information than previous methods.
What this means in practice
- •For autonomous vehicle developers: Improve safety by quickly detecting when the vehicle's environment model disagrees with reality, minimizing false warnings.
- •For robotics system integrators: Implement monitors that efficiently use complex sensor data to alert operators when robot models become unreliable during missions.
Authors
Martin Kurečka, Roman Andriushchenko, Milan Češka, Nicola Paoletti, Petr Novotný
Abstract
Formal methods provide a principal approach to obtaining safety guarantees for autonomous agents. Their key bottleneck is their reliance on a formal model (e.g., a Markov decision process) describing the agent-environment interaction. Learning or crafting the model is an error-prone process, which undermines the guarantees offered by formal methods. Robust models account for modelling uncertainty, but may still fail to capture the true environment. This issue can be addressed through \emph{runtime model monitoring}, which aims to raise an alarm when a likely model-environment discrepancy is detected, while keeping the probability of false alarm bounded. Existing approaches impose various assumptions and do not clearly explain the rationale behind their design choices, leaving the broader design space for these monitors somewhat opaque. In this paper, we formalise the design space of monitors for robust stochastic models through the lens of \emph{parameterised sequential betting} algorithms, highlighting the importance of \emph{observation feature} design (choosing what information about the history the monitor uses) and \emph{bet design} (how rich a family of betting rules the monitor can represent). We show that our framework generalizes the existing approaches, and we use its formalization to propose a new \emph{mixture of linear monitors (ML)} design. We prove that these ML monitors achieve an asymptotically optimal detection time within the class of linear monitors, making them a principled choice for our monitoring problem. Our experiments confirm that ML monitors significantly reduce detection times compared to existing monitors and can effectively exploit more complex observation features.