Generalized configurator using multiple interacting packers and declaratively defined constraint expressions

• US 5,617,514 A
• Filed: 07/13/1994
• Issued: 04/01/1997
• Est. Priority Date: 07/13/1994
• Status: Expired due to Term

• Current Assignee: Unisys Corporation
• Original Assignee: Unisys Corporation
• Inventors: Dolby, Nigel I., Nagle, Timothy E., Goessling, Thomas R.
• Primary Examiner(s): Hafiz, Tariq R.
• Application Number:
  US08/275,194
• Time in Patent Office: 993 Days
• Field of Search: 395/50-51, 395/54, 395/910, 395/60-64, 395/76
• US Class Current: 706/45
• CPC Class Codes: G06F 2111/04 Constraint-based CAD
• CPC Class Codes: G06F 30/18 Network design, e.g. design based on topological or interconnect aspects of utility systems, piping, heating ventilation air conditioning [HVAC] or cabling circuit design at the physical level G06F30/39; network planning tools for wireless communication networks H04W16/18
• CPC Class Codes: G06N 5/022 Knowledge engineering; Knowledge acquisition

Abstract

A generalized configuration expert system for generating a complete, legal, and near-optimal configuration for any complex system consisting of multiple components is disclosed. The present invention allows a developer to specify a configurator framework for solving a particular configuration problem. A user then operates the customized configurator to generate a configuration solution based on the user'"'"'s requests and the system'"'"'s requirements and constraints. The generalized configurator uses declaratively constructed graphs and multiple interacting packing engines. A two-level, bi-partite, spreading activation graph is used as the knowledge representation of the components to be configured and their associated relationships. The invention dynamically manages the interaction of the multiple packer engines to select the appropriate piece of the total configuration problem to work on at any point in time, while still taking into account the other packing problems. The invention provides the ability to declaratively define the constraints used by the packing engines to assure correct configuration results.

Claims

1. A non-rule-based, generalized configurator expert system for generating a a configuration of connected components by solving packing problems through the execution of packing operations, the configurator expert system being customized for a given domain of components by a configurator developer, and operated by a configurator user to generate a configuration solution based on user requests, predetermined component requirements, and connection constraints specified by component definitions, the configurator expert system having a first spreading activation bi-partite graph for storing the component definitions and constraint expressions declaratively specified by the configurator developer, a second spreading activation bi-partite graph for storing instances of components defined in the first spreading activation bi-partite graph interactively selected by the configurator user, and a processing module that can accept requests from the configurator user to configure selected components, match the requests to the component definitions stored in the first spreading activation bi-partite graph, create and connect the instances of the selected components in the second spreading activation bi-partite graph if creation and connection are valid based on the component definitions and prior configurator user requests, and report the configuration resulting from the requests to the configurator user, the non-ruled-based, generalized configurator expert system comprising:

packing definition means coupled to the processing module for storing and retrieving at least one piece of knowledge relating to the type of packing operations that may be attached to component definitions in the first spreading activation bi-partite graph; and

packing processing means coupled to the processing module, the first spreading activation bi-partite graph, and the second spreading activation bi-partite graph for concurrently performing multiple packing operations to define the connection of selected components to other selected components in the second spreading activation bi-partite graph according to criteria declaratively specified by the configurator developer in constraint expressions stored in the first spreading activation bi-partite graph.

2. The non-rule-based, generalized configurator expert system as in claim 1, further comprising expression handling means coupled to said packing processing means and the processing module for evaluating constraint expressions and returning a resulting signal to said packing processing means and the processing module.

3. The non-rule-based, generalized configurator expert system as in claim 1, wherein said packing processing means includes:

a plurality of packer means for analyzing the effect of a configurator user request to configure a selected component on the state of the instances in the second spreading activation bi-partite graph according to the constraint expressions, each of said packer means including means for generating a bid to modify the second spreading activation bi-partite graph in response to a configurator user request; and

master scheduler means coupled to each of said packer means for coordinating and controlling the actions of each of said packer means, and for selecting, according to predetermined criteria, which one of said bids should be implemented.

4. The non-rule-based, generalized configurator expert system as in claim 3, wherein said master scheduler means comprises:

supervisor means coupled to each of said packer means for determining a most important bid of said bids to implement according to said predetermined criteria; and

master consultant means coupled to each of said packer means for querying each of said packer means to determine if said most important bid is acceptable to all of said packer means.

