Optimization of Real-Time Rule-Based Expert Systems

Albert Mo Kim Cheng

Real-Time Systems Laboratory
Department of Computer Science
University of Houston--University Park

Contact Information

Department of Computer Science
Houston, TX 77204-3475
Phone: (713) 743-3353
Fax : (713) 743-3335
Email: cheng@cs.uh.edu

WWW PAGE

http://www.cs.uh.edu/~acheng/acheng.html

Keywords

real-time systems, expert systems, rule-based systems, analysis, optimization, synthesis

Project Award Information

3 years, year 2, ``Optimization of Real-Time Rule-Based Expert Systems.''

Project Summary

The major focus of this research is to develop the scientific foundation and to implement practical tools for optimizing and synthesizing rule-based expert systems to meet specified response time constraints. Real-time rule-based expert systems are embedded artificial intelligence (AI) systems increasingly used in many applications, such as airplane avionics, medical monitoring instruments, smart robots, space vehicles, and other safety critical applications. In addition to functional correctness, these systems must also satisfy stringent timing constraints. The result of missing a deadline in these systems may be catastrophic. If a given rule-based system cannot deliver an adequate performance in bounded time, then it has to be optimized or resynthesized. The first part of the project investigates several approaches (state-space-based and semantics-based) for optimizing the rule base of expert systems. The second part of the project investigates the optimization of the match phase, which has a highly unpredictable runtime.

Goals, Objectives, and Targeted Activities

This should consist of what is generally going to be in the research overview in your 1997-98 year end report and next years goals. Several steps for rule base optimization are accomplished this year (1997-1998): (1) refinement of our EQL optimization algorithm with bidirectional search; (2) application of a modified EQL optimization algorithm to MRL nd OPS5-style programs; (3) development of new rule-splitting techniques to increase rule parallelism; and (4) preliminary design of a conjunct-reordering optimization algorithm. Our next year's goals will be the refinement, implementation, and evaluation of these and possibly more techniques, yielding an optimization toolset.

Indication of Success

We have modified the optimization method [Zupan & Cheng 98] that we have developed earlier for EQL (Equational Rule-based Language) systems to optimize MRL (Macro Rule-based Language) systems. In particular, we show how the EQL optimization method can be applied to an MRL system after its corresponding state space graph is constructed. Since the time and space complexity of bidirectional search (O(b^(d/2))) is better than breadth-first search's (O(b^d)), we use bidirection and bidirectional breadth-first search strategies instead of the original bottom-up and breadth-first search strategies employed earlier. The resulting optimized MRL system (1) has in general better response time because it requires a fewer number of rule firings to reach the fixed point, (2) is stable because it has no cycles, and (3) has no redundant rules. The main difficulty in applying the EQL optimization method to MRL programs is how to handle the different logics used in EQL and MRL. Once this problem is resolved, then our optimization methodology will not only work for MRL but also for similar first-order logic-based production languages.

Rule-based expert systems use rules to make decisions based on current knowledge. Often the rules consist of two parts, the left-hand side (LHS) and right-hand side (RHS). The LHS is the condition the rule must fulfill and the RHS is the conclusion determined by the rule. If the LHS is instantiated, then the RHS may fire. This causes insertions or deletions from the current knowledge base or working memory (WM). It is possible for two or more rules' LHS to instantiate (enter the conflict set), forcing the inference engine to choose which rule to fire (conflict resolution). One popular way to determine conflict resolution is to fire the rule instantiated by the most recently inserted WM element (WME).

With parallel machines, it is possible to fire all of the rules in the conflict set simultaneously. However, this is unstable since a slight timing difference may cause different results in the WM. A stable parallel strategy will often mimic a sequential strategy. The only difference in the strategies being that the parallel version will not only fire the same rule, it will also fire other rules the first enables. In fact, this parallel strategy may fire several rules in the same conflict set under certain circumstances. In order to determine which rules can be stably fired in parallel, the relations between each rule must first be sought after.

The most important rules relations are enable, disable, and conflict. Rule A enables rule B if and only if (iff) firing rule A implies rule B is instantiated. Rule A disables rule B iff firing rule A implies rule B is not instantiated. Rule A conflicts rule B iff rule A fired adds some WME and B fired deletes that same WME.

Often these relations cannot be absolutely determined without information from the WM. One particular WM may cause rule A to enable rule B, but another WM will not. These potential relations are often caused by using rule conditions with variables based on the WM. If the potential relations are not examined for possible parallelism at runtime, unnecessary synchronization among rule instantiations will occur. Furthermore, more parallelism can be exploited by further reducing potential relations in a process called rule splitting.

