A Study of Dynamic Coordination Mechanisms
Avi Rosenfeld · The Knowledge Engineering Review · 2009
With increasing deployment of multiple agents in complex, dynamic settings, there is an increasing need to respond to failures that occur in the agents' coordination.In particular, there is need to detect and diagnose coordination failures-failures to maintain relationships between agents.We refer to this type of diagnosis as social diagnosis.Previous approaches to diagnosis in multi-agent settings have either ignored failures in coordination, or utilized heuristic approaches, which do not scale up as the number of agents (and their interactions) increases.This dissertation offers a comprehensive and principled approach to social diagnosis.We use a model-based diagnosis (MBD) approach.Here, a model of a diagnosed system is used to simulate the behavior of the system given the operational context (typically, the system's inputs), and to pinpoint possible failing components within the system.MBD has been difficult to apply to diagnosing coordination failures, because of the challenges in constructing a model of coordination, and the lack of appropriate (scalable) diagnosis algorithms.In the first part of this dissertation, we formally show how to construct a model of agent coordination, and use it to formally define the two key variant social diagnosis problems: the Consistency-based diagnosis problem, and the abductive diagnosis problem.We show that these are NP-Hard problems.We then build on known methods in constraint-satisfaction problems, to provide several algorithms for social diagnosis in centralized and distributed settings.The algorithmswhose analytical guarantees vary in terms of completeness and correctness-are evaluated empirically, in experiments carried out with teams