111111
`
`1111111111111111111111111111111111111111111111111111111111111
`US007882057Bl
`
`c12) United States Patent
`Little et al.
`
`(10) Patent No.:
`(45) Date of Patent:
`
`US 7,882,057 Bl
`Feb. 1, 2011
`
`(54)
`
`COMPLEX CONFIGURATION PROCESSING
`USING CONFIGURATION SUB-MODELS
`
`(75)
`
`Inventors: Nathan E. Little, Austin, TX (US);
`Brandon M. Beck, Austin, TX (US);
`Brian K. Showers, Cedar Park, TX (US)
`
`6,675,294 B1
`6,721,748 B1 *
`7,043,407 B2
`7,200,582 B1
`7,464,064 B1
`2003/0187950 A1 *
`
`112004 Gupta et a!.
`4/2004 Knight et a!.
`5/2006 Lynch et a!.
`4/2007 Smith
`12/2008 Smith
`10/2003 Rising, III
`
`.. ... ... .. ... ... .. 707/3
`
`.................. 709/218
`
`(73) Assignee: Trilogy 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 0 days.
`
`(21) Appl. No.: 10/957,919
`
`(22) Filed:
`
`Oct. 4, 2004
`
`(51)
`
`(52)
`(58)
`
`Int. Cl.
`G06F 17100
`(2006.01)
`G06N 5104
`(2006.01)
`U.S. Cl. ........................................................ 706/60
`Field of Classification Search . ... ... ... ... .. ... ... 706/1,
`706/15, 45, 46, 47, 6, 20, 8, 28, 60; 700/1,
`700/90, 30; 707/3, 10; 709/218; 710/8;
`703/25; 705/56, 26, 103
`See application file for complete search history.
`
`(56)
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`
`5,515,524 A
`5,708,798 A
`5,825,651 A *
`6,002,854 A
`6,115,547 A
`6,167,383 A *
`6,405,308 B1
`6,430,730 B1
`
`................ 700/103
`
`511996 Lynch
`111998 Lynch et a!.
`10/1998 Gupta eta!.
`12/1999 Lynch eta!.
`9/2000 Ghatate eta!.
`12/2000 Henson ....................... 705/26
`6/2002 Gupta et a!.
`8/2002 Ghatate eta!.
`
`OTHER PUBLICATIONS
`
`http:/ /web.archive.org/web/20030324212039/http:/ /fordvehicles.
`com/.*
`* cited by examiner
`Primary Examiner-Michael B. Holmes
`Assistant Examiner-Peter Coughlan
`(74) Attorney, Agent, or Firm-Hamilton & Terrile, LLP;
`Kent B. Chambers
`
`(57)
`
`ABSTRACT
`
`A configuration model dividing and configuration sub-model
`inference processing system and procedure addresses the
`issue of configuration model and query complexity by break(cid:173)
`ing a configuration problem down into a set of smaller prob(cid:173)
`lems, solving them individually and recombining the results
`into a single result that is equivalent to a conventional infer(cid:173)
`ence procedure. In one embodiment, a configuration model is
`divided into configuration sub-models that can respectively
`be processed using existing data processing resources. A sub(cid:173)
`model inference procedure provides a way to scale queries to
`larger and more complicated configuration models. Thus, the
`configuration model dividing and configuration sub-model
`processing system and inference procedure allows processing
`by a data processing system of configuration models and
`queries whose collective complexity exceeds the complexity
`of otherwise unprocessable conventional, consolidated con(cid:173)
`figuration models and queries.
`
`46 Claims, 8 Drawing Sheets
`
`401(1)
`
`401(n)
`
`414
`
`I
`I
`I
`I
`I
`
`L---------------------------------------1
`
`Page 1 of 19
`
`FORD 1201
`
`

