111111
`
`1111111111111111111111111111111111111111111111111111111111111
`US007200582Bl
`
`c12) United States Patent
`Smith
`
`(10) Patent No.:
`(45) Date of Patent:
`
`US 7,200,582 Bl
`Apr. 3, 2007
`
`(54) CONFIGURATION MODEL CONSISTENCY
`CHECKING USING FLEXIBLE RULE SPACE
`SUBSETS
`
`(75)
`
`Inventor: Shawn A. P. Smith, Austin, TX (US)
`
`(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 568 days.
`
`(21) Appl. No.: 10/404,891
`
`(22) Filed:
`
`Mar. 31, 2003
`
`(51)
`
`Int. Cl.
`G06F 17100
`B06N 5102
`
`(2006.01)
`(2006.01)
`
`(52) U.S. Cl. ............................. 706/47; 706/45; 706/46
`
`(58) Field of Classification Search .................. 706/45,
`706/46, 47; 717/105; 707/100
`
`(56)
`
`References Cited
`
`OTHER PUBLICATIONS
`Polat, Faruk, eta!., UVT: A Unification-Based Tool for knowledge
`Base Verification, Validation and Verification of Knowledge-Based
`Systems, Jun. 1993, IEEE Computer Society Press, pp. 69-75.*
`* cited by examiner
`Primary Examiner-Joseph P Hirl
`(74) Attorney, Agent, or Firm-Hamilton & Terrile, LLP;
`Kent B. Chambers
`
`(57)
`
`ABSTRACT
`
`Inconsistencies between configuration rules represent a sig(cid:173)
`nificant concern when modeling a product using configura(cid:173)
`tion rules. The consistency checking system approaches a
`configuration model from the perspective of a sets of fea(cid:173)
`tures and families. The configuration space of a model
`represents the entire set of all combinations of selections
`within a configuration model. The consistency checking
`system operates on subsets of the configuration space by
`consolidating data within the configuration space into mini(cid:173)
`mized subsets that represent a portion of the configuration
`space where a particular consistency error can occur. Thus,
`the contents of each subset vary depending upon which
`consistency error is being checked, and consistency check(cid:173)
`ing is performed on reduced subsets determined on an error
`by error basis rather than on the configuration space as a
`whole.
`
`See application file for complete search history.
`
`5 Claims, 26 Drawing Sheets
`
`I
`
`User Input 406
`
`Display/Report
`408
`
`I
`
`,,
`
`Consistency Checking System
`400
`
`"----
`_./
`Configuration Model
`(Configuration Space)
`402
`
`~
`
`...
`
`Consistency
`Checking Error
`Operations
`404
`
`Page 1 of 34
`
`FORD 1005
`
`

`
`U.S. Patent
`
`Apr. 3, 2007
`
`Sheet 1 of 26
`
`US 7,200,582 Bl
`
`100
`
`/200
`
`RULES
`Feature Optionality
`F1
`S
`F1
`0
`M
`F2
`0
`F2
`0
`F2
`0
`F2
`0
`F3
`F3
`0
`0
`F4
`0
`F4
`
`Constraint
`A1,81,C1, 01,E1
`A1,81,C1,01,E2
`A1,81,C1,01,E1
`A1, 81, C1, 01, E3
`A1,81,C1,02,E1
`A1, 81, C1, 02, E2
`A1, 81, C1, 02, E1
`A1, 81, C1, 02, E2
`A1,81,C1,02,E1
`A1, 81, C1, 02, E2
`
`Figure 1 (prior art)
`
`• • •
`
`A1
`81
`C1
`01
`E1
`s
`
`M
`
`A1
`A1
`A1
`A1
`81
`81
`81
`81
`C1
`C1 C1
`C1
`01
`02 01
`01
`E2 E3
`E1
`E2
`
`0
`
`0
`
`0
`
`0
`
`0
`
`0
`
`0
`0
`L_j L_j L_j L_j L__j
`•
`Figure 2A (prior art)"
`
`•
`
`•
`
`/202
`
`• • •
`
`A1
`81
`C1
`01
`E1
`s
`M
`
`A1
`A1
`81
`81
`C1
`C1
`01
`01
`E2 E3
`
`A1
`A1
`81
`81
`C1
`C1
`02 02
`E1
`E2
`
`0
`
`0
`
`0
`
`0
`
`0
`
`0
`
`0
`0
`L_j L_j L_j L -1 __ ....J 1----IIJI~
`
`Figure 28 (prior art)
`
`F1
`
`F2
`
`F3
`
`F4
`
`F1
`
`F2
`
`F3
`
`F4
`
`Page 2 of 34
`
`FORD 1005
`
`

`
`U.S. Patent
`
`Apr. 3, 2007
`
`Sheet 2 of 26
`
`US 7,200,582 Bl
`
`• • •
`
`A1
`81
`C1
`01
`E1
`s
`
`M
`
`A1
`A1
`A1
`A1
`81
`81
`81
`81
`C1 C1
`C1
`C1
`01
`02 01
`01
`E2 E3
`E1
`E2
`
`0
`
`0
`
`0
`
`0
`
`0
`
`0
`
`0
`
`0
`
`F1
`
`F1
`
`F2
`
`F3
`
`F4
`
`IF2(a)l .__I __ F2_(a_) _--Jill F2(a)..,
`
`I F2(c)JI
`
`F2(c)
`
`I . . __ I F_2(_c)....,....,
`
`Figure 3
`
`Page 3 of 34
`
`FORD 1005
`
`

`
`U.S. Patent
`
`Apr. 3, 2007
`
`Sheet 3 of 26
`
`US 7,200,582 Bl
`
`/500
`
`~
`
`501\
`
`User selects a specific family to consistency
`check (which becomes the "main family", or
`consistency checking will loop through all
`families in the model, selecting each in turn as
`the main family.
`
`User Input 406
`
`Display/Report
`408
`
`Consistency Checking System
`400
`
`Consistency
`Checking Error
`Operations
`404
`
`Figure 4
`
`~-------------,--------~
`
`l
`
`/502
`Select consistency v /
`checking error operation
`
`Consolidate selected v 504
`
`l
`
`configuration space data into
`feature subsets within a
`configuration space based on
`particular selected
`consistency error operation.
`
`for feature subsets.
`
`Ge"emte dL '''"c!"'e' V" 506
`j_
`
`508
`
`Conduct set math
`routines to
`determine any
`consistency errors.
`
`/
`
`1
`
`Display/Report
`consistency check
`results
`
`Figure 5
`
`V 510
`
`Page 4 of 34
`
`FORD 1005
`
`

`
`U.S. Patent
`
`Apr. 3, 2007
`
`Sheet 4 of 26
`
`US 7,200,582 Bl
`
`-----
`1
`
`/600
`I v602
`
`Level
`
`1
`
`I
`I
`----r---------
`'
`
`Node
`
`L--------...A
`
`Figure 6A
`
`Page 5 of 34
`
`FORD 1005
`
`

`
`U.S. Patent
`
`Apr. 3, 2007
`
`Sheet 5 of 26
`
`US 7,200,582 Bl
`
`/600
`
`610
`
`- -1
`
`606
`
`I A1
`
`A2
`
`A3
`
`81
`
`Figure 68
`
`Page 6 of 34
`
`FORD 1005
`
`

`
`U.S. Patent
`
`Apr. 3, 2007
`
`Sheet 6 of 26
`
`US 7,200,582 Bl
`
`/700
`
`X1
`
`A1
`
`81
`
`704
`
`82
`L------------------
`
`Figure 7A
`
`706
`
`/700
`
`710
`
`82
`
`83
`
`81
`
`82
`
`83
`
`Figure 78
`
`Page 7 of 34
`
`FORD 1005
`
`

`
`U.S. Patent
`
`Apr. 3, 2007
`
`Sheet 7 of 26
`
`US 7,200,582 Bl
`
`0
`
`0
`
`A1
`
`A2
`
`A3
`
`0
`
`82
`
`0
`
`83
`
`81
`
`0
`
`A1
`
`A2
`
`A3
`
`0
`
`81
`
`0
`
`83
`
`82
`
`X1
`
`Figure 7C
`
`Page 8 of 34
`
`FORD 1005
`
`

`
`U.S. Patent
`
`Apr. 3, 2007
`
`Sheet 8 of 26
`
`US 7,200,582 Bl
`
`800
`
`802
`
`SOML
`
`804
`
`806
`
`Figure 8
`
`Page 9 of 34
`
`FORD 1005
`
`

`
`U.S. Patent
`
`Apr. 3, 2007
`
`Sheet 9 of 26
`
`US 7,200,582 Bl
`
`/900
`
`Rules
`
`Feature Optionality Constraint
`EN1
`0
`ALL
`EN2
`S
`ALL
`
`TR1
`TR2
`TR2
`
`AX1
`AX2
`AX2
`AX2
`AX3
`
`s
`s
`0
`s
`s
`0
`R
`0
`
`EN1
`EN2
`EN1
`
`EN1
`EN1.TR2
`EN2.TR2
`EN2
`TR2.EN2
`
`Figure 9
`
`/1000
`
`Main
`EN1
`Frtmilv
`TR1 TR2 TR1
`AX1 s
`s
`s
`AX2
`AX2
`AX3
`
`R
`
`EN2
`TR2
`
`0
`R
`0
`
`1002
`
`1004
`
`1006
`
`/1002
`
`1014
`
`Figure 10
`
`Page 10 of 34
`
`FORD 1005
`
`

`
`U.S. Patent
`
`Apr. 3, 2007
`
`Sheet 10 of 26
`
`US 7,200,582 Bl
`
`SOML
`
`/
`
`1102
`
`F1 error
`
`---~--L __________ _
`: I I I 0 I 0 I
`I
`I
`I
`I
`I
`I
`I
`
`EN! EN2
`
`EN!
`
`EN2
`
`EN!
`
`EN2
`
`Figure 11A
`
`Page 11 of 34
`
`FORD 1005
`
`

`
`e •
`
`00
`•
`~
`~
`~
`
`~ = ~
`
`~ :-:
`
`(.H
`
`~
`
`N
`0
`0
`-....l
`
`('D
`('D
`
`rFJ =(cid:173)
`.....
`....
`....
`0 .....
`N
`0\
`
`d
`rJl
`-....l
`
`00
`
`'N = = u.
`N = """"'
`
`AX'
`
`AX' AXJ
`
`Axl
`
`Ax2
`
`'X3
`'
`
`AX!
`
`4.X2
`
`AX3
`
`F1 error
`
`01
`
`AXI
`
`4.X2
`· .
`
`AX3 AX!
`
`~>::2
`
`AX3
`
`1~ I 0 1~ I I 0 1~ l OJ
`l
`~
`
`01 - - ~ ~.
`LL..J
`LL..J Ftgure 11 B
`TRl ~TR2
`TRl rR2
`
`I-ll 0 I o I BlTOI CD I oJI I
`c=b
`c=b
`c=b SOML 1\ 'R
`ct;ct;
`TR! m
`rn
`
`ENI
`
`EN2
`
`EN! EN2
`
`EN!
`
`EN2
`
`rn
`- ~ _
`10 I 0 r:J 17171!]
`~ rn
`~ rn
`rn
`rn
`
`rn
`
`EN! EN2
`
`1
`
`EKl
`
`El\:2
`
`1
`
`6
`
`110
`
`AXO
`
`AX2
`
`I L
`l
`1,..------,0 1,-----,0 I I
`,....---0
`- - - -
`AX3 I
`
`~ rn
`rn
`
`TRl tTR2
`
`EN!
`
`EN2
`
`-
`
`5
`
`- -
`
`4
`
`5 -
`
`AXO
`
`AX2
`
`AX3
`
`AXO
`
`AX2
`
`AX3
`
`:I ' " I 0 I
`
`AXO
`: J ;X J
`I
`
`2
`
`3
`
`-
`
`- ___± -
`I 0 I oE] CY-l oIl I
`AXO~AXJ AXO~AX3
`
`J;J;
`
`ENI EN2
`
`ENI
`
`EN2
`
`1
`
`TRI TR2
`
`:~
`
`ENI
`
`EN2
`
`I
`
`TRI ~TR2
`
`TRI ~TR2
`
`EN! EN2
`
`EN! DJ2
`
`______ ___ _ j
`
`Page 12 of 34
`
`FORD 1005
`
`

`
`/1112
`
`I
`: AXO
`
`AX2
`
`AX3
`
`AXO
`
`AX2
`
`AX3
`
`TRI TR2
`
`I
`I
`I
`: I !
`I
`I
`I
`I
`I
`I
`I
`I
`:
`I
`I
`
`,
`
`o
`
`EN! EN2
`
`01
`
`TRI TR2
`
`,
`
`,
`
`EN! EN2
`
`/
`'
`
`\
`'
`I
`AXO \ AX2 /~3 I
`
`\
`
`\
`
`/
`/
`/
`
`0 \1
`/
`
`/
`
`I
`
`/
`/
`I
`/
`
`\
`
`\
`
`\
`t\
`
`1
`I
`I
`
`I
`
`I
`I
`I
`I
`1
`I
`I
`
`EN! EN2
`
`\
`
`I
`\1
`
`r--------------------------- 1
`I
`I
`*
`*
`
`*
`
`1116
`
`I
`1
`I
`I
`
`~
`~I
`~I
`I
`1 ~ TRI ~TR2
`:
`I
`I
`:
`I
`:
`I
`---------------------------~
`1 - - - - - - _j~~~~~L __ _
`*
`*
`I~ I
`d51122:
`
`:------=----j ____ -- - --I SOMl:" -- --,
`~ I' I o I o I I , I o I' I I'~ I , I o l!
`I~ ~ !' 1
`[]Q:
`I d J ~ TRliTR2
`/CE} :
`L--- ----- _____________________ /__ ---- ______ : h 1124
`1 8520
`VI
`~ c±J 1118 1
`J;J; TRI tTR2
`rn
`
`0
`
`-
`-
`
`I
`I
`I
`I
`I
`I
`:
`I
`I
`I
`I
`
`i
`
`EN!
`
`EN2
`
`EN!
`
`EN2
`
`EN!
`
`EN2
`
`I
`I
`I
`I
`I
`I
`---------------------------~
`
`(~OMl:"( / _ 1114--------------
`!
`*
`*
`I
`: ~
`
`,
`
`:
`
`1
`I
`I
`I
`I
`
`rn :
`
`0
`
`1
`
`EN! EN2
`
`I
`I
`I
`:
`
`1
`1
`I
`
`1
`I
`I
`I
`I
`I
`
`1
`
`1
`
`TR! TR2
`
`1
`
`0
`
`EN! EN2
`
`I
`I
`I
`I
`
`I
`I
`I
`
`1
`
`1
`
`·
`
`]
`
`:
`1
`I
`1
`I
`I
`
`: dJTRl TR2
`1
`I
`1
`I
`
`1
`
`0
`
`0
`
`TRl TR2
`
`:
`I
`I
`I
`I
`
`Figure 11C
`
`il 0 ~
`
`EN!
`
`I
`I EN! EN2
`I
`I
`I
`I
`I
`__________________ j
`I
`I
`
`EN2
`
`e •
`
`00
`•
`~
`~
`~
`
`~ = ~
`
`~ :-:
`
`(.H
`
`~
`
`N
`0
`0
`-....l
`
`('D
`('D
`
`rFJ =(cid:173)
`.....
`....
`N
`0 .....
`N
`0\
`
`d
`rJl
`-....l
`
`00
`
`'N = = u.
`N = """"'
`
`Page 13 of 34
`
`FORD 1005
`
`

`
`c±;*
`cb 1 I 0
`
`TRl TR2 -
`
`EN! EN2
`
`I
`
`I
`I
`:
`I
`I
`I
`
`I
`
`0
`
`0
`
`I
`
`c±;TRI TR2 I TRt TR21
`I I
`ENl EN2
`
`I
`I
`
`:
`
`i
`
`I
`I
`:
`1
`I
`I
`
`ENl EN2
`I
`[ _________________ ,
`
`F1 error
`
`ALL
`
`L_
`
`1124
`
`[SOML-Rl
`r------------- ---~
`1
`I
`I
`1
`
`1126: ~* 112d£* 1132\
`
`1130
`/_
`___ --------------
`I
`I
`I
`I
`
`i ~* ~· :
`
`l
`
`O
`
`O
`
`1
`
`I
`I
`I
`
`TRI TR2 :
`
`I
`I
`- I
`
`-
`
`: TRI TR2
`1
`
`c±;1 ~I i
`
`I
`I
`: EN! EN2
`I
`I
`.I
`
`EN! EN2
`
`L _________________ J
`
`I
`I
`:
`I
`I
`I
`
`* l; 1132
`~
`TRlTR2
`CTI
`
`EN! EN2
`
`e •
`
`00
`•
`~
`~
`~
`
`~ = ~
`
`~ :-:
`
`(,H
`
`~
`
`N
`0
`0
`-....l
`
`('D
`('D
`
`rFJ =(cid:173)
`.....
`....
`0 .....
`N
`0\
`
`(,H
`
`d
`rJl
`-....l
`
`00
`
`'N = = u.
`N = """"'
`
`-~
`
`1136
`
`Transmission 1/Enqine 2
`configuration lacks an axle.
`
`Figure 11D
`
`* 1 /1134
`~
`TRrR2
`~
`
`[F11 = -[SOML-RJ
`
`ENl EN2
`
`Page 14 of 34
`
`FORD 1005
`
`

`
`F2a error
`
`1 1202
`
`j
`SML
`~---------- - - - -1
`~~-~EJ
`
`~-~ r~ ,- 0 J
`AX3 c6
`"l "'
`rn
`
`AX!
`
`AX2
`
`EN! EN2
`
`AX!
`
`AX2
`
`&X3 c6 "l "'
`
`IT]
`
`EN!
`
`EN2
`
`_______________ ___,
`
`-
`
`-
`
`R
`
`1206
`
`:
`
`I
`I
`I
`I
`I
`
`TRI ~TR2
`
`I
`I
`I
`
`I
`I
`I
`
`TRl
`
`TR2
`
`~
`
`.
`I
`TRl
`1R2
`..
`
`I
`I
`I
`
`!! L 1204
`1- _______ L __ _
`~ -
`I
`'
`I·I,I·T~
`: 1·1,1,1: :1'1"1'1
`AX' T =
`"' '~ m i
`i : ~' ~ '~
`1 1
`I 1
`rn :~m m~
`: rn::rn
`rn:
`
`EN!
`
`EN2
`
`ENI
`
`EC/2
`
`ENI
`
`EN2
`
`I
`I
`I
`I
`I
`I
`I
`I
`L _______ J ~-------------~
`0
`/1212
`1214
`I-------=- _L - - - -
`\
`I _\._
`[0-R]
`
`I
`: AXl
`
`AX2
`
`AX3
`
`AXI
`
`AX2
`
`AX3
`
`TRI ITR2
`..
`
`L.L:.J
`TRI ITR2
`..
`
`I
`I
`I
`
`0
`
`I
`I
`I EN!
`
`I
`
`EN2
`
`0
`
`I
`
`I
`L _ _:_N~ EN2
`EN2
`ENJ
`_________ j
`
`I Transmission 2/Engine 2
`1218 ~ has no standard.
`
`(SML-R] = (SMlil-, R]
`
`, - -
`
`ENl EN2
`
`---, [SML-R]
`-
`-
`-
`- 1
`1- -
`- 1
`-
`-
`*
`*
`I
`I 12os 1
`1 L.L:.J
`L.L:.J
`I
`TRl I TR2
`TRI I TR2
`I
`I
`I
`:
`-t
`I
`1
`..
`I
`11210"" I ~ I
`rT-:-1
`I
`'i LLJ I
`I L.L:.J
`I
`I
`I
`I
`I
`I
`EN!
`EN2
`~-----~
`"":- ___ I
`Figure 12
`
`[0-RJ-fSML-Rl
`~1216
`I I 0 I 1 I 0 I I 0 I 0 I 1 I I I
`- - - 1 1- -
`~ v I ~ I
`I
`-
`*
`*
`I
`I
`I I
`I
`I ~ I I ~I
`I
`I
`I
`1 1 L.L:.J I I L.L:.J 1= [F2a]
`I rn ~ I 1
`
`I ~Rl TR2 I I ~RI TR2
`..
`..
`I
`I
`l1
`I
`I I
`I
`I I
`I
`: rn
`. , : ~----~ L - - -J
`I I EN!
`EN2 I
`rn I
`
`e •
`
`00
`•
`~
`~
`~
`
`~ = ~
`
`~ :-:
`
`(.H
`
`~
`
`N
`0
`0
`-....l
`
`('D
`('D
`
`rFJ =(cid:173)
`.....
`....
`0 .....
`N
`0\
`
`.j;o.
`
`d
`rJl
`-....1
`
`00
`
`'N = = u.
`N = """"'
`
`Page 15 of 34
`
`FORD 1005
`
`

`
`U.S. Patent
`
`Apr. 3, 2007
`
`Sheet 15 of 26
`
`US 7,200,582 Bl
`
`Start
`
`1302
`
`/1304
`
`/1300
`
`/ 1306
`
`1308
`
`Create empty tries for
`[F2b]0 and [familySML] 0
`
`N=number of main features
`
`[F2b];+ 1 = [F2b]; U ([familySML]; 1\ [featureSML - featureRJ;)
`
`1310
`
`i = i+1
`
`1314
`
`Yes
`
`1316
`
`([familySMLJ;+1 =
`
`([familySMLJ; U [featureSML - featureR]i)
`
`No
`
`Figure 13
`
`1318
`
`Page 16 of 34
`
`FORD 1005
`
`

`
`U.S. Patent
`
`Apr. 3, 2007
`
`Sheet 16 of 26
`
`US 7,200,582 Bl
`
`i = 0
`
`TRI TR2
`
`L ____________ _
`
`EN! EN2
`- - - - - - - - - - - -
`1412
`
`[F2b] 1
`
`Figure 14A
`
`TRI TR2
`
`EN!
`
`EN2
`
`Page 17 of 34
`
`FORD 1005
`
`

`
`U.S. Patent
`
`Apr. 3, 2007
`
`Sheet 17 of 26
`
`US 7,200,582 Bl
`
`i:: 0
`
`[family SML]
`
`1
`
`1414
`
`,------11
`
`1 [feature SM L • featureR]) 0 I I
`I I
`I I
`I I
`I I
`I I
`I I
`I I
`I I
`I
`I I
`I EN I EN2
`L_ _ __ __ _ I
`
`IAXI AX2 AX3
`
`TRl TR2
`1 o
`
`11416
`I
`I
`I
`I
`I I
`I
`I I EN l EN2
`I L_ _ __ _ j
`
`-------*---------
`
`....------,
`
`AX3 v1418
`
`jAXl AX2
`I
`I
`I TRI TR2
`I
`I
`I ENI EN2
`
`I
`I
`I
`I
`I
`
`L -1-- J
`i AXI~X * ~X~ (
`
`1420
`
`Figure 148
`
`[family SML] 1
`
`::
`
`I
`I
`I
`I
`I
`I
`I
`I
`L ____ J
`EN! EN2
`
`Page 18 of 34
`
`FORD 1005
`
`

`
`U.S. Patent
`
`Apr. 3, 2007
`
`Sheet 18 of 26
`
`US 7,200,582 Bl
`
`i = 1
`, - - - - - - - - - - - - - - - - - - - - - - - - - - .......
`
`[F2b] 2
`
`*
`
`TRL TR2
`
`ENL EN2
`
`Figure 14C
`
`Page 19 of 34
`
`FORD 1005
`
`

`
`U.S. Patent
`
`Apr. 3, 2007
`
`Sheet 19 of 26
`
`US 7,200,582 Bl
`
`i = 1
`
`[family SML] 2
`
`=
`
`U
`
`- - - - - - - - - - - - - - - - - ,
`I -----1
`~-------,
`I
`I [feature SML- featureR])
`1 I
`[family SML] 1
`1
`*
`I
`II
`I I
`*
`I
`l1
`I
`I
`I
`l1
`I I
`I
`I
`II
`I I
`I
`I
`l1
`I I
`I
`I
`l1
`I I
`I
`I
`II
`I I
`I
`I
`II
`I I
`I
`IL__ ____ j
`L~N_l EN2 ___ 11
`L ___ :~J ~~-----_.J
`
`*
`
`I
`I
`I
`I
`I
`I
`I
`I
`I
`[family SML] 2 = I
`I
`I
`I
`I
`I
`I
`ENI EN2
`L_ ____ j
`
`Figure 14D
`
`Page 20 of 34
`
`FORD 1005
`
`

`
`U.S. Patent
`
`Apr. 3, 2007
`
`Sheet 20 of 26
`
`US 7,200,582 Bl
`
`:
`
`-
`
`-
`
`-
`
`AX3
`
`AX! AX2
`
`AX3
`
`I _i=2_--- = = = = = = = = = = = = = ======-::;I
`F2b
`[featu" s~~ featureRJ~ -
`~
`- I u : [[family SML[ 2 A
`[F2b[ 3 =: : [F2bl; -
`II
`I
`I
`I
`II
`I
`I
`I
`I
`I I
`I
`I
`I
`II
`I
`I
`II
`I
`I
`I
`I
`II
`I
`I
`11
`I
`I
`I
`1 o
`11
`I
`I
`I
`I
`I
`I
`I
`I~ --=-N~ EN:_ I
`I EN! EN2
`J
`I
`I
`
`*
`
`*
`
`TRI TR2
`
`I
`I
`I AX! AX2
`o
`I
`I
`I
`
`TRI TR2
`
`I
`I
`~ _!N~ ~N~-
`
`TRI TR2
`
`EN! EN2
`
`! -----
`
`: :
`I I
`I I
`I I
`I I
`I I
`I I
`I 1
`I 1
`I I
`I I
`II
`
`I I
`I
`I
`I I
`I
`I
`I I
`I
`I
`1 I
`I
`I
`I I
`I
`I
`TRI TR2
`o o
`I I
`I
`I
`I I
`I
`I
`L __________ mifN2 ______
`1
`1
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`EN! EN2
`L - - - - - - - - - - - - - . - - - - - - - - - - - -
`
`TRI TR2
`
`*
`
`*
`
`1422
`
`Figure 14E
`
`[F2b)
`
`3
`
`Transmission 2/Engine 1
`has multiple standards.
`
`EN! EN2
`
`Page 21 of 34
`
`FORD 1005
`
`

`
`U.S. Patent
`
`Apr. 3, 2007
`
`Sheet 21 of 26
`
`US 7,200,582 Bl
`
`/1500
`
`Rules
`
`Feature Optiona~ity Constraint
`EN1
`0
`ALL
`EN2
`S
`ALL
`
`TR1
`TR2
`TR2
`
`AX1
`AX1
`AX2
`AX2
`AX2
`AX3
`
`s
`s
`0
`
`s
`M
`s
`0
`R
`0
`
`EN1
`EN2
`EN1
`
`EN1
`EN2.TR2
`EN1.TR2
`EN2.TR2
`EN2
`TR2.EN2
`
`Figure 15
`
`/1600
`
`Main EN1
`EN2
`Family TR1 TR2 TR1
`s
`AX1 s
`s
`tv<2
`AX2
`AX3
`
`R
`
`TR2
`M
`0
`R
`0
`
`Figure 16
`
`Page 22 of 34
`
`FORD 1005
`
`

`
`U.S. Patent
`
`Apr. 3, 2007
`
`Sheet 22 of 26
`
`US 7,200,582 Bl
`
`,---~~--/ 1702,-----~-~ 1704
`
`I
`I
`I
`'------'---...---'---
`I
`AXJ
`1 AX! AX
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`EN! EN2
`1
`I
`L _________ _
`
`TRl
`
`TR2
`
`I
`I
`
`AXI AX2
`
`AX3
`
`TRI
`
`TR2
`
`I
`I
`I
`I
`L _________ _
`EN! EN2
`I
`
`R
`
`j 1706
`
`AXI AX2 AX3
`
`AXl AX2 AX3
`
`TRI TR2
`
`1
`- - - - - - - - - - - - - - - - - - - - - ----1
`I
`I
`I
`I
`1
`I
`I
`I
`I
`I
`I
`I
`I
`J
`I
`I
`EN2
`EN!
`EN2
`ENl
`1
`1
`L-------------------------1
`
`Figure 17A
`
`n
`
`---~~~~~02
`
`I
`I
`I r-----.r----.---, I
`I
`J
`I
`I
`I L----l-----,.---l.-.....1
`I
`I AXl AX
`AX3 1
`I
`J
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`EN!
`EN2
`I
`I
`L----------
`
`TRl
`
`TR2
`
`1710
`/_
`[ML-R]
`----------.....,
`I
`*
`:
`
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`1
`EN!
`EN2
`L _________ _
`
`TRI
`
`TR2
`
`Page 23 of 34
`
`FORD 1005
`
`

`
`U.S. Patent
`
`Apr. 3, 2007
`
`Sheet 23 of 26
`
`US 7,200,582 Bl
`
`--, R
`/1720
`r--------------~------,
`
`AXl AX2 AX3
`
`1
`
`1
`
`TRl TR2
`
`1
`
`ENI EN2
`
`ENI EN2
`
`2
`
`3
`
`------~-/ 1718
`
`I
`I
`I
`
`0
`
`1
`
`0
`
`IL-----L..--.-....L..-----J
`I
`iAXI AX2
`I
`I
`I
`I
`1
`I
`I
`I
`I
`I
`~_~til __ E~~ __ _
`
`TRl
`
`0
`
`1
`
`r- - - -
`
`- - - - - - -~-:_R-------- j 1722
`
`In3
`
`0
`
`In2
`0
`
`AXI AX2 AX3
`
`AXl AX2
`
`AX3
`
`0
`
`TRl
`
`0
`
`0
`
`TRl
`
`0
`
`________________________ j
`
`ENl EN2
`
`ENl EN2
`
`Figure 178
`
`Page 24 of 34
`
`FORD 1005
`
`

`
`U.S. Patent
`
`Apr. 3, 2007
`
`Sheet 24 of 26
`
`US 7,200,582 Bl
`
`1712
`
`~-~~-~~--~
`*
`
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`EN! EN2
`1....--------...J
`
`TRl TR2
`
`1714
`
`r ____ _j_ __ _
`*
`
`TRI TR2
`
`EN2
`EN!
`L _________ _
`
`1\
`
`1716
`
`Transmission 2/Engine 2
`has mandatory and/or legal
`optionalities conflicting with
`an "optional" optionality.
`
`Figure 17C
`
`Page 25 of 34
`
`FORD 1005
`
`

`
`~ 1806(1)
`
`1804(i)
`
`1804(2)
`
`1806(3)
`
`Network
`1802
`
`1806(N)
`
`1806(N-1)
`
`1806(9)
`
`Figure 18
`
`e •
`
`00
`•
`~
`~
`~
`
`~ = ~
`
`>
`'e :-:
`
`(.H
`
`~
`
`N
`0
`0
`-....l
`
`rFJ =(cid:173)
`('D a
`
`N
`Ul
`0 .....
`N
`0\
`
`d
`rJl
`-....l
`
`00
`
`'N = = u.
`N = """"'
`
`Page 26 of 34
`
`FORD 1005
`
`

`
`U.S. Patent
`
`Apr. 3, 2007
`
`Sheet 26 of 26
`
`US 7,200,582 Bl
`
`1
`
`1/0
`
`..
`....
`
`/1919
`
`/1916
`
`VIDEO
`DRIVER
`
`..
`
`....
`
`/
`
`DISPLAY
`
`/1913
`
`J/1914
`
`Processor
`
`VIDEO
`MEMORY
`
`,
`
`MAIN
`MEMORY
`
`/1918
`
`•
`
`~------~~----------~~--~--------~
`~
`
`r
`
`/1910
`
`USER INPUT
`DEVICE(S)
`
`1909
`
`MASS STORAGE
`
`/
`
`Figure 19
`
`Page 27 of 34
`
`FORD 1005
`
`

`
`US 7,200,582 Bl
`
`1
`CONFIGURATION MODEL CONSISTENCY
`CHECKING USING FLEXIBLE RULE SPACE
`SUBSETS
`
`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 checking consistency of configuration mod- 10
`els against predetermined rules and assumptions using flex(cid:173)
`ible rule space subsets.
`2. Description of the Related Art
`A configurable product can be described by a configura(cid:173)
`tion model having a set of configuration rules. A config- 15
`urable product can be conceptually broken down into sets of
`selectable families and features of families that make up
`each product. A family represents a classification of a
`particular type of feature. Families are typically classified as
`groups of features with the same functional purpose. 20
`Example families for an automobile are "engines," "tires,"
`"seats," and "exterior paint color." Families can be repre(cid:173)
`sented in terms of the minimum and maximum number of
`features that must be present in a configuration from a family
`for the configuration to be valid. A common family mini- 25
`mum and maximum or "(min, max)" is (1, 1). This notation
`means that exactly one feature from the family must be part
`of a configuration for the configuration to be valid. Other
`common (min, max) settings are (0, 1), meaning that either
`no features or a single feature from the family must be 30
`present in a configuration for it to be valid, and (0, -1 ),
`meaning that zero or any positive number of features from
`the family must be present in a configuration for it to be
`valid.
`A feature represents an option that can be ordered on a 35
`product. All features are members of a family. Features are
`both assigned optionalities and used to qualifY other features
`and the optionalities assigned to them. An example feature
`from the engine family is a "4.8 liter V8." Features relate to
`each other via ordering codes or optionalities. Example
`optionalities include "S", "0", "M", and "N," which trans(cid:173)
`late to standard, optional, mandatory, and not available. A
`specific example would be "the 4.8 liter V8 engine is
`standard on the GS trim."
`A configuration rule includes a main feature, an option(cid:173)
`ality, one or more constraints, and an applicable timeframe.
`As an example:
`
`45
`
`2
`above defines a buildable configuration in the following
`way: "the 4.8 liter V8 is buildable (because it is standard)
`with the combination of XL and US." If the combination of
`features, such as of XL and US, is not buildable, the example
`rule is inactive. Consequently, even though the engine is
`buildable with that combination, if the combination is not
`buildable, the three features together are not a buildable
`configuration. A rule that would make the example rule
`inactive is the following:
`
`Main feature
`
`Optionality Constraints Timefrarne
`
`XL
`
`N
`
`us
`
`September 2002 Rule 2
`
`Rule 2 means "the XL trim main feature is not available
`with US from September of 2002 onward." Until the XL
`main feature is made available with the US by changing the
`optionality from "N" to one that expresses a positive rela(cid:173)
`tionship, there will not be a buildable configuration for XL,
`US, and the 4.8L engine.
`Thus, a rule defines a buildable configuration between its
`main feature and its constraints only. A rule does NOT define
`a buildable configuration relationship between the members
`of its constraints. A separate rule must define that buildable
`configuration. Consequently, all rules together for a product
`define the complete product buildable configurations. In
`order to determine if the three features in the example rule
`(the main feature and the constraints) are a buildable con(cid:173)
`figuration, the rules written on each of those features (i.e.
`where each feature is the main feature) need to be considered
`jointly. Inactive rules do not define buildable configurations
`until they become active.
`Inconsistencies between rules represent a significant con-
`cern when modeling a product using rules. Inconsistencies
`among rules in configuration models result in errors that
`negatively impact the usability of a configuration model.
`Inconsistencies can occur due to modeling mistakes or due
`40 to multiple parties generating rules for the same configura(cid:173)
`tion model. Thus, detecting inconsistency errors through
`consistency checking plays an important role in developing
`useable, robust configuration models.
`
`For example:
`
`Main feature
`
`Optionality Constraints Time frame
`
`Main feature
`
`Optionality Constraints
`
`Timeframe
`
`4.8 liter V8
`
`s
`
`XL&US
`
`May-December
`2003
`
`Rule 1
`
`Rule 1 means "the 4.8 liter V8 is standard with the XL
`trim and US market from May to December 2003." The
`main feature represents the feature that is being affected by
`the rule. Optionalities can be positive or negative: positive
`optionalities state that the main feature can work with the
`constraints; negative optionalities state the main feature
`cannot work with the constraints. Constraints qualifY the
`rule and can be an arbitrary Boolean expression of features
`such as AND, NOT, and OR operators. The timeframe
`specifies when the other rule elements are effective.
`A configuration buildable describes what features can and
`can't exist with other features of a product. The example rule
`
`50
`
`XL
`XL
`
`N
`s
`
`us
`us
`
`September 2003
`September 2003
`
`Rule 3
`Rule 4
`
`Rule 3 and Rule 4 are inconsistent because Rule 3
`signifies that the feature XL is not available in the U.S.
`55 market, and Rule 4 signifies that the feature XL is standard
`in the U.S. market. As the number of rules grows, the ability
`to detect inconsistencies becomes more challenging.
`FIG. 1 depicts a set of rules 100 with features F1-F4 of
`a single family, optionalities, and constraints represented by
`60 families A, B, C, D, E (each having "X" numberoffeatures).
`FIGS. 2 and 3 depict the rules of FIG. 1 in respective grids
`200 and 202 and illustrate two conventional ways of detect(cid:173)
`ing inconsistencies between rules. In FIG. 2A, each cell in
`a colunm is compared against every other cell in a colunm.
`65 An inconsistency error exists if two cells with a colunm have
`inconsistent optionalities or other assumptions are violated,
`such as a lack of a standard configuration in a colunm. Some
`
`Page 28 of 34
`
`FORD 1005
`
`

`
`US 7,200,582 Bl
`
`3
`configurable products have tens of thousands or hundreds of
`thousands of rules defining buildable configurations. As the
`number of rules and, thus, colunms in the grid of FIG. 2A
`grow, colunm by column inconsistency checking becomes
`very computationally time consuming.
`FIG. 2B depicts a variation on the colunm-by-column
`consistency checking approach of FIG. 2A. In FIG. 2B
`colunms with identical optionalities are grouped together.
`Thus, the number of consistency checking operations is
`reduced; however, this can still result in long periods of
`computational processing.
`
`SUMMARY OF THE INVENTION
`
`In one embodiment of the present invention, a method of 15
`detecting multiple consistency error types between configu(cid:173)
`ration rules, wherein each consistency error is represented
`by a set equation, includes, for each consistency error,
`identifying one or more sets of feature combinations in
`accordance with the set equation of the consistency error. 20
`The method further includes detecting the consistency error
`using the one or more identified sets of feature combinations
`and the set equation associated with the consistency error.
`In another embodiment of the present invention, a con(cid:173)
`sistency checking system for detecting multiple consistency 25
`error types between configuration rules, wherein each con(cid:173)
`sistency error is represented by a set equation, the system
`including a processor and a memory coupled to the proces(cid:173)
`sor. The memory having instructions executable by the
`processor that for each consistency error identifies one or 30
`more sets of feature combinations in accordance with the set
`equation of the consistency error and detects the consistency
`error using the one or more identified sets of feature com(cid:173)
`binations and the set equation associated with the consis(cid:173)
`tency error.
`
`4
`FIGS. llA, llB, llC, and llD depict a use of trie data
`structures and set routines to determine a missing optionality
`consistency error within a subset of a configuration space.
`FIG. 12 depicts a use of trie data structures and set
`routines to determine a consistency error when a usage rule
`is present, a standard optionality is required, and no standard
`optionality is present.
`FIG. 13 depicts an operational flow chart to determine a
`consistency error indicating the existence of multiple stan-
`10 dards for a subset of configuration rules.
`FIGS. 14A, 14B, 14C, 14D, and 14E depict a use of trie
`data structures and set routines to determine a consistency
`error indicating the existence of multiple standards for a
`subset of configuration rules.
`FIG. 15 depicts example configuration rules to illustrate
`consistency checking operations of the consistency checking
`system of FIG. 4 when determining a consistency error that
`occurs when mandatory or legal optionalities conflict with
`an "optional" optionality.
`FIG. 16 depicts a grid containing the rules of FIG. 15.
`FIGS. 17 A, 17B, and 17C depict a use of trie data
`structures and set routines to determine a consistency error
`that occurs when mandatory or legal optionalities conflict
`with an "optional" optionality.
`FIG. 18 depicts a block diagram depicting a network
`enviroument in which a consistency checking system may
`be practiced.
`FIG. 19 depicts a computer system.
`
`DETAILED DESCRIPTION
`
`Although the present invention has been described in
`detail, it should be understood that various changes, substi(cid:173)
`tutions and alterations can be made hereto without departing
`35 from the spirit and scope of the invention as defined by the
`appended claims.
`As stated above, inconsistencies between rules represent
`a significant concern when modeling a product using rules.
`The amount of time and processing resources used to
`40 perform consistency checking also represents a significant
`concern. Long processing times for consistency checks
`introduce a number of problems, such as detrimental post(cid:173)
`ponement of consistency checks, reluctance to make
`changes to a configuration model, and work force inefli-
`45 ciencies. Embodiments of the consistency checking system
`described herein improve consistency checking perfor(cid:173)
`mance, especially when performing consistency checks on
`large configuration models, i.e. configuration models having
`a large number of rules.
`The consistency checking system approaches a configu-
`ration model from the perspective of sets of features and
`families. The configuration space of a model represents the
`entire set of all combinations of selections within a configu(cid:173)
`ration model. The consistency checking system operates on
`55 subsets of the configuration space by consolidating data
`within the configuration space into minimized subsets that
`represent a portion of the configuration space where a
`particular consistency error can occur. Thus, the contents of
`each subset vary depending upon which consistency error is
`60 being checked, and consistency checking is performed on
`reduced subsets determined on an error by error basis rather
`than on the configuration space as a whole.
`One difficulty that has been overcome by embodiments of
`the consistency checking system described herein is the
`65 identification of individual consistency errors and the ability
`to identify the subsets of the configuration space where such
`consistency errors can occur.
`
`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 set of configuration rules
`having features, optionalities, and constraints.
`FIG. 2A (prior art) depicts a colunm-by-colurnn approach
`to rule consistency checking.
`FIG. 2B (prior art) depicts a consolidation of identical
`colunms followed by a colunm-by-colunm approach to rule
`consistency checking.
`FIG. 3 depicts a grid with features grouped in accordance
`with particular consistency checking error operations.
`FIG. 4 depicts a consistency checking system.
`FIG. 5 depicts an operational flow chart for the consis(cid:173)
`tency checking system of FIG. 4.
`FIG. 6A depicts an example trie data structure.
`FIG. 6B depicts a binary form of the trie data structure of
`FIG. 6A.
`FIGS. 7 A, 7B, and 7C depict trie minimization operations
`applied to the trie data structure of FIGS. 6A and 6B.
`FIG. 8 depicts example configuration rules to illustrate
`consistency checking operations of the consistency checking
`system of FIG. 4.
`FIG. 9 depicts a grid containing the rules of FIG. 8.
`FIG. 10 depicts a configuration space with multiple sub(cid:173)
`sets.
`
`Page 29 of 34
`
`FORD 1005
`
`

`
`US 7,200,582 Bl
`
`5
`Following are four examples of consistency error types
`that utilize subsets of the configuration space to efficiently
`identify associated consistency errors. The particular subsets
`and example data structure representation and set operations
`are described in more detail below. Arbitrary labels are
`applied to each consistency error type for reference pur(cid:173)
`poses.
`(a) Error "F1" no usage rule of any optionality for a
`particular configuration of families and features.
`(b) Error "F2 (a)"-a usage rule is present, but a standard 10
`optionality is required and no standard optionality is
`present.
`(c) Error "F2 (b)"-multiple standards.
`(d) Error "F2 (c)"-mandatory and legal optionalities
`conflict with an "optional" optionality.
`Another difficulty overcome by the consistency checking
`system relates to identifying and refining a data structure to
`represent such subsets and determining the 'mathematical
`set operations' applied to the data structure in a data pro(cid:173)
`cessing system that provide identification of consistency 20
`errors. A trie data structure effectively represents the con(cid:173)
`figuration subsets, and data processing systems can effi(cid:173)
`ciently conduct set operations on the trie data structures.
`FIG. 3 depicts an example grid that reflects the consoli(cid:173)
`dation of features and columns in the grid into subsets. For 25
`example, the F1 consistency error operates on the set of
`features having standard, mandatory, optional, and legally
`required optionalities less restrictions. The F2( a) consis(cid:173)
`tency error operates on a first set of features having
`'optional' optionalities and a second set of features having 30
`standard, mandatory, and legally required optionalities. The
`F2(c) consistency error operates on a first of features having
`mandatory and legally required optionalities and a second
`set of features having 'optional' optionalities. These sets can
`be further refined as described below to account for 35
`restricted configurations and other contingencies.
`FIG. 4 depicts consistency checking system 400, which
`includes a model having the configuration rules that define
`the configuration space of one or more products. The con(cid:173)
`sistency checking system 400 also includes a consistency 40
`checking error operations module 404 that includes consis(cid:173)
`tency error definitions and operations to generate configu(cid:173)
`ration subsets based on a particular consistency error being
`checked, asso