Verifying Fault-tolerance in Parameterised Multi-Agent Systems

Verifying Fault-tolerance in Parameterised Multi-Agent Systems

Panagiotis Kouvaros, Alessio Lomuscio

Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence
Main track. Pages 288-294. https://doi.org/10.24963/ijcai.2017/41

We develop a technique to evaluate the fault-tolerance of a multi-agent system whose number of agents is unknown at design time. We present a method for injecting a variety of non-ideal behaviours, or faults, studied in the safety-analysis literature into the abstract agent templates that are used to generate an unbounded family of multi-agent systems with different sizes. We define the parameterised fault-tolerance problem as the decision problem of establishing whether any concrete system, in which the ratio of faulty versus non-faulty agents is under a given threshold, satisfies a given temporal-epistemic specification. We put forward a sound and complete technique for solving the problem for the semantical set-up considered. We present an implementation and a case study identifying the threshold under which the alpha swarm aggregation algorithm is robust to faults against its temporal-epistemic specifications.
Keywords:
Agent-based and Multi-agent Systems: Formal verification, validation and synthesis
Multidisciplinary Topics and Applications: Validation and Verification