Modular blackboard based expert system

• US 5,101,362 A
• Filed: 11/05/1990
• Issued: 03/31/1992
• Est. Priority Date: 12/14/1988
• Status: Expired due to Term

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Digital Equipment Corporation (HP Inc.)
• Inventors: Simoudis, Evangelos
• Primary Examiner(s): MacDonald, Allen R.
• Application Number:
  US07/609,032
• Time in Patent Office: 512 Days
• Field of Search: 364/513, 364/200
• US Class Current: 706/49
• CPC Class Codes: G06N 5/043 Distributed expert systems; Blackboards

Abstract

An expert system includes a blackboard, a plurality of knowledge sources, a control knowledge source and a control module. The blackboard stores data used during an execution cycle. Each knowledge source includes rules for performing selected operations in connection with the data in the blackboard. The control knowledge source includes selection rules for selecting among the knowledge sources. The control module performing an execution cycle including an eligibility determination phase to identify one or more of the knowledge sources, a knowledge source selection phase using the selection rules in said control knowledge source to select one of the identified knowledge sources, and an action phase to process a rule of the selected knowledge source.

Claims

1. A system comprising:

A. a blackboard for storing data;

B. means for defining a plurality of knowledge sources, the knowledge sources defining corresponding sets of operations to be performed in connection with said data in said blackboard;

C. means for defining selection operations for selecting one set of operations from among said set of operations to be performed in connection with said data in said blackboard;

D. means for performing an execution cycle, said execution cycle including an eligibility determination phase to identify one or more of the sets of operations as eligible sets of operations, a selection phase using said selection operations to select one of said identified eligible sets of operations, and an action phase to process at least one operation defined by the selected one of the sets of operations.

2. The system of claim 1 further comprising a rule base for storing a plurality of rules, each of said sets of operations including pointers to one or more rules in said rule base to define said operations.

3. The system of claim 2 wherein each of said sets of operations further defines scheduling information, said means for performing an execution cycle, processing, in said action phase, a plurality of said rules defined by said selected set of operations in an order determined by scheduling information associated with said selected one of the sets of operations.

4. The system of claim 1 further comprising a procedure base for storing a plurality of procedures, each of said sets of operations including pointers to one or more procedures in said procedure base to define said operations.

5. The system of claim 1 wherein each of said sets of operations further defines one or more eligibility determination operations, said eligibility determination operations being accessed during said eligibility determination phase.

6. The system of claim 5 further comprising a rule base for storing a plurality of rules, each of said sets of operations including pointers to one or more rules in said rule base to define said eligibility determination operations.

7. The system of claim 6 wherein each of said sets of operations further includes pointers to said rule base to define said operations.

8. The system of claim 6 wherein each of said sets of operations further defines scheduling information, said means for performing an execution cycle processing, in said eligibility determination phase, a plurality of said rules defined by the selected one of the sets of operations in an order determined by scheduling information associated with the selected one of the sets of operations.

9. The system of claim 5 further comprising a procedure base for storing a plurality of procedures, each of said sets of operations including pointers to one or more procedures in said procedure base to define said eligibility determination operations.

10. The system of claim 9 wherein each of said sets of operation further include pointers to said procedure base to define said operations.

11. The system of claim 1 further comprising a rule base for storing a plurality of rules and a procedure base for storing a plurality of procedures, each of said sets of operations including one or more pointers to one or more of said rules and procedures to define ;

said operations.

12. The system of claim 11 wherein each of said sets of operations includes pointers either to said rule base or to said procedure base.

13. The system of claim 11 wherein each of said sets of operations includes pointers to at least one rule and at least one procedure.

14. The system of claim 11 further comprising a control knowledge rule base including a plurality of rules, at least one of said rules used during said selection phase.

15. The system of claim 1 wherein said blackboard is divided into a plurality of regions, each of said regions storing a portion of said data.

16. The system of claim 15 wherein said means for performing an execution cycle obtains results associated with one or more operations processed in said action phase, and stores said results in one of said regions in said blackboard.

17. The system of claim 15 wherein each of said sets of operations includes an identifier that identifies one of said regions of said blackboard, said means for performing an execution cycle processing, in said action phase, said at least one operation defined by said selected one of the sets of operations in connection with data stored in a region of said blackboard identified by an identifier associated with said selected one of the sets of operations.

