111111
`
`1111111111111111111111111111111111111111111111111111111111111
`US008805825Bl
`
`c12) United States Patent
`Showers et al.
`
`(10) Patent No.:
`(45) Date of Patent:
`
`US 8,805,825 Bl
`Aug. 12, 2014
`
`(54) ATTRIBUTE PRIORITIZED
`CONFIGURATION USING A COMBINED
`CONFIGURATION-ATTRIBUTE DATA
`MODEL
`
`(75)
`
`Inventors: Brian K. Showers, Cedar Park, TX
`(US); Brandon M. Beck, Austin, TX
`(US); Nathan E. Little, Austin, TX (US)
`
`(73) Assignee: Versata Development Group, Inc.,
`Austin, TX (US)
`
`( *) Notice:
`
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 80 days.
`
`(21) Appl. No.: 11/034,141
`
`(22) Filed:
`
`Jan.12,2005
`
`(51)
`
`(52)
`
`(58)
`
`(56)
`
`(2006.01)
`
`Int. Cl.
`G06F 7100
`U.S. Cl.
`USPC .......................................... 707/723; 705/26.5
`Field of Classification Search
`USPC .......................................... 707/723; 705/26.5
`See application file for complete search history.
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`
`5,515,524 A
`5,708,798 A
`5,825,651 A
`6,002,854 A
`6,405,308 B1
`6,549,908 B1 *
`6,675,294 B1
`6,725,257 B1 *
`
`511996 Lynch et a!.
`111998 Lynch et a!.
`10/1998 Gupta et a!.
`12/1999 Lynch eta!.
`6/2002 Gupta et a!.
`4/2003 Loomans ...................... 707/101
`112004 Gupta et a!.
`4/2004 Cansler eta!. ................ 709/219
`
`6,810,406 B2 *
`6,871,198 B2 *
`7,043,407 B2
`7,043,464 B2 *
`7,127,313 B2 *
`7,140,013 B2 *
`7,200,582 B1
`7,200,583 B1 *
`7,216,092 B1 *
`7,552,102 B2 *
`2004/0122807 A1 *
`2005/0144090 A1 *
`2006/0111878 A1 *
`2007/0233730 A1 *
`* cited by examiner
`
`10/2004 Schlabach eta!. ............ 707/201
`111
`3/2005 Neal eta!.
`5/2006 Lynch et a!.
`5/2006 Abrahams ....................... 706/14
`10/2006 Neri .............................. 700/103
`1112006 Te'eni eta!. .................. 717/173
`4/2007 Smith
`4/2007 Shah eta!. ...................... 706/47
`5/2007 Weber et al ..................... 705/26
`6/2009 Huelsman eta!. .............. 706/47
`6/2004 Hamilton eta!. ................. 707/3
`6/2005 Gadamsetty eta!. ........... 705/26
`5/2006 Pendyala et al ................... 703/1
`10/2007 Johnston .................... 707/104.1
`
`Primary Examiner- Sherief Badawi
`Assistant Examiner- Christopher J Raab
`(7 4) Attorney, Agent, or Firm - Terrile, Cannatti, Chambers
`& Holland, LLP; Kent B. Chambers
`
`ABSTRACT
`(57)
`A combined configuration rules-attribute configuration sys(cid:173)
`tem uses an integrated configuration model to efficiently
`identify and attribute prioritize valid configuration answers.
`Submitting an attribute-based configuration query to the
`combined configuration rules-attribute configuration system
`allows the query to be answered in a single step. The com(cid:173)
`bined configuration rules and attribute data guide product
`configuration processing and minimize configuration pro(cid:173)
`cessing by, for example, calculating only the valid configu(cid:173)
`ration answers that are candidates for the preferred valid
`answer(s). Thus, the combined configuration rules-attribute
`configuration system can minimize the number of valid con(cid:173)
`figuration answers to be considered for presentation to a
`client system or other user of the combined configuration
`rules-attribute configuration system.
`
`20 Claims, 9 Drawing Sheets
`
`501(1)
`
`501(n)
`
`500
`
`Page 1 of 17
`
`FORD 1001
`
`

