Verifying Emergence of Bounded Time Properties in Probabilistic Swarm Systems

Alessio Lomuscio, Edoardo Pirovano

Abstract

Robotic swarms rely on emergent global behaviors arising from simple local rules. However, verifying these properties for arbitrary swarm sizes is challenging due to the probabilistic nature of agent behavior and the state-space explosion in parameterized systems. This paper presents a formal framework for Emergent Property Identification (EPI) and Emergence Threshold Identification (ETI) in probabilistic swarms. By utilizing an abstraction technique based on action saturation and a mathematical generalization of the Coupon Collector’s Problem, the authors provide a method to determine the minimum population threshold required to guarantee bounded-time properties. Evaluation on an Ant Coverage benchmark demonstrates that the approach can efficiently verify emergence and calculate sufficient population thresholds for various environment scales.

Introduction

Robotic swarms are valued for their robustness and scalability, yet their verification remains a significant hurdle for engineers. Traditional model checking typically requires a fixed number of agents, meaning a proof for a 10-robot swarm does not necessarily hold for an 11-robot swarm. In real-world deployments where robots may fail or be added dynamically, parameterized verification—proving a property holds for any number of robots—is essential.

Furthermore, swarm behavior is often inherently probabilistic (e.g., an agent might turn left with a specific probability). Existing parameterized verification methods often struggle with this complexity. This research addresses these challenges by focusing on bounded-time properties (e.g., "Will the swarm cover the area within $k$ steps?") and identifying the population threshold beyond which a desired property is guaranteed to emerge.

Methods

The proposed framework introduces two primary procedures: Emergent Property Identification (EPI) and Emergence Threshold Identification (ETI).

Probabilistic Semantics and the Abstract Model

The system models a swarm as a "Probabilistic Agent Template" interacting with a deterministic environment. Properties are expressed using a fragment of Probabilistic Computation Tree Logic (PCTL). The core innovation is an abstraction technique based on the "saturation" assumption: in a sufficiently large swarm, any local action possible with non-zero probability will eventually occur. This allows the creation of a single, finite abstract model that represents the "saturated" state of an infinite swarm, making the verification of emergent properties decidable for bounded time horizons.

Threshold Calculation

To determine the specific number of robots needed (the Emergence Threshold), the authors employ a mathematical generalization of the Coupon Collector’s Problem. They calculate the population size required to ensure that all necessary sequences of actions occur with a high enough probability to satisfy the global goal within a specified time. This approach provides a sufficient, though not necessarily minimal, population bound. The algorithms are implemented in a tool called PSV-BD, which extends the PRISM model checker.

Key Results

The framework was evaluated using the Ant Coverage Algorithm, where robots move on an $n \times n$ grid to cover all nodes. The results, summarized in the table below, demonstrate the tool's ability to calculate concrete thresholds and verify emergence across different grid sizes and probability requirements.

Experimental results for the Ant Coverage Algorithm across various grid sizes and probability thresholds.

The EPI procedure, which checks if a property is emergent, proved highly efficient, typically completing in approximately 2 seconds regardless of the grid size. In contrast, the ETI procedure for calculating thresholds is more computationally intensive. For a $3 \times 3$ grid, calculating the threshold for a 95% probability of coverage within 7 steps (threshold = 38) took 2.3 seconds. However, for a $5 \times 5$ grid with the same probability (threshold = 145), the computation time increased to 81 seconds. For a $10 \times 10$ grid, the ETI procedure timed out, highlighting scaling challenges for the numerical solvers used in threshold identification.

Discussion and Future Work

While the framework successfully provides formal guarantees for probabilistic swarms, several limitations remain. Currently, the method is restricted to bounded-time properties and cannot prove "liveness" properties (events that will eventually happen without a fixed deadline). Additionally, the evaluation focused on homogeneous swarms; extending the mathematical foundations to heterogeneous systems is a key area for future research.

Future work will also focus on optimizing the numerical solvers to prevent timeouts in larger environments and refining the algorithms to identify minimal thresholds rather than just sufficient upper bounds. Despite these limitations, this research represents a significant step toward providing rigorous safety and performance guarantees for autonomous robotic swarms.

Summary updated

Abstract

We introduce a parameterised semantics for reasoning about swarms as unbounded collections of agents in a probabilistic setting. We develop a method for the formal identification of emergent properties, expressed in a fragment of the probabilistic logic PCTL. We introduce algorithms for solving the related decision problems and show their correctness. We present an implementation and evaluate its performance on an ant coverage algorithm.
BibTeX
@inproceedings{lomuscio2018verifying,
  author = {Alessio Lomuscio and Edoardo Pirovano},
  title = {{Verifying Emergence of Bounded Time Properties in Probabilistic Swarm Systems}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2018},
  doi = {10.24963/ijcai.2018/56},
}
Figure