Data processing: artificial intelligence – Knowledge processing system – Knowledge representation and reasoning technique
Reexamination Certificate
1997-12-29
2001-04-24
Lintz, Paul R. (Department: 2122)
Data processing: artificial intelligence
Knowledge processing system
Knowledge representation and reasoning technique
C706S046000, C706S051000
Reexamination Certificate
active
06223170
ABSTRACT:
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.
BACKGROUND OF THE INVENTION
This invention relates to a method of configuring a set of object values in a computer, at least one object value of said set of object values being user-chosen from a number of object values, each object having at least one possible object value, each object value being determined or undetermined, each of said determined object values each being assigned to a value, some of these or all of these object values being comprised in the said set of object values, and said object values being constrained by a rule base defining a number of relationships between the objects or the object 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 l 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.
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.
THE INVENTION
This invention relates to a method of configuring a set of object values in a computer,
at least one object value of said set of object values being user-chosen from a number of object values,
each object having at least one possible object value,
each object value being determined or undetermined,
each of said determined object values being assigned to a value,
some of these or all of these object values being comprised in the said set of object values,
and said object values being constrained by a rule base defining a number of relationships between the objects or the object values.
When the method further comprises at least one interruptable algorithm adapted to deduce knowledge about the undetermined object values,
said knowledge indicating whether a user selection of a part of or all of the individual undetermined object values are possible or not,
said algorithm or algorithms comprising at least one readout point
in at least one readout point storing the deduced knowledge in at least one dynamic representation of object values, the deduced knowledge in each readout point representing partial knowledge about the undetermined objects,
said partial knowledge being presented to the user in response to a user interrupt or a time interrupt, it is made possible to achieve a prediction of whether a following configuration will have a chance of success.
According to the invention, this prediction can be supplemented by a further active guidance to the user in the sense that information about the possible user selections can be presented to the user before these are actually selected. This feature is a very important aspect related to an interactive communication with the user.
Another and very important aspect of the invention is t
Baan Development B.V.
Khatri Anil
Lintz Paul R.
Oliff & Berridg,e PLC
LandOfFree
Method and apparatus for inference of partial knowledge in... 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 and apparatus for inference of partial knowledge in..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for inference of partial knowledge in... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2441743