Hierarchical knowledge system

• US 4,591,983 A
• Filed: 07/09/1984
• Issued: 05/27/1986
• Est. Priority Date: 07/09/1984
• Status: Expired due to Term

• Current Assignee: Teknowledge Corporation
• Original Assignee: Teknowledge Corporation
• Inventors: Bennett, James S., Lark, Jay S.
• Primary Examiner(s): Harkcom, Gary V.
• Application Number:
  US06/628,817
• Time in Patent Office: 687 Days
• Field of Search: 364/400-401, 364/403, 364/468-469, 364/478, 364/513, 364/518, 209/1-2, 209/546, 209/552, 235/385, 29/33 K, 29/33 R, 29/400 R, 29/400 M, 29/428-431, 29/469, 29/564, 29/568, 29/700-703, 29/711
• US Class Current: 706/53
• CPC Class Codes: G05B 19/41865 characterised by job scheduling, process planning, material flow
• CPC Class Codes: G06Q 10/087 Inventory or stock management, e.g. order filling, procurement or balancing against orders
• CPC Class Codes: G06Q 10/0875 Itemisation or classification of parts, supplies or services, e.g. bill of materials
• CPC Class Codes: Y02P 90/02 Total factory control, e.g. smart factories, flexible manufacturing systems [FMS] or integrated manufacturing systems [IMS]
• CPC Class Codes: Y10S 706/904 Manufacturing or machine, e.g. agricultural machinery, machine tool
• CPC Class Codes: Y10T 29/53013 Computer input

Abstract

A knowledge system has a hierarchical knowledge base comprising a functional decomposition of a set of elements into subsets over a plurality of hierarchical levels, a plurality of predefined functions or conditions of the elements within the subsets of a plurality of the hierarchical levels, and a predefined set of operations to perform on a user-defined set of elements responsive to the functional knowledge base. Preferably, the knowledge base is defined declaratively by assigning parent sets to offspring subsets to define the hierarchy, by indicating the conditions of the subsets which satisfy the predefined functions and by writing task blocks in an imperative language defining the sequence of operations to perform on the user-defined set of elements. Preferably the operations include matching, configuring and expanding the user-defined set of elements into the defined subsets of individual elements and evaluating the predefined functions, and the operations are executed recursively. In a specific embodiment the elements are available components for a system or item of manufacture, and the subsets of elements are sub-assemblies or functionally related components. The predefined functions define condition-action constraints to insure that the sub-assemblies have compatible components. Such a knowledge system has general applicability, is easy to maintain and incrementally modify, has transparent representation of the functional decomposition and the configuration operations, and provides explanation for an assessment of the configuration.

Claims

1. A knowledge system comprising a computer having a memory storing a knowledge base, said knowledge base including

predefined descriptions of assemblies of predefined components for indicating whether a specified component is permitted in a specified assembly, and

for at least some of said descriptions of assemblies, sets of predefined conditions of different properties of the components in the assembly for indicating whether certain predefined properties of a specified set of components are compatible within the assembly,

said memory comprising a control procedure for

first obtaining a predetermined initial set of predefined components,

thereafter matching the initial set of components to the predefined descriptions of assemblies to determine respective sets of matching components including the components in the initial set which are also permitted in the respective assemblies,

thereafter applying the sets of conditions to the respective sets of matching components for the respective assemblies, and

indicating whether the respective conditions are satisfied,

said computer including means for executing said control procedure to thereby first obtain said predetermined initial set of predefined components, thereafter match said initial set of components to said predefined descriptions of assemblies, thereafter apply said sets of conditions to the respective sets of matching components for the respective assemblies and generate an indication of whether the conditions are satisfied.

2. The knowledge system as claimed in claim 1, wherein said descriptions of assemblies include the names of at least some of said components in the initial set of components.

3. The knowledge system as claimed in claim 1, wherein said knowledge base further includes a catalog of components including component names and respective names of assemblies comprising said components, and wherein said descriptions of assemblies include the names of some of said assemblies in said catalog of components.

4. The knowledge system as claimed in claim 3, wherein said descriptions of assemblies comprise Boolean functions of names of assemblies.

5. The knowledge system as claimed in claim 1, wherein said control procedure includes a set of control steps for obtaining attributes of the components in said initial set of components, and wherein said descriptions of assemblies include respective Boolean functions of said attributes.

6. The knowledge system as claimed in claim 1, wherein said control procedure includes a set of control steps for obtaining a predetermined initial set of predefined components by inputting a predetermined list of components.

7. The knowledge system as claimed in claim 1, wherein the knowledge base further includes respective actions for said conditions, and wherein said control procedure includes a set of control steps for carrying out said actions for indicating whether the respective conditions are satisfied.