5. The non-rule-based, generalized configurator expert system as in claim 4, wherein said packer means comprises:

selecting proposer means coupled to said supervisor means for choosing said bid and for numerically rating said bid in terms of desirability and importance;

assigning proposer means coupled to said supervisor means and said master consultant means for provisionally implementing said bid to modify the second spreading activation bi-partite graph, and for ensuring that actual implementation of said bid is acceptable to all of said packer means;

consultant means coupled to said selecting proposer means, said assigning proposer means, and said master consultant means for reviewing the global state of the instances in the second spreading activation bi-partite graph, for verifying, in the context of said packer means, the legality of the current state of the second spreading activation bi-partite graph after implementation of said most important bid, and for reporting a legality result to said master consultant means; and

implementer means coupled to said supervisor means for permanently modifying the instances in the second spreading activation bi-partite graph according to said most important bid if said consultant means of each one of said packer means reports an acceptable legality result.

6. A non-rule-based, generalized configurator expert system for generating a configuration of components connected to form a computer system by solving packing problems through the execution of packing operations, the configurator expert system being customized for a given computer system configuration domain by a configurator developer, and operated by a configurator user to generate a computer system configuration solution based on user requests, predetermined computer system component requirements, and connection constraints specified by computer system component definitions, the configurator expert system having a first spreading activation bi-partite graph for storing the computer system component definitions and constraint expressions declaratively specified by the configurator developer, a second spreading activation bi-partite graph for storing instances of computer system components defined in the first spreading activation bi-partite graph interactively selected by the configurator user, and a processing module that can accept requests from the configurator user to connect selected computer system components, match the requests to the computer system component definitions stored in the first spreading activation bi-partite graph, create and connect the instances of the selected computer system components in the second spreading activation bi-partite graph if creation and connection are valid based on the computer system component definitions and prior configurator user requests, and for report the computer system configuration resulting from the requests to the configurator user, the configurator expert system comprising:

packing definition knowledge base means coupled to the processing module for storing at least one piece of knowledge relating to the type of packing operations that may be attached to the computer system component definitions in the first spreading activation bi-partite graph; and

packing processing means coupled to the processing module, the first spreading activation bi-partite graph, and the second spreading activation bi-partite graph for concurrently performing multiple packing operations to define the connection of selected computer system components to other computer system components according to criteria declaratively specified by the configurator developer in constraint expressions stored in the first spreading activation bi-partite graph.

7. The non-rule-based, generalized configurator expert system as in claim 6, further comprising expression handling means coupled to said packing processing means and the processing module for evaluating said constraint expressions and returning a resulting signal to said packing processing means and the processing module.

8. The non-rule-based, generalized configurator expert system as in claim 6, wherein said packing processing means comprises:

a plurality of packer means for analyzing the effect of a configurator user request to configure a selected computer system component on the state of the instances in the second spreading activation bi-partite graph according to said constraint expressions, each of said packer means including means for generating a bid to modify the second spreading activation bi-partite graph in response to a configurator user request; and

master scheduler means coupled to each of said packer means for coordinating and controlling the actions of each of said packer means, and for selecting, according to predetermined criteria, which one of said bids should be performed.

9. The non-rule-based, generalized configurator expert system as in claim 8, wherein said master scheduler means comprises:

supervisor means coupled to each of said packer means for determining a most important bid of said bids to implement according to said predetermined criteria; and

master consultant means coupled to each of said packer means for querying each of said packer means to determine if said most important bid is acceptable to all of said packer means.

10. The non-rule-based, generalized configurator expert system as in claim 9, wherein said packer means comprises:

selecting proposer means coupled to said supervisor means for choosing said bid and numerically rating said bid in terms of desirability and importance;

assigning proposer means coupled to said supervisor means and said master consultant means for provisionally implementing said bid to modify the second spreading activation bi-partite graph, and for ensuring that actual implementation of said bid is acceptable to all of said packing means;

consultant means coupled to said selecting proposer means, said assigning proposer means, and said master consultant means for reviewing the global state of the instances in the second spreading activation bi-partite graph, for verifying, in the context of said packer means, the legality of the current state of the second spreading activation bi-partite graph after implementation of said most important bid, and for reporting a legality result to said master consultant means; and

implementer means coupled to said supervisor means for permanently modifying the instances in the second spreading activation bi-partite graph according to said most important bid if said consultant means of each one of said packer means reports an acceptable legality result.

