UTILITY
`«Em/707187
`
`
`APPLICANTS
`
`
`
`
`
`
`
`ATTORNEY'S
`FILING FEE
`
`['3 y
`Foreign pn'otily claimed
`
`DOCKET NOI
`RECEIVED
`
`35 USC 119 conditions me! D yes
`
`
`
`,2;
`I
`
`, PARTS OF APPLICATION
`-_ EILED’TSIE‘PARATELY
`
`us. DEPT OF COMMJ PAT. & TM-ké‘ro-436L (a
`
`
`
`
`KEVINA
`
`
`PRIMARY SWIM}
`BATCH
`
`
`
`Primary Examiner NUMBER Z,/. .
`
` WARNING: The information dSSclosed herein may be Iegm ad Unauthorized discIoSure may be prohib
`Patent & Trademark OfficeIs restrictedto authorized employees and contractors only.
`by the United Siates Code Tnle 35 Segm’ns 122 181 and 368 Possession outside the
`
`
`
`FomI ’T0-436A
`(Rev. 5222)
`
`
`
`{CAPT—W
`
`
`
`1
`1
`
`CONFIGIT 1013
`CONFIGIT 1013
`
`

`

`
`
`
`
`
`
`
`
`Da‘e
`Entered
`or
`Counted
`
`PATENT APPLICATION»
`iIIIWIIWNWIIIHll!!!llllFEEIIEIIHHIIHIII
`11870718?
`
`CONTENTS
`
`
`
`;
`
`APPROVED FOR LICENSE D
`,V
`1x
`A“
`INHIAtgbi A §m
`
`Date
`Received
`or
`Mailed
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`(FRONT)
`
`2
`
`
`
`“W‘ 9 My,
`
`