`
`U.S. Patent
`
`Aug. 12, 2014
`
`Sheet 1 of9
`
`US 8,805,825 Bl
`
`.....
`0
`
`co
`0
`
`c::
`<(
`
`.....
`~ en
`
`c:
`0
`... c:
`~ <ll
`::J'-
`C) C)
`1;::: c:
`c:UJ
`0
`(,)
`
`Q)
`"0
`0
`:2
`c:
`,Q
`
`iii ... ::J
`C)
`1;::: c:
`0
`(,)
`
`N
`0
`
`~
`Q)
`::::s
`0
`
`~ -9: -e ::s
`
`t' C\'S
`....
`.~
`
`.t:n u:
`
`Page 2 of 17
`
`FORD 1001
`
`

`
`U.S. Patent
`
`Aug. 12, 2014
`
`Sheet 2 of9
`
`US 8,805,825 Bl
`
`5 200
`
`Y1
`
`Y1,Y2
`
`Figure 2 (prior art)
`
`A1
`
`81,82
`
`C1
`
`C2
`
`X1,X2
`
`q
`A2 0 Q
`82 ¢ ¢
`¢ ¢
`X2 ¢ ¢
`6 6
`
`Page 3 of 17
`
`FORD 1001
`
`

`
`301(1)
`
`301(n)
`
`300
`
`Attribute
`Information
`308
`
`Preference
`Algorithm
`316
`
`Configuration
`Query
`310
`
`Valid
`Answers
`
`Weighted
`Answers
`
`Preferred
`Answer
`318
`
`312
`
`314
`
`Figure 3 (prior arl)
`
`~
`00
`•
`~
`~
`~
`
`~ = ~
`
`~
`~ ....
`
`~
`
`N
`N
`
`0 ....
`
`.j;o.
`
`rFJ =(cid:173)
`.....
`
`('D
`('D
`
`(.H
`
`0 .....
`\0
`
`d
`rJl
`00
`Oo = u.
`Oo
`N u. = """"'
`
`Page 4 of 17
`
`FORD 1001
`
`

`
`U.S. Patent
`
`Aug. 12, 2014
`
`Sheet 4 of9
`
`US 8,805,825 Bl
`
`Configuration rules are manipulated to
`
`form a configuration model that is /
`
`capable of answering configuration
`questions
`
`402
`
`Interrogate configuration model to
`
`provide a set of valid answers to a ___/ 404
`
`particular configuration query
`
`Apply attributes from an attribute
`information model to the valid answers
`
`to order to associate each valid answer ___/ 406
`
`with the attributes that apply to it,
`which associates a weight to each
`valid answer.
`
`Use a preference algorithm to select
`the preferred answer given the
`weighted valid answers.
`
`408
`___/
`
`Figure 4 (prior art)
`
`Page 5 of 17
`
`FORD 1001
`
`

`
`501(1) """'\
`
`I
`
`VIICIIL
`..... ___ .1_
`
`I
`
`• • •
`
`I Client L/ 501(n)
`
`System
`
`500
`
`Prioritized,
`Valid
`Configuration
`Answers
`
`512
`
`Configuration
`Query
`508
`
`Preference
`Algorithm
`510
`
`Configuration
`Rules-Attribute
`Model
`506
`
`Figure 5
`
`~
`00
`•
`~
`~
`~
`
`~ = ~
`
`~
`~ ....
`~
`N
`0 ....
`
`.j;o.
`
`('D
`('D
`
`rFJ =(cid:173)
`.....
`Ul
`0 .....
`\0
`
`d
`rJl
`00
`Oo = u.
`N u. = """"'
`
`Oo
`
`Page 6 of 17
`
`FORD 1001
`
`

`
`U.S. Patent
`
`Aug. 12, 2014
`
`Sheet 6 of9
`
`US 8,805,825 Bl
`
`Combine configuration data
`and attributes into a single
`configuration-attribute model
`capable of answering
`configuration queries.
`
`/60 2
`
`/
`:
`Receive
`Configuration __./
`Query
`
`604
`
`Interrogate configuration(cid:173)
`attribute model with a
`r
`configuration query and a
`606
`preference algorithm to ~
`determine a preferred and
`valid configuration answer.
`
`1
`
`Provide preferred valid
`configuration answer(s) to
`user client system.
`
`I
`
`r
`f-../
`
`608
`
`Figure 6
`
`Page 7 of 17
`
`FORD 1001
`
`

`
`U.S. Patent
`
`Aug. 12, 2014
`
`Sheet 7 of9
`
`US 8,805,825 Bl
`
`702
`
`704
`
`~700
`
`706
`
`708
`
`710
`
`Figure 7
`
`Page 8 of 17
`
`FORD 1001
`
`

`
`U.S. Patent
`
`Aug. 12, 2014
`
`Sheet 8 of9
`
`US 8,805,825 Bl
`
`804(1}
`
`806(3)
`
`806(N} 806(N-1}
`
`806(9}
`
`Figure 8
`
`Page 9 of 17
`
`FORD 1001
`
`

`
`U.S. Patent
`
`Aug. 12, 2014
`
`Sheet 9 of9
`
`US 8,805,825 Bl
`
`900
`
`917
`
`~ ~
`
`919
`
`1/0
`
`I~
`
`916
`
`~
`1:
`li
`~~1-----.1
`11
`
`VIDEO
`DRIVER
`
`913
`
`914
`
`~ ~
`~
`VIDEO
`MEMORY I~
`
`MAIN
`MEMORY
`
`I ~ 915
`!.._...../
`
`918
`
`~
`
`1
`
`Iii ~ 910
`USER INPUT IH-_../
`DEVICE(S) F li
`
`MASS
`STORAGE
`
`v909
`
`Figure 9
`
`Page 10 of 17
`
`FORD 1001
`
`

`
`US 8,805,825 Bl
`
`1
`ATTRIBUTE PRIORITIZED
`CONFIGURATION USING A COMBINED
`CONFIGURATION-ATTRIBUTE DATA
`MODEL
`
`BACKGROUND OF THE INVENTION
`
`1. Field of the Invention
`The present invention relates in general to the field of
`information processing, and more specifically to a system and
`method for prioritizing configuration using a combined con(cid:173)
`figuration-attribute data model.
`2. Description of the Related Art
`Computer assisted product configuration continues to offer
`substantial benefits to a wide range of users and industries.
`FIG. 1 depicts a conventional product configuration process
`100 performed by a configuration engine 101. The configu(cid:173)
`ration process 100 represents one embodiment of an infer(cid:173)
`ence procedure. In one embodiment of a conventional infer(cid:173)
`ence procedure, configuration query 102 is formulated based
`on user configuration input, a configuration engine performs
`the configuration query 102 using a configuration model104,
`and the configuration engine provides an answer 106 to the
`configuration query 102 based on the configuration query 102
`and the contents of the configuration model104. The answer
`106 represents a particular response to the configuration
`query 102.
`A configuration model104 uses, for example, data, rules,
`and/or constraints (collectively referred to as "data") to define
`compatibility relationships between parts (also commonly
`referred to as "features") contained in a specific type of prod(cid:173)
`uct. A part represents a single component or attribute from a
`larger, more complex system. Parts may be combined in
`different ways in accordance with rules and/or constraints to
`define different instances of the more complex system. For
`example, "V6 engine" or the exterior color "red" can be parts
`on a vehicle, and a specific hard disk drive can be a part on a
`computer. A part group, also called a group or family, repre(cid:173)
`sents a collection of related parts. For example, an "Engines"
`group might contain the parts "V6 engine" and "4 cylinder
`engine". A product configuration is a set of parts that define a
`product. For example, a vehicle configuration containing the
`parts "V6 engine" and "red" represents a physical vehicle that
`has a red exterior and a V6 engine. A product can be a physical
`product such as a vehicle, computer, or any other product that 45
`consists of a number of configurable features such as an
`insurance product. Additionally, a product can also represent
`a service such as financial services, insurance services, or
`consulting services.
`An attribute represents a particular detail about a part or 50
`part group. Attributes describe details about the part or part
`group. A single part or part group can have many attributes.
`For example, the part "V 6 engine" might have a price attribute
`of"$500", a weight attribute of"1,000 lbs" and a description
`attribute of"Six cylinder gas engine." Also, an attribute for a 55
`given part or part group may change depending on context
`(what other parts or attributes are present). For example, the
`price attribute for the "V6 engine" might be "$500" when the
`"XLT trim" part is present and the price attribute for the "V6
`Engine" might be "$800" when the "XL trim" part is present. 60
`A configuration query (also referred to as a "query") is
`essentially a question that is asked about the parts, relation(cid:173)
`ships, and attributes in a configuration model. The answer
`returned from a configuration query will depend on the data in
`the configuration model, the approach used for answering the 65
`question, and the specifics of the question itself. For example,
`one possible configuration query, translated to an English
`
`2
`sentence, is the following: For the given configuration model,
`are the parts "red" and "V6 engine" compatible with each
`other? Another possible configuration query is the following:
`For the given configuration model, is the "V6 engine" part
`standard or optional when in the presence of the "XLT trim",
`"XL trim", "USA", and "Canada" parts, wherein "standard"
`and "optional" are attributes?
`The configuration model1 04 can be used to determine, for
`example, which parts are compatible with other parts, and
`10 provide additional details around specific relationships. For
`example, a vehicle configuration model can indicate that
`"red" (a part) is the standard feature from the color part group
`for a specific vehicle and "red" is not compatible with "V6
`engine" (a part). Configuration model104 may also contain
`15 additional information needed to support specific product
`related queries. Configuration models can be developed in
`any number of ways. U.S. Pat. No. 5,825,651 entitled
`"Method and Apparatus for Maintaining and Configuring
`Systems", inventors Gupta et a!., and assigned to Trilogy
`20 Development Group, Inc., describes an example configura(cid:173)
`tion engine and rules based configuration model. U.S. Pat.
`No. 5,825,651 (referred to herein as the "Gupta Patent") is
`incorporated herein by reference in its entirety. U.S. Pat. No.
`5,515,524 entitled "Method and Apparatus for Configuring
`25 Systems", inventors John Lynch and David Franke, and
`assigned to Trilogy Development Group, Inc., describes
`another example configuration engine and constraint based
`configuration model. U.S. Pat. No. 5,515,524 (referred to
`herein as the "Lynch Patent") is also incorporated by refer-
`30 ence in it entirety.
`FIG. 2 depicts an example configuration model 200 of a
`product represented in a graphical, tree based form. The prod(cid:173)
`uct can be configured to include part combinations A1, B 1 or
`B2, C1, X1 or X2, and Y1 or configured to include part
`35 combinations A2, B2, C2, X2, and Y1 or Y2. The configura(cid:173)
`tion model 200 includes rules to define these part relation(cid:173)
`ships. Table 1 represents an example rule set, wherein "S"
`represents "standard" and "0" represents optional. Configu(cid:173)
`ration model 200 represents a relatively non-complex con-
`40 figuration model. Actual configuration models for a single
`product can include hundreds of thousands or more parts,
`rules, and attributes.
`
`TABLE 1
`
`Example Configuration
`Rules for a Product
`
`Al SALL
`A20ALL
`Bl SAl
`B2 SA2
`B20Al
`Cl SAl
`C2 SA2
`Xl S Cl
`X2 S C2
`X20Cl
`Yl S Cl
`Yl S C2
`Y20C2
`
`Many configuration queries are formulated with respect to
`attribute values. Such processing is referred to herein as
`"attribute-based configuration" Attributes can (1) be used to
`find "preferred" answers to configuration queries (such que(cid:173)
`ries are referred to herein as "attribute-prioritized queries"),
`(2) be an output of a configuration query (such queries are
`referred to herein as "attribute queries"), and (3) be used in a
`query that is both an attribute-prioritized query and an
`
`Page 11 of 17
`
`FORD 1001
`
`

`
`US 8,805,825 Bl
`
`3
`attribute query. An example of an attribute-prioritized query
`is the following: "Given a set of configured parts, return the
`part with the lowest cost that is compatible with the given
`parts, according to the rules in a given configuration model".
`An example of an attribute query is the following: "Given a
`configuration model and a fully specified configuration,
`determine the sum of the price attributes for all of the parts in
`that configuration." Attribute-based configuration processing
`has conventionally suffered from scale and performance
`issues, an example of which is described below.
`Example: A Conventional Approach to Attribute-Priori(cid:173)
`tized Solutions
`When more than one answer to a configuration query is
`valid, the attributes of each configuration answer can be used
`to assign a preference weighting to the valid answers. For
`example, there may be many answers that satisfy the configu(cid:173)
`ration query of"Add parts to the list of 'red' and 'V6 engine'
`until a complete vehicle is specified." However, attribute val(cid:173)
`ues can be used to identifY preferred valid answers such as the
`least expensive vehicle, the most expensive vehicle, the
`heaviest vehicle, etc.
`FIG. 3 depicts a conventional attribute based priority con(cid:173)
`figuration system 300 (also referred to as a "conventional
`attribute based priority configuration engine"), and FIG. 4
`depicts a conventional attribute based priority solution pro(cid:173)
`cess 400 to determine an attribute based priority solution.
`Client systems 301(1) through301(n) access the conventional
`attribute based priority solution system 300 via a network
`302, such as the Internet. The system 300 and process 400 are
`typically implemented configured as a server computer sys- 30
`tern.
`Conventionally, a configuration model304 is driven solely
`by configuration rules 306. Thus, in operation 402, configu(cid:173)
`ration rules 306 are manipulated to form a configuration
`model 304 that is capable of answering configuration ques(cid:173)
`tions. The configurationmodel304 is separated from attribute
`information 308 and, thus, the configuration model304 is not
`used to process attribute related data. In operation 404, the
`conventional attribute based priority solution process 400
`answers an attribute specific configuration query 310 to deter- 40
`mine an attribute based priority solution by querying configu(cid:173)
`ration model 304 for the set of valid answers 312. The valid
`answers 312 represent product configurations that conform to
`the configuration model 304. Operation 404 interrogates the
`configuration model304 to find the preferred answer from the
`set of valid answers. Operation 406 then applies attribute
`information 308 to the valid answers 312 to associate each
`valid answer with the attributes that apply to the valid answer.
`A weight can be derived from the applied attribute informa(cid:173)
`tion 308 to generate weighted answers 314. For example, for
`the attributes "standard" and "optional", the weight can be the
`total number of standard features or the total number optional
`features in each answer. Operation 408 uses a preference
`algorithm 316, e.g. search for the valid answer with the most
`standard features and lowest price, to select the preferred 55
`valid answer 318 given the weighted valid answers. The par(cid:173)
`ticular preference algorithm is a matter of system usage. Once
`a preferred answer is selected, conventional attribute based
`priority solution process 400 can determine answers for the
`next configuration query.
`A software application developed by Trilogy Development
`Group, Inc. and referred to as "MCC Config" implemented
`the conventional attribute based priority configuration system
`300 using a modified attribute based priority solution process
`400. MCC Config solved a configuration problem by taking 65
`partial configuration answers as input data and over iterative
`processes, provided a complete configuration output. The
`
`60
`
`4
`modified process was an iterative process that created a
`single, preferred complete configuration over multiple itera(cid:173)
`tions, rather than providing all valid complete configurations
`and choosing a preferred one. For each iteration the configu(cid:173)
`ration model 304 provided a set of part selections. The set of
`part selections formed a subset of all of the part selections that
`needed to be made to generate a preferred, complete configu(cid:173)
`ration. The modified process then used the attribute informa(cid:173)
`tion 308 and the preference algorithm 316 to make the part
`10 selections provided by the configuration model 304. Part
`selections answers were then fed back into the configuration
`model 304 and added to the partial configuration answers.
`The partial configuration answers were then used by the con(cid:173)
`figuration model3 04 to generate the next set of part selections
`15 that needed to be made, and so on until the configuration was
`completed. For example, in an automotive configuration con(cid:173)
`text, a user could initially select: engine=V6 and color=red.
`The configuration engine could determine that, for example,
`2 different transmissions and 6 different body styles were
`20 compatible with engine=V6 and color=red. The modified
`process would then select a transmission and body style from
`the set of transmissions and body styles provided according to
`the preference algorithm 316. If"standard" was the control(cid:173)
`ling preference in the preference algorithm 316, the modified
`25 process would select the standard transmission and body
`style, if possible, from the available choices. The selected
`transmission and body style would then be added to the initial
`user selections and the process would repeat until a complete
`configuration was attained.
`Process 400 exhibits the drawback of expending effort to
`determine valid answers that will eventually be ignored if
`they are not preferred by the attribute model. Also, the num(cid:173)
`ber of valid answers can be so large that calculating the full set
`and identifYing the preferred answer is often computationally
`35 infeasible.
`
`SUMMARY OF THE INVENTION
`
`In one embodiment of the present invention, a method for
`using computer assisted configuration technology to generate
`one or more attribute prioritized configuration answers to one
`or more configuration queries includes receiving one or more
`configuration queries from a client system. The method fur(cid:173)
`ther includes processing the one or more configuration que-
`45 ries using a combined configuration rules-attributes model to
`determine valid configuration answers prioritized by one or
`more predetermined attributes and providing at least a subset
`of the valid configuration answers to the client system.
`In another embodiment of the present invention, a com-
`50 puter system to generate one or more attribute prioritized
`configuration answers to one or more configuration queries
`includes a processor and a storage medium having data
`encoded therein. The data includes processor executable code
`for:
`receiving one or more configuration queries from a client
`system;
`processing the one or more configuration queries using a
`combined configuration rules-attributes model to deter(cid:173)
`mine valid configuration answers prioritized by one or
`more predetermined attributes; and
`providing at least a subset of the valid configuration
`answers to the client system.
`In another embodiment of the present invention, a com(cid:173)
`puter storage medium includes data embedded therein to
`cause a computer system to generate one or more attribute
`prioritized configuration answers to one or more configura-
`tion queries. The data includes processor executable code for:
`
`Page 12 of 17
`
`FORD 1001
`
`

`
`US 8,805,825 Bl
`
`5
`receiving one or more configuration queries from a client
`system;
`processing the one or more configuration queries using a
`combined configuration rules-attributes model to deter(cid:173)
`mine valid configuration answers prioritized by one or
`more predetermined attributes; and
`providing the valid configuration answers to the client sys(cid:173)
`tem.
`In another embodiment of the present invention, a com(cid:173)
`puter system to generate one or more attribute prioritized
`configuration answers to one or more configuration queries
`includes means for receiving one or more configuration que(cid:173)
`ries from a client system. The computer system further
`includes means for processing the one or more configuration
`queries using a combined configuration rules-attributes
`model to determine valid configuration answers prioritized
`by one or more predetermined attributes and means for pro(cid:173)
`viding at least a subset of the valid configuration answers to
`the client system.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`20
`
`6
`terns 501(1) through 501(n) via a network such as the Inter(cid:173)
`net, wherein n2: 1. The combined configuration rules-attribute
`configuration system 500 can also be referred to as a configu(cid:173)
`ration engine. Combined configuration rules-attribute con(cid:173)
`figuration system 500 operates in accordance with combined
`configuration rules-attribute configuration process 600.
`Operation 602 integrates configuration rules 502 and attribute
`information 504 into a configuration rules-attribute model
`506. Configuration rules 502 are any type of configuration
`10 rules data such as the configuration rules described with ref(cid:173)
`erence to Table 1. As described above, attributes can represent
`any particular detail about a part or part group. Table 2 sets
`forth example attribute types. An attribute can also be an
`15 aggregate of other attributes. For example, a part group price
`may be an aggregate of prices for other parts and/or part
`groups.
`
`TABLE2
`
`Example Attribute Types
`
`Standard
`Optional
`Price
`Weight
`Towing Capacity
`Description
`Warranty
`Fuel Efficiency
`
`The present invention may be better understood, and its
`numerous objects, features and advantages made apparent to
`those skilled in the art by referencing the accompanying 25
`drawings. The use of the same reference number throughout
`the several figures designates a like or similar element.
`FIG. 1 (prior art) depicts a conventional product configu-
`ration process.
`FIG. 2 (prior art) depicts a configuration model in graphi- 30
`cal, tree based form.
`FIG. 3 (prior art) depicts a conventional attribute based
`priority solution system.
`FIG. 4 (prior art) depicts a conventional attribute based
`priority solution process.
`FIG. 5 depicts a combined configuration rules-attribute
`configuration system.
`FIG. 6 depicts a combined configuration rules-attribute
`configuration process.
`FIG. 7 depicts an example trie implementation of a con- 40
`figuration rules-attributes model.
`FIG. 8 depicts a block diagram illustrating a network envi(cid:173)
`ronment in which the system and process of FIGS. 5 and 6
`may be practiced.
`FIG. 9 depicts an example data processing system used in 45
`the network of FIG. 8.
`
`DETAILED DESCRIPTION
`
`A combined configuration rules-attribute configuration
`system uses an integrated configuration model to efficiently
`identify and attribute prioritize valid configuration answers to
`attribute-prioritized configuration queries. Submitting an
`attribute-based configuration query to the combined configu(cid:173)
`rationrules-attribute configuration system allows the query to
`be answered in a single step. The combined configuration
`rules and attribute information guide product configuration
`processing and minimize configuration processing by, for
`example, calculating only the valid configuration answers
`that are candidates for the preferred valid answer( s ). Thus, the
`combined configuration rules-attribute configuration system
`can minimize the number of valid configuration answers to be
`considered for presentation to a client system or other user of
`the combined configuration rules-attribute configuration sys(cid:173)
`tem.
`FIG. 5 depicts combined configuration rules-attribute con(cid:173)
`figuration system 500 communicatively coupled to client sys-
`
`The implementation of configuration rules-attributes
`model 506 is a matter of design choice. In one embodiment,
`the configuration rules-attributes model 506 is implemented
`as a trie, and trie operations are used to manipulate the data.
`Example tries and trie operations are set forth in U.S. Pat. No.
`35 7,200,582, issued Apr. 3, 2007, entitled "Configuration
`Model Consistency Checking Using Flexible Rule Space
`Subsets", inventor Shawn A. P. Smith, filing date Mar. 31,
`2003, and assigned to Trilogy Development Group, Inc. U.S.
`Pat. No. 7,200,582 is hereby incorporated by reference in its
`entirety.
`FIG. 7 depicts an example trie implementation of configu(cid:173)
`ration rules-attributes model 506. The trie implemented con(cid:173)
`figuration rules-attributes model 700 includes a root node X1
`and two part groups 702 and 704. Each complete branch of the
`model 700 represents a valid configuration. A trie-based rep(cid:173)
`resentation can be used to represent the valid combinations in
`a compact and precise marmer. Nodes in part group 702
`contain partsA1, A2, andA3. Each of the partsA1, A2, andA3
`may be armotated with one or more associated attributes such
`so asATTA1, ATTA2, andATTA3. Each of the parts B1 and B2
`may include one or more attributes such as ATTB 1 and
`ATTB2. The attributes associated with different parts may be
`the same or may be different. Model 700 additionally
`includes leaf nodes 706, 708, and 710 with associated aggre-
`55 gate attribute values. For example, each leaf node could
`include the total number of standard parts in the product
`represented by the valid configuration branch to which the
`leaf node is attached and/or could include the price of the
`product represented by the valid configuration branch to
`60 which the leaf node is attached.
`In one embodiment, "release" attributes are combined with
`configuration rules to form the configuration rules-attributes
`model506. "Release" attributes describe how a part is avail(cid:173)
`able within a valid configuration context. For example,
`65 release attributes could specifY that the "V6 engine is the
`'standard' engine" and the "V8 engine is an 'optional'
`engine." Thus, in one embodiment, the configuration rules-
`
`Page 13 of 17
`
`FORD 1001
`
`

`
`US 8,805,825 Bl
`
`7
`attributes model 506 not only represents which combinations
`of parts are valid together but also how those parts are
`released.
`Referring to FIGS. 5, 6, and 7, client systems 501(1)
`through 501(n) each access combined configuration rules(cid:173)
`attribute configuration system 500 to configure a product by
`submitting a respective configuration query 508. The particu-
`lar data structure( s) used to represent configuration query 508
`is a matter of design choice and depends upon, for example,
`configuration engine specifications, etc. In one example, the 10
`configuration query 508 results from the selection of a par(cid:173)
`ticular feature displayed via a web browser application
`executed by client system 501(i), wherein i is an element of
`the set { 1, ... , n}. The combined configuration rules-attribute
`configuration system 500 receives the configuration query 15
`508 in operation 604. In operation 606, combined configura(cid:173)
`tion rules-attribute configuration system 500 interrogates
`configuration rules-attributes model 506 with configuration
`query 508 and an attribute based preference algorithm 510 to
`determine a set of one or more attribute prioritized, valid 20
`configuration answers 512. In one embodiment, combined
`configuration rules-attribute configuration system 500 pro(cid:173)
`cesses the configuration query 508 and configuration rules of
`configuration rules-attributes model 506 in accordance with
`the Gupta Patent or the Lynch Patent.
`The preference algorithm 510 is a matter of system usage
`and depends upon which preferences are anticipated to be
`consistent with the user preferences of client system 501(i).
`For example, the user of client 501(i) could select the prefer(cid:173)
`ence(s) for valid configuration answers or some or all of the 30
`preference( s) could be predetermined by combined configu(cid:173)
`ration rules-attribute configuration system 500. In one
`embodiment, a preference is for maximizing the number of
`standard parts. Thus, only valid configurations with a maxi(cid:173)
`mum number of standard parts or a number of standard parts 35
`that is greater than or equal to a predetermined threshold are
`determined to be valid answers. In another embodiment, only
`valid configurations that have a towing capacity greater than
`or equal to a predetermined threshold are determined to be
`valid answers. The preference algorithm can then prioritize 40
`valid configurations based upon evaluation of more than one
`type of attribute. For example, only valid configuration
`answers with a maximum number of standard parts, a fuel
`efficiency greater than or equal to a predetermined threshold,
`and a price less than or equal to a predetermined threshold are 45
`presented to a user. The valid answers can be prioritized in
`accordance with one or more attribute values. For example,
`valid answers can be ordered based on lowest to highest price.
`Thus, operation 606 uses the configuration rules-attributes
`model506 to process each configuration query 508 with valid 50
`answers determined in accordance with preference algorithm
`510. For example, the preference algorithm could prefer valid
`configurations that maximize the combined number of stan(cid:173)
`dard-attribute features in the answer. For example, the con(cid:173)
`figuration query 506 might be to "Find the complete configu- 55
`ration that contains that parts "red" and "V 6" and maximizes
`the number of standard-attribute parts." There could be many
`possible configurations that contain "red" and "V6" but the
`configuration rules-attributes model 506 allows operation
`606 to single out the valid answers that meet the preference 60
`algorithm. Thus, operation 606 does not spend resources
`calculating other "red" and "V6" configurations that do not
`contain the maximal number of standard parts.
`Once operation 606 determines one or more prioritized,
`valid configuration answers 512, operation 608 provides the 65
`attribute prioritized, valid configuration answer(s) 512 to the
`client system 501(i) that submitted the configuration query
`
`8
`508. The number of prioritized, valid configuration answers
`can be a predefined number or a user selected number. For
`example, if "standard" and "price" are the controlling pref(cid:173)
`erences, only "X" valid configuration answers 512 are pro(cid:173)
`vided to the user, where X is the predefined or user selected
`number. The combined configuration rules-attribute configu(cid:173)
`ration process 600 then returns to operation 604 to process a
`subsequent configuration query 508.
`Thus, it is often the case that a single set of configuration
`rules and a single set of attributes will be used to perform
`many c