Reference: Murdock, L. Model-Matching and Individuation for Model-Based Diagnosis. Ph.D Thesis, Stanford University, 1995.
Abstract: In model-based systems that reason about the physical world, models must be matched to portions of the physical system. To make model-based reasoning and diagnosis systems more readily extensible and re-usable, this thesis explores automating model matching. If matching is automated, one can add a model without specifying every place in the physical equipment where it can be used. One can apply the system to new equipment without identifying every place that every model may be used. However, models address particular {\em individuals}, portions of the physical world identified as separate entities. If the set of models is not fixed, one cannot carve the physical system into a fixed set of individuals. Our goals are to develop methods for individuating and matching models and to identify characteristics of physical equipment that must made explicit for those methods. Our investigation involves three steps. First we explore examples of engineering models applied to physical systems found in textbooks or in manufacturing equipment to identify relevant characteristics. Second, we implement matching methods using the characteristics. Third, we test re-usability and extensibility. If the system can correctly define individuals and match some models, even when models call for individuals not previously defined, then we can conclude that we have identified some subset of the characteristics required to automate model matching. The first step of the investigation revealed that a number of models used in the domain of fluid processing and chemical manufacturing do not correspond to {\em components} such as valves, tanks, or pumps. Many principles apply to regions containing particular materials or phases, or having particular parameter values. An example is the Ideal Gas Law, which applies to any volume of space occupied by molecules in the gas phase. Individuals for these kinds of models cannot be identified in advance because there are too many possible individuals. Previous model-based diagnosis work assumes the set of individuals is given and fixed. This assumption excludes real world diagnosis problems where models like the Ideal Gas Law are required. Identification of this class of models also shows that run-time individuation is required to solve certain kinds of problems. We develop two matching and two reconfiguration algorithms which use descriptions of the space occupied by the equipment and the space required by models to reconfigure individuals at run-time. Two series of equipment description replacements demonstrate re-usability. Each equipment description in a series has content to match the same model, but had represented as different individuals. Two series of model additions demonstrate extensibility. In each series, the equipment description remains constant, and the added models' individuals vary. The system correctly reconfigures and matches in all cases. We conclude that the 3-dimensional space occupied by the equipment and required by the models along with the distribution of phases, materials, and functional components within that space are required for model matching. The locations and spatial extents of parameters are also required.
Notes: Also STAN-CS-TR-95-1540 February.