USO00S825651A
`5,825,651
`(11) Patent Number:
`United States Patent
`Gupta etal.
`[45] Date of Patent:
`Oct. 20, 1998
`
`
`115
`
`[54] METHOD AND APPARATUS FOR
`MAINTAINING AND CONFIGURING
`SYSTEMS
`
`[75]
`
`Inventors: Neeraj Gupta; Venky Veeraraghavan;
`Ajay Agarwal, all of Austin, Tex.
`
`[73] Assignee: Trilogy Development Group,Inc.,
`Austin, Tex.
`
`sooowmNwPFNbNSec|&
`
`NeBe
`
`oO
`
`[56]
`
`Appl. No.: 707,187
`.
`Sep. 3, 1996
`Filed:
`Int, CLS cosssossnnsnnuntnnnaninnnene GO6F 1/00
`US. Cl.
`...
`. 364/468.09; 364/488
`Field of Search 364/468.09, 468.02
`364/468.03, 468.1 488: 395/651
`,
`,
`,
`References Cited
`
`4,796,194
`5,019,961
`5,019,992
`
`U.S. PATENT DOCUMENTS
`1/1989 Atherton .
`5/1991 Addesso et al. wcccuceesceeees 364/192
`5/1991 Browmet al. oe eeeeeeeees 364/468
`
`602
`
`5,355,317 10/1994 Talbott et al. cece 364/468
`5,357,440 10/1994 Talbott et al.
`......
`. 364/467
`
`eeeeeee 364/512
`5,586,052 12/1996 Jannuzzi et al. oe
`8/1997 Pennisi et al. wee 364/468.01
`5,659,478
`
`;
`;
`.
`.
`Primary Examiner—Kevin A.Kriess
`Attorney, Agent, or Firm—Hecker & Harriman
`[57]
`ABSTRACT
`The invention provides the ability to interactively select and
`configure a product amonga setof related products based on
`availability and compatibility of features and options.It does
`not impose ao order in the selection of products, features or
`options; only valid selections can be made at any time. To
`create an electronic representation of the product informa-
`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 asystem. A configuration system validates a configuration
`using the system definition, the current state of the configu-
`ration and user input.
`
`85 Claims, 24 Drawing Sheets
`
`622
`
`604
`
`606
`
`650
`
`608 f
`
`
`
`al
`
`
`
`Included Requires
`
`Choice
` 624
`
`652
`
`f
`
`
` requires choice
`includes
`NN,
`—/
`excludes
`removes
`
`1
`
`CONFIGIT 1012
`
`CONFIGIT 1012
`
`1
`
`

`

`U.S. Patent
`
`Oct. 20, 1998
`
`Sheet 1 of 24
`
`5,825,651
`
`116
`
`119
`
`~
`
`113
`
`114
`
`WwW
`
`115
`
`
`
`CPU VIDEO MEMORY||MAIN MEMORY
`
`118
`
`_
`
`110
`
`-
`
`KEYBOARD
`.
`
`MOUSE
`
`11
`
`|
`
`MASS STORAGE
`
`FIG. 1
`
`2
`
`

`

`U.S. Patent
`
`Oct. 20, 1998
`
`Sheet 2 of 24
`
`5,825,651
`
`202
`
`\
`
`Maintenance
`
`, Configuration
`
`212
`a
`
`214
`
`206
`
`Part
`Relationships
`
`:
`
`204
`
`Parts
`
`Verification Catalog|mmm
`
`Definition(s)
`
`Product
`Specification/
`
`Product
`
`FIG. 2
`
`3
`
`

`

`U.S. Patent
`
`Oct. 20, 1998
`
`Sheet 3 of 24
`
`5,825,651
`
`312
`
`302
`
`304
`
`
`aaa AOE RAD AAR DAE BORDER ADE AAD DAI DIP BASSO DRAEREREAP DEP D AAD TE EO,
`
`
`
`
`
`RRRRREREREARARSENEERRAREEEREEEERSEEN
`
`306
`
`310
`
`308 ry
`
`ERNERRSNRREEeeeEEE
`
`nd ae a Dad ADD DAME RO EEE ERA PPD DIEDRARDDS DDI APDAAOAR DBD MEROED
`
`314
`
`
`
`RRROURTTERTURRUEUUUSEERURESPERTTESTEETAT
`
`Peete scewarereresenewsawssesen
`
`312
`
`318
`
`
`
`316
`
`
`
`cer vecsesosercresfbvvevovasare,‘’?’.’.,.?’>’.,’’
`’‘’’,,’s,’.’‘’
`ARRAes
`
`aa Oa OAR ee PAPO PPE EED BEDE AE ADODIRAAREAPEBDEOLOIOHOEE
`
`FG. 3
`
`4
`
`

`

