Optimizing real-time equational rule-based systems

Analyzing and reducing the execution-time upper bound of real-time rule-based expert systems is a very important task because of the stringent timing constraints imposed on this class of systems. We present a new runtime optimization to reduce the execution-time upper bound of real-time rule-based expert systems. In order to determine rules to be evaluated at runtime, a predicate dependency list, which consists of a predicate, its active rule set and corresponding inactive rule set, is created for each predicate in a real-time rule-based program. Based on the predicate dependency list and the current value of each variable, the new runtime optimization dynamically selects rules to be evaluated at runtime. For the timing analysis of the proposed algorithm, we introduce a predicate-based rule dependency graph, a predicate-based enable-rule graph, and their construction algorithm. We also discuss the bounded time of the equational logic rule-based program using the predicate-based rule dependency graph as well as the predicate-based enable-rule graph. The implementation and performance evaluation of the proposed algorithm using both synthetic and practical real-time rule-base programs are also presented. The performance evaluation shows that the runtime optimizer reduces the number of rule evaluations and predicate evaluations as well as the response time upper bound significantly, and the new algorithm yields better execution-time upper bound compared to other optimization methods.     

Overcoming deficiencies of the rule-based medical expert system

One of the current deficiencies of the rule-based expert system is its static nature. As these systems are applied to medicine, this shortcoming becomes accentuated by: the rapid speed at which new knowledge is generated, the regional differences associated with the expression of many diseases, and the rate at which patient demographics and disease incidence change over time. This research presents a solution to the static nature of the rule-based expert system by proposing a hybrid system. This system consists of an expert system and a statistical analysis system linked to a patient database. The additional feature of a rule base manager which initiates automatic database analysis to refresh the statistical correlation of each rule ensures a dynamic, current, statistically accurate rule base. The philosophical differences between data and knowledge are also addressed as they apply to this type of hybrid system. The system is then used to generate four rule bases from different knowledge sources. These rule bases are then compared.     

An integrated system for knowledge sharing among heterogeneous knowledge derivation systems

Solving problems in a complex application domain often requires a seamles integration of some existing knowledge derivation systems which have been independently developed for solving subproblems using different inferencing schemes. This paper presents the design and implementation of an Integrated Knowledge Derivation System (IKDS) which allows the user to query against a global database containing data derivable by the rules and constraints of a number of cooperative heterogeneous systems. The global knowledge representation scheme, the global knowledge manipulation language and the global knowledge processing mechanism of IKDS are described in detail. For global knowledge representation, the dynamic aspects of knowledge such as derivational relationships and restrictive dependencies among data items are modeled by a Function Graph to uniformly represent the capabilities (or knowledge) of the rule-based systems, while the usual static aspects such as data items and their structural interrelationships are modeled by an object-oriented model. For knowledge manipulation, three types of high-level, exploratory queries are introduced to allow the user to query the global knowledge base. For deriving the best global answers for queries, the global knowledge processing mechanism allows the rules and constraints in different component systems to be indiscriminately exploited despite the incompatibilities in their inferencing mechanisms and interpretation schemes. Several key algorithms required for the knowledge processing mechanism are described in this paper. The main advantage of this integration approach is that rules and constraints can in effect be shared among heterogeneous rule-based systems so that they can freely exchange their data and operate as parts of a single system. IKDS achieves the integration at the rule level instead of at the system level. It has been implemented in C running in a network of heterogenous component systems which contain three independently developed expert systems with different rule formats and inferencing mechanisms.Database Systems Research and Development Center, Department of Computer Information Sciences, Department of Electrical Engineering, University of Florida     

Shortening matching time in OPS5 production systems

A rule-based system must satisfy stringent timing constraints when applied to a real-time environment. As the scale of rule-based expert systems increases, the efficiency of systems becomes a pressing concern. The most critical performance factor in the implementation of a production system is the condition-testing algorithm. We propose a new method based on the widely used RETE match algorithm. We show an approach designed to reduce the response time of rule-based expert systems by reducing the matching time. There are two steps in the method we propose: The first makes an index structure of the tokens to reduce the /spl alpha/-node-level join candidates. The second chooses the highest time tag for certain /spl beta/-nodes to reduce the amount of combinatorial match that is problematical in a real-time production system application. For this purpose, a simple compiler is implemented in C and the response time of test programs is measured.     