`

`
`
`1
`
`ix
`
`PATENTNUMEER
`ORIGINAL CLASSIFICATION
`'
`CLASS
`.
`alSUBCLAss
`;
`.;
`
`
`
`///
`}
`
`APPLICATIOh/Jl/QERIAL NUMBER
`J,
`CROSS REFERENCES)
`
`
`A!
`3 / “ ‘7
`suacmss
`“' j
`f
`'El»
`’
`(ONESUBCLASSPERBLOCM
`’/
`x
`
`
`APPLICANTS NAMF (PLEASE PRINT)
`
`M
`
`HR“
`
`
`
`I A
`1:; bk I)
`IF REISSDE‘ ORIGINAL PATENT NUMBER
`
`
`
`
`INTERNATIONAL CLASSIFICATION
`VII
`
`
`
`
`
`
`PTO 27o
`(FIEV. 5.91;
`
`GROUP
`
`ARTUNIT
`
`
`
`
`
`[CQIIC
`
`
`ily cIaime
`condition
`I\cknowIe
`
`
`\PPLIC.
`IRATEL
`AL LOV
`
`
`
`Labé
`Area
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`_
`
`,
`
`.
`
`
`
`
`
`I
`
`
`
`
`
`
`mEmm».1,«3.112;
`XAfiLgLé-Axihmmzmuilnvmiktiuiem
`
`
`
`
`.m:AmyE-mEmexmy
`
`
`
`
`
`(IIA m,U:ml”WWW.ww‘Lg
` :Tfiwfii
`
`mm\IG) ::r:4:4:
`
`
` “IE,“
`
`
`
`
`
`
`
`
`
`
`
`
`L
`I
`_I
`
`‘TASSISTANT EXAMINER (PLEASE STAMD OR PRINT FULL NAME)
`
`]
`HM __,,
`"
`
`
`ITbIaM’ '
`a ELI
`.: @Iin
`‘L 61“.
`InI
`
`incom
`
`
`
`
`01OD
`
`
`
`
`
`
`
`65
`
`
`
`
`
`
`
`
`
`
`
`
`I713“
`
`SYMBOLS
`
`
`Mum-a
`AIlowefl
`
`(Through numnml) CnnceIed
`ResIrictan
`.
`
`,..,NonveIecIea
`33d 83
`Inlcrmmnnn
`AnDBaI
`Omwea
`
`
`
`n\
`
`O)—Z+
`
`
`
`
`
`
`
`
`
`
`
`I94
`
`:95
`I96
`
`97‘
`
`98-
`I
`
`9-5
`
`
`100;
`
`
`
`I I
`
`‘
`
`I
`
`(LEFT INSIDE)
`
`3
`3
`
`
`
`igkéim in"
`77'
`Date
`IE 1 § {h
`I
`I
`
`E IE1;
`{Q
`“ 5
`E:
`40 M:
`7,
`‘
`‘
`L,
`V -n:
`MUEEi.
`’J— 2
`,
`L
`I
`1:? IL,
`, ,
`I
`UI
`I 4i
`_
`'> SI
`<
`,
`E
`‘1"
`I
`..
`A
`,_
`7
`‘6
`6I
`I
`s L
`
`’
`7I
`I. M,
`1
`
`E;
`8I
`,_
`LI
`3
`
`I
`I
`I
`
`
`p 10
`'I
`'
`
`flaw I
`H M
`I
`I
`
`51-12 I
`l
`13735 I
`I
`14
`I
`:U
`
`I
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
` LAM“.AME,”.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`

`

`
`
`SEARCH NOTES
`
`
`
`
`
`
`
`
`
`4
`
`

`

`U8005825651A
`
`5,825,651
`[11] Patent Number:
`[19]
`Ulllted States Patent
`
`Gupta et al.
`[45] Date of Patent:
`Oct. 20, 1998
`
`[
`
`54 METHOD AND APPARATUS FOR
`l
`1
`MAINTAINING AND CONFIGI RING
`SYSTEMS
`
`5,355,317 10/1994 Talbott et a].
`5,357,440 10/1994 Talbott et a].
`5,586,052 12/1996 Iannuzzi et a1.
`5,659,478
`8/1997 Pennisi el al.
`
`
`
`...... 364/468
`..
`.. 364/467
`
`.. 364/512
`.........
`364/468.01
`
`[75]
`
`Inventors: Nee-raj Gupta; Venky Veeraraghavan;
`Ajay Agarwal, all of Austin, TeX.
`
`.
`.
`.
`.
`Primary anmmer4evtn A. Kness
`Attorney, Agent, or Firm—Becker & Harriman
`
`[73] As51gnee: Eggiyvggelopment Group, Inc.,
`
`ABSTRACT
`[57]
`The invention provides the ability to interactively select and
`configure a product among a set of related products based on
`availability and compatibility of features and options. It does
`not impose an order in the selection of products, features or
`Options; only valid selections can be made at any time. To
`crea e an e ec romc re resen a 10H 0
`e
`ro uc 1n orma-
`1
`1
`1
`P
`t l
`f 1h P d
`t
`f
`tion to achieve the above goal,
`the invention provides a
`framework for defining a systems by defining the compo-
`nents of the system using elements contained in a parts
`catalog and defining relationships between the components
`of a system. Aconfiguration system validates a configuration
`using the system delimtion, the current state of the configu—
`ration and user input.
`
`85 Claims, 24 Drawing Sheets
`
`[21] Appl. No.: 707,187
`,
`[22]
`Flled:
`SCP' 3’ 1996
`
`[51]
`Int. Cl." ........................................................ G06F 1/00
`.
`,
`
`[52] U.S. Cl. ............................ 364/468.09, 364,488
`[58] Field of Search
`364 ’468 09 468 02
`W364/468D5. 4681 4583395651,
`'
`’
`’
`I
`‘
`i
`’
`References Cited
`U.S. PATENT DOCUMENTS
`1/1989 Athcrton .
`.............
`5/1991 Addesso et al.
`5/1991 Brown et al.
`................
`
`[50]
`
`4,796,194
`5,019,961
`5,019,992
`
`
`364/192
`
`.. 364/468
`
`602
`
`
`
`
`608 /
`
`650
`
`
`
`
`requires choice
`includes
`
`Requires
`Choice
`
`
`excludes
`
`removes
`
`5
`
`

`

`US. Patent
`
`Oct. 20, 1998
`
`Sheet 1 0f 24
`
`5,825,651
`
`119
`
`116
`
`VIDEO AMP
`
`CRT
`
`113
`
`.
`
`114
`
`117
`
`115
`
`CPU
`
`VIDEO MEMORY
`
`MAIN MEMORY
`
`118
`
`110
`
`KEYBOARD
`.
`
`MOUSE
`
`‘
`
`MASS STORAGE
`
`FIG. 1
`
`6
`
`

`

`US. Patent
`
`Oct. 20, 1998
`
`Sheet 2 of 24
`
`5,825,651
`
`202
`
`\
`
`Maintenance
`
`1 Configuration
`
`206
`
`212
`/
`
`Part
`Relationships
`
`5
`
`214
`
`204
`
`
`
`Verification Catalog
`
`Definition(s)
`
`Product
`
`Specification/
`
`Product
`
`FIG. 2
`
`7
`
`

`

`US. Patent
`
`Oct. 20, 1998
`
`Sheet 3 of 24
`
`5,825,651
`
`302
`
`306
`
`308
`
`304
`
`310
`
`..............................................................
`
`318
`
`...........................................................
`.
`
`I".
`
`FIG. 3
`
`8
`
`

`

`US. Patent
`
`Oct. 20, 1998
`
`Sheet 4 of 24
`
`5,825,651
`
`402
`
`414
`
`
`
`/
`Includes
`
`\
`Excludes
`
`removes ——-> ‘
`
`404 /
`
`\ 406
`
`requires
`choice
`
`
`
`9
`
`

`