`U.S. Patent
`
`Oct. 20, 1998
`
`Sheet 4 of 24
`
`5,825,651
`
`402
`
`
`
`414
`
`removes——}>oS
`
`Includes
`
`Excludes
`
`404 x
`
`Ny
`
`406
`
`requires
`choice
`
`
`
`teen cae tamer ec and ewe wnenans cn csnssanamesesosnewacassesamanrarsasecceseuawsasase sea eenn
`
`5
`
`

`

`U.S. Patent
`
`Oct. 20, 1998
`
`Sheet 5 of 24
`
`5,825,651
`
`514
`
`502
`
`-—
`Includes
`
`—Optional——c
`
`516
`
`requires
`
`choice
`
`FIG. 5
`
`6
`
`

`

`U.S. Patent
`
`Oct. 20, 1998
`
`Sheet 6 of 24
`
`5,825,651
`
`zS9J
`
`929
`
`v9
`
`clo\saaouads
`
`sapnjoxa
`
`
`
`9“DI
`
`
`
`aa10yosaainbas
`
`sapnyout
`
`0190¢€9
`
`809
`
`909
`
`709
`
`cCO
`
`709
`
`joUDHAC
`
`
`
`saainbayPapRyau]
`
`
`
`a0104)
`
`veo
`
`7
`
`
`

`

`U.S. Patent
`
`Oct. 20, 1998
`
`Sheet 7 of 24
`
`5,825,651
`
`904
`
`OL
`
`COL
`
`uoleyUasaiday
`
`yeurazuy
`
`
`
`(tu:UOT}e]SURI])
`
`yajiduio7
`
`uoteyuasaiday
`
`jeura}xy
`
`Zansty
`
`8
`
`
`
`
`

`

`U.S. Patent
`
`Oct. 20, 1998
`
`Sheet 8 of 24
`
`5,825,651
`
`S 802
`
`8047
`S 806
`S 808
`
`S 810
`
`812
`
`P bits
`
`N bits
`
`Fo
`
`P+N Bits
`
`Required Groups Vector
`
`FIG. 8A
`
`9
`
`

`

`U.S. Patent
`
`Oct. 20, 1998
`
`Sheet 9 of 24
`
`5,825,651
`
`Runtime
`Table
`
`822
`
`S
`
`Left-Hand
`
`Side
`
`826
`
`824
`
`Includes,
`Excludes, or
`Removes Tables
`
`JS 828
`932
`836
`
`830
`
`Requires
`Choice
`Tables
`
`834
`
`838
`
`01010... 0
`
`| 10001...
`
`1
`
`01010... 0
`
`i
`
`imin,max Pointer
`
`Right-Hand Side
`Side
`
`Left-Hand|Right-Hand Left-Hand _
`
`
`Side
`Side
`
`FIG. 8B
`
`10
`
`10
`
`

`

`U.S. Patent
`
`Oct. 20, 1998
`
`Sheet 10 of 24
`
`5,825,651
`
`raise error
`
`906
`
`
`
`set nth bit in uVec
`
`update state
`
`evaluate
`relationships
`
`902
`
`
`
`
`
`
`
`
`apply to interface and
`giver user control
`
`FIG. 9
`
`11
`
`11
`
`

`

`U.S. Patent
`
`Oct. 20, 1998
`
`Sheet 11 of 24
`
`5,825,651
`
`@
`
`os
`
`1004
`
`iVecCopy = iVec
`xVecCopy = xVec
`
`rVecCopy = rVec 1006
`
`
`
`
`
`iTable forward (iVec)
`xTable forward (xVec)
`rTable forward (rVec)
`
`1008
`
`iTable backward (xVec)
`
`xTable backward (selectedVec) rTable backward (uVec)
`
`1010
`
`1012
`
`rctable backward
`rctable forward
`
`update state
`
`
`
`change in a
`vector?
`
`
`12
`
`12
`
`

