Autonomous, Model-based Diagnosis Agents

Michael Schroeder

"Self modeling and self configuration, coordinating autonomic functions through symbolic reasoning, and compositional, model-based programming are the three key elements of a model-based autonomous systems architecture that is taking us into the New Millennium."

Williams and Nayak, AI Magazine, 1996

In this thesis we set out to define and implement such an architecture for autonomous, model-based diagnosis agents. We first develop a logic programming approach for model-based diagnosis and introduce strategies to deal with more complex diagnosis problems. Then we embed the diagnosis framework into the agent architecture of vivid agents.

First, we survey extended logic programming and show how this expressive language is used to model diagnosis problems stemming from applications such as digital circuits, traffic control, integrity checking of a chemical database, alarm-correlation in cellular phone networks, diagnosis of an automatic mirror furnace, and diagnosis of communication protocols. To compute diagnoses we review a bottom-up algorithm to remove contradictions from extended logic programs and substantially improve it by top-down evaluation of extended logic programs. Both algorithms are evaluated in the circuit domain including some of the ISCAS85 benchmark circuits.

To deal with complex diagnosis problems we lift the idea of model-based diagnosis to the meta-level of the diagnostic process and define a strategy language that allows a declarative description of the diagnostic process. Taking into account both practical needs and rigorous formal treatment, we define syntax and declarative and operational semantics of the strategy language. With the concept of deterministic and non-deterministic as well as monotonic and non-monotonic strategies, we design a strategy knowledge base for circuit diagnosis with strategies for structural refinement, choice of models, measurements, and preferences. We evaluate the knowledge base and the algorithm on a voter circuit which is part of the benchmark circuits.

Based on the inference engine lined out above we turn to the autonomous agent's behaviour specification. We present the concept of vivid agents which comprise a vivid knowledge system and reaction and action rules to specify the agent's reactive and pro-active behaviour. To realise vivid agents we develop an architecture for concurrent action and planning. For implementation we use PVM-Prolog that provides coarse-grain parallelism to spawn agents in a network and fine-grain parallelism to run action and planning component concurrently. The interpreter is evaluated in distributed diagnosis where we implement fault-tolerant diagnosis and diagnosis of a communication protocol. The agent interpreter satisfies the requirements for a state-of-the-art multi-agent programming language: it supports reactive and pro-active behaviour specification; the specifications are executable; the language has a formal semantics; the modular design facilitates plug and play according to the problem domain; the system is open to heterogeneous agents based on other concepts and languages.