VLSI hardware implemented rule-based expert system apparatus and method

• US 5,218,669 A
• Filed: 03/07/1990
• Issued: 06/08/1993
• Est. Priority Date: 03/11/1988
• Status: Expired due to Term

• Current Assignee: Ricoh Company Limited
• Original Assignee: International Chip Corporation, Ricoh Company Limited
• Inventors: Kobayashi, Hideaki, Shindo, Masahiro
• Primary Examiner(s): MacDonald, Allen R.
• Application Number:
  US07/489,892
• Time in Patent Office: 1,189 Days
• Field of Search: 364/513, 395/51, 395/52, 395/54, 395/11
• US Class Current: 706/47
• CPC Class Codes: G06N 5/046 Forward inferencing; Production systems

Abstract

The hardware-implemented rule-based expert system of this invention is suitable for performing high speed inferencing in artificial intelligence (AI) applications, and is characterized by being domain independent so that it can be applied to a variety of different application domains. The expert system includes a working memory in which, at the beginning of an inferencing operation, is stored known information or facts pertaining to the application domain. Additionally, a rule memory is provided for storing a rule set for the application domain. The rule set is comprised of a series of instructions, each defining a condition or an action. Instructions are successively loaded from the rule memory into via a first data bus. The logic unit successively executes the instructions in working memory with reference to the stored facts in working memory to thereby deduce new facts. The logic unit is coupled to working memory via a second data bus. During the inferencing operation, as new facts are deduced, they are stored in working memory and may be used for the execution of subsequent instructions. Upon the completion of the inferencing operation, an input/output interface transfers the facts stored in working memory to an output device.

Claims

1. A hardware-implemented rule-based expert system apparatus suitable for performing high speed inferencing based upon a rule set for an application domain, comprising:

working memory means for storing therein facts pertaining to the application domain;

rule memory means for storing therein the rule set for the application domain, comprised of a series of instructions each defining a condition or an action;

logic means;

a first communications bus for communicatively connecting said working memory means to said logic means;

a second communications bus for communicatively connecting said rule memory means to said logic means;

said logic means comprising means for successively executing the instructions in said rule memory means obtained via said second communications bus, with reference to the stored facts in said working memory means obtained via said first communications bus, to thereby deduce new facts at high speed, and for storing the deduced new facts in said memory means;

host computer means communicatively connected to said working memory means, for providing the facts pertaining to the application domain to said working memory means and for accepting the deduced new facts from said working memory means; and

wherein each of the instructions of said rule set includes an operator, a condition/action flag, and a pair of operands; and

wherein said logic means includes an instruction decoder for testing said condition/action flag to determine whether the instruction is a condition or an action;

means operable if the instruction is a condition for comparing the operands in accordance with the logical operation specified by the operator to generate a logic result; and

means operable if the instruction is an action for performing the action specified by the operator on the operands.

2. The system of claim 1 wherein said logic means includes means operable if the logic result of said comparing means is TRUE for effecting fetching of the next instruction of the same rule.

3. The system of claim 1 wherein said logic means includes means operable if the logic result of said comparing means is FALSE for effecting fetching of the first instruction of the next rule.

4. The system of claim 1 wherein each of said instructions also includes a direct/immediate flag for specifying the addressing mode of one of the operands.

5. A hardware-implemented rule-based expert system apparatus suitable for performing high speed inferencing based upon a rule set for an application domain, comprising:

working memory means for storing therein facts pertaining to the application domain;

rule memory means for storing therein the rule set for the application domain, comprised of a series of instructions each defining a condition or an action;

logic means;

a first communications bus for communicatively connecting said working memory means to said logic means;

a second communications bus for communicatively connecting said rule memory means to said logic means;

said logic means comprising means for successively executing the instructions in said rule memory means obtained via said second communications bus, with reference to the stored facts in said working memory means obtained via said first communications bus, to thereby deduce new facts at high speed, and for storing the deduced new facts in said memory means;

host computer means communicatively connected to said working memory means, for providing the facts pertaining to the application domain to said working memory means and for accepting the deduced new facts from said working memory means; and

wherein at least one of said instructions of each rule represents a condition to be satisfied by the facts of a given problem and including;

(i) an operation code defining a logical operation to be performed;

(ii) a first operand defining a first value to be compared by said logical operation; and

(iii) a second operand defining the address in said working memory containing a second value to be compared by said logical operation.

6. A hardware-implemented rule-based expert system apparatus suitable for performing high speed inferencing based upon a rule set for an application domain, comprising:

