This paper presents a model-based approach to diagnosis of hybrid systems. We have developed a combined qualitative-quantitative diagnosis scheme that uses hybrid models of the system and a model of the supervisory controller. By applying the supervisory controller model to diagnostic analysis we significantly cut down on the complexity in tracking behaviors, and in generating and refining hypotheses across discrete mode changes in the system behavior. We present the algorithms for hybrid diagnosis: hypotheses generation by back propagation, and hypotheses refinement by forward propagation and parameter estimation. Example scenarios demonstrate the effectiveness of this approach.
This paper proposes a clustering methodology, for sequence data, using hidden Markov model (HMM) representation. The proposed methodology improves upon existing HMM-based clustering methods in two ways: (i) it enables HMMs to dynamically change its model structure, to obtain a better fit model for data during the clustering process, and (ii) it provides objective criterion function, to select the optimal clustering partition. The algorithm is presented in terms of four nested levels of searches: (i) the search for the optimal number of clusters in a partition, (ii) the search for the optimal structure for a given partition, (iii) the search for the optimal HMM structure for each cluster, and (iv) the search for the optimal HMM parameters for each HMM. Preliminary results are given to support the proposed methodology.
This work has been developed within the framework of agent- based decentralized scheduling for flexible manufacturing systems. In this framework, all workcells comprising the manufacturing system, and the products to be generated, are modeled via intelligent software agents. These agents interact dynamically using a bidding production reservation (BPRS) scheme, based on the Contract Net Protocol, to devise the production schedule for each product unit. Simulation studies of a job shop have demonstrated the gains in performance achieved by this approach over heuristic dispatching rules commonly used in industry. Manufacturing environments are also prone to operational uncertainties such as variations in processing times and machine breakdowns. In order to cope with these uncertainties, the BPRS algorithm has been extended for dynamic rescheduling to also occur in a fully decentralized manner. The resulting multi-agent rescheduling scheme results in decentralized control of flexible manufacturing systems that are capable of responding dynamically to such operational uncertainties, thereby enhancing the robustness and fault tolerance of the proposed scheduling approach. This paper also presents the effects of the proposed agent-based decentralized scheduling approach on the performance of the underlying flexible manufacturing system under a variety of production and scheduling scenarios, including forward and backward scheduling. Future directions for this work include applying the proposed scheduling approach to other advanced manufacturing areas such as agile and holonic manufacturing.
Manufacturing is currently undergoing a revolutionary transition with focus shifting from mass production to mass customization. This trend motivates a new generation of advanced manufacturing systems that can dynamically respond to customer orders and changing production environments. It is becoming increasingly important to develop control architectures that are modifiable, extensible, reconfigurable, adaptable, and fault tolerant. Heterarchical control structures, made up of multiple, distributed, locally autonomous entities, provide this kind of control. Our research focus is on efficient and effective scheduling and routing methodologies that can be applied to heterarchically controlled manufacturing processes. The Contract-Net based scheduling approach, developed in distributed artificial intelligence (DAI), adopts a multi-agent cooperative problem- solving paradigm based on bidding and negotiation mechanisms to implement production plans as distributed and localized schedules for individual workstations. This paper discusses a Contract-Net based scheduling algorithm in a realistic manufacturing testbed, a model induction motor assembly plant. This testbed, developed as part of the HMS project, is a typical example of low-volume, high-variety production facility, and it highlights many of the problems that arise from the inflexibility of centralized management system architectures.
This paper discusses DOC, an efficient method for diagnosis of continuous systems based on qualitative analysis of an analytic constraint equation model of the system. Starting with equations that relate observations (measurements of parameter values) of a system to its individual components, the system first generates a diagnosis model based on partial explanations of the associated measurement parameters. Partial explanations are generated by qualitative causal analysis of the given constraint equations. These relations are then exploited for effective candidate generation and measurement selection when multiple candidates are generated. A method for analyzing systems with complex feedback loops is also presented. DOC has been successfully applied to diagnosing faults in the Space Station Thermal Bus system.
This paper discusses the application of a conceptual clustering algorithm called ITERATE to improve complex problem solving. More specifically, we apply the ITERATE system to build a hierarchy of rule models from sets of rules defined for PLAYMAKER, an expert system for characterizing hydrocarbon fields and plays in terms of their essential geological characteristics for the purposes of prospect analysis. PLAYMAKER is built on MIDST, an expert system shell that employs task-specific reasoning structures. The rule model hierarchy derived by ITERATE is then used with the task-specific reasoning structures to develop a more efficient and focused reasoning mechanism. A set of case studies were conducted to demonstrate the improved performance of the reasoning system.
This paper develops a qualitative reasoning methodology for problem solving at multiple levels of abstraction. The goal is to address two important control issues in the behavior generation process: (i) the selection problem, which deals with the right level of detail to solve a problem, and (ii) the efficiency problem, which deals with information transfer from higher levels of abstraction to focus problem solving at more detailed levels. The CMOS digital circuit domain is used as a test bed to illustrate the methodologies developed.
A variety of problems must be overcome for a system that learns from examples to be useful. Such problems include reducing the dependency on the order of presented examples; reducing the number of examples required to learn a concept; pruning the generalization space; handling both conjunctive and disjunctive concept descriptions; and dealing with noisy training instances. This paper presents a system that effectively deals with many of these problems in a real-world domain by actively participating in the example selection process
This paper discusses the design and implementation of PLAYMAKER: a knowledge base system for characterizing hydrocarbon plays. PLAYMAKER is a component of XX (eXpert eXplorer), a workstation-based tool that aids exploration geologists in a number of different tasks: sediment and carbonates simulation, play and field characterization, retrieval and storage of information in a geological database, comparison of play or field under study with other fields in the database, and report generation. PLAYMAKER is implemented using MIDST (Mixed Inferencing Dempster Shafer Tool), a rule-based expert system shell that incorporates mixed-iniative reasoning and inexact reasoning based on the Dempster-Shafer evidence combination scheme. This paper discusses the effectiveness of a two-level knowledge base structure adopted for the design and implementation of PLAYMAKER.
Diagnostic problem solving is a major application area of knowledge-based system research. However, most of the current approaches, both heuristic and model-based, are designed to identify single faults, and do not generalize easily to multiple fault diagnosis without exhibiting exponential behavior in the amount of computation required. In this paper, we employ a decomposition approach based on system configuration to generate an efficient algorithm for multiple fault diagnosis. The basic idea of the algorithm is to reduce the inherent combinatorial explosion that occurs in generating multiple faults by partitioning the circuit into groups that correspond to output measurement points. Rules are developed for combining candidates from individual groups, and forming consistent sets of minimal candidates.