8. The knowledge system as claimed in claim 7, wherein said actions comprise adding and deleting specified components from said initial set of components.

9. The knowledge system as claimed in claim 1, wherein the descriptions of assemblies of predefined components include at least one definition of a relationship between at least two of said descriptions of assemblies, and wherein the control procedure includes a set of control steps for matching the initial set of components to at least one of said two descriptions of assemblies in response to the descriptions of the two assemblies and in response to the defined relationship between the two assemblies.

10. The knowledge system as claimed in claim 9, wherein said relationship is a structural relationship between said two assemblies.

11. The knowledge system as claimed in claim 9, wherein said relationship is a functional relationship between said two assemblies.

12. The knowledge system as claimed in claim 1, wherein some of said assemblies are sub-assemblies of other of said assemblies, and wherein said knowledge base includes a definition of a hierarchy of said descriptions of assemblies defining offspring-parent relationships between said descriptions of sub-assemblies and the respective descriptions of assemblies which comprise said sub-assemblies, and wherein said control procedure for matching the initial set of components to the predefined descriptions of assemblies includes means for first matching the list of components to the parent descriptions of assemblies, and then matching the list of the respecting matching components for the respective parent assemblies to their respective offspring descriptions of sub-assemblies.

13. The knowledge system as claimed in claim 12, wherein some of said parent descriptions of assemblies represent structures comprising their respective sub-assemblies physically connected together.

14. The knowledge system as claimed in claim 12, wherein some of said parent descriptions of assemblies represent functions collectively performed by the respective offspring sub-assemblies.

15. The knowledge system as claimed in claim 1, wherein said knowledge base further comprises a set of expansion rules defining expandable components including some of said components in the initial set of components in terms of respective sub-components of the expandable components and wherein said control procedure further includes a set of control steps for selecting expandable components from the initial set of components and adding the respective sub-components corresponding to the selected expandable components to the initial set of components.

16. The knowledge system as claimed in claim 15, wherein said set of control steps for selecting expandable components includes control steps for searching the initial set of components for specified components and when any of the specified expandable components are found, expanding those expandable components by adding their respective sub-components to the initial set of components.

17. The knowledge system as claimed in claim 1, further comprising a working configuration portion of said memory, and wherein said set of control steps for matching the initial set of components to the defined assemblies includes control steps for recording the respective matching components in respective bin portions of said working configuration portion of said memory.

18. The knowledge system as claimed in claim 17, wherein said knowledge base further includes respective modification actions for making specified changes to the recorded set of matching components in the respective bin portions of said working configuration portion of said memory, and wherein the said control procedure for applying the sets of conditions includes a set of control steps for conditionally executing said changes in response to whether the respective conditions are found to be satisfied for the respective assemblies when the respective conditions are applied.

19. The knowledge system as claimed in claim 18, wherein said conditions include descriptions of assemblies including specific components.

20. The knowledge system as claimed in claim 18, wherein said descriptions of assemblies include Boolean functions of specified attributes of components.

21. The knowledge system as claimed in claim 1, wherein said control procedure includes

a built-in control procedure independent of the descriptions of assemblies and said predefined conditions, and

task blocks defining control steps for said matching of said components to specified descriptions of assemblies and applying said conditions to the respective matching components, said task blocks being executed when specified steps in said built-in control procedure are reached.

22. The knowledge system as claimed in claim 21, wherein said task blocks include task blocks associated with respective assemblies and executed when said components are matched with the respective descriptions of assemblies of the task blocks.

23. The knowledge system as claimed in claim 22, wherein said descriptions of assemblies of predefined components include Boolean functions of specified attributes of components.

24. The knowledge system as claimed in claim 22, wherein said control steps defined by said task blocks include control steps for applying specified subsets of said conditions corresponding to the specified descriptions of assemblies.

25. The knowledge system as claimed in claim 21, wherein said task blocks include a specified task block to be executed before the other task blocks are executed.

26. The knowledge system as claimed in claim 21, wherein said conditions include Boolean functions of specified attributes of specified components, and wherein said knowledge base includes a knowledge base function associated with a respective one of said specified attributes, said knowledge base function being implicitly invoked when said condition is applied including said Boolean function of said specified attribute, so that the knowledge base function determines a value for its respective specified attribute.

27. The knowledge system as claimed in claim 21, wherein said built-in control procedure includes a set of control steps for generating a trace of the operations performed by said control procedure including the sequence of control steps performed when said task blocks are executed, and wherein said control procedure also includes a set of control steps for generating a user-understandable explanation from said trace and transmitting said explanation to a user.