working memory means for storing therein facts pertaining to the application domain;

rule memory means for storing therein the rule set for the application domain, comprised of a series of instructions each defining a condition or an action;

logic means;

a first communications bus for communicatively connecting said working memory means to said logic means;

a second communications bus for communicatively connecting said rule memory means to said logic means;

said logic means comprising means for successively executing the instructions in said rule memory means obtained via said second communications bus, with reference to the stored facts in said working memory means obtained via said first communications bus, to thereby deduce new facts at high speed, and for storing the deduced new facts in said memory means;

host computer means communicatively connected to said working memory means, for providing the facts pertaining to the application domain to said working memory means and for accepting the deduced new facts from said working memory means; and

wherein said rule set comprises a series of instructions in successive memory addresses beginning at one end of said rule memory means, and additionally including means for storing a rule index in successive memory addresses beginning at the opposite end of said rule memory means, the rule index comprising a series of memory addresses defining the beginning memory address of each rule of said rule set.

7. A hardware-implemented rule-based expert system apparatus suitable for performing high speed inferencing based upon a rule set for an application domain, comprising:

working memory means for storing therein facts pertaining to the application domain;

rule memory means for storing therein the rule set for the application domain, comprised of a series of instructions each defining a condition or an action;

logic means;

a first communications bus for communicatively connecting said working memory means to said logic means;

a second communications bus for communicatively connecting said rule memory means to said logic means;

said logic means comprising means for successively executing the instructions in said rule memory means obtained via said second communications bus, with reference to the stored facts in said working memory means obtained via said first communications bus, to thereby deduce new facts at high speed, and for storing the deduced new facts in said memory means;

host computer means communicatively connected to said working memory means, for providing the facts pertaining to the application domain to said working memory means and for accepting the deduced new facts from said working memory means; and

wherein at least one of said instructions of each rule represents an action to be performed if all of the conditions of the rule are satisfied, and including;

(i) an operation code defining the action to be performed; and

(ii) a first operand defining a value for a fact, and

(iii) a second operand defining the address in said working memory means where the value defined in the first operand is to be stored.

8. The system of claim 7 wherein said means for successively executing instructions in said rule memory means comprises rule memory counter means including an address register for storing the address of the current instruction in said rule memory means;

and means for updating said address register with the address of the next instruction each time an instructions fetched from said rule memory means.

9. The system of claim 7 further comprising means for loading the rule set into said rule memory means in forward chaining order;

and wherein said logic means successively executes the instructions in said rule memory means to perform forward chaining inferencing upon the loaded rule set, and thereby deduce the new facts at high speed.

10. The system of claim 7 further comprising means for loading the rule set into said rule memory means in backward chaining order;

and wherein said logic means successively executes the instruction in said rule memory means to perform backward chaining inferencing upon the loaded rule set, and thereby deduce the new facts at high speed.

11. The system of claim 7 further comprising means for loading the rule set into said rule memory means in combination chaining order;

and wherein said logic means successively executes the instructions in said rule memory means to perform combination chaining inferencing upon the loaded rule set, and thereby deduce the new facts at high speed.

12. A hardware-implemented rule-based expert system apparatus suitable for performing high speed inferencing based upon a rule set for an application domain, comprising:

working memory means for storing therein facts pertaining to the application domain;

rule memory means for storing therein the rule set for the application domain, comprised of a series of instructions each defining a condition or an action;

logic means;

a first communications bus for communicatively connecting said working memory means to said logic means;

a second communications bus for communicatively connecting said rule memory means to said logic means;

said logic means comprising means for successively executing the instructions in said rule memory means obtained via said second communications bus, with reference to the stored facts in said working memory means obtained via said first communications bus, to thereby deduce new facts at high speed; and

wherein at least one of said instructions of each rule represents an action to be performed if all of the conditions of the rule are satisfied, and including;

(i) an operation code defining the action to be performed; and

(ii) a first operand defining a value for a fact, and

(iii) a second operand defining the address in said working memory where the value defined in the first operand is to be stored.

13. A hardware-implemented rule-based expert system apparatus suitable for performing high speed inferencing based upon a rule set for an application domain, comprising:

working memory means for storing therein facts pertaining to the application domain;

rule memory means for storing therein the rule set for the application domain, comprised of a series of instructions each defining a condition or an action;

logic means;

a first communications bus for communicatively connecting said working memory means to said logic means;

a second communications bus for communicatively connecting said rule memory means to said logic means;