`

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

`

`U.S. Patent
`
`Oct. 20, 1998
`
`Sheet 13 of 24
`
`5,825,651
`
`create rels. based on
`hierarchy
`
`perform back
`linking
`
`evaluate include
`chains
`
`evaluate subgroup
`excludes
`
`compression
`
`evaluate rel.
`factorization
`
`perform
`relationship
`
`FIG. 12
`
`14
`
`14
`
`

`

`U.S. Patent
`
`Oct. 20, 1998
`
`Sheet 14 of 24
`
`5,825,651
`
`1302
`
`1304Lo\1306
`
`13161318
`
`LSS1310
`
`
`
`13121314
`
`1308
`
`
`
`FIG.13A
`
`15
`
`

`

`U.S. Patent
`
`Oct. 20, 1998
`
`Sheet 15 of 24
`
`5,825,651
`
`COET
`
`IDET
`
`POET
`
`iSTET
`
`ITEL
`
`IEL.CLeL
`
`OTET
`
`80ET
`
`16
`
`
`
`del‘Old
`
`16
`
`

`

`U.S. Patent
`
`Oct. 20, 1998
`
`Sheet 16 of 24
`
`5,825,651
`
` 1402
`
`all includerels.
`processed?
`
`1408
`
`1406
`
` all rels.
`temp = tempsave?
`
`1404
`
`r.rhs = temp &~ r.lhs
`
`compared?
`
`Yes
`
`
`
`
`
`Fig. 144
`
`17
`
`17
`
`

`

`U.S. Patent
`
`Oct. 20, 1998
`
`Sheet 17 of 24
`
`5,825,651
`
`get anotherrel. (r2)
`
`
`
`
`
`temp = temp | r2.rhs
`
`FIG. 14B
`
`18
`
`18
`
`

`

