MAS-DRiVe: A practical approach to decentralized runtime verification of agent interaction protocols

We address the problem of decentralized runtime verification of interaction protocols in multiagent systems by means of MAS-DRiVe, an algorithm for partitioning a multiagent system (MAS) into sub-MASs which can be monitored independently. Given a global interaction protocol named AIP (for "Agent Interaction Protocol") describing all the interactions which can take place in the MAS, the MAS-DRiVe algorithm extracts the interaction graph from AIP, identifies the clusters of agents which cannot be split during the decentralized monitoring as the interactions they are involved in are not independent, collapses each of those clusters into a single node in the interaction graph, and finally partitions the collapsed graph obtained so far. Although the "unsplittable agents identification" stage is still in its early design and prototyping phases and requires a better formalization and a deeper analysis, the MAS-DRiVe algorithm pipeline has been fully implemented and demonstrated on two simple MASs. Once the independently monitorable sub-MASs have been identified by MAS-DRiVe, the global interaction protocol AIP can be projected onto the subsets of agents belonging to each graph partition, thus obtaining local versions of AIP which can be monitored in a decentralized way.