EXERCISES 365

state-space graphs checked in most cases have been effectively reduced, resulting in an obvious reduction in the time spent in analyzing real-time rule-based systems.

Applying our approach to the three systems (i.e., the SSV program, the ISA program, and the FCE program), we found that the programs can be partitioned into subsets, most of which are in known special forms. The subset of rules not in special form actually contains rules which lead to unbounded rule firings. So far, we do not have statistical data to show the percentage of programs that can be analyzed by the special form approach. However, from the limited experience we have, it is our view that this is a feasible approach to reducing the time needed to conduct analysis.

Chapter 11 describes the time analysis of more expressive, predicate-logic rulebased languages such as OPS5 [Forgy, 1981] and MRL [Wang, 1990a], both of which allow the use of structured variables.

EXERCISES

1.Why is the timing analysis of rule-based systems more difficult than that of sequential programs?

2.Describe the system represented by the rule-based program in example 2 (object detection) in terms of the real-time decision system model shown in Figure 10.1.

3.Construct the state-space graph corresponding to the rule-based program in example 2.

4.How can a model-checking algorithm such as the one for the computation tree logic be used to analyze the response time of EQL rule-based systems with finitedomain variables?

5.Consider the following EQL program:

Use the general analysis strategy to analyze this program and report the analysis results.

6.Construct the enable-rule graph for the following rules and identify the simple cycles, if any.

7.Specify Special Form D in the Estella specification language.

8.Explain the difficulty in checking whether two enabling conditions are mutually exclusive. Describe how the approximation algorithm presented tackles this analysis complexity.

9.Why is the response-time analysis of EQL programs that assign expressions containing variables to left-side variables much more difficult than those with only constant assignments?

10.Determine an upper bound on the execution time in terms of the number of rule firings for the following EQL program:

PROGRAM Example 1

INPUTVAR

a,b : INTEGER;

VAR

c,d,e,f,g,h:INTEGER;

INIT

c:=0,d:=0,e:=0,f:=0,g:=0,h:=0

(*r9*)[] g:=2!h:=2 IF f<=1 and e>1

END.

368 TIMING ANALYSIS OF PREDICATE-LOGIC RULE-BASED SYSTEMS

Moldovan, 1991; Pasik, 1992; Schmolze, 1991] have been provided to achieve this goal. The other solution is to optimize the expert system by modifying or resynthesizing the rule base if the response time is found to be inadequate [Zupan and Cheng, 1994a; Zupan and Cheng, 1998].

In this chapter, we present more approaches for the response-time analysis of rule-based systems. In particular, we study the timing properties of programs written in the predicate-logic-based OPS5 language [Forgy, 1981] (and other OPS5-style languages), which is not designed for real-time purposes although it has been widely adopted in practice. In chapter 10, we introduced the propositional-logic-based rulebased language EQL (equational rule-based language), for real-time applications. EQL is a simple, rule-based language with well-defined semantics. It has been used to program a number of practical real-time applications.

OPS5 exhibits an incremental increase in expressiveness over MRL [Wang, Mok, and Cheng, 1990; Wang, 1990a] but it is not as complex as more recent objectoriented rule-based languages. OPS5 has been successfully used in a variety of applications [Forgy, 1985]. MRL is designed to be an extension of EQL. It includes set variables (working memories) and logical quantifiers over set variables. However, MRL does not include the timing tags in its working memory, so many conflict resolution strategies, such as LEX and MEA, cannot be applied to MRL programs. It is entirely the programmer’s responsibility to guarantee that any firing sequence is a normal execution flow. Under this situation, the programmer usually needs to avoid interference among rules; otherwise, the program may be hard to debug and maintain.

OPS5 has been used to implement several industrial expert systems, including MILEX (The Mitsui Real Time Expert System) and XCON/R1, which is generally considered the first commercially successful expert system [Forgy, 1985].

Our goal is to obtain a tighter bound on the execution time that is close to the real upper bound. We consider the case where an OPS5 expert-system program forms the decision module of a real-time monitoring and controlling system [Payton and Bihari, 1991]. 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 that 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 [Cheng et al., 1993; Chen and Cheng, 1995b]. Therefore, our goal is to determine, before run-time, a tight upper bound on the execution time of the expert system in every invocation following each reading of sensor input values.

To analyze the timing behavior of an OPS5 program, we first formalize a graphical representation of rule-based programs. This high-level data-dependency graph captures all possible logical control paths in a program. Based on this graph, we design a termination detection algorithm to determine whether an OPS5 program always terminates in bounded time. If an OPS5 program is not detected to terminate for all initial program states, then the “culprit” conditions that cause nontermination are extracted to assist programmers in correcting the program. They then modify