A Rule-based Extension to the C++ Language

In rule-based systems, sets of rules are applied to known information to generate new, consequential information. The majority of the large number of existing systems¹ has been produced with the objective of ease of use, enforcing an English-like syntax in the rules and hiding the control methods from the developer. The method adopted in the current work aims to provide rule-based facilities while maintaining the flexibility and implementation efficiency of a conventional language. This is achieved by extending the features of C++ to permit the development of rule-based systems whose control is decided by the developer. The design can be tailored to the application unrestricted by the normal constraints of the rule-based system, and a framework is made available for the development of multiple expert systems for use in blackboard system applications. This paper describes the approach adopted in the current work, the operation of the system and describes two example implementations. © 1997 John Wiley & Sons, Ltd.     

Optimization of rule-based systems using state space graphs

Embedded rule-based expert systems must satisfy stringent timing constraints when applied to real-time environments. The paper describes a novel approach to reduce the response time of rule-based expert systems. The optimization method is based on a construction of the reduced cycle-free finite state space graph. In contrast with traditional state space graph derivation, the optimization algorithm starts from the final states (fixed points) and gradually expands the state space graph until all of the states with a reachable fixed point are found. The new and optimized system is then synthesized from the constructed state space graph. The authors present several algorithms implementing the optimization method. They vary in complexity as well as in the usage of concurrency and state-equivalency-both targeted toward minimizing the size of the optimized state space graph. Though depending on the algorithm used, optimized rule-based systems: (1) in general have better response time in that they require fewer rule firings to reach the fixed point; (2) are stable, i.e., have no cycles that would result in the instability of execution; and (3) have no redundant rules. They also address the issue of deterministic execution and propose optimization algorithms that generate the rule-bases with single corresponding fixed points for every initial state. The synthesis method also determines the tight response time bound of the new system and can identify unstable states in the original rule-base     

Robustness analysis of linear parameter varying systems using integral quadratic constraints

A general approach is presented to analyze the worst case input/output gain for an interconnection of a linear parameter varying (LPV) system and an uncertain or nonlinear element. The LPV system is described by state matrices that have an arbitrary, that is not necessarily rational, dependence on the parameters. The input/output behavior of the nonlinear/uncertain block is described by an integral quadratic constraint (IQC). A dissipation inequality is proposed to compute an upper bound for this gain. This worst‐case gain condition can be formulated as a semidefinite program and efficiently solved using available optimization software. Moreover, it is shown that this new condition is a generalization of the well‐known bounded real lemma type result for LPV systems. The results contained in this paper complement known results that apply IQCs for analysis of LPV systems whose state matrices have a rational dependence on the parameters. The effectiveness of the proposed method is demonstrated on simple numerical examples. Copyright © 2014 John Wiley & Sons, Ltd.     

Towards a theory of fuzzy causality for diagnosis

Parsimonious covering offers an alternative to rules for building diagnostic expert systems. Abductive paradigms, such as parsimonious covering, are a departure from the forward-chaining, rule-based approach, which is based on deduction. Parsimonious covering addresses weaknesses of rule-based systems where the diagnosis may contain multiple faults or disorders, or where the need to include all the necessary context for each rule's application in the antecedent clauses of each rule would make the representation of the knowledge base too large or overly complex.

In this paper, we compare the notions of deterministic covering and the probabilistic causal model with two fuzzy analogies: fuzzy subsethood and fuzzy similarity. Monotonic upper and lower bounds for fuzzy similarity are derived, and pruning opportunities are identified for search through the power set of disorders, given a measured, crisp manifestation set.     

A distributed expert control system for a hydrometallurgical zinc process