18. The system of claim 17 wherein each of said sets of operations includes a second identifier that identifies a second one of the regions in said blackboard, said means for performing an execution cycle storing results of an operation processed in said action phase in a region of said blackboard identified by a second identifier associated with said selected one of the sets of operations.

19. The system of claim 1 further comprising a control knowledge of rule base including a plurality of rules, at least one of said rules used during said selection phase.

20. The system of claim 1 wherein said system is a system for redesigning electronic circuitry.

21. The system of claim 20 wherein said data represents a simulation of the operation of said electronic circuitry.

22. A system comprising:

A. a blackboard for storing data;

B. a rule base for storing a plurality of rules;

C. a procedure base for storing a plurality of procedures;

D. a plurality of sets of data operation pointers which identify one or more rules and procedures to define operations to be performed in connection with said data and one or more eligibility operation pointers which identify one or more rules and procedures to define eligibility determination operations;

E. means for defining selection operations for selecting one set of data operation pointers from among the plurality of sets of data operation pointers; and

F. means for performing an execution cycle including;

i. an eligibility determination phase to identify one or more of the sets of operation pointers as eligible sets of data operation pointers by, for each one of the sets of data operation pointers, accessing corresponding eligibility operation pointers and processing eligibility determination operations identified by said eligibility operation pointers;

ii. a selection phase using said selection operations to select one of said identified eligible sets of data operation pointers; and

iii. an action phase to process one or more data operations identified by data operation pointers corresponding to said selected one of the sets of data operation pointers.

23. The system of claim 22 wherein each of said sets of data operation pointers includes pointers to at least one rule and at least one procedure.

24. A system for redesigning electronic circuitry comprising:

A. a blackboard for storing data representing a simulation of the operation of said electronic circuitry;

B. means for defining a plurality of sets of redesign operations to be performed in connection with said data in said blackboard;

C. means for defining selection operations for selecting one set of redesign operations from among said plurality of sets of redesign operations;

D. means for performing an execution cycle, said cycle including an eligibility determination phase to identify one or more of the plurality of sets of redesign operations, as eligible sets of redesign operations, a selection phase using said selection operations to select one of said identified eligible sets of operations, and an action phase to process at least one redesign operation.

25. The system of claim 24 wherein said blackboard is divided into a plurality of regions, each of said regions storing simulation data corresponding to different simulations of the operation of said electronic circuitry.

26. The system of claim 25 wherein each of said simulations corresponds to simulations of varying levels of complexity.

27. The system of claim 25 wherein each of said sets of redesign operations includes an identifier that identifies one of said regions of said blackboard, said means for performing an execution cycle, in said action phase, processing said at least one operation defined by said selected one of the sets of redesign operations in connection with data stored in a region of said blackboard identified by an identifier associated with said selected one of the sets of redesign operations.

28. The system of claim 27 wherein each of said sets of redesign operations includes a second identifier that identifies a second one of said regions in said blackboard, said means for performing an execution cycle storing results of an operation processed in said action phase in a region of said blackboard identified by a second identifier associated with said selected one of the sets of said redesign operations.

29. A method for processing operations in a system comprising a blackboard for storing data, a plurality of knowledge sources, each of which defines one or more selected operations to be performed in connection with said data in said blackboard, and a control knowledge source defining selection operations for selecting one knowledge source from among a plurality of identified knowledge sources, said method comprising the steps of:

A. identifying one or more of the knowledge sources as eligible knowledge sources;

B. selecting one of said identified eligible knowledge sources using said selection apparatus in said control knowledge source; and

C. processing at least one operation defined by said selected knowledge source.

30. The system of claim 29 further comprising a rule base for storing a plurality of rules, each of said knowledge sources including pointers to one or more rules in said rule base to define said selected operations.

31. The system of claim 30 wherein each of said knowledge sources further defines scheduling information, and wherein said processing step comprises processing a plurality of said rules in an order determined by scheduling information associated with said selected knowledge source.

32. The system of claim 29 further comprising a procedure base for storing a plurality of procedures, each of said knowledge sources including pointers to one or more procedures in said procedure base to define said selected operations.

33. The system of claim 29 wherein each of said knowledge sources further defines one or more eligibility determination operations, said eligibility determination operations being used in said step of identifying.

34. The system of claim 33 further comprising a rule base for storing a plurality of rules, each of said knowledge sources including pointers to one or more rules in said rule base to define said eligibility determination operations.