said logic means comprising means for successively executing the instructions in said rule memory means obtained via said second communications bus, with reference to the stored facts in said working memory means obtained via said first communications bus, to thereby deduce new facts at high speed; and

wherein said rule set is stored as a series of instructions in successive memory addresses beginning at one end of said rule memory means, and additionally includes means for storing a rule index in successive memory addresses beginning at the opposite end of said rule memory means, the rule index comprising a series of memory addresses defining the beginning memory address of each rule of said rule set.

14. A hardware-implemented rule-based expert system apparatus suitable for performing high speed inferencing based upon a rule set for an application domain, comprising:

working memory means for storing therein facts pertaining to the application domain;

rule memory means for storing therein the rule set for the application domain, comprised of a series of instructions each defining a condition or an action;

logic means;

a first bidirectional communications bus for communicatively connecting said working memory means and said logic means;

a second unidirectional communications bus for communicatively connecting said rule memory means to said logic means;

said logic means comprising means for successively executing the instructions in said rule memory means obtained via said second communications bus, with reference to the stored facts in said working memory means obtained via said first communications bus, to thereby deduce new facts at high speed, for storing the deduced new facts in said working memory means; and

an input-output interface means, and a bidirectional input-output interface bus communicatively connecting said working memory means and said input-output interface means, for storing in said working memory from an external system, the facts pertaining to the application domain and for transferring the deduced new facts stored in said working memory to an external system; and

wherein at least one of said instructions of each rule represents a condition to be satisfied by the facts of a given problem and including;

(i) an operation code defining a logical operation be performed;

(ii) a first operand defining a first value to be compared by said logical operation; and

(iii) a second operand defining the address in said working memory a second value to be compared by said logical operation.

15. A hardware-implemented rule-based expert system apparatus suitable for performing high speed inferencing based upon a rule set for an application domain, comprising:

working memory means for storing therein facts pertaining to the application domain;

rule memory means for storing therein the rule set for the application domain, comprised of a series of instructions each defining a condition or an action;

logic means;

a first communications bus for communicatively connecting said working memory means to said logic means;

a second communications bus for communicatively connecting said rule memory means to said logic means;

said logic means comprising means for successively executing the instructions in said rule memory means obtained via said second communications bus, with reference to the stored facts in said working memory means obtained via said first communications bus, to thereby deduce new facts at high speed; and

wherein at least one of said instructions of each rule represent a condition to be satisfied by the facts of a given problem and including;

(i) an operation code defining a logical operation to be performed;

(ii) a first operand defining a first value to be compared by said logical operation; and

(iii) a second operand defining the address in said working memory containing a second value to be compared by said logical operation.

16. The system of claim 15 wherein said means for successively executing instructions in said rule memory means comprises rule memory counter means including an address register for storing the address of the current instruction in said rule memory means;

and means for updating said address register with the address of the next instruction each time an instruction is fetched form said rule memory means.

17. The system of claim 15 further comprising means for loading the rule set into said rule memory means in forward chaining order;

and wherein said logic means successively executes the instructions in said rule memory means to perform forward chaining inferencing upon the loaded rule set, and thereby deduce the new facts at high speed.

18. The system of claim 15 further comprising means for loading the rule set into said rule memory means in backward chaining order;

and wherein said logic means successively executes the instructions in said rule memory means to perform backward chaining inferencing upon the loaded rule set, and thereby deduce the new facts at high speed.

19. The system of claim 15 further comprising means for loading the rule set into said rule memory means in combination chaining order;

and wherein said logic means successively executes the instructions in said rule memory means to perform combination chaining inferencing upon the loaded rule set, and thereby deduce the new facts at high speed.

20. The system of claim 15 further comprising:

host computer means communicatively connected to said hardware-implemented rule-based expert system, for providing the facts pertaining to the application domain to said working memory means and for accepting the deduced new facts from said hardware-implement rule-based expert system.

21. The system of claim 15 further comprising:

host computer means communicatively connected to said memory means, for providing the facts pertaining to the application domain to said working memory means and for accepting the deduced new facts from said working memory means.

22. A hardware-implemented rule-based expert system apparatus suitable for performing high speed inferencing based upon a rule set for an application domain, comprising:

working memory means for storing therein facts pertaining to the application domain;

rule memory means for storing therein the rule set for the application domain, comprised of a series of instructions each defining a condition or an action;

logic means;

a first bidirectional communications bus for communicatively connecting said working memory means and said logic means;

a second unidirectional communications bus for communicatively connecting said rule memory means to said logic means;