28. The knowledge system as claimed in claim 1, wherein said control procedure includes a set of control steps for generating a trace of the results of said matching of said components and said application of said conditions and also includes a set of control steps for generating an explanation understandable to a human user from said trace and transmitting said explanation to a human user.

29. A knowledge system comprising a computer having a memory storing a knowledge base, said knowledge base including

predefined descriptions of assemblies of predefined components for indicating whether a specified component is permitted in a specified assembly, and

corresponding sets of assembly constraints including predefined conditions of different properties of the components in their respective assemblies for indicating whether certain predefined properties of a specified set of components are compatible within the assembly, and also including predefined actions to perform when the constraints are applied and the conditions are satisfied including outputting a warning to a user indicating specified conditions are satisfied,

said memory further comprising a control procedure for

first obtaining a predetermined list of components,

thereafter matching the components in said list to the predefined descriptions of assemblies to determine respective sets of matching components containing the components in said list which are permitted in the respective assemblies,

thereafter applying the sets of assembly constraints to the respective sets of matching components from the list for the respective assemblies, and

conditionally performing the respective actions in response to whether their respective conditions are satisfied when the assembly constraints are applied, said computer including means for executing said control procedure to thereby first obtain said predetermined list of components, thereafter match the components in said list to the predefined descriptions of assemblies, thereafter apply said sets of constraints to the respective sets of matching components from said list of components, and conditionally perform said respective actions in response to whether their respective conditions are satisfied when the assembly constraints are applied.

30. The knowledge system as claimed in claim 29 wherein said descriptions of assemblies define a hierarchy of descriptions of assemblies and sub-assemblies, and said control procedure for matching includes a procedure for matching said components in the respective assemblies to the descriptions of specified sub-assemblies to determine the components for which said constraints are applied.

31. The knowledge system as claimed in claim 29, wherein said constraints include conditions responsive to whether specified parts have been matched to the respective descriptions of assemblies.

32. The knowledge system as claimed in claim 29, wherein said constraints include conditions responsive to whether specified parts have specified attributes.

33. The knowledge system as claimed in claim 32, wherein the knowledge base includes definitions of variables for specifying the attributes of components included in the descriptions of respective assemblies.

34. The knowledge system as claimed in claim 33, wherein said knowledge base includes knowledge base functions for at least some of said variables specifying steps for determining values for the respective attributes of said components, and said control procedure includes a set of control steps for implicitly invoking and executing the respective knowledge base functions when applying constraints including conditions referencing the respective variables having the knowledge base functions.

35. The knowledge system as claimed in claim 29, further comprising a working configuration portion of said memory, and wherein said control procedure for matching the components in said list to the descriptions of assemblies includes a set of control steps for recording the respective matching components in respective bin portions of said working configuration portion of said memory.

36. The knowledge system as claimed in claim 35, wherein said control procedure for applying the sets of assembly constraints includes a set of control steps for applying a specified set of constraints to the matching components recorded in a specified bin portion of said working configuration portion of said memory.

37. The knowledge system as claimed in claim 35, wherein said knowledge base includes expansion rules defining sub-components for respective components, and wherein said control procedure includes a set of control steps for searching a specified bin for at least some of said components having sub-components defined by said expansion rules, and recording the respective sub-components in the specified bin.

38. The knowledge system as claimed in claim 35, wherein the actions of the assembly constraints include actions specifying modifications to the set of components recorded in a specified bin.

39. The knowledge system as claimed in claim 35, wherein said working configuration portion of said memory includes a current bin memory location for storing a value specifying a particular bin.

40. The knowledge system as claimed in claim 39, wherein the control procedure includes task blocks including control steps, at least some of the bins having an associated task block for specifying operations to perform in connection with their respective bins, and the control procedure includes a set of steps for executing the task block associated with a specified bin.

41. The knowledge system as claimed in claim 40, wherein the set of steps for executing the task block associated with a specified bin include the steps of pushing the value of the current bin memory location onto a stack, setting the value of the current bin memory location to specify the specified bin, executing the control steps in the task block for the specified bin, popping the stack and assigning the popped value to the current bin memory location.

42. The knowledge system as claimed in claim 40, wherein the task blocks include imperative language statements specifying distinct steps in said control procedure.

43. The knowledge system as claimed in claim 42, wherein the knowledge base includes expansion rules specifying that at least some of said components are expandable and are comprised of sub-components and wherein the imperative language statements include a separate statement for specifying that for each expandable component in a specified bin, its respective sub-components are to be recorded in the specified bin.

