DocumentCode :
1393498
Title :
Optimization of rule-based systems using state space graphs
Author :
Zupan, Blaz ; Cheng, Albert Mo Kim
Author_Institution :
Dept. of Intelligent Syst., Jozef Stefan Inst., Ljubljana Univ., Slovenia
Volume :
10
Issue :
2
fYear :
1998
Firstpage :
238
Lastpage :
254
Abstract :
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
Keywords :
decision support systems; expert systems; graph theory; optimisation; real-time systems; state-space methods; timing; algorithms; complexity; concurrency; deterministic execution; embedded rule-based expert systems; execution instability; fixed point; optimization; optimized rule-based systems; optimized state space graph; real-time environments; reduced cycle-free finite state space graph; response time reduction; rule firings; state equivalency; tight response time bound; timing constraints; unstable states; Application software; Concurrent computing; Delay; Expert systems; Knowledge based systems; Optimization methods; Protocols; Real time systems; State-space methods; Timing;
fLanguage :
English
Journal_Title :
Knowledge and Data Engineering, IEEE Transactions on
Publisher :
ieee
ISSN :
1041-4347
Type :
jour
DOI :
10.1109/69.683755
Filename :
683755
Link To Document :
بازگشت