Data processing: artificial intelligence – Knowledge processing system – Knowledge representation and reasoning technique
Reexamination Certificate
1997-12-29
2001-02-20
Lintz, Paul R. (Department: 2762)
Data processing: artificial intelligence
Knowledge processing system
Knowledge representation and reasoning technique
C706S046000, C706S049000
Reexamination Certificate
active
06192355
ABSTRACT:
BACKGROUND OF THE INVENTION
This invention relates to a method of configuring a set of objects in a computer, each object having at least one possible value, each value being determined or undetermined, and at least: one of said object values being accessible to a user for assigning at least one value to be determined or undetermined, said values being constrained by a rule base defining a number of relationships between the values,
More particularly, this invention relates to the solving of configuration problems by means of a computer acting as a configuration aid for either a salesman or the customer himself. E.g. configuring a car, i.e. choosing a specific combination of engine, paint, accessories, etc. or e.g. configuring a computer system comprising different kinds of CPU's, ports, terminals, communications units, etc. will typically result in a huge and very complicated problem because of a great number of choices to be made and an overwhelming system of constraints between the different elements to be decided on.
A computer system intended to solve a configuration problem is a special application of artificial intelligence where the problem can be stated in terms of a set of selectable elements (e.g. engines, colors . . . ), or in other terms selectable values, and a number of relations (constraints) between these selectable elements (e.g. 4.0 1 engine is not possible together with the color of paint light blue).
In the following a selectable element is anything that can be included or excluded in a configuration. It can be a physical object (e.g. a car or a computer system as mentioned), an attribute (e.g. the color red or the texture pattern of a carpet) or something abstract (e.g. a specific number of trips between home and work or a particular type of contracts.
Typically, selections are constrained by previous choices of elements. If for instance a shopper in a supermarket wants only to buy ecological products, he may not be able to buy coffee. Thus, when selecting products, parts or features in a configuration system there should never be any available selections which are in fact invalid. This might seem very easy but is in fact one of the main difficulties in interactive configuration systems, as will be understood more fully from the following description.
The shopper from before could choose not to buy only ecological products. He may also choose not to buy coffee even if it is available. It is therefore desirable at any time to have a dynamic display of key figures, descriptions, graphics and video which change according to the customer's current focus and history.
An interactive computer configuration system is an aid for the salesman or the customer to make it just as easy to grasp and configure a huge problem as it is for a customer in the supermarket to know himself that he has bought exactly what he needs to treat his dinner guests according to his own decisions and the expectations of the guests.
Prior Art
Prior art systems only solve the configuration problem to some extent. Many prior art configuration systems are batch mode systems which are completely out of interest. Only interactive systems are of interest, but the known systems have the disadvantage that the successive selection or discarding of elements often turns out to be a dead-end, because the choices successively made by the user suddenly turn out to be an invalid configuration.
Interactive configuration systems comprise a configuration model defining mutual predefined relations (constraints) between selectable elements and comprise programs for validating a set of choices against a set configuration model.
The basic problem of interactive configuration is that the algorithms needed to support a true interactive environment are extremely time-consuming, as the time increases exponentially as a function of object values. This problem is called the NP-hard problem, which has restricted the possible obtainable results related to configuration.
The NP-hard problem affects two very important features related to configuration. First of all, it should be realized that a NP-hard problem affects the time complexity of the involved algorithms. This means that the necessary processing time becomes unacceptable in relation to configuration models or rule bases comprising many object values and many constraints between these. Secondly, dealing with the above-mentioned problems related to processing time, the configuration will have to be reduced in such a way that the configuration problems are reduced to be polynomial. Due to these facts, the prior art has focused on modified configuration models, i.e. rule bases, and modified algorithms. These modified configuration models imply bad structures of the configuration models, and the configuration models are usually not capable of being separately validated.
Three of the most used modifications related to the configuration model are
1. Establishing a certain search order in a decision-tree. This leads to very restricted facilities for the user.
2. Avoiding inference on partial information. This leads to the use of the well known batch mode configuration systems.
3. Establishing the rule base or configuration model in a conditional IF-THEN programming.
All of the previously mentioned techniques have the disadvantage of a very complicated modeling, as the models in attempting to deal with the NP-hard problem, becomes very intrigue. This drawback is somewhat critical, as the generation and maintenance of configuration models of the above mentioned types tends to be very time consuming. It should be noted that the maintenance of a configuration model is one of the most critical and expensive parameters to companies who needs an almost daily modification of the configuration model.
CROSS REFERENCES
A reference is made to the following patent applications, filed at the same day as this application and assigned to the same assignee, Beologic A/S:
(1) A Method of Configuring a Set of Objects in a Computer
(2) A Method and Apparatus for Inference of Partial Knowledge in Interactive Configuration
(3) A Method of Processing a Request to a Boolean Rule
(4) Configuration via Network
(5) A Method for enabling invalid choices in interactive configuration systems
which are hereby incorporated as references to be understood in connection with the present invention.
THE INVENTION
By searching the undetermined object values in order to find at least one first subset of values, said first subset and a subset of determined values defining at least one first possible configuration of object values satisfying the rule base if said first subset exists, and initiating said search when at least one value of an object is changed, or said search being initiated upon a user request, very important knowledge about the undetermined object values has been gained.
By finding at least one possible configuration of object values, the user is assured that the current partial configuration can be brought into a consistent final configuration. On the other hand, if at least one set of values is not found, the user can be warned that the current partial configuration cannot be brought into a consistent final configuration, and the risk of a configuration process ending up at a dead end is thereby eliminated. Moreover, by finding at least one set of values it is possible to terminate a configuration automatically when a user is satisfied with the selections he has made.
It is to be remembered that a configuration is a quite complicated process wherein the implemented configuration method is a very critical and crucial connecting link between an intuitive user and the very strong performance of a computer with respect to calculation and memory capacity. The other way round, the intuitive user is limited with respect to processing and memory, and the user thus has a very urgent need for support offered by a computer. In spite of many attempts to implement a kind of intelligence in a computer, the computer is nevertheless limited to perform rather canonical processing.
It should furth
Baan Development B.V.
Khatri Anil
Lintz Paul R.
Oliff & Berridg,e PLC
LandOfFree
Method of configuring a set of objects in a computer does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method of configuring a set of objects in a computer, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method of configuring a set of objects in a computer will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2586847