44. The knowledge system as claimed in claim 42, wherein the imperative language statements include a separate statement for specifying that specified assembly constraints are to be applied to the components in a specified bin.

45. The knowledge system as claimed in claim 42, wherein the imperative language statements include a separate statement for executing a specified task block.

46. The knowledge system as claimed in claim 42, wherein the control procedure includes a set of control steps for generating a sequential record of the imperative language statements that are executed, the components added to bins, the constraints applied, and the actions that are executed when the conditions of the applied constraints are satisfied.

47. The knowledge system as claimed in claim 40, wherein said knowledge base includes a plurality of separate portions for processing predetermined lists to configure different respective products, and wherein the control procedure includes control steps for obtaining said predetermined list by an input operation and for selecting the knowledge base portion corresponding to a product number in said predetermined list.

48. The knowledge system as claimed in claim 35, wherein said control procedure for matching the components in said list includes a set of control steps for finding the components in a specified bin which satisfy a specified assembly description.

49. The knowledge system as claimed in claim 48, wherein said control steps for finding the components in a specified bin are responsive to specified assembly descriptions including Boolean functions of part names, names of assemblies and part types.

50. A knowledge system comprising a computer having memory storing

a knowledge base including knowledge about a set of related elements, and

an initial list of certain ones of said elements,

said knowledge about said set of related elements including

a predefined declaration of hierarchical decomposition of said set of related elements into separately defined subsets of said elements, some of said separately defined subsets being composed of other of said separately defined subsets having fewer elements, and

for said separately defined subsets of said elements, respective predefined functions of the respective elements in the subsets, the domain of each function thereby being its respective subset, such function having a predefined result obtained when the function is applied responsive to the specified elements within its domain,

said memory including a working configuration portion for storing lists of said elements,

said memory storing a predefined matching procedure for matching a specified list of certain ones of said elements to a specified one of said subsets to thereby obtain a list of matching elements which are the elements in said specified list which are also elements of said specified subset, said list of matching elements being stored in said working configuration portion of said memory, and said memory further storing a predefined control procedure for

successively applying said matching procedure to match said initial list to said subsets of elements composing said set of related elements, and for each of said subsets of elements composed of said subsets of fewer elements applying said matching procedure to match the previously obtained respective list of matching elements to each of said subsets of fewer elements composing said subset of elements to thereby obtain lists of matching elements representing the configuration of said initial list according to said hierarchical decomposition, and

applying said functions to the respective lists of matching elements within the domains of the respective functions and obtained by matching to the respective subsets, and

said computer including means for executing said control procedure to thereby obtain said matching lists of elements representing a configuration of said initial list according to said hierarchical decomposition, and for applying said functions to the respective matching lists within the domains of the respective functions.

51. The knowledge system as claimed in claim 50, wherein said functions include functions responsive to whether specified elements of the initial list are included within said respective lists of matching elements within the domains of the respective functions.

52. The knowledge system as claimed in claim 50, wherein the knowledge base includes predetermined changes to the composition of said lists of matching elements stored in said working configuration portion of said memory, and wherein said functions include respective Boolean condition functions for indicating said changes, and wherein the control procedure includes control steps for executing the indicated changes to thereby conditionally change said lists of matching elements.

53. The knowledge system as claimed in claim 52, further comprising an explanation facility for generating an ordered list of the conditions for which changes were indicated and the changes which were executed, and transmitting the ordered list to a user.

54. The knowledge system as claimed in claim 50 wherein said subsets correspond to hierarchical functions collectively performed by the combinations of their respective elements, and the definitions of said subsets explicitly state their respective functions.

55. The knowledge system as claimed in claim 54, wherein said respective functions of the respective elements in the subsets include at least one function defining a variable, and at least one of said task blocks includes a statement specifying when the function is applied to determine a value for its respective variable.

56. The knowledge system as claimed in claim 50, wherein said declaration of hierarchical decomposition defines classes of subsets of said elements, and said control procedure includes configuring control steps for creating specified instances of said classes of subsets and adding corresponding elements of said initial list to the instances of said subsets.

57. The knowledge system as claimed in claim 56, wherein said control procedure includes a set of control steps for recursively applying said configuring control steps.

58. The knowledge system as claimed in claim 57, wherein said set of control steps for recursively applying starts recursive application at the uppermost level of the hierarchical decomposition.

59. The knowledge system as claimed in claim 50, wherein said knowledge base includes a plurality of task blocks specifying in part the operation of said control procedure, and said subsets are associated with particular ones of said task blocks, and said task blocks specify operations to perform with respect to their associated subsets.

