Verifying Fault-Tolerance in Probabilistic Swarm Systems

Alessio Lomuscio, Edoardo Pirovano

Introduction

Swarm robotics offers significant potential for applications in search-and-rescue, logistics, and manufacturing. However, ensuring the reliability of these systems in safety-critical environments remains a challenge due to two primary factors: the scalability gap and the inherent uncertainty of real-world operations. Traditional model checking is often limited to a fixed number of components, making it difficult to reason about "unbounded" swarms where the number of agents is unknown at design time. Furthermore, existing tools struggle to account for probabilistic behaviors combined with runtime malfunctions, or faults.

This research introduces a formal framework to bridge this gap, allowing designers to mathematically verify whether a swarm protocol remains resilient when a portion of its members fail. By "injecting" faults into agent templates and using a specialized model-checking procedure, the framework can prove whether a swarm remains resilient even when members malfunction.

Methodology: Fault Injection and Verification

The authors extend the Probabilistic Parameterised Interleaved Interpreted Systems (PPIIS) framework to incorporate fault-tolerance. Central to this approach is the definition of a Fault Profile ($\chi$), which specifies the probability of various malfunctions occurring during specific agent actions, such as sensor failures or motor stalls.

A key innovation is the automatic transformation of "clean" agent models into "faulty" ones. To model a mixed population of healthy and malfunctioning robots, the framework uses a specialized initialization phase. As shown in Figure 1, each agent starts by probabilistically transitioning into either a normal ($l_n$) or faulty ($l_f$) state based on a parameter $p$. This allows the verifier to reason about the collective behavior of a mixed population.

Figure 1: The agent template and environment models showing the probabilistic initialization into normal or faulty states.

The verification process is implemented in a Java-based toolkit called PSV-F, which leverages the PRISM model checker. By using abstraction techniques, PSV-F reduces the infinite-agent problem into a solvable decision procedure, termed the Parameterised Fault-Tolerance Problem (PFTP). This procedure checks if a probabilistic specification, written in a variant of Linear-time Temporal Logic (LTL), holds for a swarm of any size $n$.

Experimental Evaluation

The framework was evaluated using the Swarm Foraging Protocol, a standard benchmark where robots transition between resting, searching for food, and returning to a nest. The authors injected a fault where robots have a probability $p_f$ of dropping food while returning. The verification goal was to determine the probability that at least two units of food reach the nest within $k$ time steps.

Results and Discussion

The analysis produced "resilience curves" that quantify how swarm performance degrades under various fault conditions. As illustrated in Figure 2, the success probability $p$ increases with the number of time steps $k$, demonstrating the inherent redundancy and eventual recoverability of the swarm.

Figure 2: Resilience curves showing the probability of goal achievement over time for different individual fault probabilities ($p_f$).

Key findings include:

  • Redundancy and Time: Swarms can often achieve their goals even with a high percentage of faulty agents, provided they are given sufficient time ($k$ steps). This quantifies the inherent robustness of decentralized systems.
  • Critical Thresholds: Certain fault probabilities (e.g., $p_f = 1$, where robots always drop food) render goals impossible, identifying clear limits to swarm resilience.
  • Computational Efficiency: Despite the theoretical complexity, the PSV-F tool efficiently handled models with 2 million states and 46 million transitions, completing verification in seconds after model construction.

Conclusion

This work provides the first formal framework for verifying fault-tolerance in unbounded probabilistic swarms. While the general problem remains theoretically undecidable, the proposed decision procedure offers a practical and efficient means of quantifying swarm resilience. Future research will focus on handling multiple concurrent faults per agent and applying the framework to a broader range of complex swarm protocols beyond foraging.

Summary updated

Abstract

We present a method for reasoning about fault-tolerance in unbounded robotic swarms. We introduce a novel semantics that accounts for the probabilistic nature of both the swarm and possible malfunctions, as well as the unbounded nature of swarm systems. We define and interpret a variant of probabilistic linear-time temporal logic on the resulting executions, including those arising from faulty behaviour by some of the agents in the swarm. We specify the decision problem of parameterised fault-tolerance, which concerns determining whether a probabilistic specification holds under possibly faulty behaviour. We outline a verification procedure that we implement and use to study a foraging protocol from swarm robotics, and report the experimental results obtained.
BibTeX
@inproceedings{lomuscio2020verifying,
  author = {Alessio Lomuscio and Edoardo Pirovano},
  title = {{Verifying Fault-Tolerance in Probabilistic Swarm Systems}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2020},
  doi = {10.24963/ijcai.2020/46},
}
Figure