`US. Patent
`
`Oct. 20, 1998
`
`Sheet 5 of 24
`
`5,825,651
`
`Includes
`
`502
`
`[—
`l
`
`514
`
`—-——Optional-—< I
`\
`
`516
`
`requires
`choice
`
`504
`
`FIG. 5
`
`10
`10
`
`

`

`US. Patent
`
`0,2m
`
`a\
`
`woo
`
`O./“vow
`
`whS
`
`f0
`
`mN3\
`
`M8.559:33:
`
`%REED9ll...1“2.33%33:3:
`
`
`
`5,825,651
`
`«3
`
`/
`
`“33:2:
`
`/|_..I|
`
`\l
`
`3%588
`
`$5059.
`
`o.UE
`
`«No
`
`now
`
`11
`11
`
`
`
`

`

`US. Patent
`
`Oct. 20, 1998
`
`Sheet 7 0f 24
`
`5,825,651
`
`m25me
`
`con
`
`«on
`
`Non
`
`gmfihmuCH
`
`cofificgmammm
`
`“2&8an
`
`9:58:39:25
`
`EEme
`
`coflfifimwhmmm
`
`12
`12
`
`
`
`
`
`

`

`US. Patent
`
`Oct. 20, 1998
`
`Sheet 8 0f 24
`
`5,825,651
`
`/ 802
`
`804
`
`806
`
`808
`
`810
`
`/
`
`/ /
`
`/
`
`\___V___/\_____V_____/
`
`P bits
`
`N bits
`
`Included Vector
`
`Excluded Vector
`
`P+N Bits
`
`Required Groups Vector
`
`/ 812
`
`FIG. 8A
`
`13
`13
`
`

`

`US. Patent
`
`Oct. 20, 1998
`
`Sheet 9 of 24
`
`5,825,651
`
`Runtime
`Table
`
`822
`
`/
`
`Right—Hand Side
`
`Side
`
`826
`
`Left-Hand
`
`1
`E
`
`824
`
`Includes, /
`Excludes, or
`Removes Tables
`
`832
`
`830
`
`828
`
`836
`
`-
`Requlres
`Choice
`Tables
`
`334
`
`838
`
`0 1 0 1 0
`
`0
`
`i
`gminfinax Pointer
`
`Left-Hand
`Side
`
`Right-Hand
`Side
`
`Left-Hand? Right-Hand
`Side
`
`Side
`
`FIG. 8B
`
`14
`14
`
`

`

`US. Patent
`
`Oct. 20, 1998
`
`Sheet 10 0f 24
`
`5,825,651
`
`
`
`
`user selects item :1
`
`902
`
`
`
`
`
`raise error
`
`
`
`906
`
`
`
`04
`9,
`
`No
`
`
`
`Yes
`
`908
`
`set nth bit 111 uVec
`
`
`
`update state
`
`
`
`
`
`evaluate
`
`
`
`
`
`
`relatmnshtps
`
`apply to interface and
`giver user control
`
`916
`
`FIG. 9
`
`15
`15
`
`

`

`US. Patent
`
`Oct. 20, 1998
`
`Sheet 11 0f 24
`
`5,825,651
`
`0
`
`1002
`Illllligiialalilllll
`
`1004
`
`iVecCopy == iVec
`xVecCopy = xVec
`
`rVecCopy = rVec 1 006
`
`iTable forward (iVec)
`xTable forward (xVec)
`rTable forward (rVec)
`
`
`
`
`rTable backward (uVec)
`
`iTable backward (xVec)
`xTable backward (selectedVec)
`
`1008
`
`1010
`
`1012
`
`rctable backward
`rctable forward
`
`update state
`
`1014
`
`
`
`change in a
`vector?
`
`
`Ye54)©
`
`N0 1016
`
`end
`
`FIG . 10
`
`16
`16
`
`

`

`US. Patent
`
`Oct. 20, 1998
`
`Sheet 12 0f 24
`
`5,825,651
`
`
`
`1102
`
`
`
`selection in
`uVec?
`
`
`No
`
`Yes
`
`1104
`
`raise error
`
`1106
`
`1108
`
`1110
`
`1112
`
`remove selection
`from uVec
`
`update state
`
`evaluate
`
`relationships
`
`1114
`
`apply to interface and
`give user control
`
`1116
`
`FIG. 11
`
`17
`17
`
`

`

`U.S. Patent
`
`Oct. 20, 1998
`
`Sheet 13 0f 24
`
`5,825,651
`
`create rels. based on
`
`hierarchy
`
`perform back
`linking
`
`evaluate include
`chains
`
`evaluate subgroup
`excludes
`
`1204
`
`1206
`
`1208
`
`1210
`
` 1202
`
`
`
`
`
`
`
`
` evaluate rel.
`factorization
`
`
`
`
`perform
`relationship
`compression
`
`1212
`
`
`
`1214
`
`FIG. 12
`
`18
`18
`
`

`

