`[19]
`[11] Patent Number:
`5,825,651
`
`Gupta et al.
`[45] Date of Patent:
`Oct. 20, 1998
`
`U8005825651A
`
`[54] METHOD AND APPARATUS FOR
`MAINTAINING AND CONFIGURING
`SYSTEMS
`
`5,355,317 10/1994 Talbott et a1.
`5,357,440 10/1994 Talbott et a1.
`5,586,052 12/1996 lannuzzi et a1.
`5,659,478
`8/1997 Pennisi et a1.
`
`.......................... 364/468
`......
`. 364/467
`
`..... 364/512
`..................... 364/468.01
`
`[75]
`
`Inventors: Neeraj Gupta; Venky Veeraraghavan;
`Ajay Agarwal, all of Austin, Tex.
`
`.
`.
`.
`.
`Primary Examiner—Kevm A. Kriess
`Attorney, Agent, or Firm—Hecker & Harriman
`
`[73] Assignee: Trilogy Development Group, Inc.,
`Austin, TeX.
`
`[57]
`
`ABSTRACT
`
`[
`
`] Appl. No.: 707,187
`.
`.
`Sep. 3’ 1996
`Flled‘
`]
`[
`Int. Cl.6 ........................................................ G06F 1/00
`[51]
`
`[
`] US. Cl.
`. 364/468.09‘ 364/488
`[
`]
`Field of Search
`364/468 06 468 02
`364’46803 468 1 488’395/651’
`'
`’
`’
`]
`'
`’
`References Cited
`
`[56]
`
`U.S. PATENT DOCUMENTS
`1/1989 Atherton .
`........................ 364/192
`5/1991 Addesso et a1.
`5/1991 Brown et a1.
`........................... 364/468
`
`4,796,194
`5,019,961
`5,019,992
`
`602
`
`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 T0
`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 a system. Aconfiguration system validates a configuration
`using the system definition, the current state of the configu-
`“no“ and user mpm‘
`
`85 Claims, 24 Drawing Sheets
`
`
`
`
`608 /
`
`650
`
`
`
`
`requires choice
`includes
`
`Requires
`Choice
`
`652
`
`/
`
`
`excludes
`
`removes \
`
`1
`
`CONFIGIT 1012
`
`CONFIGIT 1012
`
`1
`
`
`
`US. Patent
`
`Oct. 20, 1998
`
`Sheet 1 0f 24
`
`5,825,651
`
`.119 VIDEO“11116114.:
`
`13
`
`- VIDEOMEMORY
`
`MAINMEMORY
`
`110
`
`KEYBOARD
`
`-
`
`MOUSE
`
`111
`
`MASS STORAGE
`
`FIG. 1
`
`2
`
`
`
`US. Patent
`
`Oct. 20, 1998
`
`Sheet 2 0f 24
`
`5,825,651
`
`202
`
`\
`
`Maintenance
`
`1 Configuration
`
`206
`
`212
`/
`
`204
`
`Part
`Relationships
`
`3
`
`214
`
`Product
`Specification/
`
`Verification Catalog
`
`Definition(s)
`
`Parts
`
`.—
`
`Product
`
`FIG. 2
`
`3
`
`
`
`US. Patent
`
`Oct. 20, 1998
`
`Sheet 3 0f 24
`
`5,825,651
`
`302
`
`304
`
`faraaflovoaoatacoa4o:—ol«-——o—rn
`
`
`
`312
`
`
`».4;.an.;..;....aa..a.-.,...aa.a.:p...;....4‘ ..4‘ .c.........,
`
`312
`
`.~‘.‘.‘.~“~.‘-“...‘....s‘..s.\..~‘\-~.~\-q~\.--~‘
`
`306
`
`308 ...-
`
`\‘~‘-~x~\~‘.--~s~xs~s-s-‘-~.-\......‘.....
`
`310
`
`..-.....“.... ... ... ........‘.,..........,..............,
`
`314
`
`316
`
`x~“.V‘.~»~“~.“.u-‘-‘.....\“~.v.‘~»‘\‘-~\..‘~u.-‘-
`
`318
`
`
`
`.-....¢.,...—...-..).aa.....n-......‘.a.......,.....aoua...-
`
`40—ptraaagacovava o..¢o¢.o-o.llvI,aa;I1ucr:vIaI
`rlIrIrI;Irvv:l
`«..‘...‘~‘.-.-‘.“.~
`
`FIG. 3
`
`4
`
`
`
`US. Patent
`
`Oct. 20, 1998
`
`Sheet 4 0f 24
`
`5,825,651
`
`402
`
`414
`
`
`
`removes —-—> ‘
`
`Includes
`
`Excludes
`
`404
`
`A/
`
`\ 406
`
`requires
`choice
`
`
`
`.......................................................................................
`
`5
`
`
`
`US. Patent
`
`Oct. 20, 1998
`
`Sheet 5 0f 24
`
`5,825,651
`
`514
`
`502
`
`——Optional—< I
`[—
`Inchildes
`/ \ \
`
`516
`
`requires
`choice
`
`504
`
`FIG. 5
`
`6
`
`
`
`US. Patent
`
`Oct. 20, 1998
`
`Sheet 6 0f 24
`
`5,825,651
`
`5\
`
`wow
`
`coo
`
`Uvow
`
`mmc
`
`moo
`
`33$
`
`autismEEEQE
`
`
`
`82:5
`
`“vmo
`
`mmo\
`
`owe
`
`30
`
`NS
`
`/mmDDEmL
`
`/
`
`
`
`8.8:”.3.11::
`
`33:3:
`
`mmufiuxu
`
`
`
`0.UE
`
`Soone
`
`7
`
`
`
`
`US. Patent
`
`Oct. 20, 1998
`
`Sheet 7 0f 24
`
`5,825,651
`
`won
`
`«on
`
`Non.
`
`REES
`
`cofificmmoummm
`
`HEEEOU
`
`£5consmcfib
`
`3::me
`
`confinemmawm
`
`mmusmfi
`
`8
`
`
`
`
`
`
`US. Patent
`
`Oct. 20, 1998
`
`Sheet 8 0f 24
`
`5,825,651
`
`_/ 802
`
`/ 804
`
`/- 806
`
`808
`
`810
`
`/
`
`/
`
`/ 812
`
`W P
`
`N bits
`
`bits
`
`Included Vector
`
`Excluded Vector
`
`P+N Bits
`
`Required Groups Vector
`
`FIG. 8A
`
`9
`
`
`
`US. Patent
`
`Oct. 20, 1998
`
`Sheet 9 0f 24
`
`5,825,651
`
`Runtime
`Table
`
`822
`
`-/
`
`Right-Hand Side
`
`Side
`
`826
`
`Left-Hand
`
`’
`i
`
`324
`
`Excludes, or /
`Includes,
`Removes Tables
`832
`
`828
`
`836
`
`830
`
`834
`
`Choice /
`Requires
`Tables
`838
`
`0 1 0 1 0
`
`O
`
`imin,max Pointer
`
`Left-Hand
`Side
`
`Right-Hand
`Side
`
`Left-Hand? Right-Hand
`Side
`
`Side
`
`FIG. 8B
`
`10
`
`10
`
`
`
`US. Patent
`
`Oct. 20, 1998
`
`Sheet 10 0f 24
`
`5,825,651
`
`
`
`user selects item n
`
`902
`
`906
`
`
`
`
`
`04
`9.
`
`No
`
`raise error
`
`Yes
`
`908
`
`set nth bit 111 uVec
`
`
`
`update state
`
`
`
`
`
`
`evaluate
`
`
`
`
`app.1y to interface and
`g1ver user control
`
`
`relatonshtps
`
`916
`
`FIG. 9
`
`11
`
`11
`
`
`
`US. Patent
`
`Oct. 20, 1998
`
`Sheet 11 M24
`
`5,825,651
`
`0
`
`Illllligiiiifilfillllll
`
`1004
`
`iVecCopy = iVec
`xVecCopy = xVec
`
`1006
`
`rVecCopy = rVec
`
`
`
`rTable backward (uVec)
`
`iTable forward (iVec)
`xTable forward (xVec)
`rTable forward (rVec)
`
`1008
`
`iTable backward (xVec)
`xTable backward (selectedVec)
`
`1010
`
`1012
`
`rctable backward
`
`rctable forward
`
`update state
`
`1014
`
`
`
`change in a
`vector?
`
`
`Ye54p©
`
`FIG . 1 0
`
`N0 1016
`
`end
`
`12
`
`12
`
`
`
`US. Patent
`
`Oct. 20, 1998
`
`Sheet 12 0f 24
`
`5,825,651
`
`
`
`
`
`1102
`
`1104
`
`No
`
`raise error
`
`1106
`
`1108
`
`1110
`
`1112
`
`
`
`“lemon m
`uVec?
`
`
`
`
`Yes
`
`remove selection
`from uVec
`
`update state
`
`evaluate
`
`relationships
`
`1114
`
`apply to interface and
`give user control
`
`1116
`
`FIG. 11
`
`13
`
`13
`
`
`
`US. 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
`
`1202
`
`1204
`
`1206
`
`1208
`
`1210
`
`1212
`
`1214
`
`evaluate rel.
`
`factorization
`
`perform
`relationship
`compression
`
`FIG. 12
`
`14
`
`14
`
`
`
`US. Patent
`
`Oct. 20, 1998
`
`Sheet 14 0f 24
`
`5,825,651
`
`00
`
`Hc
`
`H
`
`o ‘illlllll
`
`<
`
`(‘3
`x—l
`
`U
`1—4
`
`|||||
`
`OH
`03
`H
`
`<fl
`8
`H
`
`rd
`5
`1—1
`
`1\
`D
`
`1310
`
`1308
`
`15
`
`u:
`COH
`
`c:
`N /
`
`c:
`52
`
`1
`
`\ <
`
`r
`c>
`CO
`H
`
`15
`
`
`
`nu
`
`S.
`
`tnuetna
`
`no
`
`am2
`
`00w”1
`
`”m
`
`.42f0
`
`5,825,651
`
`Dd.NomH
`
`.wfimfi
`
`
`
`m.oomfi.«omH
`
`
`
`mm\\\\\.onH.«Hmfi.NHmH.onH
`
`
`
`
`
`.82
`
`16
`
`m2.UE
`
`16
`
`
`
`US. Patent
`
`Oct. 20, 1998
`
`Sheet 16 0f 24
`
`5,825,651
`
`1402
`
`all include rels.
`
`processed?
`
`Yes
`
`end
`
`N o
`
`1408
`
`get next rel. (r)
`
`1410
`
`1412
`
`temp = r.]hs | r.rhs
`
`tempsave = temp
`
`1406
`
`
`
`
`
`temp = tempsave?
`
`all rels.
`
`compared?
`
` No‘.@
`
`Yes
`
`1404
`
`
`
`
`
`r.rhs = temp &~ r.th
`
`Fig. 14A
`
`17
`
`17
`
`
`
`US. Patent
`
`Oct. 20, 1998
`
`Sheet 17 0f 24
`
`5,825,651
`
`
`
`get another rel. (r2)
`
`
`
`
`
`temp = temp | r2.rhs
`
`FIG. 14B
`
`18
`
`18
`
`
`
`US. Patent
`
`Oct. 20, 1998
`
`Sheet 18 0f 24
`
`5,825,651
`
` 1504
`
`all rels.
`
`end
`
`Yes
`
`
`processed?
`
`
`0
`N
`1506
`
`
`
`
`
`
`get next rel. (r)
`
`1507
`
`Yes
`
`1508
` all rels.
`
`
`
`N 0
`
`Yes
`
`
`compared?
`
`
`
`
`
`
`No
`
`1510
`
`get other rel. (r2)
`
`@No
`
`1512
`
`Yes’0
`
`FIG. 15A
`
`19
`
`19
`
`
`
`US. Patent
`
`Oct. 20, 1998
`
`Sheet 19 0f 24
`
`5,825,651
`
`
`
`r2.grp subset of
`r.grp?
`
`1514
`
`
`
`1516
`
`
`
`create exclude rel.
`(r.1hs I r2.1hs _r>r2.grp &~ r.grp
`
`
`
`FIG. 15B
`
`20
`
`20
`
`
`
`US. Patent
`
`Oct. 20, 1998
`
`Sheet 20 0f 24
`
`5,825,651
`
`1 602
`
`mark each rel.
`as "new"
`
`1609
`
`added = "false"
`
`all includes rels.
`
`processed?
`
`0
`
`N
`
`1612
`
`get next includes
`rel. (i)
`
`_
`
`
`
`1613
`
`reset relationships
`
`1610
`
`end
`
`
`reset includes rels.
`
`
`
`
`
`
`
`
`
`Gm)
`
`Yes—>®
`
`all "new" rels.
`
`1614
`
`processed?
`
`FIG. 16A
`
`21
`
`21
`
`
`
`US. Patent
`
`Oct. 20, 1998
`
`Sheet 21 0f 24
`
`5,825,651
`
`1616
`
`get next rel. (1'),
`mark as "old"
`
`1620
`
`!(r.lhs &:& i.rhs)?
`
`Yes
`
`
`1622
`
`new.th = (r.1hs and not i.rhs) or i.lhs
`
`No
`
`new.th has
`
`1624
`
`value?
`
`
`
`Yes
`
`FIG. 16B
`
`22
`
`22
`
`
`
`US. Patent
`
`Oct. 20, 1998
`
`Sheet 22 0f 24
`
`5,825,651
`
`add new rel.
`
`(new.lhs 37> r.rhs
`
`mark new rel.
`
`as "new"
`
` 1626
`
`
`
`
`1628
`
`1630 >
`
`
`
`FIG. 16C
`
`23
`
`23
`
`
`
`US. Patent
`
`Oct. 20, 1998
`
`Sheet 23 0f 24
`
`5,825,651
`
`1702
`
`table processed?
`
`m6)
`
`No
`
`1704
`
` all relationships in
`
`
`
`get next relationship as
`current relationship (r)
`
`
`
` r processed against a
`
`other rels. in table?
`
`
`
`r.lhs Subset of
`r2.lhs?
`
`
`
`- FIG. 17A
`
`24
`
`24
`
`
`
`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-
`
`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 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
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`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.
`A part 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.
`
`26
`
`26
`
`
`
`5,825,651
`
`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 understandable 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
`
`the systems represents ele-
`greater processing efliciency,
`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
`
`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.
`
`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
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`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. 13A—13B 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. 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
`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.
`lt 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. A keyboard
`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 lines.
`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
`
`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 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 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. 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 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 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
`
`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 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 group 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. 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
`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.
`
`10
`
`20
`
`25
`
`30
`
`35
`
`40
`
`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 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).
`
`28
`
`28
`
`
`
`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 of parts. 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 filrther 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. Product definition
`208 is generated by population of a product with its com-
`ponent parts. The parts within a product are 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 embodiment of the invention.
`
`An included part is a part that is included in a product by
`default. For example, parts 504 and 506 are automatically
`included in product 502. for example, when a configuration
`user chooses the product definition product 502, the parts
`504 and 506 are automatically included in the configuration.
`A required choices classification specifies that a choice
`among a group of parts has to be made to create a valid
`product configuration. For example, product 502 (e.g.,
`automobile) can include a color group 518 containing red
`(part 508), green (part 510) and blue (part 512) that is a
`required choice. In configuring a product, the user must
`choose a color in this group to create a valid product
`configuration. Parts 514 and 516 are optional parts. An
`optional part is not required for a valid configuration.
`Aproduct line is defined as a set of related products. The
`invention provides the framework for defining a product
`line. To define a product line: all parts (components) in the
`product line are entered into parts catalog 204. An instance
`in products definition 208 is created that identifies parts from
`parts catalog 204 that are assigned to a product. Part
`relationships 206 can also be defined for the product.
`Maintenance System
`Parts catalog 204, part relationships 206, and product
`definition 208 are created and maintained using maintenance
`system 202. Whi