11. The non-rule-based, generalized configurator expert system as in claim 10, wherein said packing processing means performs multiple packing operations to concurrently solve bin packing, cabling, rack packing, and computer system component stringing configuration problems.

12. A non-rule-based, generalized computer-based configurator expert system for generating a configuration of connected components by solving packing problems through the execution of packing operations, the configurator expert system being customized for a given configuration domain by a configurator developer, and operated by a configurator user to generate a configuration solution based on configurator user requests, predetermined component requirements and connection constraints specified by component definitions, said non-rule-based, generalized computer-based configurator expert system comprising:

an a priori net including component definitions and constraint expressions declaratively specified by the configurator developer, said component definitions being logically coupled to resources implied by the use of said component definitions, said component definitions and said resources being represented as first nodes in a first bi-partite, spreading activation graph;

an instance net containing instances of components defined in said a priori net interactively selected by the configurator user, said instances being logically coupled to instances of said implied resources, said instances and said implied resources being represented as second nodes in a second bi-partite graph;

a logic engine coupled to said a priori net and said instance net to accept requests from the configurator user to configure selected components, match the configurator user requests to said component definitions in said first bi-partite, spreading activation graph, automatically propagate logical implications of the configurator user requests across as many ones of said first nodes of said first bi-partite, spreading activation graph as are required to build a complete set of connected components fulfilling the configurator user requests by creating and connecting said selected instances of said selected components in said second bi-partite graph only if creation and connection of said selected instances are valid based on said component definitions and previous configurator user requests, validity being determined by analyzing the relationships between nodes inherent in said first bi-partite, spreading activation graph and said second bi-partite graph, and report the configuration resulting from said requests to the configurator user;

packing definition knowledge base means responsive to said logic engine for storing at least one piece of knowledge relating to the type of packing operations that may be attached to said items in said a priori net; and

packing engine means coupled to said logic engine, said a priori net, and instance net for concurrently performing multiple packing operations to define the connection of said selected components to other selected components according to criteria declaratively specified by the configurator developer in said constraint expressions stored in said instance net.

13. The non-rule-based, generalized computer-based configurator expert system as in claim 12, further comprising expression handling means coupled to said packing engine means and said logic engine for evaluating said constraint expressions and returning a resulting signal to said packing engine means and said logic engine.

14. The non-rule-based, generalized computer-based configurator expert system as in claim 12, wherein said packing engine means comprises:

a plurality of packer means for analyzing the effect of a configurator user request to configure said selected component on the state of said second bi-partite graph according to said constraint expressions, each of said packer means including means for generating a bid to modify said second bi-partite graph stored in said instance net in response to a configurator user request; and

master scheduler means coupled to each of said packer means for coordinating and controlling the actions of each of said packer means, and for selecting, according to predetermined criteria, which one of said bids should be implemented.

15. The non-rule-based, generalized configurator expert system as in claim 14, wherein said master scheduler means comprises:

supervisor means coupled to each of said packer means for determining a most important bid of said bids to perform according to said predetermined criteria; and

master consultant means coupled to each of said packer means for querying each one of said packer means to determine if said most important bid is acceptable to all of said packer means.

16. The non-rule-based, generalized computer-based configurator expert system as in claim 15, wherein said packer means comprises:

selecting proposer means coupled to said supervisor means for choosing said bid and rating said bid in terms of desirability and importance;

assigning proposer means coupled to said supervisor means and said master consultant means for provisionally implementing said bid to modify said second bi-partite graph stored in said instance net, and ensuring that actual implementation of said bid is acceptable to all of packer means;

consultant means coupled to said selecting proposer means, said assigning proposer means, and said master consultant means for reviewing the global state of said second bi-partite graph, for verifying the legality of performance of said most important bid in the context of said packer means, and for reporting a legality result; and

implementer means coupled to said supervisor means for permanently modifying said second bi-partite graph according to said most important bid if said consultant means of each of said packer means reports an acceptable legality result.

17. A non-rule-based, generalized computer-based configurator expert system for generating a configuration of components connected to form a computer system by solving packing problems through the execution of packing operations, the configurator expert system being customized for a given computer system configuration domain by a configurator developer, and operated by a configurator user to generate a computer system configuration solution based on configurator user requests, predetermined computer system component requirements and connection constraints specified by computer system component definitions, said non-rule-based, generalized computer-based expert system comprising:

