Automatic Verification of Parameterised Interleaved Multi-Agent Systems

Abstract

A key problem in verification of multi-agent systems by model checking concerns the fact that the state-space of the system grows exponentially with the number of agents present. This makes practical model checking unfeasible whenever the system contains more than a few agents. In this paper we put forward a technique to establish a cutoff result, thereby showing that all systems of arbitrary number of agents can be verified by model checking a single system containing a number of agents equal to the cutoff of the system. While this problem is undecidable in general, we here define a class of parameterised interpreted systems and a parameterised temporal-epistemic logic for which the result can be shown. We exemplify the theoretical results on a robotic example and present an implementation of the technique on top of mcmas, an open-source model checker for multi-agent systems.

8 pages with 1 figure; Published in the Proceedings of the 12th International Conference on Autonomous Agents and Multi-Agent systems (AAMAS13). Saint Paul, MN, USA