A distributed expert control system (DECSHZ) has been built for a hydrometallurgical zinc process, whose basic steps are leaching, purification and electrolysis. It consists of a central computer management system and three local expert control systems, one for each of the basic steps. This paper deals with the design and application of DECSHZ, especially its distributed architecture and main functions; expert control strategies based on rule models and a combination of rule models and steady-state mathematical models; system implementation; and the results of actual runs. DECSHZ has been found to provide not only a very pure product, but also significant economic benefits.     

Use of conditional rule structure to automate clinical decision support: a comparison of artificial intelligence and deterministic programming techniques

A rule-based computer system was developed to perform clinical decision-making support within a medical information system, oncology practice, and clinical research. This rule-based system, which has been programmed using deterministic rules, possesses features of generalizability, modularity of structure, convenience in rule acquisition, explanability, and utility for patient care and teaching, features which have been identified as advantages of artificial intelligence (AI) rule-based systems. Formal rules are primarily represented as conditional statements; common conditions and actions are stored in system dictionaries so that they can be recalled at any time to form new decision rules. Important similarities and differences exist in the structure of this system and clinical computer systems utilizing artificial intelligence (AI) production rule techniques. The non-AI rule-based system possesses advantages in cost and ease of implementation. The degree to which significant medical decision problems can be solved by this technique remains uncertain as does whether the more complex AI methodologies will be required.     

Evaluation of expert systems for automatic shape recognition by ultrasound

This paper presents an evaluation of several types of expert systems in automatic object recognition for robotic manipulators, using ultrasound. In fact, rule-based expert systems and probabilistic expert systems have been compared in a calculation of prismatic body orientation and object shape recognition. Furthermore, both types of expert systems were used to distinguish different piece shapes and to detect object position in a real scenario using a robotic manipulator. Information for the automatic recognition system is provided to the expert system by means of the ultrasonic signal coming back from the illuminated object, which is captured by only one receiver placed on the robot grip. Subsequently, in order to reduce the number of parameters to work with, a parametric method for characterisation of this signal is presented. This has been done by calculating several geometric parameters from the signal envelope. Afterwards, a study of the probability distribution function for each parameter provides the necessary information for the expert system to carry out the distinction between the different objects of interest. In this way, it permits the establishment of a comparison among different expert system types for automatic shape recognition using ultrasounds.     

Parallel implementation of rule-based expert systems for interactive applications

A novel approach to parallel implementation of rule-based expert systems is presented in this paper. This approach is tailored for expert systems in interactive applications. Rule-based expert systems are modeled by state space and AND/OR graphs. The interdependences among rules are analyzed to guide rule-base partitioning and memory bank assignment. Parallel execution of rule-based expert systems is investigated in the environment of closely coupled multiprocessors. Algorithms are developed for the parallel execution of rules and for the allocation of data to memory banks in interactive applications.     

Developing maintainable expert systems using case-based reasoning

Abstract: Maintainability problems associated with traditional software systems are exacerbated in rule-based systems. The very nature of that approach — separation of control knowledge and data-driven execution — hampers maintenance. While there are widely accepted techniques for maintaining conventional software, the same is not true for rule-based systems. In most situations, both a knowledge engineer and a domain expert are necessary to update the rules of a rule-based system. This paper presents, first, an overview of the software engineering techniques and object-oriented methods used in maintaining rule-based systems. It then discusses alternate paradigms for expert system development. The benefits of using case-based reasoning (from the maintenance point of view) are illustrated through the implementation of a case-based scheduler. The main value of the scheduler is that its knowledge base can be modified by the expert without the assistance of a knowledge engineer. Since changes in application requirements can be given directly to the system by the expert, the effort of maintaining the knowledge base is greatly reduced.     

Scalable Parallel and Distributed Expert Database Systems with Predictive Load Balancing

Much prior work in AI on various attempts to speed up rule-based systems by parallel processing has been reported. Unfortunately, many of these results indicate that there is limited parallelism to be found when rules are applied to relatively small amounts of data. Thus, one can predict that much greater parallelism can be extracted when rules are applied to large amounts of data. However, traditional compile-time parallelization strategies as developed for main-memory based systems do not scale to large databases. We propose a scalable strategy for the efficient parallel implementation of rule-based systems operating upon large databases. We concentrate on load balancing techniques in a synchronous model of rule execution, where the variance in runtime of the distributed sites is minimized per cycle of rule processing, thus increasing utilization and speedup. We demonstrate that static load balancing techniques are insufficient, and thus low overhead dynamic load balancing is the key to successful scaling. We present a form of dynamic load balancing that is based upon predicting future system loads, rather than conventional demand-driven approaches that monitor current system state. We analyze a number of possible predictive dynamic load balancing protocols by isoefficiency analysis to guide the design of a parallel database rule processing system.     

