STL-GO: Spatio-Temporal Logic with Graph Operators for Distributed Systems with Multiple Network Topologies
Open Access
- 26 September 2025
- journal article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Embedded Computing Systems
- Vol. 24 (5s) , 1-23
Abstract
Multi-agent systems (MASs) consisting of a number of autonomous agents that communicate, coordinate, and jointly sense the environment to achieve complex missions can be found in a variety of applications such as robotics, smart cities, and internet-of-things applications. Modeling and monitoring MAS requirements to guarantee overall mission objectives, safety, and reliability is an important problem. Such requirements implicitly require reasoning about diverse sensing and communication modalities between agents, analysis of the dependencies between agent tasks, and the spatial or virtual distance between agents. To capture such rich MAS requirements, we model agent interactions via multiple directed graphs, and introduce a new logic – Spatio-Temporal Logic with Graph Operators (STL-GO). The key innovation in STL-GO are graph operators that enable us to reason about the number of agents along either the incoming or outgoing edges of the underlying interaction graph that satisfy a given property of interest; for example, the requirement that an agent should sense at least two neighboring agents whose task graphs indicate the ability to collaborate. We then propose novel distributed monitoring conditions for individual agents that use only local information to determine whether or not an STL-GO specification is satisfied. We compare the expressivity of STL-GO against existing spatio-temporal logic formalisms, and demonstrate the utility of STL-GO and our distributed monitors in a bike-sharing and a multi-drone case study.Keywords
All Related Versions
Funding Information
- National Science Foundation (CAREER award (SHF-2048094), CNS-1932620, CNS-2039087, FMitF-1837131, CCF-SHF-1932620, IIS-SLES-2417075)
- Toyota R&D and Siemens Corporate Research through the USC Center for Autonomy and AI, an Amazon Faculty Research Award
- Airbus Institute for Engineering Research
This publication has 45 references indexed in Scilit:
- Predicate monitoring in distributed cyber-physical systemsInternational Journal on Software Tools for Technology Transfer, 2023
- Online Causation Monitoring of Signal Temporal Logic2023
- Optimal time trajectory and coordination for connected and automated vehiclesAutomatica, 2021
- Robust online monitoring of signal temporal logicFormal Methods in System Design, 2017
- Safe Autonomy Under Perception Uncertainty Using Chance-Constrained Temporal LogicJournal of Automated Reasoning, 2017
- On the succinctness of some modal logicsArtificial Intelligence, 2013
- Multi-robot deployment and coordination with Embedded Graph GrammarsAutonomous Robots, 2008
- Monitoring Temporal Properties of Continuous Signals2004
- Reasoning with Temporal Logic on Truncated Paths2003
- Application of multi-agent systems in traffic and transportationIEE Proceedings - Software Engineering, 1997