Diagnosis of coordination failures: a matrix-based approach

One of the key requirements in many multi-agent teams is that agents coordinate specific aspects of their joint task. Unfortunately, this coordination may fail due to intermittent faults in sensor readings, communication faults, etc. A key challenge in the model-based diagnosis (MBD) of coordination failures is to represent a model of the coordination among the agents in a way that allows efficient detection and diagnosis, based on observation of the agents involved. Previously developed mechanisms are useful only for small groups of agents, since they represent the coordination with binary constraints. This paper presents a MBD approach to coordination failures in which non-binary constraints are allowed. This model has two inherent advantages: (1) the model enables to address real problems, (2) the model enables to address large groups by gathering multiple coordinations in one constraint. To solve the diagnosis problem, we propose a matrix-based approach to represent the basic building blocks of the MBD formalization. Theoretical and empirical evaluations show that this representation is efficient for large-scale teams.