an a priori net including computer system component definitions and constraint expressions declaratively specified by the configurator developer, said computer system component definitions being logically coupled to resources implied by the use of said computer system component definitions, said computer system component definitions and said resources being represented as first nodes in a first bi-partite, spreading activation graph;

an instance net containing instances of computer system components defined in said a priori net interactively selected by the configurator user, said instances being logically coupled to instances of said implied resources, said instances and said implied resources being represented as second nodes in a second bi-partite graph;

a logic engine coupled to said a priori net and said instance net to accept requests from the configurator user to configure selected computer system components, match the configurator user requests to said computer system component definitions in said first bi-partite, spreading activation graph, automatically propagate logical implications of the configurator user requests across as many ones of said first nodes of said first bi-partite, spreading activation graph as are required to build a complete set of connected computer system components fulfilling the configurator user requests by creating and connecting said selected instances of said selected computer system components in said second bi-partite graph only if creation and connection of said selected instances are valid based on said computer system component definitions and previous configurator user requests, validity being determined by analyzing the relationships between nodes inherent in said first bi-partite, spreading activation graph and said second bi-partite graph, and report the configuration resulting from said requests to the configurator user;

packing definition knowledge base means responsive to said logic engine for storing at least one piece of knowledge relating to the type of packing operations that may be attached to said items in said a priori net; and

packing engine means coupled to said logic engine, said a priori net, and instance net for concurrently performing multiple packing operations to define the connection of said selected computer system components to other selected computer system components according to criteria declaratively specified by the configurator developer in said constraint expressions stored in said instance net.

18. The non-rule-based, generalized computer-based configurator expert system as in claim 17, further comprising expression handling means coupled to said packing engine means and said logic engine for evaluating said constraint expressions and returning a resulting signal to said packing engine means and said logic engine.

19. The non-rule-based, generalized computer-based configurator expert system as in claim 17, wherein said packing engine means comprises:

a plurality of packer means for analyzing the effect of a configurator user request to configure said selected computer system component on the state of said second bi-partite graph according to said constraint expressions, each of said packer means including means for generating a bid to modify said second bi-partite graph stored in said instance net in response to a configurator user request; and

master scheduler means coupled to each of said packer means for coordinating and controlling the actions of each of said packer means, and for selecting, according to predetermined criteria, which one of said bids should be implemented.

20. The non-rule-based, generalized configurator expert system as in claim 19, wherein said master scheduler means comprises:

supervisor means coupled to each of said packer means for determining a most important bid of said bids to perform according to said predetermined criteria; and

master consultant means coupled to each of said packer means for querying each one of said packer means to determine if said most important bid is acceptable to all of said packer means.

21. The non-rule-based, generalized computer-based configurator expert system as in claim 20, wherein said packer means comprises:

selecting proposer means coupled to said supervisor means for choosing said bid and rating said bid in terms of desirability and importance;

assigning proposer means coupled to said supervisor means and said master consultant means for provisionally implementing said bid to modify said second bi-partite graph, and ensuring that actual implementation of said bid is acceptable to all of packer means;

consultant means coupled to said selecting proposer means, said assigning proposer means, and said master consultant means for reviewing the global state of said second bi-partite graph, for verifying the legality of performance of said most important bid in the context of said packer means, and for reporting a legality result; and

implementer means coupled to said supervisor means for permanently modifying said second bi-partite graph according to said most important bid if said consultant means of each of said packer means reports an acceptable legality result.

22. A non-rule-based, computer-implemented method for generating a configuration of connected components by using multiple interacting packing processing modules, wherein each component can be described by a component definition, comprising the steps of:

(a) declaratively defining components to be configured;

(b) representing the component definitions and the resources implied by their use as nodes in a first bi-partite, spreading activation graph, wherein an arc of said first bi-partite, spreading activation graph connects a first selected node representing one of said component definitions to at least one second selected node representing said resources;

(c) assigning a packing processing module to a selected node in said first bi-partite, spreading activation graph;

(d) accepting a request to connect a selected component from a configurator user;

(e) selecting a set of packing processing modules according to the configurator user'"'"'s request;

(f) identifying a most important action to implement said request according to each one of said set of selected packing processing modules;

(g) assigning numerical weights to said most important action for each selected packing processing module representing how desirable and how constrained said most important action is;

(h) comparing said numerical weights assigned by said selected packing processing modules to select one of said selected packing processing module to tentatively perform said most important action by creating and connecting an instance of said selected component and said resources defined in said first bi-partite, spreading activation graph as nodes in a second bi-partite graph;