Rule splitting often involves comparing two rules (usually with potential relations) and reducing them into several subrules which collectively are logically equivalent except that the relation's unsureness is reduced. At times, certain culprit rules with complicated conditions are identified and split to even processor loads. Thus, rule splitting algorithms may significantly speed up runtime execution.

Our EQL optimization method works only for rules with constant assignments in their subactions and cannot handle match optimization. We are in the preliminary stage of developing a combination of new approaches for rule base optimization that can be applied to a larger class of practical programs. These techniques are based on a construction of conjunctive normal form and conjunct dependency list corresponding to the input variables of a rule-based system. Currently, a variation of this approach is used only in the match step of the recognize-act cycle during the execution of a rule-based program. It is not easy to follow the dependency of the program variables since they frequently change their values during execution, so only the input variables are used for optimization. Once the conjunct dependency list is computed, we can generate a simplified rule-based system from it. We are also developing a probability-based conjunct reordering algorithm which can reduce the match time of rules.

The development of practical and efficient solutions to the rule base optimization problem are fundamental in making rule-based systems practical in a real-time environment. These optimization techniques can also be applied to other areas of computer science, especially database systems. There are similarities between expert system rules and database queries. Currently, no practical optimization method exists and thus funding for this project is well justified. I am happy with the progress so far, meeting the stated goals as well as inventing new approaches not previously planned.

Project Impact and Output

Human Resources: Ling-Hua Chang, a female doctoral student, is studying the different stages of OPS5 rule-based system execution so that the ``hot spots'' can be identified and then optimized with existing and/or new techniques. In particular, she is investigating areas which have not been studied carefully in our earlier analysis method. Raymond Cheung, a masters student, is collaborating with Ling-Hua on techniques for rule-based optimization. He is also evaluating the implemented analysis tools by testing them with rule-based programs from several applications. Rajat Agarwal, a masters student who has just graduated under my supervision, collaborated with Ling-Hua on the problem. He is now employed by AT&T Lucent Technologies.
Liem Nguyen, an undergraduate, is working on an undergraduate honor thesis on rule-base optimization under my supervision. Pou-Yun Lee, a masters graduate, performed an excellent job in the development of a match algorithm called HAL. He is now with Taos Mountain in Palo Alto. Fan Chiang, an NSF-REU stipend recipient who graduated under my supervision, is now pursuing a PhD in computer science at Duke University. Steven Avery, another undergraduate, has completed a project on rule-base optimization via rule splitting.
Mark Tsung-I Huang is studying the scheduling and execution aspects of rule execution and is very experienced with implementation and machine details. Yun-Hong Lee, a new doctoral student under my supervision, is investigating the use of conjunctive normal form and conjunct dependency list for the optimization of rule-based systems. Currently, a variation of this approach is used only in the match step of the recognize-act cycle during the execution of a rule-based program.
Jeong-A Kang, a new female masters student under my supervision, is studying the optimization problem for rule-based systems. She is investigating semantic approaches to program optimization. Seiya Fujii, a new masters student under my supervision, is studying ways to make rule-based systems more fault-tolerant. In particular, he is applying self-stabilization transformation, based on an earlier method for EQL systems, to OPS5-style systems. Jui-chan Wang, a new female doctoral student currently working on a project with me, is investigating more efficient search strategies such as bidirectional search for the state-based optimization method we developed earlier for EQL systems. She is also applying a modified EQL optimization method to MRL systems. Raymond and Rajat were supported by NSF research assistantships. Raymond is now supported by Compaq. Mark and Ling-Hua are currently supported by NSF research assistantships.
Education and curriculum development: In addition to research activities, I have incorporated well-developed results into the course materials of my two graduate courses (real-time systems and advanced real-time systems) and have given basic introduction in my undergraduate operating systems course.
Department/institution infrastructure: Besides my Real-Time Systems Laboratory, there are several centers/laboratories devoted to specialized research. The Virtual Environment Technology Laboratory (VETL) is a state-of-the-art facility with a CAVE to investigate virtual reality issues. The brand new Multimedia and Graphics Laboratory with the latest Silicon Graphics workstations is used for undergraduate and graduate instruction as well as for research in graphics and multimedia communication. The Texas Center for Computational and Information Sciences is an interdisciplinary facility that serves as a fusion of resources from several departments to solve challenging scientific problems in biology, biochemistry, chemistry, and physics. The Department of Computer Science also hosts a variety of equipment, ranging from personal computers to supercomputers for instruction and research.
Industry collaborations: I am discussing with local companies such as Valmet Automation about possible collaboration and technology transfer.

Project References

B. Zupan and A. M. K. Cheng, ``Optimization of Rule-Based Systems Using State Space Graphs,'' IEEE Transactions on Knowledge and Data Engineering, April 1998.

