Data processing: artificial intelligence – Knowledge processing system – Knowledge representation and reasoning technique
Reexamination Certificate
1997-09-24
2003-04-08
Khatri, Anil (Department: 2122)
Data processing: artificial intelligence
Knowledge processing system
Knowledge representation and reasoning technique
C706S057000, C706S060000
Reexamination Certificate
active
06546380
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention generally relates to data processing systems, and more particularly relates to rules-based expert systems.
2. Description of the Prior Art
With the rapid advancement of modern electronics, data processing systems have found many new and useful applications. Today, almost every industry sector uses some form of data processing systems in its daily activities. The banking industry, for example, uses mainframe type data processing systems to maintain large accounting databases, and to manage the large number of banking transactions that occur every day. The manufacturing industry uses data processing systems to maintain process flows, and manage inventory. Engineering and scientific applications are self evident. Even in the home, personal computers have become widely used.
Numerous software programs exist to support each of these varying applications. Traditionally, most software is written using a conventional high level computer programming language such as FORTRAN, PASCAL, COBOL, C++, Visual Basic, etc. A common statement in all of these programming languages is some form of a conditional statement. One example of a conditional statement is an if-then type statement, and typically includes an if type clause and a corresponding then type clause. The if type clause usually has a corresponding expression, which if true, allows the execution of the then type clause. When using conventional programming languages, all statements including the conditional statements must be explicitly specified in the context of the overall program flow.
Recently, rules-based expert systems have gained popularity, and are particularly suited for certain applications. In a rules-based expert system, a number of rules are provided. Each rule is similar to a conditional statement in a conventional programming language. However, in a rules-based expert system, a special program called an inference engine is typically provided. The inference engine manages the rules and applies them as appropriate, rather than simply executing the rules in a strictly sequential manner as in a conventional computer programming language.
Typically, the inference engine applies the rules in an iterative manner. During a first pass, the inference engine typically sequentially executes a number of selected rules. For each rule, the inference engine determines if the expression of the if type clause is true. If the expression is found to be true, the corresponding then type clause is executed. Often, the then type clause executes statements that change a variable or parameter within the system. The inference engine maintains a listing of the updated parameters.
During a subsequent pass, the inference engine determines which of the rules have an expression of the if type clause that is dependent on one or more of the parameters in the listing of updated parameters. The inference engine re-executes only those rules, and again updates the listing of updated parameters. This is repeated until no parameters exist in the listing of updated parameters.
As can readily be seen, the precise flow of rule processing in a rules-based expert system can vary dramatically, depending on the particular interactions of the rules that are processed. The interactions between rules can be very difficult to predict, particularly since hundreds of rules may exist within the system. Thus, robust debug and product testing of rules-based expert systems can be difficult, time consuming, and tedious.
For these and other reasons, rules based expert systems may be particularly susceptible to errors caused by unforeseen interactions between rules, including those interactions that cause the system to become stuck in an endless loop. This may occur, for example, when the expression of the if type clause of a first rule is dependent upon a parameter that is changed by the statement of the then type clause of a second rule, and the if type clause of the second rule is dependent upon a parameter that is changed by the statement of the then type clause of the first rule. In this instance, the rules-based expert system may become stuck in an endless loop.
SUMMARY OF THE INVENTION
The present invention overcomes many of the disadvantages of the prior art by providing a method and apparatus for detecting an endless loop in a rules-based expert system. This is preferably accomplished by maintaining a count for each of the rules during rule processing. The count indicates the number of times a corresponding rule is executed by the rules based expert system. If the count corresponding to any of the rules exceeds a predetermined value, the rules-based expert system is determined to be stuck in an endless loop. When stuck in an endless loop, the present invention contemplates interrupting the rules-based expert system, and returning control to a calling program or to the user.
As described above, the rules-based expert system preferably includes an inference engine for processing the rules. When it is concluded that the rules-based expert system is stuck in an endless loop, the inference engine is interrupted, and control is passed back to the rules-based expert system.
Each of the rules preferably includes an if type clause which specifies an expression, and a then type clause which may include one or more statements. The then type clause is executed only if the expression of the if type clause is satisfied. In accordance with a preferred embodiment of the present invention, the then type clause preferably includes a statement that increments a counter for the corresponding rule. In this way, a counter value is maintained for selected rules in the system, and preferably all rules. The value stored in each rule counter is periodically compared to a predetermined value. If any of the counter values exceed the predetermined value, it is concluded that the rules based expert system is stuck in an endless loop, and the inference engine is interrupted.
More specifically, and during a first pass, the inference engine executes a number of selected rules. The count is incremented for each of the rules that have their then type clause executed. In addition, the rules-based expert system maintains a listing of updated parameters, wherein the listing of updated parameters includes those parameters that are changed by the execution of a then type clause of the selected rules.
During a second pass, the inference engine determines which of the number of rules have an if type clause that is dependent on one or more of the parameters in the listing of updated parameters. The inference engine then re-executes those rules, and updates the listing of updated parameters. The count is also updated for those rules that have their then type clause re-executed.
The inference engine continues to re-execute those rules that are determined to have an if type clause that is dependent on one or more of the parameters in the listing of updated parameters, update the listing of updated parameters, and increment the corresponding counters until either the listing of updated parameters becomes empty or the count corresponding to any of the number of selected rules exceeds a predetermined value.
It is contemplated that the present invention may be implemented either in hardware, software or a combination thereof. When implemented in hardware, a counting means may be provided for maintaining a count for each of a number of rules. A comparing means may be provided for comparing the count for each of the number of rules to a predetermined value. Finally, an interrupting means may be provided for interrupting the system if the count corresponding to any of the number of rules exceeds a predetermined value.
REFERENCES:
patent: 5129043 (1992-07-01), Yue
patent: 5191638 (1993-03-01), Wakami et al.
patent: 5283856 (1994-02-01), Gross et al.
patent: 5412802 (1995-05-01), Fujinami et al.
patent: 5442792 (1995-08-01), Chun
patent: 5446883 (1995-08-01), Kirkbride et al.
patent: 5701400 (1997-12-01), Amado
patent: 5758031 (1998-0
Austin Thomas K.
Lautzenheiser Ted G.
Peters Thomas R.
Johnson Charles A.
Khatri Anil
Nawrocki, Rooney & Sivertson P.A.
Starr Mark T.
Unisys Corporation
LandOfFree
Method and apparatus for detecting an endless loop in a... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for detecting an endless loop in a..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for detecting an endless loop in a... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3002394