Meir Kalech, Gal A.
With increasing deployment of multi-agent and distributed systems, there is an increasing need for failure diagnosis systems. While successfully tackling key challenges in multi-agent settings, model-based diagnosis has left open the diagnosis of coordination failures, where failures often lie in the boundaries between agents, and thus the inputs to the model - with which the diagnoser simulates the system to detect discrepancies - are not known. However, it is possible to diagnose such failures using a model of the coordination between agents. This paper formalizes model-based coordination diagnosis, using two coordination primitives (concurrence and mutual exclusion). We define the consistency-based and abductive diagnosis problems within this formalization, and show that both are NP-Hard by mapping them to other known problems.
Subjects: 1.5 Diagnosis; 7.1 Multi-Agent Systems
Content Area: 1. Agents/Multiagent Systems
Submitted: May 10, 2005