(i) determining whether the configuration represented by said second bi-partite graph is valid according to each packing processing module;

(j) making the changes in said second bi-partite graph occurring as a result of the implementation of said most important action permanent if each one of said set of selected packing processing modules approves of said most important action implementation; and

(k) reporting the configuration represented by said second bi-partite graph which resulted from said requests to the configurator user.

23. The non-rule-based, computer-implemented method of claim 22, wherein said representing step comprises the steps of:

(a) supplying a definition of a current component from component definitions;

(b) creating an item node in said first bi-partite, spreading activation graph for said current component;

(c) loading said item node with information describing the requirements and constraints on connecting said current component to other components in a second bi-partite graph;

(d) creating one or more resource nodes representing resources implied by the use of said current component, if said resource nodes have not previously been created;

(e) connecting said item node with said resource nodes and any pre-existing item nodes supplying resources consumed by said item node; and

(f) repeating steps (a) through (e) for all components defined by the configurator developer.

24. The non-rule-based, computer-implemented method of claim 22, wherein said accepting step comprises the steps of:

(a) displaying menus, icons, and data entry windows as part of a graphical user interface to the configurator user; and

(b) accepting configurator user requests to configure components by responding to commands and data entered via said menus, icons, and data entry windows.

25. The non-rule-based, computer-implemented method of claim 22, wherein said reporting step comprises the steps of:

(a) converting the nodes of said second bi-partite graph into display objects capable of being displayed by a graphical user interface; and

(b) displaying said display objects on a display for viewing by the configurator user.

26. A non-rule-based, computer-implemented method for generating a configuration of components connected to form a computer system by using multiple interacting packing processing modules, wherein each computer system component can be described by a computer system component definition, comprising the steps of:

(a) declaratively defining computer system components to be configured;

(b) representing the computer system component definitions and the resources implied by their use as nodes in a first bi-partite, spreading activation graph, wherein an arc of said first bi-partite, spreading activation graph connects a first selected node representing one of said component definitions to at least one second selected node representing said resources;

(c) assigning a packing processing module to a selected node in said first bi-partite, spreading activation graph;

(d) accepting a request to connect a selected computer system component from a configurator user;

(e) selecting a set of packing processing modules according to the configurator user'"'"'s request;

(f) identifying a most important action to implement said request according to each one of said set of selected packing processing modules;

(g) assigning numerical weights to said most important action for each selected packing processing module representing how desirable and how constrained said most important action is;

(h) comparing said numerical weights assigned by said selected processing modules to select one of said selected packing processing module to tentatively perform said most important action by creating and connecting an instance of said selected component and said resources defined in said first bi-partite, spreading activation graph as nodes in a second bi-partite graph;

(i) determining whether the computer system configuration represented by said second bi-partite graph is valid according to each packing processing module;

(j) making the changes in said second bi-partite graph occurring as a result of the implementation of said most important action permanent if each one of said set of selected packing processing modules approves of said most important action implementation; and

(k) reporting the computer system configuration represented by said second bi-partite graph which resulted from said requests to the configurator user.

27. The non-rule-based, computer-implemented method of claim 26, wherein said representing step comprises the steps of:

(a) supplying a definition of a current computer system component from computer system component definitions;

(b) creating an item node in said first bi-partite, spreading activation graph for said current computer system component;

(c) loading said item node with information describing the requirements and constraints on connecting said current computer system component to other computer system components in a second bi-partite graph;

(d) creating one or more resource nodes representing resources implied by the use of said current computer system component, if said resource nodes have not previously been created;

(e) connecting said item node with said resource nodes and any pre-existing item nodes supplying resources consumed by said item node; and

(f) repeating steps (a) through (e) for all components defined by the configurator developer.

28. The non-rule-based, computer-implemented method of claim 26, wherein said accepting step comprises the steps of:

(a) displaying menus, icons, and data entry windows as part of a graphical user interface to the configurator user; and

(b) accepting configurator user requests to configure computer system components by responding to commands and data entered via said menus, icons, and data entry windows.

29. The non-rule-based, computer-implemented method of claim 26, wherein said reporting step comprises the steps of:

(a) converting the nodes of said second bi-partite graph into display objects capable of being displayed by a graphical user interface; and

(b) displaying said display objects on a display for viewing by the configurator user.