Bounceback detection in online product configuration6980967Abstract The present invention provides techniques for effecting improved guidance to the user of a configuration system by detecting and eliminating bounceback behavior that unnecessarily eliminates otherwise valid domain members from the selection provided to the user. Generally, domain members that would have been eliminated (e.g., grayed out) solely because of bounceback behavior are identified and prevented from being displayed as grayed out or otherwise eliminated on the user display. Claims 1. A computer-implemented method for eliminating bounceback behavior while performing a product configuration, the method comprising: Description FIELD OF THE INVENTION
The first given constraint, K1, states that the 700 MHz CPU is compatible with the 20 Gbyte DiskDrive, and that the 900 MHz CPU is compatible with the 40 Gbyte DiskDrive. It can further be stated that the 700 MHz CPU is not compatible with the 40 Gbyte DiskDrive, and that the 900 MHz CPU is not compatible with the 20 Gbyte DiskDrive. The second given constraint, K2, states that the 20 Gbyte DiskDrive is compatible with the 64 Mbyte Memory, and that 40 Gbyte DiskDrive is compatible with the 128 Mbyte Memory. It can further be stated that the 20 Gbyte DiskDrive is not compatible with the 128 Mbyte Memory, and that 40 Gbyte DiskDrive is not compatible with the 64 Mbyte Memory. The third given constraint, K3, states that the 64 Mbyte Memory is compatible with the 700 MHz CPU, and that the 128 Mbyte Memory is compatible with the 900 MHz CPU. It can further be stated that the that the 64 Mbyte Memory is not compatible with the 900 MHz CPU, and that the 128 Mbyte Memory is not compatible with the 700 MHz CPU. Note that other logical conclusions and transformations may be drawn from the given constraints. Continuing with the example, assume that the user picks the 700 MHz CPU, and sends the selection to the configuration side (e.g., user selects the 700 MHz CPU radio button and clicks on the submit button). Once the configuration side receives the user pick, the configuration system propagates the constraints associated with that pick. More specifically, the bounceback detection bit vector for the domain members of CPU that were not picked (the 900 MHz CPU) is set to #001, and the elimination flag associated with the 900 MHz is set to true. Setting the bounceback detection bit vector associated with the 900 MHz CPU to #001 indicates that the pick that caused the elimination of the 900 MHz CPU is the pick associated with variable 1, which in this example is the CPU. This is an indication of bounceback behavior. Since the only eliminating variable is the variable of the eliminated domain member, that domain member is not actually eliminated (as indicated by the bounceback detection bit vector) despite the associated elimination flag being set. Constraint K1 can now be propagated. The 900 MHz CPU domain member behaves as if eliminated, since its elimination flag is true. Thus, the 40 Gbyte DiskDrive is eliminated by K1, which can be interpreted to mean: If the 900 MHz CPU is eliminated, then the 40 GB DiskDrive must be eliminated. The bounceback detection bit vector associated with the 900 MHZ CPU is therefore propagated to the 40 Gbyte DiskDrive (e.g., the bounceback detection bit vector associated with the 900 MHz CPU is copied to the bounceback detection bit vector associated with the 40 Gbyte DiskDrive). As such, the bounceback detection vector for the 40 Gbyte DiskDrive is set to #001. In addition, the elimination flag associated with the 40 Gbyte DiskDrive is set to true. The 40 Gbyte DiskDrive is therefore eliminated. The elimination is confirmed by the bounceback detection bit vector associated with 40 Gbyte DiskDrive because the bit position of that bit vector which corresponds to the DiskDrive variable (the second bit) is not the only 1 bit (in fact, that bit is not set at all). Next, constraint K2 can be propagated. The 40 Gbyte DiskDrive domain member behaves as if eliminated, since its elimination flag is true. Thus, the 128 Mbyte Memory is eliminated by K2, which can be interpreted to mean: If the 40 Gbyte DiskDrive is eliminated, then the 128 Mbyte Memory must be eliminated. The bounceback detection bit vector associated with the 40 Gbyte DiskDrive is therefore propagated to the 128 Mbyte Memory (e.g., the bounceback detection bit vector associated with the 40 Gbyte DiskDrive is copied to the bounceback detection bit vector associated with the 128 Mbyte Memory). As such, the bounceback detection vector for the 128 Mbyte Memory is set to #001. In addition, the elimination flag associated with the 128 Mbyte Memory is set to true. The 128 Mbyte Memory is therefore eliminated. The elimination is confirmed by the bounceback detection bit vector associated with 128 Mbyte Memory because the bit position of that bit vector which corresponds to the Memory variable (the third bit) is not the only 1 bit (in fact, that bit is not set at all). Note that the 128 Mbyte Memory is also eliminated by K3, which can be interpreted to mean: If the 900 MHz CPU is eliminated, then the 128 Mbyte Memory must be eliminated. Thus, the bounceback detection bit vector associated with the 900 MHz CPU is propagated to the 128 Mbyte Memory (e.g., the bounceback detection bit vector associated with the 900 MHz CPU is copied to the bounceback detection bit vector associated with the 128 Mbyte Memory). As such, the bounceback detection vector for the 128 Mbyte Memory is set to #001 and the 128 Mbyte Memory is eliminated, thereby producing the same result described with reference to the propagation of K2. Next, constraint K3 can be propagated. The 128 Mbyte Memory domain member behaves as if eliminated, since its elimination flag is true. Thus, the 900 MHz CPU is eliminated by K3, which can be interpreted to mean: If the 128 Mbyte Memory is eliminated, then the 900 MHz CPU must be eliminated. The bounceback detection bit vector associated with the 128 Mbyte Memory is therefore propagated to the 900 MHz CPU (e.g., the bounceback detection bit vector associated with the 128 Mbyte Memory is copied to the bounceback detection bit vector associated with the 900 MHz CPU). As such, the bounceback detection vector for the 900 MHz CPU is set to #001. In addition, the elimination flag associated with the 900 MHz CPU is set to true. Note, however, that bounceback detection vector for the 900 MHz CPU was already set to #001, and propagation of K3 introduced no changes. Further note the 900 MHz CPU is not actually eliminated (as indicated by the bounceback detection bit vector) despite the associated elimination flag being set) as previously explained. As can be seen, the 900 MHz CPU would have been eliminated without bounceback detection. Note that this example is representative of a spurious elimination in that the user could have selected the 900 MHz CPU (thereby deselecting the 700 MHz CPU) without violating any constraints. Bounceback Detection Over a Disjunction In addition to the three problem variables and respective domains described above, add a fourth: a DiskController (DC1, DC2). In addition, assume a fourth constraint, K4: Compatible<DiskDrive, DiskController>((20 GB DC1)(40 GB DC2)). Since there are now four variables in the problem, the bounceback detection bit vectors will consist of four bits instead of the three as in the previous example. Assume that the user picks the DC1 DiskController in addition to the 700 MHz CPU as indicated above. Once the configuration side receives the user picks, the configuration system propagates the constraints associated with each pick. The discussion with regards to propagating the constraints associated with the 700 MHz CPU pick generally applies here as will be apparent in light of this disclosure. In addition, the configuration system propagates the constraints associated with the DC1 DiskController. As such, the bounceback detection bit vector for the domain members of DiskController that were not picked (the DC2) is set to #1000, and the elimination flag associated with the DC2 is set to true. Setting the bounceback detection bit vector associated with the DC2 DiskController to #1000 indicates that the pick that caused the elimination of the DC2 DiskController is the pick associated with variable 4, which in this example is the DiskController. This is an indication of bounceback behavior as previously explained. Constraint K1 can now be propagated as described above with reference to the "Bounceback Detection With No Conjunctions Or Disjunctions" section. Note, however, that the bounceback detection bit vector for the 40 Gbyte DiskDrive is set to #0001 (as opposed to #001) thereby accounting for the fourth variable, the DiskController. Next, constraint K4 can be propagated. Here, notice that 40 Mbyte DiskDrive is eliminated for two reasons: because of K1 and the fact that the 900 MHz CPU was not chosen, or because of K4 and the fact that the DC2 was not chosen. Thus, a join corresponding to a disjunction can be derived from the given constraints. This join could be stated logically: if either or both of the 700 MHz CPU or the DC1 DiskController are selected, then the 40 Mbyte DiskDrive cannot be selected. To propagate this join, the bounceback detection process logically ANDs the bounceback detection bit vector of the 900 MHz CPU with the bounceback detection bit vector of the DC2 DiskController. More specifically, #0001 is logically ANDed with #1000 thereby producing a bounceback detection bit vector of #0000 for the 40 Mbyte DiskDrive. The 40 Mbyte DiskDrive is therefore eliminated. The elimination flag associated with the 40 Mbyte DiskDrive is also set. Next, K2 can be propagated as described above with reference to the "Bounceback Detection With No Conjunctions Or Disjunctions" section. Note, however, that the bounceback detection bit vector for the 128 Mbyte Memory is set to #0000 (as opposed to #001) because of the disjunction associated with the elimination of the 40 Mbyte DiskDrive as explained above with reference to the propagation of K4. The bounceback detection bit vector of #0000 associated with the 40 Gbyte DiskDrive is propagated to the 128 Mbyte Memory (e.g., the bounceback detection bit vector associated with the 40 Gbyte DiskDrive is copied to the bounceback detection bit vector associated with the 128 Mbyte Memory). The 128 Mbyte Memory is therefore eliminated. Next, K3 can be propagated as described above with reference to the "Bounceback Detection With No Conjunctions Or Disjunctions" section. Note, however, that the bounceback detection bit vector for the 900 MHz CPU is set to #0000 (as opposed to #001) because the bounceback detection bit vector of #0000 associated with the 128 Mbyte Memory is propagated to the 900 MHz CPU (e.g., the bounceback detection bit vector associated with the 128 Mbyte Memory is copied to the bounceback detection bit vector associated with the 900 MHz CPU). The 900 MHz CPU is therefore eliminated. This elimination is confirmed by the bounceback detection bit vector associated with 900 MHz CPU because the bit position of that bit vector which corresponds to the CPU variable (the first bit) is not set to 1. In this case, therefore, the 900 MHz CPU has been appropriately eliminated as a result of subsequent constraint propagation. Consequently, if the user picks the 900 MHz CPU instead of the 700 MHz CPU, a constraint violation would occur because the user has also picked DC1. Similarly, DC2 is also eliminated as a result of subsequent constraint propagation. Note that propagation continues until the bounceback detection bit vectors reach quiescence. As such, bounceback detection bit vectors initially set to indicate bounceback may subsequently be modified to indicate elimination due to reasons other than bounceback. Bounceback Detection Over a Conjunction For this case, assume a configuration problem having the following four variables and respective domains: a CPU (700 MHz or 900 MHz), a DiskDrive (20 Gbyte or 30 Gbyte or 40 Gbyte), a DiskController (DC1 or DC2), and a Memory (64 Mbyte or 128 Mbyte). The ordering given to the variables is: variable 1=CPU, variable 2=DiskDrive, variable 3=DiskController, and variable 4=Memory. As there are four variables in this particular configuration problem, the bounceback detection bit vector associated with each domain member of each variable consists of 4 bits. The bounceback detection bit vector could be verbally described (excluding the commas) by: #Memory bit, DiskController bit, DiskDrive bit, CPU bit. In addition, assume the following constraints (Kn) are defined: The first given constraint, K1, states that the 700 MHz CPU is compatible with either the 20 Gbyte DiskDrive or the 30 Gbyte DiskDrive, and that the 900 MHz CPU is compatible with either the 30 Gbyte DiskDrive or the 40 Gbyte DiskDrive. It can further be stated that the 700 MHz CPU is not compatible with the 40 Gbyte DiskDrive, and that the 900 MHz CPU is not compatible with the 20 Gbyte DiskDrive. The second given constraint, K2, states that the DC1 is compatible with the 30 Gbyte DiskDrive, and that DC2 is compatible with either the 20 Gbyte DiskDrive or the 40 Gbyte DiskDrive. It can further be stated that the DC1 is not compatible with either the 20 Gbyte DiskDrive or the 40 Gbyte DiskDrive, and that DC2 is not compatible with the 30 Gbyte DiskDrive. The third given constraint, K3, states that the 64 Mbyte Memory is compatible with the 20 Gbyte DiskDrive, and that the 128 Mbyte Memory is compatible with either the 30 Gbyte DiskDrive or the 40 Gbyte DiskDrive. It can further be stated that the that the 64 Mbyte Memory is not compatible with either the 30 Gbyte DiskDrive or the 40 Gbyte DiskDrive, and that the 128 Mbyte Memory is not compatible with the 20 Gbyte DiskDrive. The fourth given constraint, K4, states that the 64 Mbyte Memory is compatible with the 700 MHz CPU, and that the 128 Mbyte Memory is compatible with the 900 MHz CPU. It can further be stated that the that the 64 Mbyte Memory is not compatible with the 900 MHz CPU, and that the 128 Mbyte Memory is not compatible with the 700 MHz CPU. Other logical conclusions and transformations may be drawn from the given constraints. Assume that the user has selected the 700 MHz CPU and the DC2 DiskController. Once the configuration side receives the user picks, the configuration system propagates the constraints associated with each pick. As such, the bounceback detection bit vector for the 900 MHz CPU is set to #0001, and the associated elimination flag is set. Likewise, the bounceback detection bit vector for the DC1 DiskController is set to #0100, and the associated elimination flag is set. Next, constraint K1 can be propagated. As a result, the 40 Gbyte DiskDrive is eliminated (because of the 700 MHz CPU selection), and its bounceback detection bit vector is set to #0001, and its associated elimination flag is set. Next, constraint K2 can be propagated. This results in the elimination of the 30 Gbyte DiskDrive (because of the DC2 selection). The bounceback detection bit vector associated with the 30 Gbyte DiskDrive is set to #0100, and the associated elimination flag is also set. Next, constraint K3 is propagated, with the result that the 128 Mbyte Memory is eliminated. This elimination occurs because both the 30 Gbyte and the 40 Gbyte DiskDrives have been eliminated. Thus, a join corresponding to a conjunction can be derived from the given constraints. This join could be stated logically: if both of the DC2 DiskController and the 700 MHz CPU are selected, then the 128 Mbyte Memory cannot be selected. To propagate this join, the bounceback detection process logically ORs the bounceback detection bit vector for the 30 Gbyte (eliminated by selection of the DC2 DiskController) and 40 Gbyte (eliminated by selection of the 700 MHz CPU) DiskDrives thereby yielding a bounceback detection bit vector of #0101 for the 128 Mbyte Memory. The elimination flag associated with the 128 Mbyte Memory is also set. Next, constraint K4 is propagated. As the elimination flag associated with the 128 Mbyte Memory is set, the 900 MHz CPU is also tentatively eliminated. The bounceback detection bit vector of the 900 MHz CPU is set to #0101 (since its elimination is necessitated by the elimination of the 128 Mbyte Memory, which has a bounceback detection bit vector is #0101). The elimination flag associated with the 900 MHz CPU is also set. The 900 MHz CPU is not really eliminated, however, because the bit in its bounceback detection bit vector corresponding to its variable (the first bit) is set to 1. Notice that if the user selected the 900 MHz CPU, thereby deselecting the 700 MHz CPU, this would not lead to a constraint violation, and so the 900 MHz CPU is appropriately not eliminated. The three example cases above illustrate bounceback detection in accordance with one embodiment of the present invention. For each selected variable, the bounceback detection bit vectors of the not selected domain members are initially set to the variable's identifier. Propagation of bounceback detection bit vectors can be accomplished by copying the bounceback detection bit vectors. Propagation of a join corresponding to a conjunction (AND) is achieved by logically ORing the corresponding bounceback detection bit vectors. Propagation of a join corresponding to a disjunction (OR) is achieved by logically ANDing the corresponding bounceback detection bit vectors. Bounceback is detected when a domain member's bounceback detection bit vector has the bit corresponding to the domain member's variable set to 1. Such domain members are not eliminated. Generally, note that in all cases bounceback detection is indicated when a domain member's bounceback detection bit vector has a 1 bit in the bit position that corresponds to the variable associated with that domain member. The values of the other bit positions for that domain member's bounceback detection bit vector will depend on factors such as the received user selections and the degree to which the given constraints have been propagated. FIG. 2 illustrates a method for detecting and eliminating bounceback behavior associated with a configuration problem in accordance with one embodiment of the present invention. This method may be implemented, for example, by the system illustrated in FIG. 1. However, other configuration systems may also beneficially employ the method as will be apparent in light of this disclosure. The present invention is not intended to be limited to any one type of configuration system. Assume the configuration problem defines a number of variables, the respective domains of each of those variables, and a number of constraints. In response to a user request, the method begins with generating 205 a page that provides user selectable features for a configurable product, and providing 210 the page to the user. In the system embodiment shown in FIG. 1, page generation module 140 can be used to carry out steps 205 and 210. Once the user receives the page and provides a number of selections, then the method proceeds with receiving 215 the user selections. The user selections may include a number of selected features where domain members for two or more variables are provided. Alternatively, the user selections may include a single selected feature (a domain member of one variable). The method further includes propagating 220 the constraints associated with the configurable product over the received user selections. The result of this propagation identifies incompatibilities between various product features given the current configuration state. The current configuration state represents the aggregate of received user selections at any one point in time during the configuration process. In the system embodiment shown in FIG. 1, configuration engine 125 can be used to effect step 220. The method further continues with modifying 225 the result of propagating the constraints by detecting and eliminating constraints caused by bounceback behavior. In the system embodiment shown in FIG. 1, bounceback detection module 120 can be used to effect step 225. The method may further include generating 230 a new page where the product features identified as incompatible with previously provided user selections are grayed out. Note, however, that product features eliminated solely due to bounceback are not grayed out. The method proceeds with providing 235 the new page to the user, and repeating 240 steps 215 through 235 until the product configuration is complete. FIG. 3 illustrates a method for detecting and eliminating bounceback behavior associated with a configuration problem in accordance with another embodiment of the present invention. This method may be implemented, for example, by a module combining the functionality of the bounceback detection module 120 and the configuration engine 125 of the system illustrated in FIG. 1. This combination module may be implemented in hardware, software, firmware or any combination thereof. For example, the described method steps can be carried out by a set of software instructions running on a conventional computer system or server. Assume the configuration problem defines a number of variables, the respective domains of each of those variables, and a number of constraints. The method begins with initializing 305 a bounceback detection bit vector for each domain member of each variable, and initializing 310 an elimination flag for each domain member. The method further includes receiving 315 a domain member selection for a particular variable. Note that any number of domain member selections for a corresponding number of variables can be received, depending on the user. The following steps can be performed for each domain member selection received. For discussion purposes, however, assume that one domain member selection is received. For the variable associated with the selected domain member, the method proceeds with setting 320 the bounceback detection bit vector of each non-selected domain member for that variable. Each set bounceback detection bit vector will thereby indicate that the variable associated with the selected domain member is responsible for elimination of the non-selected domain members. This setting can be used, therefore, to indicate that the non-selected domain members were eliminated because of bounceback behavior. The method further includes setting 325 the elimination flag of each non-selected domain member of the variable associated with the selected domain member. Each of these elimination flags can be used to indicate that its associated domain member is tentatively eliminated thereby facilitating propagation of the given constraints. Recall, however, that the corresponding bounceback detection bit vector can be used to effectively reinstate a domain member that was solely eliminated because of bounceback behavior. The method further includes propagating 330 the given constraints to identify eliminated domain members of the variables, and setting 335 the bounceback detection bit vector of those eliminated domain members to reflect the variable causing their elimination. In one embodiment, step 335 is achieved by propagating the relevant bounceback detection bit vectors as earlier described in reference to three fundamental cases: bounceback detection with no conjunctions or disjunctions, bounceback detection over a disjunction, and bounceback detection over a conjunction. In short, the bounceback detection bit vector associated with the domain member that is causing the elimination of another domain member is copied or otherwise propagated to the bounceback detection bit vector associated with the domain member being eliminated. Propagation of a join corresponding to a conjunction (AND) is achieved by logically ORing the corresponding bounceback detection bit vectors, while propagation of a join corresponding to a disjunction (OR) is achieved by logically ANDing the corresponding bounceback detection bit vectors. The method further includes setting 340 the elimination flag of each of the eliminated domain members. Upon completion of the method (for any number of domain selections provided by a user), a new configuration page can then be generated and presented to the user. The product features identified as incompatible with previously provided user selections are grayed out on the new page. Note, however, that product features eliminated solely due to bounceback are not grayed out. The method may be repeated each time the user submits one or more new domain selections. In an alternative embodiment of the present invention, bounceback detection is performed with a multiple pass approach. More specifically, constraint propagation is performed N+1 times, where N is equal to the number of variables for which user choices have been entered thus far. For each of the individual N variables, domain reductions are computed by propagating all of the user choices except the user choice associated with that individual variable. Thus, N iterations of propagation are performed. Each iteration is referred to as a pass. The aggregate effect of these N passes is that the remaining domain members for each variable are identified. Then, a final pass (the N+1 pass) where all of the user choices are represented is made in order to detect contradictions (e.g., a user choice that is not included in any of the reduced domains). The foregoing description of the embodiments of the invention has been presented for the purposes of illustration and description. It is not intended to be exhaustive or to limit the invention to the precise form disclosed. Many modifications and variations are possible in light of the above teaching. It is intended that the scope of the invention be limited not by this detailed description, but rather by the claims appended hereto.
|
Same subclass Same class Consider this |
||||||||||