Method and apparatus for detecting an endless loop in a rules-based expert system

• US 6,546,380 B1
• Filed: 09/24/1997
• Issued: 04/08/2003
• Est. Priority Date: 09/24/1997
• Status: Expired due to Term

• Current Assignee: Unisys Corporation
• Original Assignee: Unisys Corporation
• Inventors: Austin, Thomas K., Lautzenheiser, Ted G., Peters, Thomas R.
• Primary Examiner(s): Khatri, Anil
• Application Number:
  US08/937,353
• Time in Patent Office: 2,022 Days
• Field of Search: 395/706, 395/708, 706/47, 706/48, 706/60, 706/52, 706/45, 707/10, 707/3, 707/7, 704/240
• US Class Current: 706/47
• CPC Class Codes: G06N 5/022 Knowledge engineering; Knowledge acquisition

Abstract

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, it is concluded that the rules-based expert system is stuck in an endless loop, and the rules-based expert system is interrupted.

Claims

1. A method for determining if a rules based expert system is stuck in a loop, the method comprising the steps of:

a. maintaining a count for each of a number of rules, the count indicating the number of times a corresponding rule is executed by the rules based expert system; and

b. interrupting the rules based expert system if the count corresponding to any of the rules exceeds a predetermined value.

2. A method according to claim 1 wherein the rules based expert system includes an inference engine.

3. A method according to claim 2 wherein the interrupting step 1(b) interrupts the inference engine from processing the rules if the count corresponding to any of the rules exceeds the predetermined value.

4. A method according to claim 3 wherein each of the number of rules includes an if type clause which specifies an expression, and a then type clause, wherein during execution the then type clause is executed only if the expression of the if type clause is satisfied.

5. A method according to claim 4 wherein the expression of the if type clause is dependent on one or more parameters.

6. A method according to claim 5 wherein the then type clause of selected rules changes one or more parameters.

7. A method according to claim:

6 wherein the inference engine 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 one of the number of rules.

8. A method according to claim 7 wherein 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.

9. A method according to claim 8 wherein the inference engine re-executes 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.

10. A method according to claim 9 wherein the inference engine updates the listing of updated parameters during the re-executing step of claim 9.

11. A method according to claim 10 wherein the inference engine continues to determine 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, re-executes 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 and updates the listing of updated parameters during the re-executing step until the listing of updated parameters becomes empty or until the count of step 1(a) corresponding to any of the number of rules exceeds the predetermined value.

12. A method for determining if a rules based expert system is stuck in a loop, the rules based expert system executing a number of rules wherein each of the rules includes an if type clause which specifies an expression, and a then type clause that is executed only if the expression of the if type clause is true, the expression of the if type clause of selected rules being dependent on one or more parameters, the then type clause of selected rules changing one or more parameters, the method comprising the step of:

a. executing a number of selected rules;

b. maintaining a count for each of the number of selected rules, wherein the count indicates the number of times that the then type clause of the corresponding rule is executed;

c. maintaining 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;

d. determining 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;

e. re-executing 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;

f. updating the listing of updated parameters as a result of the re-executing step 12(e);

g. updating the count for those rules re-executed in step 12(e); and

h. repeating steps 12(d)-12(g) until either the listing of updated parameters becomes empty or the count corresponding to any of the number of selected rules exceeds the predetermined value.

13. Apparatus for determining if a rules based expert system is stuck in a loop, comprising:

a. counting means for maintaining a count for each of a number of rules, the count indicating the number of times a corresponding rule is executed by the rules based expert system;

b. comparing means for comparing the count for each of the number of rules to a predetermined value; and

c. interrupting means for interrupting the rules based expert system if the count corresponding to any of the number of rules exceeds the predetermined value.

14. An apparatus according to claim 13 wherein the rules based expert system includes an inference engine block.

15. An apparatus according to claim 14 wherein the interrupting means interrupts the inference engine block from processing the rules if the count corresponding to any of the rules exceeds the predetermined value.

16. An apparatus according to claim 15 wherein each of the number of rules includes an if type clause which specifies an expression, and a then type clause, wherein during execution the then type clause is executed only if the expression of the if type clause is satisfied.

17. An apparatus according to claim 15 wherein the expression of the if type clause is dependent on one or more parameters.

18. An apparatus according to claim 17 wherein the then type clause of selected rules changes one or more parameters.

19. An apparatus according to claim 18 wherein the inference engine block 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 one of the number of rules.

20. An apparatus according to claim 19 wherein the inference engine block 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.

21. An apparatus according to claim 20 wherein the inference engine block re-executes those rules that are determined to have an if type claus,e that is dependent on one or more of the parameters in the listing of updated parameters.

22. An apparatus according to claim 21 wherein the inference engine block updates the listing of updated parameters when the inference engine block re-executes 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.

23. An apparatus according to claim 22 wherein the inference engine block continues to determine 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, re-executes 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, and updates the listing of updated parameters during the re-executing step until the listing of updated parameters becomes empty or until the count corresponding to any of the number of rules exceeds the predetermined value.