`US. Patent
`
`Oct. 20, 1998
`
`Sheet 14 0f 24
`
`5,825,651
`
`1318
`
`1316l
`
`1306
`
`1302
`
`
`13121314
`/ \C
`
`
`
`FIG.13A
`
`1304
`
`1310
`
`1308
`
`19
`19
`
`

`

`US. Patent
`
`()cL 20,1998
`
`SheetlS 0f24
`
`5,825,651
`
`.NomH
`
`.oomH
`
`.womH
`
`.meH
`
`\2.2.32.22
`
`.onH
`
`,womH
`
`20
`20
`
`m2.05
`
`

`

`US. Patent
`
`Oct. 20, 1998
`
`Sheet 16 0f 24
`
`5,825,651
`
`1402
`
`1406
`
`all include rels.
`
`
`
`processed?
`
`Yes
`
`end
`
`1408
`
`all rels.
`
`compared?
`
`
`
`Yes
`
`1404
`
`
`
`temp = tempsave?
`
`
`
`Fig. 14A
`
`21
`21
`
`

`

`US. Patent
`
`Oct. 20, 1998
`
`Sheet 17 0f 24
`
`5,825,651
`
`
`
`get another rel. (r2)
`
`
`
`
`
`temp = temp | r2.rhs
`
`FIG. 14B
`
`22
`22
`
`

`

`U.S. Patent
`
`Oct. 20, 1998
`
`Sheet 18 0f 24
`
`5,825,651
`
`end
`
`Yes
`
`all rels.
`
`7
`processed.
`
`1506
`
`get next rel. (r)
`
`1507
`
`No
`
`1504
`
`
`
`
`
`
`
`
`
`Yes
`
`all rels.
`
`compared?
`
`Yes
`
`No
`
`1510
`
`get other rel. (r2)
`
`1512
`
`@010
`
`FIG. 15A
`
`23
`23
`
`

`

`US. Patent
`
`Oct. 20, 1998
`
`Sheet 19 0f 24
`
`5,825,651
`
`r.grp?
`
`r2. grp subset of
`
`1514
`
`
`
`
`
`create exclude rel.
`
`(r.1hs | r2.lhs f) r2.grp 8z~ r.grp
`
`FIG. 15B
`
`24
`24
`
`

`

`US. Patent
`
`Oct. 20, 1998
`
`Sheet 20 0f 24
`
`5,825,651
`
`1602
`
`mark each rel.
`as "new"
`
`1609
`
`reset includes rels.
`
`
`added = "false"
`
`Yes
`
`all includes rels.
`
`processed?
`
`1606
`
`1608
`
`Yes
`
`added = "true"?
`
`
`
`
`
`
`
`
`
`
`
`
`No
`
`1610
`
`Yes—>®
`
`N
`
`O
`
`1612
`
`get next includes
`
`
`
`1613
`
`reset relationships
`
`all "new" rels.
`
`1614
`
`processed?
`
`FIG. 16A
`
`25
`25
`
`@No
`
`

`

`US. Patent
`
`Oct. 20, 1998
`
`Sheet 21 0f 24
`
`5,825,651
`
`1616
`
`get next rel. (r),
`mark as "old"
`
`
`
`
`
`!(r.lhs 8:8: i‘rhs)?
`
`Yes
`
`NO
`
`1622
`
`new.th = (rlhs and not i.rhs) or i.lhs
`
`
`
`1624
`
`newlhs has
`value?
`
`
`
`Yes
`
`FIG. 16B
`
`26
`26
`
`

`

`U.S. Patent
`
`Oct. 20, 1998
`
`Sheet 22 0f 24
`
`5,825,651
`
`add new rel.
`
`(new.lhs 33> r.rhs
`
`mark new rel.
`as "new"
`
` 1626
`
`
`
`
`1628
`
`1630 »
`
`
`
`FIG. 16C
`
`27
`27
`
`

`

`US. Patent
`
`Oct. 20, 1998
`
`Sheet 23 0f 24
`
`5,825,651
`
` 1702
`
`
`all relationships in
`table processed?
`
`
`
`
`Yes@
`
`No
`
`1704
`
`get next relationship as
`current relationship (r)
`
`
`
`
`
`r processed against -
`other rels. in table?
`
`
`
`r2.lhs?
`
` r.lhs subset of
`
`— FIG. 17A
`
`28
`28
`
`

