B. Zupan et Amk. Cheng, OPTIMIZATION OF RULE-BASED SYSTEMS USING STATE-SPACE GRAPHS, IEEE transactions on knowledge and data engineering, 10(2), 1998, pp. 238-254
Citations number
23
Categorie Soggetti
Computer Science Artificial Intelligence","Computer Science Information Systems","Engineering, Eletrical & Electronic","Computer Science Artificial Intelligence","Computer Science Information Systems
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.