`U.S. Patent
`
`Oct. 20, 1998
`
`Sheet 18 of 24
`
`5,825,651
`
`end
`
`Yes
`
`all rels.
`
`0
`
`
`processed?
`
`
`N
`1506
`
` 1504
`
`get nextrel. (r)
`
`compared?
`get other rel. (r2)
`
`
`
`
`all rels.
`
`
`
`Yes
`
`No
`
`1510
`
`(2«No
`
`FIG. 15A
`
`19
`
`19
`
`

`

`U.S. Patent
`
`Oct. 20, 1998
`
`Sheet 19 of 24
`
`5,825,651
`
`1514
`
`r2.grp subset of
`r.grp?
`
`
`
`
`
`create excluderel.
`(rhs | r2.lhs 41r2.grp &~ r.grp
`
`FIG. 15B
`
`20
`
`20
`
`

`

`U.S. Patent
`
`Oct. 20, 1998
`
`Sheet 20 of 24
`
`5,825,651
`
`mark each rel.
`as “new"
`
`1609
`
`added = "false"
`
`1608
`
`all includesrels.
`
`added = “true"?
`processed?
`
`No
`
`end
`
`1610
`
`No
`
`1612
`
`get next includes
`rel. (i)
`
`
`
`1613
`
`reset relationships
`
`1602
`
` reset includes rels.
`
`
`
`
`
`
`
`
`
`(2No
`
`all “new”rels.
`processed?
`
`1614
`
`Yes—>(2)
`
`FIG. 16A
`
`21
`
`21
`
`

`

`U.S. Patent
`
`Oct. 20, 1998
`
`Sheet 21 of 24
`
`5,825,651
`
`1616
`
`get next rel. (r),
`mark as “old”
`
`1620
`
`{(r.lhs && i.rhs)?
`
`1622
`
`new.lhs = (r.lhs and not i.rhs) or i.lhs
`
`Yes
`1624
`
`new.lhs has
`value?
`
`
`
`Yes
`
`FIG. 16B
`
`22
`
`22
`
`

`

`U.S. Patent
`
`Oct. 20, 1998
`
`Sheet 22 of 24
`
`5,825,651
`
`add newrel.
`(new.lhs | r.rhs
`
`mark newrel.
`as "new"
`
`1628
`
`1630 -
`
` 1626
`
`
`
`
`
`
`FIG. 16C
`
`23
`
`23
`
`

`

`U.S. Patent
`
`Oct. 20, 1998
`
`Sheet 23 of 24
`
`5,825,651
`
`1702
`
`all relationships in
`
`
`table processed? Yes
`
`
`No
`
`1704
`
`
`
`get next relationship as
`current relationship (r)
`
`
`
` t processed against a
`
`1706
`
`otherrels. in table?
`
`r.lhs subset of
`
`r2.chs = r2.rhs and
`not r.rhs
`
`
`r2.lhs?
`
`
`FIG. 17A
`
`24
`
`24
`
`

`

`U.S. Patent
`
`Oct. 20, 1998
`
`Sheet 24 of 24
`
`5,825,651
`
`1716
`
` all relationships in
`table processed?
`
`1718
`
`Yes
`
`end
`
`
`
`delete r from table
`
`r.rhs = zeroes?
`
`
`
`
`
`FIG. 17B.
`
`25
`
`25
`
`

`

`5,825,651
`
`1
`METHOD AND APPARATUS FOR
`MAINTAINING AND 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 mustbe identified.
`‘lo configure a system, a user mustselect 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, ete. 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 languageto 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 (ie., 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 flowororder-
`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 becomefrustrated 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
`configuralion 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 sct 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
`
`20
`
`25
`
`30
`
`35
`
`45
`
`50
`
`55
`
`60
`
`65
`
`2
`made at any lime. To create an electronic representation of
`the product
`information to achieve the above goal,
`the
`invention provides a framework for defining a productline.
`A productline 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 amonga groupof 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
`whenits inclusion would result in an invalid configuration.
`A part may be removed when another part is added. Thus,
`whena 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 productline, 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
`productclassifications and the part relationships. A graphical
`user interface (GUI) is usedto allow theuserto interactively
`generate a definition. Instead of configuration languages,
`GUIoperations 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-
`lationshipsis 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 cnsures that the current configuration
`state is always valid. The user can select and unselect parts
`in any order. Whenuser inputis received, the configuration
`system validates the input based on the currentstate of the
`configuration. In addition, the configuration system identi-
`fies selections that could cause a valid configuration to
`becomeinvalid. The configuration removesthese selections
`from the set of possible selections so that the user does not
`make an invalid selection.
`
`The configuration system cvaluatcs the current state of a
`configuration based on the product definition, part relation-
`ships and state information. After receipt of input from a
`uscr, 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.
`
`26
`
`26
`
`

`

`5,825,651
`
`3
`The invention uses both an external and internal repre-
`sentation of a definition or definitions. A translation mecha-
`
`nism is used translate an external representation into an
`internal representation. The external representation uses a
`conceptually understandableset 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
`
`the systems represents ele-
`greater processing efficiency,
`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 correspondsto 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
`membersthat 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
`
`FIG. 1 provides anillustration 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 embodimentof the invention.
`FIG. 4 illustrates relationships between parts according to
`an embodimentof the invention.
`
`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.
`
`10
`
`20
`
`25
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`4
`FIG. 7 provides an block diagram illustrating the conver-
`sion process according to one embodimentof the invention.
`TIGS. 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 embodimentof the invention.
`FIG. 12 provides a flow for translation processing accord-
`ing to an embodiment of the invention.
`FIGS. 13A-13B provide an illustration of groups and
`nested groups according to an embodimentof the invention.
`FIGS. 14A-14B provide an includes chain process flow
`according to an embodiment of the invention.
`TIGS. 15A-15B provides an example of a subgroup
`excludes process flow according to an embodimentof the
`invention.
`
`FIGS. 16A-16C provide an example of a relationship
`factorization process flow according to an embodiment of
`the invention.
`
`FIGS. 17A-17B 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
`systemsis 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 suchasillustrated in FIG. 1. A keyboard
`110 and mouse 111 are coupled to a bidirectional system bus
`118. The keyboard and mouseare 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 memory115 and massstorage 112,
`all coupled to bi-directional system bus 118 along with
`keyboard 110, mouse 111 and CPU 113. The massstorage
`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
`memory114 or main memory 115. The system bus 118 also
`includes, for example, a 32-bit DATA busfor transferring
`DATA between and among the components, such as CPU
`113, main memory 115, video memory 114 and massstorage
`112. Alternatively, multiplex DATA/address lines may be
`used instead of separate DATA and addresslines.
`In the preferred embodimentof 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 maybe utilized. Main memory 115 is comprised of
`dynamic random access memory (DRAM). Vidco 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
`
`27
`
`27
`
`

`

`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 aboveis for purposes of
`example only. The present invention may be implemented in
`any type of computer system or programmingor processing
`environment.
`
`The invention maintains and configures systems. The
`invention eliminates the need for a user to learn a configu-
`ration language or write code to maintain and/or configure a
`system. A user 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 flow 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 productsthat 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 aspart, 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 productlines, 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
`mapsthe 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
`
`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 user to only makevalid
`selections. However, selections can be made in anyorder.
`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 embodimentof the invention.
`Referring to FIG. 3, a parts catalog (e.g., parts catalog 204)
`contains parts 302-310, 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 group 312.
`Part-to-part relationships can be created between parts
`within a product. Relationships are defined betweena first
`set of parts and a second set of parts. During configuration,
`whenall of the members ofthe first set of parts are selected,
`the relationship between the twosets is enforced on the parts
`in the second set. In 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
`embodimentof the invention.
`
`Part 402 includes part 404. The includesrelation causes a
`set of parts in a secondset (e.g., part 404) to be included in
`the configuration whena first set of parts (€.g., part 402) is
`selected. For example, a luxury package includes a CD
`player; when the luxury package is selected, a CD playeris
`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.
`
`10
`
`20
`
`25
`
`30
`
`35
`
`45
`
`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-
`
`50
`
`55
`
`60
`
`65
`
`figuration when theleft side is selected. For example, when
`a high endstereois 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 sccond 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 408-410 (e.g., 1 zone A/C or
`2 zone A/C). A requires choice relationship requires that a
`numberof 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 uscr 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).
`
`28
`
`28
`
`

`

`5,825,651
`
`10
`
`15
`
`20
`
`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 forall products.
`These relationships are referred to as global relationships.
`A product includes zero or more elements of parts catalog
`204. Product definition 208 (scc FIG. 2) is generate by
`populating it with its component parts. Product definition
`208 is generated by population of a product with its com-
`ponent parts. The parts within a productare classified as one
`of three different types: included parts, required choices, or
`optional parts. A part that is not classified as one of these
`types is assumed to be unavailable in that product. FIG. 5
`provides an example of product classifications according to
`an embodimentof the invention.
`
`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 memberof group 416. A hierarchy of groups (e.g., group
`408 contained within group 416) can be usedin 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 logicalor intuitive relationship between the parts in the
`group. For example, a group can contain an engine,a color,
`and a sun roof.
`
`8
`ure a system defined in maintenance system 202. Parts
`catalog 204 uses a database or other type of storage and
`retrieval capability, for example, to store information about
`its parts (e.g., part oumber, description, price, etc.).
`‘The GUI screen of FIG. 6 is divided into a product
`definition section 650 and a part relationship definition
`section 652. Pane 602 displays elements from parts catalog
`204. Panes 604, 606, 608 are used to define a product. Panes
`604, 606, and 608 represent classifications or product rela-
`tionships. Panes 610 and 614 and relationship 612 are used
`to define part relationships.
`Ausercan drag elements from pane 602 to panes 604-608
`to define a product. For cxample, to include Part B in the
`product definition, Part B is dragged from pane 602 to pane
`604. Alternatively, to drag parts B, C, D, and E, group Acan
`be dragged from pane 602 to pane 604. Group A and its
`componentparts (parts B, C, D, and E)are thereby included
`in the product definition. Similarly, a user can specify that a
`configuration user must choose a part from a group, e.g.,
`GroupI, by dragging one or more parts or a group into pane
`606. An optional part or group can be identified by dragging
`an element, e.g., Group L,into pane 608. If an element from
`pane 602 is not movedto oneof panes 604—608 it is assumed
`that the maintainer wants to exclude that element from the
`product that is being defined. The product-level relation-
`ships orclassifications (or types) illustrated in FIG. 5 can be
`defined using panes 604-608.
`Asubsetof the product-level relationships map to a subset
`of the part relationships. For example,
`the include and
`requires choice product-level relationships map to the same
`namedpart relationships (as defined in FIG. 4 and shownin
`relationships 612). Minimumand maximumvaluessetfor a
`requires choice product-level relationship map to the mini-
`mum and maximum values of a requires choice part rela-
`tionship. Elements that