A branch-and-bound algorithm for implementing set covering model expert systems

The conventional rule-based expert system can be formulated as a 0–1, integer program, specifically, as a set covering problem. However, the implementation of an expert system in this way requires that the set covering model be solved for k-best alternate optima or near-optima. We have devised a branch-and-bound algorithm which accomplishes this. The details of the algorithm are explained in the paper. Computational results are provided.     

Experimental results from parallel backward-chained expert systems

There are many applications which may be done by an expert system in real time, if the system is capable of real time response. the first Lisp- and Prolog-based expert systems have typically been too slow for real time response. This has lead to an effort to use other languages, the development of fast pattern matching techniques, and other methods of improving the speed of expert systems. Another approach to developing faster expert systems is to make use of the emerging parallel processing computer technology. A further use for parallelism is to allow reasonable response time for large knowledge bases. the size of knowledge bases may become as large as 20,000 chunks of knowledge (and more) in the near future in medical and space applications. This article describes the use of parallel processing in the EMYCIN backward chained rule-based model. Performance on two examples of shared memory multiprocessors is presented and contrasted with earlier simulations.     

Building a financial diagnosis system based on fuzzy logic production system

The purpose of this study is to build a financial expert system based on fuzzy theory and Fuzzy LOgic Production System (FLOPS), which is an expert tool for processing the ambiguity. The study consists if four parts. For the first part, the basic features of expert systems are presented. For the second part, fizzy concepts and the evaluation of classical expert systems to fuzzy expert systems will be presented. For the third part, the expert system shell (FLOPS) used in this study will be described. For the last part, it will be presented the financial diagnosis system, developed by using the Wall's seven ratios, traditional seven ratios and also 34 ratios selected by a financial expert. After analyzing and investigating these three kinds of methods, financial diagnosis system will be developed as a fuzzy expen system which used a membership function based on averages and standard deviation. At the last step, the new approach will be tried by increasing the fuzzy sets for five membership functions. Some practical examples will be given. Throughout the paper, the way of building a financial diagnosis system based on fuzzy expert system is stressed.     

Dwell time-based stabilisation of switched delay systems using free-weighting matrices

In this paper, we present a quasi-convex optimisation method to minimise an upper bound of the dwell time for stability of switched delay systems. Piecewise Lyapunov–Krasovskii functionals are introduced and the upper bound for the derivative of Lyapunov functionals is estimated by free-weighting matrices method to investigate non-switching stability of each candidate subsystems. Then, a sufficient condition for the dwell time is derived to guarantee the asymptotic stability of the switched delay system. Once these conditions are represented by a set of linear matrix inequalities , dwell time optimisation problem can be formulated as a standard quasi-convex optimisation problem. Numerical examples are given to illustrate the improvements over previously obtained dwell time bounds. Using the results obtained in the stability case, we present a nonlinear minimisation algorithm to synthesise the dwell time minimiser controllers. The algorithm solves the problem with successive linearisation of nonlinear conditions.     

Nonlocal stabilization via delayed relay control rejecting uncertainty in a time delay

Sufficient conditions for a robust relay delayed non‐local stabilization of linear systems are found, which relate the upper bound of an uncertainty in a time delay and the maximum of the real part of system spectrum. Algorithm of delayed relay control gain adaptation for non‐local stabilization is suggested. The proposed algorithm suppresses bounded uncertainties in the time delay: once this relay delayed control law for the upper bound of uncertainty in the time delay for given system is designed, we ensure non‐local stabilization for all values of the time delay less than the upper bound even in the case of a variable delay. Copyright © 2003 John Wiley & Sons, Ltd.