`
`U.S. Patent
`
`Feb. 1, 2011
`
`Sheet 1 of8
`
`US 7,882,057 Bl
`
`..-
`0 ..-
`
`c:
`
`0 = Q)
`ro
`.._ c:
`::I ·-C) C)
`~ c:
`c:W
`0
`(.)
`
`Q)
`"0
`0
`~
`c:
`
`0 = ro
`.._
`::I
`C)
`~ c:
`0
`(.)
`
`g:
`......
`
`>.
`
`... Cl)
`:::::s a
`
`r...
`
`t' cu
`-~ r..;;; .s
`....
`e :::s
`-~ u::
`
`Page 2 of 19
`
`FORD 1201
`
`

`
`U.S. Patent
`
`Feb. 1, 2011
`
`Sheet 2 of8
`
`US 7,882,057 Bl
`
`5 200
`
`A1
`
`A2
`
`81,82
`
`82
`
`C1
`
`C2
`
`X1,X2
`
`X2
`
`Y1
`
`Y1,Y2
`
`6 6
`
`Figure 2 (prior arl)
`
`Page 3 of 19
`
`FORD 1201
`
`

`
`U.S. Patent
`
`Feb. 1, 2011
`
`Sheet 3 of8
`
`US 7,882,057 Bl
`
`>--")(
`
`C].) a.
`E
`0
`(.)
`~
`C].)
`:::J
`0
`"C
`c:
`ro
`C].)
`"C
`
`0 :r:
`c:
`0
`~
`~
`:::J
`0>
`\;:: c:
`0
`(.)
`
`-....
`t
`Ctl
`....
`.o
`t:
`~
`(W)
`e
`:::,
`.t:n
`u:
`
`m
`
`- (f)X.O
`
`0>
`>-
`. :=
`-
`c:
`ro ·c;;
`ro
`ro
`ro CD
`0 :r: a.
`0
`o
`ro
`....
`a..
`(.)
`
`0> c
`"(i) >-
`( / ) (cid:173)
`Q):=
`
`o:O e ro
`a.. a.
`ro
`~(.)
`ro
`0
`
`Page 4 of 19
`
`FORD 1201
`
`

`
`401 (1)
`
`• • •
`
`Client
`System
`
`401 (n)
`
`- - - - - -
`
`406
`
`i-+
`
`CM1
`
`- 11::"1
`ie.JIQSII-+
`I
`L::JI
`IIQ211Qsll-+
`L.::J
`-+
`'r;:;:;-J
`I ..... M4
`I-+
`
`400
`
`~---
`
`A
`
`,:•1
`
`1
`
`_
`
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`L---------------------------------------
`
`,-
`I
`
`414
`
`I,
`
`l1
`II
`II
`II
`I
`
`Q
`
`•
`
`----;::r
`402 - - - - - - (cid:173)
`- - ,
`------ ---.;;;.- ------ ----.--
`- - ·- -
`--~--
`-~---- ,L _____ -+16~,
`[_ - -
`---,r.:;-]
`1
`M2 -~~fA.l1
`I
`-+ lr::;l
`L.::J I
`I
`-+ lfAil i
`I
`-+ 10
`1
`..... I 0 I An I,
`11 I~ :
`CMn •• • -+I~ I
`:~
`:IQ418~~-~---------l_~~-------~
`-~404
`
`c..:-_____
`----!
`,:
`__!
`1 ___ _.
`
`410
`
`Consolidated
`Configuration
`Model
`
`Figure 4
`
`~
`00
`•
`~
`~
`~
`
`~ = ~
`
`""f'j
`('D
`?'
`.... ~
`0 ....
`....
`
`N
`
`rFJ =(cid:173)
`......
`.j;o.
`
`('D
`('D
`
`0 .....
`
`QO
`
`d
`rJl
`-....l
`Oo
`00
`
`N = u.
`-....l = """"'
`
`Page 5 of 19
`
`FORD 1201
`
`

`
`~500
`
`Data
`Processing
`Max.
`Capability
`
`- - - - - - - -·- - - - - - - - - - - - - - - - _,_ - - - - - - - ....
`
`Consolidated
`&]configuration Model
`412
`
`Data Processing
`Capability
`
`~
`00
`•
`~
`~
`~
`
`~ = ~
`
`""f'j
`('D
`?'
`......
`N
`0 ......
`......
`
`~
`
`('D
`('D
`
`rFJ =(cid:173)
`......
`Ul
`0 ......
`
`QO
`
`Configuration Sub-Model and Sub-Query Complexity
`
`Figure 5
`
`d
`rJl
`-....l
`Oo
`00
`
`N = u.
`-....l = """"'
`
`Page 6 of 19
`
`FORD 1201
`
`

`
`U.S. Patent
`
`Feb. 1, 2011
`
`Sheet 6 of8
`
`US 7,882,057 Bl
`
`A, 8, C Sub-Model
`
`~ 602
`
`Consolidated Model
`
`---...,
`
`~CM1
`
`A1
`
`A2
`
`Q
`d b
`¢ ¢
`6 6
`
`81,82
`
`82
`
`C1
`
`C2
`
`--
`-
`
`C, X Sub-Model
`
`C, Y Model
`
`X1
`
`X2
`
`Y1
`
`Y2
`
`Q ~CM2 Q ~CM3
`d b d b
`6 6 6 6
`
`C1
`
`C1,C2
`
`C1,C2
`
`C2
`
`Figure 6
`
`A1
`
`A2
`
`81,82
`
`82
`
`C1
`
`C2
`
`X1,X2
`
`X2
`
`Q
`0 Q
`0 0
`0 ¢
`¢ 0
`6 6
`
`Y1
`
`Y1,Y2
`
`Page 7 of 19
`
`FORD 1201
`
`

`
`U.S. Patent
`
`Feb. 1, 2011
`
`Sheet 7 of8
`
`US 7,882,057 Bl
`
`704(1)
`
`706(3)
`
`706(7)
`
`706(N) 706(N-1)
`
`706(9)
`
`Figure 7
`
`Page 8 of 19
`
`FORD 1201
`
`

`
`U.S. Patent
`
`Feb. 1, 2011
`
`Sheet 8 of8
`
`US 7,882,057 Bl
`
`819
`
`816
`
`c!
`
`p
`
`1/0
`
`DRIVER
`
`• I VIDEO
`Processor I
`VIDEO I
`
`813
`
`,---J
`
`814
`
`~
`
`MEMORY
`
`j~
`
`818
`
`800
`
`817
`
`~ ~ I DISP~J
`MAIN JvB 15
`
`MEMORY
`
`~
`
`STORAGE I_/ 809
`
`MASS
`
`USER INPUT ~~/ 810
`
`DEVICE(S)
`
`~~;;II
`
`~~~
`
`Figure 8
`
`Page 9 of 19
`
`FORD 1201
`
`

`
`US 7,882,057 Bl
`
`1
`COMPLEX CONFIGURATION PROCESSING
`USING CONFIGURATION SUB-MODELS
`
`BACKGROUND OF THE INVENTION
`
`2
`tion engine and rules based configuration model. U.S. Pat.
`No. 5,825,651 is incorporated herein by reference in its
`entirety. U.S. Pat. No. 5,515,524 entitled "Method and Appa(cid:173)
`ratus for Configuring 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 is also incorporated by reference in it entirety.
`FIG. 2 depicts an example configuration model 200 of a
`10 product represented in a graphical, tree based form. The prod(cid:173)
`uct can be configured to include part combinations A1, B1 or
`B2, C1, X1 or X2, and Y1 or configured to include part
`combinations A2, B2, C2, X2, and Y1 or Y2. The configura(cid:173)
`tion model 200 includes rules to define these part relation-
`15 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(cid:173)
`figuration model. Actual configuration models for a single
`product can include hundreds of thousands or more parts and
`20 rules.
`
`25
`
`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 processing complex configuration problems using
`configuration sub-models.
`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 30
`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 35
`computer. A part group, also called a group, represents 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 40
`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 consists
`of a number of configurable features such as an insurance
`product. Additionally, a product can also represent a service. 45
`A configuration query (also referred to as a "query") is essen(cid:173)
`tially a question that is asked about the parts and relationships
`in a configuration model. The answer returned from a con(cid:173)
`figuration query will depend on the data in the configuration
`model, the approach used for answering the question, and the 50
`specifics of the question itself. For example, one possible
`configuration query, translated to an English sentence, is the
`following: For the given configuration model, are the parts
`"red" and "V6 engine" compatible with each other.
`The configuration model104 can be used to determine, for 55
`example, which parts are compatible with other parts, and
`provide additional details around specific relationships. For
`example, a vehicle configuration model can indicate that
`"red" (a part) is the standard color feature for a specific
`vehicle, but that the color red is not compatible with "V6 60
`engine" (a part). Configuration model104 may also contain
`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 65
`Systems", inventors Gupta et a!., and assigned to Trilogy
`Development Group, Inc., describes an example configura-
`
`TABLE 1
`
`Example Configuration Rules for a Product
`
`Al SALL
`A20ALL
`Bl SAl
`B2 SA2
`B20Al
`Cl SAl
`C2 SA2
`Xl SCI
`X2 S C2
`X20Cl
`YlOCl
`Yl SC2
`Y2 SCI
`
`Solving configuration problems using computer assisted
`technology often requires a significant amount of data pro(cid:173)
`cessing capabilities. Consequently, configuration technolo(cid:173)
`gies have attempted to exploit increased data processing
`capabilities, memory capacities, and network data transfer
`throughput rates by increasing the capabilities of the configu(cid:173)
`ration engines and/or enhancing the complexity of configu(cid:173)
`ration models and configuration queries. The complexity of a
`configuration model can be defined in any number of ways,
`such as by the diversity of parts, part groups, rules, and
`constraints supported by the configuration model, by the
`number of parts, rules, and constraints, and by the complexity
`of part and part group relationships defined by configuration
`rules and constraints. In any event, the practical complexity
`achievable for configuration models has been limited by the
`ability of computer systems to process data within a given
`period of time, T, and/or limited by other processing con(cid:173)
`straints, such as a lack of memory. The time period, T, repre(cid:173)
`sents an amount of time considered reasonable to perform a
`configuration task. Time T can vary depending upon the
`application and expectation of configuration system users.
`FIG. 3 depicts a graph 300 representing the practical limi(cid:173)
`tations of configuration model and configuration query com(cid:173)
`plexity in terms of data processing capabilities. Graph 300
`compares data processing capabilities of a particular com(cid:173)
`puter system being used to configure a product versus con(cid:173)
`figuration model and query complexity. Conventional infer(cid:173)
`ence procedures, such as configuration processes, have an
`exponential complexity associated with them as depicted by
`exponential performance curve 302. Sufficient data process-
`
`Page 10 of 19
`
`FORD 1201
`
`

`
`US 7,882,057 Bl
`
`3
`ing capability exists to process a configuration model and
`configuration query having the complexity represented by
`point A. The dashed line 304 represents the maximum data
`processing capability of the particular computer system being
`used. Thus, the computer system could not reasonably pro(cid:173)
`cess configuration models and configuration queries having a
`complexity represented by point B.
`
`SUMMARY OF THE INVENTION
`
`4
`FIG. 4 depicts a configuration model dividing and configu(cid:173)
`ration sub-model inference processing system that performs a
`configuration model dividing and configuration sub-model
`inference procedure.
`FIG. 5 depicts the data processing capability of a computer
`system being used to configure a product versus configuration
`sub-model and sub-query complexity.
`FIG. 6 depicts the division of a consolidated configuration
`model into configuration sub-models.
`FIG. 7 depicts a block diagram illustrating a network envi(cid:173)
`ronment in which the system and process of FIG. 4 may be
`practiced.
`FIG. 8 depicts an example data processing system used in
`the network of FIG. 7.
`
`DETAILED DESCRIPTION
`
`10
`
`35
`
`In one embodiment, a sub-model inference procedure pro(cid:173)
`vides a way to scale queries to larger and more complicated
`configuration models. In one embodiment of the present
`invention, a method for using computer assisted configura(cid:173)
`tion technology to solve product configuration problems 15
`using configuration sub-models includes processing one or
`more configuration queries using configuration sub-models,
`wherein the configuration sub-models collectively model a
`configurable product and generating an answer to the con(cid:173)
`figuration problem based upon the processed one or more 20
`configuration queries and the configuration sub-models.
`In another embodiment of the present invention, a com(cid:173)
`puter system to implement an inference procedure for solving
`product configuration problems using configuration sub(cid:173)
`models includes a processor and a storage medium having 25
`data encoded therein. The data includes processor executable
`code for processing one or more configuration queries using
`configuration sub-models, wherein the configuration sub(cid:173)
`models collectively model a configurable product and gener(cid:173)
`ating an answer to the configuration problem based upon the 30
`processed one or more configuration queries and the configu(cid:173)
`ration sub-models.
`In another embodiment of the present invention, a com(cid:173)
`puter storage medium comprising data embedded therein to
`cause a computer system to solve product configuration prob(cid:173)
`lems using configuration. The data includes code for process(cid:173)
`ing one or more configuration queries using configuration
`sub-models, wherein the configuration sub-models collec(cid:173)
`tively model a configurable product and generating an answer
`to the configuration problem based upon the processed one or
`more configuration queries and the configuration sub-mod(cid:173)
`els.
`In another embodiment of the present invention, a com(cid:173)
`puter system to implement an inference procedure for solving
`product configuration problems using configuration sub(cid:173)
`models. The system includes means for processing one or
`more configuration queries using configuration sub-models,
`wherein the configuration sub-models collectively model a
`configurable product and means for generating an answer to
`the configuration problem based upon the processed one or
`more configuration queries and the configuration sub-mod(cid:173)
`els.
`
`A configuration model dividing and configuration sub(cid:173)
`model inference processing system and procedure addresses
`the issue of configuration model and query complexity by
`breaking a configuration problem down into a set of smaller
`problems, solving them individually and recombining the
`results into a single result that is equivalent to a conventional
`inference procedure. In one embodiment, a configuration
`model is divided into configuration sub-models that can
`respectively be processed using existing data processing
`resources. The sub-model inference procedure does not
`change the exponential nature of configuration model and
`query complexity but instead generates configuration sub(cid:173)
`models on the side of the achievable performance curve.
`Accordingly, a sub-model inference procedure provides a
`way to scale queries to larger and more complicated configu(cid:173)
`ration models. Embodiments of the configuration model
`dividing and configuration sub-model processing system and
`inference procedure allows processing by a data processing
`system of configuration models and queries whose collective
`complexity exceeds the complexity of otherwise unprocess(cid:173)
`able conventional, consolidated configuration models and
`queries.
`FIG. 4 depicts the configuration model dividing and con(cid:173)
`figuration sub-model inference processing system 400 (re(cid:173)
`ferred to herein as "sub-model processing system 400") that
`performs configuration model dividing and configuration
`sub-model inference procedure 402 (referred to herein as
`"sub-model inference procedure 402"). The sub-model infer(cid:173)
`ence procedure 402 includes operations 404, 406, 408, and
`410. The sub-model processing system 400 can include soft(cid:173)
`ware code that is executable by a processor of a computer
`system, such as a server computer system. In a network en vi(cid:173)
`ronment, the sub-model processing system 400 can be
`accessed by and communicates with any number client sys(cid:173)
`tems 401(1) through 401(n).
`Operation 404 receives, as an input, a conventional, con-
`55 solidated configuration model 412 and divides the consoli(cid:173)
`dated configuration model 412 into a set of configuration
`sub-models CM1 through CMn, where n is an integer repre(cid:173)
`senting the number of configuration sub-models. The con(cid:173)
`figuration sub-models are an input to this process. In one
`60 embodiment, the configuration sub-models meet the follow(cid:173)
`ing criteria:
`a. Each configuration sub-model should represent a portion
`of the source configuration model 412;
`b. The data collectively contained in the configuration sub(cid:173)
`models should be sufficient to provide an answer for
`each of the sub-queries Q1 through Qn or query being
`processed; and
`
`40
`
`45
`
`50
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`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
`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(cid:173)
`ration process.
`FIG. 2 (prior art) depicts a configuration model in graphi(cid:173)
`cal, tree based form.
`FIG. 3 (prior art) depicts a graph representing data process- 65
`ing capabilities of a computer system versus configuration
`model and query complexity.
`
`Page 11 of 19
`
`FORD 1201
`
`

`
`US 7,882,057 Bl
`
`15
`
`5
`c. The configuration sub-models should be divided in such
`a way that the results of the sub-queries or query can be
`recombined to provide an answer to the input configu(cid:173)
`ration query 414.
`In another embodiment, a consolidated configuration
`model 412 is never actually created, and model developers
`develop only configuration sub-models to collectively model
`a configurable product.
`FIG. 5 depicts the data processing capability of a computer
`system being used to configure a product versus configuration 10
`sub-model and sub-query complexity. In general, the consoli(cid:173)
`dated configuration model 412 is divided sufficiently so that
`the complexity of each configuration sub-model CM1, CM2,
`through CMn is low enough to allow processing using avail(cid:173)
`able data processing capabilities while still representing the
`relationships included in the consolidated configuration
`model 412, which, in this embodiment, would otherwise not
`be cable of being processed by the computer system. Thus,
`the sub-model inference procedure 402 does not change the
`exponential nature of configuration model and query com(cid:173)
`plexity but instead generates configuration sub-models on the 20
`side of the achievable performance curve. Accordingly, the
`sub-model inference procedure 402 provides a way to scale
`queries to larger and more complicated configuration models.
`In one embodiment, operation 406 divides the conven(cid:173)
`tional, consolidated configuration query 414 into a set of 25
`sub-queries Q1 through Qn, which together contain enough
`information to represent the original query 414. Each sub(cid:173)
`query generated will be used to query against at least one
`configuration sub-model. A query is divided into enough
`sub-queries to perform a query on at least enough of the 30
`sub-models to produce an answer.
`Whether to perform operation 406 and divide query 414
`into sub-queries can depend upon the nature of the problem
`being solved. "Configuration completion" and "configuration
`validation" problems represent examples of two problems 35
`having different natures that result in different sub-query
`approaches. Configuration completion relates to determining
`whether a configuration is valid according to the Configura(cid:173)
`tion Model. A configuration is considered complete ifthere is
`a part present from every required part group in the configu- 40
`ration model. For example, when performing configuration
`completion, dividing the query 414 into sub-queries allows
`the sub-queries to each be processed using at least one con(cid:173)
`figuration sub-model. Configuration validation relates to
`determining whether a configuration is "valid" or "not valid"
`according to the configuration model. "Valid" indicates that 45
`the parts are all compatible with each other according to the
`part relationships in the configuration model, and "not valid"
`indicates that the parts are not compatible with each other. In
`performing configuration validation, dividing the query 414
`into sub-queries is unnecessary to determine validation, 50
`because the query 414 can be applied in whole against con(cid:173)
`figuration sub-models. If any answer generated by processing
`query 414 in accordance with a configuration sub-model
`results in an invalid (i.e. a non-configurable) answer, then the
`configuration is invalid. Otherwise, the configuration is valid. 55
`In one embodiment, the following criteria are used by
`operation 406:
`a. A single sub-query can be used to query against multiple
`sub-models. In other words, each sub-model does not
`have to have to process one and only one unique sub- 60
`query;
`b. The query 414 can be processed as a sub-query;
`c. When dividing a query into sub-queries, it is possible that
`there will be overlapping pieces of information con(cid:173)
`tained in the sub-queries. It is not necessarily desired or 65
`a requirement that the sub-queries contain entirely inde(cid:173)
`pendent questions;
`
`6
`d. The way the query is divided into sub-queries depends
`on the structure of the configuration sub-models. Spe(cid:173)
`cifically, it depends on the way the sub-models are
`related, and the relationships between the parts in the
`overall model. For example, assume the sub-models
`were originally generated by dividing up the model
`along family lines with some overlap. The sub-queries
`will generally (though are not required to) be divided up
`along similar family lines, with at least as many families
`present; and
`e. It will be understood by those of ordinary skill in the art
`that the way the query is divided into sub-queries also
`depends on the type of configuration query being per(cid:173)
`formed. A configuration validation query might need a
`different Query Division approach than a Configuration
`Completion query.
`Operation 408 processes the individual sub-queries Q1
`through Qn against the configuration sub-models, producing
`a set of sub-answers. Enough sub-queries should be pro(cid:173)
`cessed such that the sub-answers contain enough information
`to recombine them into a single answer to the input configu(cid:173)
`ration query.
`Operation 410 combines the sub-answers A1 through An
`together to create a single answer A. The answer A represents
`a correct answer for the input configuration query. However,
`for some queries, there are multiple correct answers. Thus,
`the answer determined by operation 410 is correct but may or
`may not be identical to an answer provided had the configu(cid:173)
`ration query been performed using the conventional process
`depicted in FIG. 1. For example, in the case where the con(cid:173)
`ventional process would return an "optimal" answer, the sub(cid:173)
`model inference procedure 402 may return a sub-optimal,
`albeit correct, answer. Also, in the case that there is more than
`one "optimal" answer, the sub-model inference procedure
`402 may return a different optimal answer than the conven(cid:173)
`tional process.
`In one embodiment, operations 404, 406, 408, and 410 are
`performed in order. However, operations 404, 406, 408, and
`410 can be overlapping. For example, it is not required that
`any given operation finish completely before the next opera(cid:173)
`tion begins. For example, as each sub-query is processed in
`operation 408, the resulting sub-answer can be determined to
`generate a growing, cumulative answer A before the next
`sub-query is processed.
`The following pseudo code represents the sub-model infer-
`ence procedure 402:
`result inference-procedure( model, query)
`{
`sub-models=divide-model(model) (Operation 404, imple(cid:173)
`mentation dependent on the specific problem) OR ini(cid:173)
`tially develop configuration sub-models
`sub-queries=divide-query(query) (Operation 406, imple-
`mentation dependent on the specific problem)
`//This loop encompasses Operation 408//
`answers={}
`for(model in sub-models) {
`sub-query=find-sub-query(sub-queries, model)
`//Get the right sub-query to be asking this sub-model//
`answers[model]=model.inference-procedure(sub-
`query)
`//Run the inference procedure for this sub-query on the
`sub-model/ I
`
`}
`//Recombine the answers to each of the sub-queries into a
`single unified answer (Operation 410)//
`result=combine( answers)
`return result
`}
`
`Page 12 of 19
`
`FORD 1201
`
`

`
`US 7,882,057 Bl
`
`7
`The following examples illustrate embodiments of sub(cid:173)
`model processing system 400 and sub-model inference pro(cid:173)
`cedure 402.
`
`Example
`
`Configuration Validation
`
`The following example details sub-model inference proce(cid:173)
`dure 402 in a context wherein an incoming configuration is 10
`complete (a part is present from every required part group). A
`query is generated using conventional processes to query
`against the configuration sub-models to determine if the con(cid:173)
`figuration is valid.
`The following pseudo code represents the embodiment of 15
`sub-model inference procedure 402 used for configuration
`validation:
`//for the complete feature string validation problem
`divide-model=procedure which breaks a consolidated
`model up into sub-models along family lines OR ini- 20
`tially develop configuration sub-models.
`divide-query=returns the original query unchanged
`combine= loop which takes each boolean answer and uses
`the logical AND operator to combine them
`into a single boolean answer//
`boolean is Buildable( sub-models, query)
`{
`sub-queries=divide( query) (Operation 406);
`//Break the query into sub-queries. For a configuration
`validation query type, it is unnecessary to divide the 30
`query 414 into multiple sub-queries. Thus, in this
`embodiment of operation 406 query 414=sub-query Q1
`and n= 1. In other words, operation 406 can just return
`the entire original query 414//
`answers=[ ] (operation 408)
`for(model in sub-models){
`sub-query=find(sub-queries, model);
`//Get the right sub-query to be asking this sub-model//
`answers[ model]=model.is Buildable( sub-query);
`//Query against each sub-model//
`
`25
`
`35
`
`40
`
`45
`
`8
`The sub-model inference procedure 402 uses the conven(cid:173)
`tional model as an input. In one embodiment, operation 404
`divides the conventional model into the following configura(cid:173)
`tion sub-models represented in Table 3. Table 4, and Table 5:
`
`TABLE3
`
`Family A model:
`
`Al SALL
`A20ALL
`
`TABLE4
`
`Family B model:
`
`Bl SAl
`B20Al
`B2 SA2
`
`TABLES
`
`Family X model:
`
`Xl SALL
`X20ALL
`
`Table 6 and Table 7 represent one embodiment of sub(cid:173)
`queries generated by operation 406 and sub-answers gener(cid:173)
`ated by operation 408:
`
`TABLE6
`
`Sub-Queries Generated by Operation 406:
`
`Is Al buildable? Yes
`1.
`2. AreAl and Bl buildable together? Yes
`3.
`Is Xl buildable? Yes
`
`TABLE 7
`
`Sub-Queries Generated by Operation 406:
`
`Is Al buildable? Yes
`1.
`2. Are A2 and Bl, buildable together? No
`3.
`Is Xl buildable? Yes
`
`}
`result= True
`for( answer in answers)//Operation 410//{
`result=result && answer;//"&&" is a logical AND
`operator//
`//Recombine answers to sub-queries (this particular query
`type can just use a boolean and operator)//
`
`}
`return result;
`}
`Table 2 represents a conventional configuration model and
`query for a configuration validation problem:
`
`TABLE2
`
`Conventional Model:
`
`Al SALL
`A20ALL
`Bl SAl
`B2 SA2
`B20Al
`Xl SALL
`X20ALL
`Conventional Query:
`
`AreAl, Bland Xl buildable together? Yes
`Are A2, Bl and Xl buildable together? No
`
`In operation 410, for this problem type, i.e. configuration
`validation problem, the sub-answers of the sub-queries can be
`50 AND-ed together and recombined into a single answer that is
`equivalent to the answer provided by querying the conven(cid:173)
`tional configuration model.
`
`55
`
`Example
`
`Configuration Completion
`
`The configuration completion example below details an
`exemplary usage of the sub-model inference procedure 402
`60 for a configuration completion query, in the specific case that
`the incoming configuration is incomplete (a part is not present
`from every required part group). The goal of a configuration
`completion query is to complete the partial configuration with
`parts from the missing part groups in such a way that the
`65 resulting configuration is valid according to the traditional
`configuration model and contains a single part from each part
`group.
`
`Page 13 of 19
`
`FORD 1201
`
`

`
`US 7,882,057 Bl
`
`9
`To solve the incomplete feature string completion problem
`using configuration sub-models, the following process can be
`used:
`divide-model=procedure which breaks a consolidated
`model up into sub-models in such a way that they are
`smaller than the original consolidated model and is suf(cid:173)
`ficient to provide an answer for each sub-query being
`processed against it as previously described OR initially
`develop configuration sub-models;
`divide-query=procedure which breaks the query up into n 10
`pieces where n is the number of sub-models (CM1,
`CM2, CMn);
`Sub-query Qi has all of the parts from the original query
`that are from the part groups present in CMi; and
`combine=set intersection operator which takes the set of 15
`buildables returned from executing