`

`US. Patent
`
`Oct. 20, 1998
`
`Sheet 24 0f 24
`
`5,825,651
`
` 1716
`
`1718
`
`all relationships in
`table processed?
`
`
`
`
`Yes
`
`end
`
`N o
`
`1720
`
`get next relationship as
`current relationship (r)
`
`
`
`
`
`
`
`r.rhs = zeroes?
`
`No
`
`
`
`Yes
`
`delete r from table
`
`FIG. 17B
`
`29
`29
`
`

`

`5,825,651
`
`1
`METHOD AND APPARATUS FOR
`MAINTAINING ANI) CONFIGURING
`SYSTEMS
`
`BACKGROUND OF THE INVENTION
`
`1. Field of the Invention
`
`This invention relates to maintaining and configuring
`systems.
`2. Background Art
`A system is comprised of components. Before a system
`can be built the components of the system must be identified.
`To configure a system, a user must select the parts to include
`in the system. Typically, one who is knowledgeable about a
`system and its components defines the system. Thus, for
`example, an automobile salesperson assists an automobile
`buyer in determining the type and features of the automo—
`bile. The salesperson understands the features and options
`that are available to create a valid configuration. Some
`features and options cannot be combined. The selection of
`some features caused other features to be unavailable, etc. It
`would otherwise be difficult for the buyer to identify all of
`the features and options available on the automobile that can
`be combined to create a valid configuration.
`Computer systems have been developed to assist one in
`configuring a system. However,
`these systems use a con—
`figuration language to define a system. Like a programming
`language, a configuration language uses a syntax that must
`be understood by a user who is maintaining the data (i.e., a
`data maintainer). To use one of these configuration systems,
`it
`is necessary for a data maintainer to understand the
`configuration language. This limits the number of users who
`are able to use the configuration systems. That is, the level
`of sophistication needed to communicate with the configu—
`ration system (through a configuration language) results in
`less sophisticated users being unable to use the system.
`In addition, configuration systems impose a flow or order-
`ing to the user operations. For example, a user is required to
`remove components from the system in reverse of the order
`in which they were chosen. Thus, a user may be forced to
`remove components that
`the user wants to keep in the
`configuration to remove an unwanted component. A novice
`user may have perform many removal operations before
`achieving an acceptable configuration. If the novice user is
`required to remove components in a preset order, the user
`can become frustrated or confused and abort the configura-
`tion process.
`These systems are designed for a more sophisticated user
`that has knowledge of the system that is being configured as
`well as the configuration system used to configure the
`system. A end user such as an automobile shopper would
`have difficulty using these systems.
`Further, to use these systems a user must be trained to
`understand the configuration language. Thus, a user who
`otherwise has knowledge of the systems that are being
`configured must undergo training to be able to use these
`configuration systems to configure systems. This leads to
`increased expenditures such as for training.
`SUMMARY OF THE INVENTION
`
`The invention provides the ability to interactively select
`and configure a product among a set of related products
`based on availability and compatibility of features and
`options. It does not impose an order in the selection of
`products, features or options; only valid selections can be
`
`10
`
`15
`
`30
`
`40
`
`60
`
`2
`made at any time. To create an electronic representation of
`the product
`information to achieve the above goal,
`the
`invention provides a framework for defining a product line.
`A product line is defined as a set of related products. A
`product line has a set of products that contain parts, or
`components. Parts used to define a product are selected from
`a parts catalog. Parts in a product definition are related or
`classified as: included (parts that are included by default),
`required choices (a choice among a group of parts that must
`be made to achieve a valid configuration), optional (parts
`that can be optionally included in the configuration).
`Relationships can be defined between the parts in a
`product definition. A relationship relates a first set of parts
`with a second set of parts. A set can include multiple parts.
`The incorporation of parts in a set can be arbitrary. That is,
`a multi—part set can contain parts that are otherwise unre—
`lated. For example, a set can contain parts such as an engine,
`sun roof and a color. These parts seem to be unrelated,
`however, it is possible to combine them into a relationship
`set for purposes of forming a relationship using the present
`invention.
`
`Preferably, the part relationships are: included, excluded,
`removed, and requires choice. An included part is included
`automatically. A part
`is excluded from the configuration
`when its inclusion would result in an invalid configuration.
`Apart may be removed when another part is added. Thus,
`when a first part exists in the configuration and a second part
`is added, the first part is removed from the configuration.
`The requires choice relationship is used to allow a set of
`choices to be made from a group of parts. The number of
`parts chosen is limited to a valid bounds specification. The
`relations that are created between parts within a product are
`enforced only on that particular product. However, if some
`part-to-part relationships are to be enforced on all products
`within a product line, then the relations are generated once
`and enforced for all products.
`A maintenance system is used to define a product. Using
`the maintenance system, a product can be defined using the
`product classifications and the part relationships. A graphical
`user interface (GUI) is used to allow the user to interactively
`generate a definition. Instead of configuration languages,
`GUI operations such as drag and drop and selection opera-
`tions can be used to specify a definition. The notions of
`included, optional and required choice are easily compre-
`hensible to a user. Further, the idea that parts have interre-
`lationships is also easily understood. Thus, a product can be
`defined without having to learn a complicated configuration
`language.
`A configuration system is used to configure a system
`using a definition created by the maintenance system. The
`configuration system ensures that the current configuration
`state is always valid. The user can select and unselect parts
`in any order. When user input is received, the configuration
`system validates the input based on the current state of the
`configuration. In addition, the configuration system identi—
`fies selections that could cause a valid configuration to
`become invalid. The configuration removes these selections
`from the set of possible selections so that the user does not
`make an invalid selection.
`
`The configuration system evaluates the current state of a
`configuration based on the product definition, part relation—
`ships and state information. After receipt of input from a
`user, the configuration system evaluates relationships in both
`the forward and backward direction. Forward and backward
`evaluations can result in the addition or deletion of elements
`from the configuration.
`
`30
`30
`
`

`