35. The system of claim 34 wherein each of said knowledge sources further includes pointers to said rule base to define said selected operations.

36. The system of claim 34 wherein each of said knowledge sources further defines scheduling information, and wherein said identifying step comprises processing, for each of said knowledge sources, a plurality of said rules in an order determined by scheduling information associated with each respective knowledge source.

37. The system of claim 33 further comprising a procedure base for storing a plurality of procedures, each of said knowledge sources including pointers to one or more procedures in said procedure base to define said eligibility determination operations.

38. The system of claim 37 wherein each of said knowledge sources further includes pointers to said procedure base to define said selected operations.

39. The system of claim 29 further comprising a rule base for storing a plurality of rules and a procedure base for storing a plurality of procedures, each of said knowledge sources including one or more pointers to one or more of said rules and procedures to define said selected operations.

40. The system of claim 39 wherein each of said knowledge sources includes pointers either to said rule base or to said procedure base.

41. The system of claim 39 wherein each of said knowledge sources includes pointers to at least one rule and at least one procedure.

42. The system of claim 29 wherein said blackboard is divided into a plurality of regions, each of said regions storing a portion of said data.

43. The system of claim 42 further comprising the step of storing said results associated with said processing step in a said region in said blackboard.

44. The system of claim 42 wherein each of said knowledge sources includes an identifier that identifies a said regions of said blackboard, said processing step comprising processing said at least one operation defined by said selected knowledge source in connection with data stored in a region of said blackboard identified by an identifier associated with said selected knowledge source.

45. The system of claim 44 wherein each of said knowledge sources include a second identifier that identifies a said region in said blackboard, said method further comprising the step of storing results of an operation processed in said action phase in a region of said blackboard identified by a second identifier associated with said selected knowledge source.

46. The system of claim 29 further comprising a control knowledge rule base including a plurality of rules, at least one of said rules used in said selection step.

47. The system of claim 39 further comprising a control knowledge rule base including a plurality of rules, at least one of said rules used in said selection step.

48. The system of claim 29 wherein said system is a system for redesigning electronic circuitry.

49. The system of claim 48 wherein said data represents a simulation of the operation of said electronic circuitry.

50. A method for processing operations in a system comprising a blackboard for storing data, a rule base for storing a plurality of rules, a procedure base for storing a plurality of procedures, a plurality of knowledge sources each of which defines one or more data operation pointers which identify one or more rules and procedures to define operations to be performed in connection with said data and one or more eligibility operation pointers which identify one or more rules and procedures to define eligibility determination operations, said method comprising the steps of:

A. identifying one or more of the knowledge sources as eligible knowledge sources by, for each knowledge source, accessing corresponding eligibility operation pointers and processing eligibility determination operations identified by said eligibility operation pointers;

B. selecting one of said identified eligible knowledge sources using said selection operations in said control knowledge source; and

C. processing one or more data operations identified by data operation pointers corresponding to said selected knowledge source.

51. The method of claim 50 wherein each of said knowledge sources includes pointers to at least one rule and at least one procedure.

52. A method for processing operations in a system for redesigning electronic circuitry, said system comprising a blackboard for storing data representing a simulation of the operation of said electronic circuitry, a plurality of knowledge sources, each of which defines one or more selected redesign operations to be performed in connection with said data in said blackboard, and a control knowledge source defining selection operations for selecting one knowledge source from among a plurality of identified knowledge sources, said method comprising the steps of:

A. identifying one or more of the knowledge sources as eligible knowledge sources;

B. selecting one of said identified eligible knowledge sources using said selection apparats in said control knowledge source; and

C. processing at least one redesign operation defined by said selected knowledge source.

53. The system of claim 52 wherein said blackboard is divided into a plurality of regions, each of said regions storing simulation data corresponding to different simulations of the operation of said electronic circuitry.

54. The system of claim 53 wherein each of said simulations correspond to simulations of varying levels of complexity.

55. The system of claim 53 wherein each of said knowledge sources includes an identifier that identifies a said regions of said blackboard, said processing step comprising processing said at least one operation defined by said selected knowledge source in connection with data stored in a region of said blackboard identified by an identifier associated with said selected knowledge source.

56. The system of claim 55 wherein each of said knowledge sources includes a second identifier that identifies a said region in said blackboard, said method further comprising the step of storing results of an operation processed in said action phase in a region of said blackboard identified by a second identifier associated with said selected knowledge source.