CABS-colloquium 2002

Titel
Multi-Agent Diagnosis

Spreker:
Nico Roos, IKAT, Universiteit van Maastricht.

Datum/Tijd:
vrijdag 26 april 15.30 uur

Plaats:
Vergaderzaal 9e etage, gebouw ITS, Faculteit ITS, Mekelweg 4, Delft



Abstract
In a large dynamical system, it is often infeasible or even
impossible to maintain a single model of the whole system.
Instead, several incomplete models of the system have to be used
to detect possible faults. These models may also be physically
distributed.

A Multi-Agent System of diagnostic agents may offer solutions for
establishing a global diagnosis of such distributed systems. If we
use a separate agent for each incomplete model of the system,
establishing a global diagnosis becomes a problem of cooperation
and negotiation between the diagnostic agents. This raises the
question whether `a set of diagnostic agents, each having an
incomplete model of the system, can (efficiently) determine the
same global diagnosis as an ideal single diagnostic agent having
the combined knowledge of the diagnostic agents?'

The answer on the above question dependents on how knowledge is
distributed over the agent. We distinguish two principle ways of
distributing knowledge; (1) spatially distributed: knowledge of
system behavior is distributed over the agents according the
spatial distribution of the system's components, and (2)
semantically distributed: knowledge of system behavior is
distributed over the agents according to the type of knowledge.

Assuming that agents can make local diagnoses in polynomial time,
the agents can efficiently establish a common diagnosis when
knowledge is semantically distributed. Protocols for establishing
the common diagnoses will be presented. When knowledge is
spatially distributed however, establishing a global diagnosis of
the whole system turns out to be an NP-hard problem in general.
Hence, in large distributed systems, the agents must use protocols
that exchange diagnostic precision for a low time complexity and
low communication overhead. Such a protocol will be presented.