SMT-based Safety Checking of Parameterized Multi-Agent Systems

Paolo Felli, Alessandro Gianola, Marco MontaliAAAI 2021 · DOI

Introduction

In modern distributed environments—ranging from robotic swarms and Industry 4.0 factories to cloud computing infrastructures—systems are increasingly designed with a "parameterized" nature. A Parameterized Multi-Agent System (PMAS) is one where the number of interacting agents is unknown at design time and potentially unbounded at runtime. Traditional model checking techniques, which typically verify a system for a fixed number of agents, are insufficient; proving a system safe for five robots does not guarantee its safety for five hundred. This paper introduces a novel framework to bridge the gap between multi-agent systems research and infinite-state model checking by encoding PMAS into Array-Based Systems (ABS).

Formalizing PMAS as Array-Based Systems

The core technical contribution of this work is a mapping from PMAS to Array-Based Systems. In this paradigm, the collective state of the system is represented using first-order logic and arrays. Agents follow "templates" (behavioral blueprints), and their internal states are stored in arrays where the index corresponds to a unique agent ID. This allows the system to be described symbolically: one can reason about "some agent $j$" without needing to specify the total number of agents.

Encoding PMAS into Array-Based Systems (ABS). The state of agents is represented as values in arrays indexed by agent ID $j$, while the environment is captured in separate arrays.

As shown in the figure above, the system state is partitioned into agent-specific arrays ($arr$) and environment arrays ($env$). The index $j$ serves as a pointer to a specific agent's state within the global configuration. This encoding enables the use of Satisfiability Modulo Theories (SMT) solvers to handle the infinite state space inherent in parameterized systems.

Verification via SMT-Based Backward Reachability

To verify safety properties, the authors employ a backward reachability search. Starting from a defined "bad state" (an unsafe configuration), the algorithm works backward through transition rules to determine if an initial state is reachable. If the search terminates without reaching an initial state, the system is proven safe for any number of agents.

This approach is implemented in a tool called SAFE, which serves as a front-end for MCMT, a state-of-the-art SMT-based model checker. By leveraging solvers like Z3 and Yices, SAFE can efficiently navigate the symbolic state space of complex agent protocols.

Theoretical Guarantees and the Locality Condition

A significant challenge in infinite-state verification is ensuring the algorithm terminates. The authors identify a critical "locality condition": if agent protocols primarily check their own internal state and do not perform complex comparisons between the variables of different agents, the safety check is guaranteed to terminate.

The paper provides formal proofs for:

  • Soundness: If the tool reports a system is safe, it is guaranteed to be safe for any number of agents.
  • Completeness: If a safety violation exists, the algorithm will eventually find a counter-example.
  • Decidability: For "local" PMAS, the safety problem is decidable, meaning the algorithm will always provide a definitive answer in finite time.

Case Study: Robotic Swarm

The framework was evaluated using a robotic swarm scenario where an unbounded number of robots navigate rooms to reach a goal while avoiding a security system (an EMP pulse). The SAFE tool successfully identified a witness of unsafety (a counter-example) in under 2.5 minutes. The generated model involved 501 lines of code and 15 transition formulae, demonstrating the scalability of the symbolic approach compared to traditional "cutoff" methods that require pre-calculating agent bounds.

Conclusion and Future Work

This research provides a robust, declarative framework for the formal verification of parameterized systems. While the current work focuses on interleaved execution (where agents move sequentially), future extensions aim to address synchronous systems where agents move simultaneously. Additionally, the authors plan to expand the framework to handle "data-aware" agents that interact with complex relational databases and to explore strategic reasoning beyond simple safety properties.

Summary updated

BibTeX
@inproceedings{felli2021smt,
  author = {Paolo Felli and Alessandro Gianola and Marco Montali},
  title = {{SMT-based Safety Checking of Parameterized Multi-Agent Systems}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2021},
  doi = {10.1609/aaai.v35i7.16785},
}
Figure