Monitoring Spatially Distributed Cyber-Physical Systems with Alternating Finite Automata
Anand Balakrishnan, Sheryl Paul, Simone Silvetti, Laura Nenzi, Jyotirmoy V. Deshmukh · 2025
Read Monitoring Spatially Distributed Cyber-Physical Systems with Alternating Finite Automata by Anand Balakrishnan, Sheryl Paul, Simone Silvetti, Laura Nenzi, Jyotirmoy V. Deshmukh (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-21906.txt.
Introduction
Anand Balakrishnan and co-authors present a 2025 arXiv paper on watching swarms and other spread-out cyber-physical systems for rule breaking. Their logic, STREL, states space-and-time requirements over shifting networks, like a drone flock keeping shape. The authors translate its statements into weighted alternating automata that encode both the yes-no and the graded meanings of the logic.
Those automata then drive both offline log checking and live monitoring. A simulated drone swarm shows the machinery working. The authors pitch the construction as a practical bridge between a rich spatial logic and tools that can actually run it.
Catalog record
| CREATOR | Anand Balakrishnan, Sheryl Paul, Simone Silvetti, Laura Nenzi, Jyotirmoy V. Deshmukh |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 56 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2503-21906
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Monitoring Spatially Distributed Cyber-Physical Systems with Alternating Finite Automata Anand Balakrishnan, Sheryl Paul, Simone Silvetti, Laura Nenzi, Jyotirmoy V. Deshmukh Abstract . Modern cyber-physical systems (CPS) can consist of various networked components and agents interacting and communicating with each other. In the context of spatially distributed CPS, these connections can be dynamically dependent on the spatial configuration of the various components and agents. In these settings, robust monitoring of the distributed components is vital to ensuring complex behaviors are achieved, and safety properties are maintained. To this end, we look at defining the automaton semantics for the Spatio-Temporal Reach and Escape Logic (STREL), a formal logic designed to express and monitor spatio-temporal requirements over mobile, spatially distributed CPS. Specifically, STREL reasons about spatio-temporal behavior over dynamic weighted graphs. While STREL is endowed with well defined qualitative and quantitative semantics, in this paper, we propose a novel construction of (weighted) alternating finite automata from STREL specifications that efficiently encodes these semantics. Moreover, we demonstrate how this automaton semantics can be used to perform both, offline and online monitoring for STREL specifications using a simulated drone swarm environment. Conference: 28th ACM International Conference on Hybrid Systems: Computation and Control; May 6–9, 2025; Irvine, CA, USA 28th ACM International Conference on Hybrid Systems: Computation and Control (HSCC ’25), May 6–9, 2025, Irvine, CA, USA DOI: 10.1145/3716863.3718033 ISBN: 979-8-4007-1504-4/2025/05 CCS: Computer systems organization Embedded and cyber-physical systems CCS: Theory of computation Modal and temporal logics CCS: Theory of computation Formal languages and automata theory † † cc-license: by 1. Introduction Multi-agent and distributed cyber-physical systems (CPS) are becoming increasingly pervasive in modern society, from IoT networks ( Xu et al., 2018 ; Latif et al., 2022 ; Pivoto et al., 2021 ) , vehicular networks ( Wang et al., 2019 ) , power grids ( Zhu and Hill, 2020 ; Pagani and Aiello, 2013 ) smart cities ( Narayanan et al., 2019 ; Habibzadeh et al., 2019 ; Madakam et al., 2018 ) , drone swarms, to multi-robot configurations used in space exploration ( NASA, 2024 ) . Individual nodes (or agents) in such systems communicate and interact with each other, and the temporal behavior of one node can affect the behavior of other nodes. A common approach to model the behavior of such systems is as a time-varying connectivity graph where individual nodes are considered as stochastic processes evolving in time. As such systems become networked at scale, it has become increasingly important to monitor them to ensure that they perform tasks as expected while satisfying safety constraints. For instance, consider the problem of detecting a real spike (vs. bad sensor data) for a given bus in a power grid. A proposed solution in ( Zhu and Hill, 2020 ) is to compare if some subset of neighboring busses also display the same spike. Monitoring such properties requires reasoning about both the spatial connectivity and temporal behavior of nodes in the underlying graph representation of the system. In systems where agents must coordinate tasks or avoid certain areas, spatial relationships play a critical role, influencing both safety and performance. For instance, in multi-robot systems, agents may need to stay within a specific proximity to maintain communication or avoid obstacles in dynamic environments. Spatio-temporal logics allow designers to specify these constraints and monitor systems to ensure they conform to such requirements. For e.g. in 1 , we have a simulation in the SwarmLab environment ( Soria et al., 2020 ) showing a flock of drones that must navigate through an obstacle-dense environment to reach a central goal. They must avoid obstacles (indicated by the black polygons), while maintaining contact with the ground-stations (indicated by the blue regions). Monitoring such systems requires advanced logic to ensure that agents maintain connectivity, avoid collisions, and achieve goals efficiently. Figure 1 . A spatially distributed system of drones coordinating with each other to “flock” towards a common goal. The drones can have requirements to maintain communications with ground stations (blue circles) either directly or through a flock member. In the CPS context, temporal logics have become a popular tool to describe and monitor for complex spatio-temporal behavior ( Taha et al., 2020 ) . Logics like Metric Temporal Logic ( Koymans, 1990 ; Ouaknine and Worrell, 2005 ; Ouaknine and Worrell, 2008 ) and Signal Temporal Logic ( Deshmukh et al., 2017 ; Bartocci et al., 2022 ) (and their extensions) have been used extensively in this context due to the various quantitative semantics proposed for them ( Haghighi et al., 2019 ) , in addition to their qualitative or Boolean semantics. Recently, there has been a lot of interest in spatio-temporal logics to explicitly reason about the spatial configuration of a system. For example, Signal spatial-temporal logic (SSTL) ( Nenzi and Bortolussi, 2015 ; Nenzi et al., 2015 ) is a modal logic that allows combining temporal modalities with two spatial modalities, one expressing that something is true somewhere nearby and the other capturing the notion of being surrounded by a region that satisfies a given spatio-temporal property. The logic SaSTL ( Ma et al., 2020 ) extends STL by introducing operators that allow spatial aggregation of real-valued quantities at neighbors and spatial counting across sets of agents. The logic SpaTel introduces directional spatial operators by combining STL with the Tree Spatial Superposition Logic ( Aydin-Gol et al., 2014 ) (TSSL) and assumes a fixed topology over the space (for example a checkerboard pattern) ( Haghighi et al., 2015 ) . Most of the aforementioned logics assume static spatial configurations. Of particular relevance to this paper is the logic STREL (Spatio-Temporal Reach and Escape Logic) ( Nenzi et al., 2022 ) . This logic combines STL with two spatial operators: reach and escape which allow reasoning about temporal properties over arbitrary routes in the graph describing the spatial configuration. The interesting aspect of STREL is that it allows reasoning about dynamic spatial configurations, and has been used to model many different kinds of properties such as bike-sharing systems in smart cities, mobile ad hoc networks ( Nenzi et al., 2022 ) , and disease spread during a pandemic ( Mohammadinejad et al., 2021 ) . In the automata theory literature, the connection between logics and automata is well-studied. For example, for every Linear Temporal Logic formula, an equivalent non-deterministic Büchi automaton can be constructed in size exponential in the length of the formula ( Esparza et al., 2022 ) , and can be efficiently constructed ( Pnueli and Zaks, 2008 ) . Similar constructions exist for translating computation tree logic (CTL) to weak Büchi tree automata ( Vardi, 1996 ) , to map metric temporal logic to timed automata ( Alur et al., 1996 ; Maler et al., 2006 ) among others. Curiously, this direction remains unexplored for spatio-temporal logics. In this paper, we present the first such translation from a discrete-time variant of the logic STREL to an alternating finite-state automaton (AFA). In a nondeterministic finite automaton (NFA), the notion of acceptance of a word w is that there exists a path from the initial state that reaches a final state. Consider a state q in the automaton that transitions to one of \{q_{1},q_{2},q_{3}\} upon reading