A. M. K. Cheng and J.-C. Wang, ``Applying a Modified EQL Optimization Method to MRL Rule-Based Programs,'' Proc. IEEE Workshop on Application-Specific Software Engineering and Technology, Richardson, TX, Mar. 1998.

A. M. K. Cheng, ``Optimization of Real-Time MRL Rule-Based Systems with the EQL Optimizer,'' Proc. WIP Session, 18th IEEE-CS Real-Time Systems Symposium, San Francisco, CA, Dec. 1997.

P.-Y. Lee and A. M. K. Cheng, ``Reducing Match Time Variance in Production Systems with HAL,'' Proc. 6th Intl. ACM Conf. on Information and Knowledge Management, Las Vegas, Nevada, Nov. 1997.

S. Avery and A. M. K. Cheng, ``Optimizing OPS5 Rule-Based Programs by Rule-Splitting,'' Proc. Intl. Conf. on Software Engineering, San Francisco, CA, Nov. 1997.

Area Background

As rule-based expert systems become increasingly adopted in new application domains such as real-time systems, ensuring that they meet stringent timing constraints in these safety-critical and time-critical environments emerges as a challenging problem. Unfortunately, rule-based expert systems are usually computationally expensive and slow. Moreover, they are considered less predictable and analyzable because of their context-sensitive control flow and possible non-determinism. However, there have been few attempts to formalize the question of whether a rule-based program has bounded response time.

Our research considers the case where an expert system forms the decision module of a real-time monitoring and controlling system. This real-time system takes sensor input readings periodically, and the embedded expert system must produce, based on these input values and state values from previous invocations of the expert system, an output decision which ensures the safety and progress of the real-time system and its environment prior to the taking of the next sensor input values. Thus, the upper bound on the expert system's execution time cannot exceed the length of the period between two consecutive sensor input readings. Therefore, the first objective is to determine before run-time a tight upper bound on the execution time of the expert system in every invocation. The second objective is to optimize the expert system by modifying or resynthesizing the rule base if the execution time is found to exceed the specified timing constraint. The most related area to our work is database systems, especially those with timing constraints or temporal characteristics (real-time, active, or temporal databases). Certain techniques for the analysis and optimization of rules can be applied to database queries and vice versa.

Area References

F. Barachini, ``Frontiers in Run-Time Prediction for the Production-System Paradigm,'' AI Magazine, Vol. 15, No. 3, pp. 47-61, Fall 1994.

J.-R. Chen and A. M. K. Cheng, ``Response Time Analysis of EQL Real-Time Rule-Based Systems,'' IEEE Transactions on Knowledge and Data Engineering, Vol. 7, No. 1, pp. 26-43, Feb. 1995.

A. M. K. Cheng, ``Parallel Execution of Real-Time Rule-Based Systems,'' Proc. 7th IEEE-CS Intl. Parallel Processing Symp., Newport Beach, CA, pp. 779-786, Apr. 1993.

A. M. K. Cheng, J. C. Browne, A. K. Mok, and R.-H. Wang, ``Analysis of Real-Time Rule-Based Systems With Behavioral Constraint Assertions Specified in Estella,'' IEEE Transactions on Software Engineering, Vol 19, No. 9, pp. 863-885, Sept. 1993.

T. Ishida, ``An Optimization Algorithm for Production Systems,'' IEEE Trans. on Knowledge and Data Engineering, Vol. 6, No. 4, pp. 549-558, Aug. 1994.

G.-C. Roman, R. F. Gamble, and W. E. Ball, ``Formal Derivation of Rule-Based Programs,'' IEEE Trans. on Software Engineering, Vol 19, No. 3, Mar. 1993.

A. J. Pasik, ``A Source-to-Source Transformation for Increasing Rule-Based System Parallelism,'' IEEE Trans. on Knowledge and Data Engineering, Vol. 4, No. 4, pp. 336-343, Aug. 1992.

C.-K. Wang, A. K. Mok, and A. M. K. Cheng, ``MRL: A Real-Time Rule-Based Production System,'' Proc. 11th IEEE-CS Real-Time Systems Symposium, Orlando, FL, pp. 267-276, Dec. 1990.

C. Y. Wang and A. M. K. Cheng, ``Increasing Production System parallelism via Synchronization minimization and Look-Ahead Conflict Resolution,'' Proc. 24th Intl. Conf. on Parallel Processing, Oconomowoc, WI, Vol. III, pp. 85-92, Aug. 1995

Potential Related Projects

If you have ideas for projects or collaborations with those related program areas within the IDM, describe some of them briefly here.