Towards a formal account of diagnostic problem solving

grantor: University of TorontoAutomated diagnosis has long been a problem of interest to the artificial intelligence community. To the practitioner, artificial intelligence holds the promise of addressing difficult problems in automated diagnostic problem solving. To the formalist, diagnostic problem solving embodies many of the fundamental challenges of artificial intelligence within a broad range of application domains. This thesis investigates formal representation and reasoning issues that underlie diagnostic problem solving. We assert that an investigation of diagnostic problem solving must address testing and repairing, in addition to the task of diagnosis. Further, we argue that a comprehensive account of diagnostic problem solving requires reasoning about action and change. Providing such an account presents at least two fundamental challenges: first, a knowledge representation scheme must be devised to capture the interrelationship between actions and the state and behaviour of a system; second, formal characterization of the tasks involved in diagnostic problem solving must be defined. This thesis proposes the predicate calculus and the situation calculus as logical languages for explicating the representation and reasoning issues involved in diagnostic problem solving. Using the language of the situation calculus, we propose a knowledge representation scheme that enables us to integrate a representation of actions with the representation of the behaviour of a static system. In doing so, we provide a semantically justified closed-form solution to the frame and ramification problems for a class of state constraints that occurs commonly in many application domains. With a representation in hand, we present a logical characterization of the task of diagnosis for behaviourally static systems whose state can be affected by actions which occur in the world. Integrating a theory of action into our representation provides for a broad definition of diagnosis. In addition to conjecturing what is wrong with a system, we employ actions both as observations to project what may be wrong with a system, and as diagnoses to explain what happened to cause observed behaviour. In diagnostic problem solving, testing is required to discriminate a space of candidate diagnoses. Using the language of the predicate calculus we study formal issues related to testing, including test design, test generation and the conclusions that can be drawn from the outcome of a test. Finally, we introduce the problem of achieving tests and repairs, characterizing these tasks as instances of the planning problem in the language of the situation calculus.Ph.D