`5,825,651
`
`4
`FIG. 7 provides an block diagram illustrating the conver-
`sion process according to one embodiment of the invention.
`FIGS. 8A—8B illustrate components of internal represen-
`tation 706 according to an embodiment of the invention
`FIG. 9 provides a process flow for processing a user
`selection according to an embodiment of the invention.
`FIG. 10 provides an example of a relationship evaluation
`process flow according to an embodiment of the invention.
`FIG. 11 provides an example of an unselect item process
`flow according to an embodiment of the invention.
`FIG. 12 provides a flow for translation processing accord-
`ing to an embodiment of the invention.
`FIGS. 13A713B provide an illustration of groups and
`nested groups according to an embodiment of the invention.
`FIGS. 14A—14B provide an includes chain process flow
`according to an embodiment of the invention.
`FIGS. 15A—15B provides an example of a subgroup
`excludes process flow according to an embodiment of the
`invention.
`
`FIGS. 16A—16C provide an example of a relationship
`factorization process flow according to an embodiment of
`the invention.
`
`FIGS. 17A717B provide an illustration of a relationship
`compression process flow according to an embodiment of
`the invention.
`
`DETAILED DESCRIPTION OF THE
`INVENTION
`
`A method and apparatus for maintaining and configuring
`systems is described. In the following description, numerous
`specific details are set forth in order to provide a more
`thorough description of the present
`invention. It will be
`apparent, however, to one skilled in the art, that the present
`invention may be practiced without these specific details. In
`other instances, well-known features have not been
`described in detail so as not to obscure the invention.
`
`The present invention can be implemented on a general
`purpose computer such as illustrated in FIG. 1. Akeyboard
`110 and mouse 111 are coupled to a bidirectional system bus
`118. The keyboard and mouse are for introducing user input
`to the computer system and communicating that user input
`to CPU 113. The computer system of FIG. 1 also includes a
`Video memory 114, main memory 115 and mass storage 112,
`all coupled to bi-directional system bus 118 along with
`keyboard 110, mouse 111 and CPU 113. The mass storage
`112 may include both fixed and removable media, such as
`magnetic, optical or magnetic optical storage systems or any
`other available mass storage technology. Bus 118 may
`contain, for example, 32 address lines for addressing video
`memory 114 or main memory 115. The system bus 118 also
`includes, for example, a 32-bit DATA bus for transferring
`DATA between and among the components, such as CPU
`113, main memory 115, video memory 114 and mass storage
`112. Alternatively, multiplex DATA/address lines may be
`used instead of separate DATA and address lilies.
`In the preferred embodiment of this invention, the CPU
`113 is a 32-bit microprocessor manufactured by Motorola,
`such as the 680X0 processor or a microprocessor manufac-
`tured by Intel, such as the 80X86, or Pentium processor.
`However, any other suitable microprocessor or microcom—
`puter may be utilized. Main memory 115 is comprised of
`dynamic random access memory (DRAM). Video memory
`114 is a dual-ported video random access memory. One port
`of the video memory 114 is coupled to video amplifier 116.
`The Video amplifier 116 is used to drive the cathode ray tube
`
`10
`
`15
`
`3
`The invention uses both an external and internal repre-
`sentation of a definition or definitions. Atranslation mecha-
`nism is used translate an external representation into an
`internal representation. The external representation uses a
`conceptually understand able set of relationships for defining
`a system and the relationships between the components of
`the system. The invention takes the definition created by a
`user and supplements and compresses the definition when
`necessary to create an internal representation. The internal
`representation is used during configuration to initialize and
`validate a configuration based on user input.
`During configuration,
`the invention maintains runtime
`information that is stored in tables and vectors. To achieve
`greater processing efliciency,
`the systems represents ele-
`ments in a configuration (e.g., product, part, and group) as
`a bit in a bit vector. Thus, for example, a vector has a length
`that is equal to the total number of elements. An element’s
`bit can be set or reset to specify the state of the element in
`the current configuration. For example, a user vector can be
`used that specifies for each element whether the element has
`been selected by the user during the configuration.
`In
`addition, excluded and removed vectors identify whether an
`element is excluded or removed (respectively) from a con-
`figuration. Vectors can be used to identify whether an
`element 1) has been selected (by the user or the configura— '
`tion system), 2) is selectable, and 3) notSelectable.
`Tables contain element relationships. A table is used to
`represent
`the includes, excludes, removes, and requires
`choice relationships, for example. Each table has a left-hand
`side and a right-hand side that corresponds to the left-hand
`and right-hand sides of a relationship.
`In each case, the
`left—hand side is a bit vector that contains bits that corre—
`spond to elements. The includes, excludes and removes
`tables contain a bit vector in the right—hand side that repre—
`sents configuration elements. The right-hand side of the
`requires choice table is a pointer that points to an entry in a
`group table. The group table entry is a bit vector that
`identifies the elements that are contained in the group from
`which a choice is to be made. The right-hand side of a
`requires choice table entry further includes minimum and
`maximum designations. Minimum and maximum values
`identify the minimum and maximum number of group
`members that are to be selected to satisfy a requires group
`relationship.
`A bit vector implementation of relationships and internal
`runtime state allows for fast and efficient computation of
`relationship based configuration. A comparison of bits can
`be performed in one machine instruction in most cases.
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`30
`
`40
`
`FIG. 1 provides an illustration of a computer system that
`can be used with the invention according to an embodiment
`of the invention.
`
`FIG. 2 provides an overview of the maintenance and
`configuration systems according to an embodiment of the
`invention.
`
`FIG. 3 illustrates examples of elements in a parts catalog
`according to an embodiment of the invention.
`FIG. 4 illustrates relationships between parts according to
`an embodiment of the invention.
`
`60
`
`FIG. 5 provides an example of product classifications
`according to an embodiment of the invention.
`FIG. 6 provides an example of a GUI screen used in
`maintenance system 202 according to an embodiment of the
`present invention.
`
`31
`31
`
`

`