said logic means comprising means for successively executing the instructions in said rule memory means obtained via said second communications bus, with reference to the stored facts in said working memory means obtained via said first communications bus, to thereby deduce new facts at high speed, for storing the deduced new facts in said working memory means;

an input-output interface means, and a bidirectional input-output interface bus communicatively connecting said working memory means and said input-output interface means, for storing in said working memory from an external system, the facts pertaining to the application domain and for transferring the deduced new facts stored in said working memory to an external system; and

wherein at least one of said instructions of each rule represents an action to be performed if all of the conditions of the rule are satisfied, and including;

(i) an operation code defining the action to be performed; and

(ii) a first operand defining a value for a fact, and

(iii) a second operand defining an address in said working memory means where the value defined in the first operand is to be stored.

23. A hardware-implemented rule-based expert system apparatus suitable for performing high speed inferencing based upon a rule set for an application domain, comprising:

working memory means for storing therein facts pertaining to the application domain;

rule memory means for storing therein the rule set for the application domain, comprised of a series of instructions each defining a condition or an action;

logic means;

a first bidirectional communications bus for communicatively connecting said working memory means and said logic means;

a second unidirectional communications bus for communicatively connecting said rule memory means to said logic means;

said logic means comprising means for successively executing the instructions in said rule memory means obtained via said second communications bus, with reference to the stored facts in said working memory means obtained via said first communications bus, to thereby deduce new facts at high speed, for storing the deduced new facts in said working memory means; and

an input-output interface means, and a bidirectional input-output interface bus communicatively connecting said working memory means and said input-output interface means, for storing in said working memory from an external system, the facts pertaining to the application domain and for transferring the deduced new facts storing in said working memory to an external system; and

wherein said rule set is stored as a series of instructions in successive memory addresses beginning at one end of said rule memory means, and additionally includes means for storing a rule index in successive memory addresses beginning at the opposite end of said rule memory means, the rule index comprising a series of memory addresses defining the beginning memory address of each rule of said rule set.

24. A hardware-implemented rule-based expert system apparatus suitable for performing high speed inferencing based upon a rule set for an application domain, comprising:

working memory means for storing therein facts pertaining to the application domain;

rule memory means for storing therein the rule set for the application domain, comprised of a series of instructions each defining a condition or an action;

logic means;

a first bidirectional communications bus for communicatively connecting said working memory means and said logic means;

a second unidirectional communications bus for communicatively connecting said rule memory means to said logic means;

said logic means comprising means for successively executing the instructions in said rule memory means obtained via said second communications bus, with reference to the stored facts in said working memory means obtained via said first communications bus, to thereby deduce new facts at high speed, for storing the deduced new facts in said working memory means;

an input-output interface means, and a bidirectional input-output interface bus communicatively connecting said working memory means and said input-output interface means, for storing in said working memory from an external system, the facts pertaining to the application domain and for transferring the deduced new facts storing in said working memory to an external system; and

wherein each of the instructions of said rule set includes an operator, a condition/action flag, and a pair of operands; and

wherein said logic means includes an instruction decoder for testing said condition/action flag to determine whether the instruction is a condition or an action;

means operable if the instruction is a condition for comparing the operands in accordance with the logical operation specified by the operator to generate a logic result; and

means operable if the instruction is an action for performing the action specified by the operator on the operands.

25. The system of claim 24 wherein said logic means includes means operable if the logic result of said comparing means is TRUE for effecting fetching of the next instruction of the same rule.

26. The system of claim 24 wherein said logic means includes means operable if the logic result of said comparing means is FALSE for effecting fetching of the first instruction of the next rule.

27. The system of claim 24 wherein each of said instructions also includes a direct/immediate flag for specifying the addressing mode of one of the operands.

28. The system of claim 24 further comprising means for loading the rule set into said rule memory means in backward chaining order;

and wherein said logic means successively executes the instruction in said rule memory means to perform backward chaining inferencing upon the loaded rule set, and thereby deduce the new facts at high speed.

29. The system of claim 24 further comprising means for loading the rule set into said rule memory means in combination chaining order;

and wherein said logic means successively executes the instructions in said rule memory means to perform combination chaining inferencing upon the loaded rule set, and thereby deduce the new facts at high speed.

30. The system of claim 24 further comprising:

host computer means communicatively connected to said input-output interface means, for providing the facts pertaining to the application domain to said input-output interface means and for accepting the deduced new facts from said input-output interface means.

31. The system of claim 24 wherein said means for successively executing instructions in said rule memory means comprises rule memory counter means including an address register for storing the address of the current instruction in said rule memory means;

