OPTIMIZATION OF RULE-BASED SYSTEMS USING STATE-SPACE GRAPHS

Embedded rule-based expert systems must satisfy stringent timing const raints when applied to real-time environments. The paper describes a n ovel approach to reduce the response time of rule-based expert systems . Our optimization method is based on a construction of the reduced cy cle-free finite state space graph. In contrast with traditional state space graph derivation, our optimization algorithm starts from the fin al states (fixed points) and gradually expands the state space graph u ntil all of the states with a reachable fixed point are found. The new and optimized system is then synthesized from the constructed state s pace graph. We present several algorithms implementing the optimizatio n method. They vary in complexity as well as in the usage of concurren cy and state-equivalency-both targeted toward minimizing the size of t he optimized state space graph. Though depending on the algorithm used , optimized rule-based systems: 1) in general have better response tim e 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. We also address the iss ue of deterministic execution and propose optimization algorithms that generate the rule-bases with single corresponding fixed points for ev ery initial state. The synthesis method also determines the tight resp onse time bound of the new system and can identify unstable states in the original rule-base. No information other than the rule-based realt ime decision program itself is given to the optimization method. The o ptimized system is guaranteed to compute correct results independent o f the scheduling strategy and execution environment.