`5,825,651
`
`5
`(CRT) raster monitor 117. Video amplifier 116 is well known
`in the art and may be implemented by any suitable means.
`This circuitry converts pixel DATA stored in video memory
`114 to a raster signal suitable for use by monitor 117.
`Monitor 117 is a type of monitor suitable for displaying
`graphic images.
`The computer system described above is for purposes of
`example only. The present invention may be implemented in
`any type of computer system or programming or processing
`environment.
`
`The invention maintains and configure-s systems. The
`invention eliminates the need for a user to learn a configu—
`ration language or write code to maintain and/0r configure a
`system. Auser interface uses various operations such as drag
`and drop and item selection to define a product, for example.
`Elements that comprise a definition (e.g., of a product) can
`be added or removed in any order. No order is imposed on
`the user. There is no requirement, for example, that the user
`remove parts of a product in the order in which they were
`added. No fixed flow or order is required to edit a given
`product.
`A definition includes an identification of the components
`that comprise the definition and the interrelationships
`between the components. The interrelationships are concep-
`tually easy for the user to understand. The same relation—
`ships are used to define and configure any system. An
`external representation that
`includes these relationships
`allows a user to view and maintain the definition. The
`external representation is translated into an internal repre-
`sentation that is designed to decrease processing time and
`increase response time.
`In addition, during a configuration session, the invention
`is capable of allowing a user to select or unselect configu—
`ration items without imposing a [low on the user. There is no
`order imposed on the user in terms of the sequence in which
`items are selected for the configuration or unselected from
`the configuration. For example, it is not necessary to select
`a product before choosing options. The invention can iden-
`tify the products that are still available based on the options
`that have already been selected. Further, a user can unselect
`an item (e. g., delete the item from the configuration) without
`regard to the order in which it was selected (e.g., added to
`the configuration).
`Examples of systems that can be maintained or configured
`using the invention include automobiles, computers, time
`clock machines, and shoes. Terms such as part, product line,
`parts catalog, and product are used herein for illustration
`purposes. It should be apparent that this invention can be
`used to configure systems that are not limited to products
`and product lines, etc.
`FIG. 2 provides an overview of the maintenance and
`configuration systems according to an embodiment of the
`invention. Maintenance system 202 maintains a parts cata-
`log 204, parts relationships 206 and product definitions 208.
`Maintenance system 202 uses a user interface that includes
`the ability to add items to parts catalog 204 and specify part
`relationships 206 and product definitions 208. The user
`interface displays a set of hierarchies that provide a con—
`ceptually easier way of viewing a definition. The invention
`maps the set of hierarchies (an external representation) to an
`internal representation.
`The internal representation is used by configuration sys—
`tem 212 to maintain and configure systems based on user
`input. Configuration system 212 provides the ability to
`specify a product. Configuration system 212 verifies the
`product specification. Using configuration system 212, a
`
`5
`
`10
`
`15
`
`30
`
`40
`
`60
`
`6
`user can interactively select and configure a product among
`a set of related products based on availability and compat-
`ibility of features and options. It does not impose an order
`in the selection of products, features or options. The con-
`figuration system 212 allows the riser to only make valid
`selections. However, selections can be made in any order.
`Parts catalog 204 consists of parts that are components of
`products. Similar parts are grouped together to form a part
`hierarchy. Easy maintenance of relationships is achieved by
`the hierarchy. For example, when a group of parts is
`assigned a behavior, all the members inherit that behavior
`automatically. FIG. 3 illustrates examples of elements in a
`parts catalog according to an embodiment of the invention.
`Referring to FIG. 3, a parts catalog (e.g., parts catalog 204)
`contains parts 3027310, 316, and 318. A parts catalog can
`also contain a group of parts such as group 312. Group 312
`contains parts 306—310. A group can contain other groups.
`For example, group 314 contains group 312 and parts
`316—318. Behavior assigned to elements of group 314 is
`inherited by members of goup 312.
`Part-to-part relationships can be created between parts
`within a product. Relationships are defined between a first
`set of parts and a second set of parts. During configuration,
`when all of the members of the first set of parts are selected,
`the relationship between the two sets is enforced on the parts
`in the second set. 1n the preferred embodiment, there are four
`kinds of relationships between parts:
`requires choice,
`includes, can’t work with (or excluded), and removes. FIG.
`4 illustrates relationships between parts according to an
`embodiment of the invention.
`
`Part 402 includes part 404. The includes relation causes a
`set of parts in a second set (e.g., part 404) to be included in
`the configuration when a first set of parts (e.g., part 402) is
`selected. For example, a luxury package includes a CD
`player; when the luxury package is selected, a CD player is
`included in the configuration. The can’t work with (or
`excluded) relation ensures that a set of parts from a second
`set are never in the same configuration as parts in the first
`set. For example, part 402 (e.g., sun roof) can’t work with
`part 406 (e.g., a roof—top antenna). When part 402 is
`selected, part 406 cannot be selected. Part 406 is excluded
`such that it cannot be selected.
`
`When part 402 is selected, part 414 is removed from the
`configuration. The removes relation causes items that are
`included in a second set of to be removed from the con-
`figuration when the left side is selected. For example, when
`a high end stereo is selected the standard stereo is removed
`from the configuration.
`The requires choice relation recognizes that a choice
`(between a minimum and maximum number) has to be made
`between a second set of parts (or members of a group) to
`ensure a valid configuration when the parts in a first set are
`selected. Part 406 (e.g., climate control feature) requires that
`a choice be made among parts 408410 (e.g., 1 zone A/C or
`2 zone A/C). A requires choice relationship requires that a
`number of items be selected based on minimum and maxi-
`mum values from the right-hand side of the relationship to
`satisfy the relationship.
`Parts 408 and 410 can be combined to form group 416.
`Group 416 can be defined by the user. If the user does not
`define group 416, the invention preferably creates group 416
`to contain parts 408 and 410. Thus, when two or more parts
`are defined on the right—hand side of a requires choice
`relationship, the invention preferably creates a group that
`contains these parts. The requires choice then becomes a
`requires choice on the group (e.g., group 416).
`
`32
`32
`
`

`

`5,825,651
`
`7
`Parts are used to illustrate relationships in FIG. 4.
`However, a relationship can contain groups. To illustrate, a
`group of parts can be substituted wherever a part is used in
`the illustration. Thus, for example, parts 402, 404, 406, 408,
`410, and 414 can each be replaced by a group ofparts. Thus,
`for example, if parts 402 and 404 are replaced by groups
`(e.g., groups 402 and 404, respectively), when the members
`of group 402 are selected, the members in group 406 are
`included in the configuration. To further illustrate, part 408
`can be replaced by group 408. In that instance, group 408 is
`a member of group 416. A hierarchy of groups (e.g., group
`408 contained within group 416) can be used in a relation-
`ship.
`Parts can be combined to form an arbitrary grouping.
`Thus, it is not necessary to combine parts in a group based
`on a logical or intuitive relationship between the parts in the
`group. For example, a group can contain an engine, a color,
`and a sun roof.
`
`The relations that are created between parts within a
`product are enforced only on that particular product.
`However,
`if some part-to-part relationships are to be
`enforced on all products within a product
`line, then the
`relations are created once and are enforced for all products.
`These relationships are referred to as global relationships.
`Aproduct includes zero or more elements of parts catalog
`204. Product definition 208 (see FIG. 2) is generate by
`populating it with its component parts.