Optimization of Real-Time Rule-Based Expert Systems

Contact Information

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 3, ``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

Several steps for rule base optimization are accomplished this year (1998-1999): (1) development of a new run-time dynamic optimizer for real-time EQL rule-based systems to complement our static optimizer, (2) more refinement of our static EQL optimization algorithm with bidirectional search; (3) implementation of parallel sorting algorithms on the IBM SP2 supercomputer for use in parallel matching of condition elements in rules; and (4) derivation of new heuristics for rearranging the condition elements in rules to reduce the match time.

Indication of Success

To complement our static optimizer [Zupan & Cheng 98], we have developed a new run-time dynamic optimizer for real-time EQL rule-based systems to satisfy the specified response time constraints. Unlike the static optimization algorithm which optimizes a program before its execution, the dynamic algorithm tries to minimize the number of rules to be executed at run-time. The new run-time optimizer constructs a predicate dependency list, which consists of a predicate, an active rule list, and an inactive rule list, for each predicate in a rule-based program. It then generates an inactive rule list by putting all false rules in a predicate dependency list together, and dynamically selects rules for execution at run-time.

The optimized program executes only selected rules at run-time but has the same semantics as the original program. We implemented and evaluated the performance of the proposed algorithm using both synthetic and industrial real-time rule-based programs. Though the dynamic optimizer can be applied to any real-time rule-based system, we use EQL real-time systems in the implementation so that we can compare the performance with our static algorithm. The performance evaluation shows that the dynamic optimizer reduces response time as well as the number of rules and predicates significantly more than that achieved by using the static optimizer alone in many cases.

We have modified the optimization method [Zupan & Cheng 98] that we have developed earlier for EQL systems to optimize MRL (Macro Rule-based Language) systems. In particular, we implemented this method to optimize MRL systems after their corresponding state space graphs are 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.

To further reduce the execution time of rule-based systems, we have been investigating parallelization of these systems. Earlier, we have developed techniques for rule-splitting to achieve a higher degree of parallelism while avoiding conflicts caused by parallel rule-firing. During this past year, we have studied the problem of implementing parallel OPS5 on the IBM SP2 supercomputer. Since up to 90% of the execution time is spent on matching (in the Rete network in the case of OPS5), improvement in the parallelization of the match phase is essential.

There are many comparisons in this match phase, especially in the two-input nodes. We first experimented with a good sorting algorithm to reduce the comparison time in two-input nodes. Performing comparison in two-input nodes is similar to performing a joint of two tables of data. If each class of working memory elements can be sorted in advance, then we can save more time when searching the required data. We implemented several alternatives of parallel sorting. We are attempting to find a good sorting algorithm which will give the best performance on IBM SP2 and can be used in the OPS5's rule interpreter.

Project Impact and Output

• Human Resources: Ling-Hua Chang, a female doctoral student, is studying parallel OPS5 implementations on the IBM SP2. Rajat Agarwal, a masters student who has graduated under my supervision, collaborated with Ling-Hua on the problem. He is now employed by AT&T Lucent Technologies.
  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 has 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 doctoral student under my supervision, is investigating the use of conjunctive normal form and conjunct dependency list for the optimization of rule-based systems.
  Jeong-A Kang, a female masters student under my supervision, is studying the optimization problem for rule-based systems. She is investigating semantic approaches to program optimization, such as new heuristics for rearranging the condition elements in rules to reduce the match time. Seiya Fujii has completed his M.S. thesis under my supervision, and is now working in a software firm in California. He studied ways to make rule-based systems more fault-tolerant.
  Jui-chan Wang, a female doctoral student currently working on a project with me, is investigating more efficient search strategies for the state-based optimization method that we have developed earlier for EQL systems. She is also applying a modified EQL optimization method to MRL systems. Rajat was supported by an NSF research assistantship. Jeong-A is supported by the Department of Psychology. Yun-Hong is now supported by Aerial Communications. 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 (RTSL), 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 (TCCIS) 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.
• Industry collaborations: I am discussing with local companies such as Compaq about possible collaboration and technology transfer.

Project References

• Y.-H. Lee and A. M. K. Cheng, ``Run-time Dynamic Optimization of Real-Time Rule-Based Systems,'' submitted to Proc. IEEE-CS Real-Time Technology and Applications Symposium, Vancouver, Canada, June 1999.
• S. Fujii and A. M. K. Cheng, ``Bounded-Response-Time Self-Stabilizing Real-Time Rule Systems,'' submitted for publication, 1999.
• P.-Y. Lee and A. M. K. Cheng, ``HAL: A New Match Algorithm with Low Match-Time Variance,'' submitted to IEEE Transactions on Knowledge and Data Engineering, Sept. 1998.
• 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.
• 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.
• 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

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.
• 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.
• 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.
• 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.
• 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

I would like to collaborate with group(s) working on the analysis and optimization of real-time expert and database systems.