and means for updating said address register with the address of the next instruction each time an instruction is fetched from said rule memory means.

32. The system of claim 24 further comprising means for loading the rule set into said rule memory means in forward chaining order;

and wherein said logic means successively executes the instructions in said rule memory means to perform forward chaining inferencing upon the loaded rule set, and thereby deduce the new facts at high speed.

33. A hardware-implemented rule-based expert system apparatus suitable for performing high speed inferencing based upon a rule set for an application domain, comprising:

logic means;

working memory means for storing therein facts pertaining to the application domain;

rule memory means for storing therein the rule set for the application domain, comprised of a series of instructions each defining a condition or an action each of the instructions of said rule set including an operator, a condition/action flag, and a pair of operands;

a first communications bus for communicatively connecting said working memory means to said logic means; and

a second communications bus for communicatively connecting said rule memory means to said logic means;

said logic means comprising means for success executing the instructions in said rule memory means obtained via said second communications bus, with reference to the stored facts in said working memory means obtained via said first communications bus, to thereby deduce new facts at high speed;

said logic means further comprising an instruction decoder for testing said condition/action flag to determine whether the instruction is a condition or an action;

means operable if the instruction is a condition for comparing the operands in accordance with the logical operation specified by the operator to generate a logic result; and

means operable if the instruction is an action for performing the action specified by the operator on the operands.

34. The system of claim 33 further comprising:

host computer means communicatively connected to said working memory means, for providing the facts pertaining to the application domain to said working memory means and for accepting the deduced new facts from said working memory means.

35. The system of claim 33 further comprising:

host computer means communicatively connected to said hardware-implement rule-based expert system, for providing the facts pertaining to the application domain to said working memory means and for accepting the deduced new facts from aid hardware-implemented rule-based expert system.

36. The system of claim 33 wherein said means for successively executing instructions in said rule memory means comprises rule memory counter means including an address register for storing the address of the current instruction in said rule memory means;

and means for updating said address register with the address of the next instruction each time an instruction is fetched from said rule memory means.

37. The system of claim 36 wherein said logic means further comprises means for storing the deduced new facts in said working memory means;

wherein said first communications bus comprises a bidirectional communications bus for loading the facts pertaining to the application domain from said working memory means into said logic means and for storing the new facts deduced by said logic means into said working memory means; and

wherein said second communications bus comprises a unidirectional communications bus for loading the instructions defining a condition or an action from said rule memory means into said logic means.

38. The system of claim 33 wherein said logic means further comprises means for storing the deduced new facts in said working memory means;

and wherein said system further comprises output means for transferring the deduced new facts stored in said working memory to an output device.

39. The system of claim 38 wherein said output means comprises an input-output interface and an input-output interface bus communicatively interconnecting said input-output interface to said working memory means.

40. The system of claim 33 wherein said rule set is stored as a series of instructions in successive memory addresses beginning at one end of said rule memory means, and additionally includes means for storing a rule index in successive memory addresses beginning at the opposite end of said rule memory means, the rule index comprising a series of memory addresses defining the beginning memory address of each rule of said rule set.

41. The system of claim 33 wherein said logic means includes mean operable if the logic result of said comparing means is TRUE for effecting fetching of the next instruction of the same rule.

42. The system of claim 33 wherein said logic means includes means operable if the logic result of said comparing means is FALSE for effecting fetching the first instruction of the next rule.

43. The system of claim 33 wherein each of said instructions also includes a direct/immediate flag for specifying the addressing mode of one of the operands.

44. The system of claim 33 further comprising means for loading the rule set for the application domain into said rule memory means.

45. The system of claim 44 wherein said means for loading the rule set for the application domain into said rule memory means comprises means for loading the rule set into said rule memory means in combination chaining order;

and wherein said logic means successively executes the instructions in said rule memory means to perform combination chaining inferencing upon the loaded rule set, and thereby deduce the new facts at high speed.

46. The system of claim 44 wherein said means for loading the rule set for the application domain into said rule memory means comprises means for loading the rule set into said rule memory means in forward chaining order;

and wherein said logic means successively executes the instructions in said rule memory means to perform forward chaining inferencing upon the loaded rule set, and thereby deduce the new facts at high speed.

47. The system of claim 44 wherein said means for loading the rule set for the application domain into said rule memory means comprises means for loading the rule set into said rule memory means in backward chaining order;

and wherein said logic means successively executes the instructions in said rule memory means to perform backward chaining inferencing upon the loaded rule set, and thereby deduce the new facts at high speed.