60. The knowledge system as claimed in claim 59, wherein said task blocks include imperative language statements including separate statements for creating and storing in said working configuration portion of memory the list of matching elements obtained by matching to a specified one of said subsets, and for applying a specified set of functions to the respective lists of matching elements within the domains of said functions.

61. A knowledge system for checking a production request for a flexibly-assembled product, said request including a list of part names and respective quantities, said knowledge system comprising a computer having a memory storing a knowledge base, said knowledge base including

a declaration of a hierarchy of functional assemblies including parent-offspring relationships between respective assemblies and sub-assemblies,

a parts catalog including a predefined set of parts and identification of the functional assemblies which the respective parts compose, and

a set of conditions applicable to respective assemblies for indicating whether parts configured into the respective assemblies are compatible,

said memory also including

a working configuration portion of said memory subdivided into respective bins for receiving the names of parts configured into the respective assemblies, and

a control procedure for

obtaining said request,

configuring the part names in the request into at least one parent assembly by referencing the parts to the parts catalog to determine whether the parts compose the parent assembly and when they compose the parent assembly adding the respective part names to the parent bin,

configuring the part names in the request to respective offspring assemblies by referencing the parts in the respective parent bins to the parts catalog to determine whether the parts comprise the offspring assemblies and when they comprise the respective offspring assemblies adding the respective part names to the respective offspring bins, and

applying said conditions to the part names in the respective assemblies, and said computer including means for executing said control procedure to obtain said request, configure the part names in said request to respective offspring assemblies, and apply said conditions to the part names in the respective assemblies to thereby check whether the request includes compatible parts for all of the assemblies in the product.

62. The knowledge system as claimed in claim 61 wherein the knowledge base further comprises task blocks for respective ones of said assemblies, said task blocks including imperative language statements for specifying control procedure steps responsive to the parts in the bins for the respective assemblies.

63. The knowledge system as claimed in claim 62 wherein the knowledge base further comprises a separate set of expansion rules specifying the composition of expandable parts in terms of sub-parts, and wherein the task blocks include imperative language statements for adding the sub-parts of expandable parts in the bins to the respective bins.

64. The knowledge system as claimed in claim 61, wherein said knowledge base further comprises a set of actions specifying changes to the set of parts configured into at least some of said assemblies in response to the respective conditions for said assemblies, and wherein said control procedure includes a set of control steps for changing the sets of parts configured into the respective assemblies in the fashion indicated by said actions in response to whether the respective conditions are satisfied when the respective conditions are applied.

65. The knowledge system as claimed in claim 64 wherein the control procedure includes a set of control steps for generating and transmitting to a user a list of said changes made to the set of parts configured into the respective assemblies in the fashion indicated by said actions and an explanation of reasons why the changes were made.

66. The knowledge system as claimed in claim 64 wherein some of said actions specify that certain additional information is to be requested from a user and that certain changes are to be conditionally made in response to information received from the user.

67. A knowledge system for designing a product including assemblies of predetermined parts, said knowledge system comprising a computer having a portion of memory storing a knowledge base and a portion of memory subdivided into respective bins for receiving selected names of said parts for comprising the respective assemblies,

said knowledge base including a control procedure for

obtaining a set of assembly constraints including conditions applicable to respective assemblies for indicating whether parts in the respective bins have desired properties and respective actions indicating predetermined changes to the sets of parts in the respective bins for obtaining said desired properties in response to whether the respective conditions are satisfied, and

applying said conditions of said assembly constraints to the respective assemblies and conditionally executing the respective changes in response to whether the conditions are satisfied,

wherein said knowledge base further includes a hierarchy defining at least some of said assemblies as offspring sub-assemblies of respective parent assemblies, and wherein said assembly constraints associated with said parent assemblies have conditions referencing the conditions of parts in the respective offspring bins, and

said computer including means for executing said control procedure to thereby obtain said set of assembly constraints, apply said assembly constraints, and conditionally execute said respective changes to thereby obtain a design for said product, said design being indicated by the list of names of the parts in the bins after said conditions are applied and said changes are conditionally executed.

68. The knowledge system as claimed in claim 67 wherein the constraints of said offspring assemblies reference the conditions of parts in the respective parent bins via respective bin variables having respective scopes including the respective parent assembly conditions and the respective offspring assembly conditions.

69. The knowledge system as claimed in claim 67 wherein the knowledge base further comprises task blocks for respective ones of said assemblies, said task blocks including imperative language statements for specifying control procedure steps responsive to the parts in the bins for the respective assemblies.

70. The knowledge system as claimed in claim 67 wherein the control procedure includes a set of control steps for generating and transmitting to a user an ordered list of said changes in the sequence that the changes are executed, and an explanation of why said changes were made.