Proc, of the 19¥1 LabE
`Int. Conf. on Tools for AI
`San Jose, CA-Nov. 1991
`
`Knowledge-based Configuration of Computer Systems Using
`Hierarchical Partial Choice
`
`Bryan M. Kramer"
`Department of Computer Science
`University of Toronto
`Toronto, Ontario, M5S 1A4
`kramer@ai.toronto.edu
`
`Abstract
`
`As the complexity of computer systems grows, configu-
`ration expert systems become increasingly imporiant as
`tools to ensure that delivered systems are workable. This
`paper introduces a novel inference scheme called hierar-
`chical partial choice that efficiently generates configura-
`tions from a knowledge base of structured descriptions of
`computer components. This approach combines the acqui-
`silion and maintenance advantages (over rule-based sys-
`tems) of a declarative system with an inference scheme that
`efficiently generates solutions, often with little backtrack-
`ing.
`The inference scheme is presented in the context of
`XKEWB, a shell for building computer configuration
`expert system. The system contains several improvements
`over its predecessor Cossack. For example, the system ts
`designed to allow configurators to configure multiple com-
`puters in a network setting, the end user interface ts partic-
`ularly suited to the task of specifying computer systems.
`
`1.0 Introduction
`
`As computer systems grow in complexity, automated
`configuration systems become increasingly important.
`Questions one might have to ask while configuring a sys-
`tem include: is the accounting software compatible with
`the word processing software, and, doesthe file server have
`enough disk space for the application? Clearly a great deal
`of knowledge is required to correctly configure a system,
`and, given the large variety of hardware and software, the
`potential search space is very large. Although several
`approaches to the problem have been described, the prob-
`lems of knowledge acquisition and maintenanceof config-
`uration knowledge and efficiently generating complex
`configuration do not appear
`to have been adequately
`addressed. This paper describes XKEWB, a shell for build-
`*
`
`: This work was done while the author was with Xerox CanadaInc.
`
`ing computer configuration systems. XKEWB provides an
`effective representation of configuration knowledge and
`efficient generation of correct configurations. XKEWB
`also provides a unique end user interface that is well suited
`to configuration systems.
`The configuration problem solved by XKEWB is a gen-
`eralization of the problem described in [7]. Given a set of
`descriptions of components and constraints on the ways
`instances of these descriptions can be connected, a valid
`configuration is a set of instances of the descriptions and a
`description of their connections that satisfies the pre-
`defined constraints and someset of input constraints. Two
`restrictions on the general problem are described: thefunc-
`tional architecture restriction which states that descrip-
`tions of components are decomposed along functional
`lines, and the key componentrestriction which states that
`there is some key component implementing each function.
`Undertheserestrictions, one describes a computer system
`as a component having a display function, a computing
`function etc. and that the key component for the display
`function is a screen. The advantages of this approach are
`that there is a top down organization on how components
`are selected: to build a workstation configuration one pro-
`vides the display function, the computing function etc. and
`that the key components identify subproblems that can be
`solved somewhat
`independently. These restrictions are
`implicit in the knowledge representation described in this
`paper.
`Interest in configuration systems dates back to the R1/
`XCON project [5]. Configuration systems are typically
`rule-based or hybrid rule and frame-based systems. The
`problems with rules have been well documented (for
`example, [2]). Maintenance and verification of knowledge
`expressed as rules can be very difficult because related
`knowledge is usually spread over several
`rules and
`changesto rules have to be checked for interactions with
`most other rules. On the other hand, rule-based systems
`have the property that heuristic knowledge for finding
`solutions efficiently is encoded in the rules. XKEWB uses
`a frame-based representation to handle the maintenance
`problem, and has an inference engine that generates solu-
`
`0-8186-2300-4/91 $01.00 © 1991 IEEE
`
`368
`
`CONFIGIT 1028
`
`CONFIGIT 1028
`
`1
`
`

`

`tions efficiently enough that procedural guidance is not
`necessary.
`The results described here are the result of a reimple-
`mentation and extension of
`the Cossack configurator
`described in [4]. The reimplementation contains novel
`solutions to several weaknesses in the Cossack inference
`scheme, knowledge representation, and user interface. In
`the course of this reimplementation, several new capabili-
`ties were introduced, particularly the ability to configure
`multiple computers in a network situation.
`The paper is organized as follows: first, a brief review of
`Cossack is presented. Next,
`there is an overview of
`XKEWBfollowed by several sections describing details of
`the system. Finally,
`the concluding section contrasts
`XKEWBwith other configuration systems and summarizes
`the contributions.
`
`2.0 The Cossack System
`
`In Cossack, components are represented as LOOPS
`objects and classes of components as LOOPS classes.
`Interrclationships between components or component
`classes are represented by slots with associated constraints.
`A constraint specifies which objects mightfill the slot by
`either enumerating the possibilities or specifying a class
`whoseinstances mightfill the slot. In addition, a constraint
`might have an associated LISP expression that would eval-
`uate to true or false given a particular candidate value for
`the slot. Thus, a class describing a high end computer
`might havea slot called printer with a constraintspecifying
`that the value must belong to the class Printer and a lisp
`expression that evaluates to rue when the value of the pag-
`esperminute slot of a chosen printer is greater than 10.
`The inference takes as input some constraints specified
`by the user. The state of the inference is represented by a
`set of goals describing components to be selected and the
`set of posted constraints which are constraints that have
`not yet been processed. For each posted constraint, the sys-
`tem first attempts to attach the constraint to an existing
`goat. Thus,if there is already a goal to find a printer and a
`second constraint requiring a printer is encountered, the
`system will try to satisfy both constraints with the same
`goal. If there is no component matching the constraint, a
`new goal is created. When there are no unprocessed con-
`straints, some goal is executed. Executing a goal involves
`selecting a componentthatsatisfies the constraints. When
`the choice is made, new constraints are posted, and the
`cycle continues.
`If no componentsatisfies the constraints attached to a
`goal, a contradiction is implied. Cossack then backtracks
`by undoing the choice at some goal that has posted a con-
`
`straint that is attached to the failed goal. Undoing the
`choice at the posting goal hasthe effect of removing a con-
`straint from the failed goal potentially allowing a choice to
`be made there.
`Cossack makes use of a version of partial choice [6}.
`Whenthere are several components that might satisfy a
`goal, Cossack attempts to find a constraint that these com-
`ponents have in common. If there is such a constraint, the
`constraint is posted and the goal is suspended. When a
`component is selected for that constraint, the system can
`make a choice for the suspended goal using the knowledge
`derived by making a choice for the constraint. This is a
`variant of least commitmentin that a choice is made at ran-
`dom only when necessary.
`
`3.0 XKEWB
`
`Cossack had several weaknesses. The most importantis
`that the backtracking mechanism frequently pruned the
`part of the search space containing the correct solution.
`Second, the partial choice mechanism was rarely invoked
`because ofdifficulty of determining that a constraint was
`common to a set of components. Third, it was difficult to
`express extra conditions on constraints using the associ-
`ated lisp expression, and more importantly, the informa-
`tion contained therein was not available to the inference
`engine. Finally, the representation lacked the ability to
`describe componentsthatpartially used other components
`(such as disk space) and to distinguish components
`belonging to different computers in a multi-computerset-
`ting.
`The XKEWB system was developed in order to address
`these weaknesses. At a high level, the system bears a
`strong resemblance to Cossack. Components are described
`in a frame-based language, and inference consists of a
`loop in which constraints are attached to goals and then a
`goal
`is executed, possibly generating new constraints.
`Whena goal cannot be successfully executed, backtrack-
`ing is necessary. For example, the input constraints might
`specify a computer and a word processing package, hence
`goals to find a computer and to find a word processing
`package would be created. Executing the word processing
`goal mightresult in a choice, Microsoft_Word! which has
`a constraint that the computer have a VGA monitor. This
`constraint would then be attached to the computer goal.
`Executing the computer goal would result in a choice
`which would post constraints requiring disk drives, moni-
`tors, etc.
`XKEWB’srepresentation language is more declarative
`and expressive than that used in Cossack. Componentsare
`
`1. Microsoft Word is a trademark of Microsoft Corporation
`
`369
`
`2
`
`

`

`represented using a frame representation! with multiple
`andstrict inheritance. Frames representing components are
`called classes and are organized in an [S-A (specialization)
`hierarchy. The slots of a frame have several facets, and the
`combination of slot and facets is called a constraint and
`corresponds to a Cossack constraint.
`Below are two partial descriptions which illustrate the
`componentrepresentation
`Workstation (abstract) IS-A Computer
`subcomponents
`display: WorkstationDisplay
`number:[1, 2]
`keyboard: WorkstationKeyboard
`disk: WorkStationDisk
`memory: Memory
`requires
`networkconnection:
`NetworkConnection
`
`Ventura_Publisher? (individual) IS-A
`PublishingPackage
`
`requires
`printer: LaserPrintingResource
`constraint:
`printer.postscript-capability
`= true
`disk: ExtStorResource
`level: 657
`consumes: bytesConsumed
`memory: MemoryResource
`constraint:
`memory.supplied-by =
`workstation
`workstation: WorkStation
`properties
`price: 2000
`Here, the class Workstation has a constraint described
`by the display slots that specifies that a workstation is con-
`nected to one or two instances of the class WorkstationDis-
`play. The following sections describe the major steps of the
`inference algorithm. The discussion will make use of the
`above examples, and the meaning of the various parts of
`component description will be clarified.
`
`4.0 Attaching Constraints
`
`The first step of the inference algorithm is 1o attach
`newly posted constraints to goals either by finding anexist-
`ing goal that is compatible or by creating a new goal. The
`attaching step is important becauseit allows componentsto
`
`1. for example, FRL [8] which introduced the terms frame,slot, and facet
`2. Ventura Publisher is a trademark of Ventura Software Inc., prices and
`storage levels are fictitions
`
`be described independently of other components that
`might require the same resources, and yetresults in config-
`urations where one componentis chosen to satisfy multi-
`ple requirements. For example, the descriptions for several
`software packages might specify that a printer is required,
`and the attaching step will attempt to find one printer to
`satisfy all of the packages. Notice that each request for a
`printer could add additional conditions to a goal. Thus a
`word processing package could request a letter quality
`printer and a legal package would add the condition that
`the printer must be able to handle jegal size paper.
`While it is frequently desirable to satisfy several con-
`straints with a single component, it is often impossible to
`do so. The following paragraphs describe properties of a
`constraint that are used to refine the description of what
`components can satisfy the constraint, and how these
`properties are used in matching constraints and goals.
`First, constraints fall into one of three categories: sub-
`component constraints, requires constraints, and proper-
`ties. Subcomponent constraints describe componentsthat
`are in some sense supplied by the containing component
`and would not be supplied by a second component. For
`example, a Workstation supplies a display therefore choos-
`ing a second workstation would result in a second display.
`Thus the inference engine will attach only one subcompo-
`nentconstraint to a goal. Requires constraints, on the other
`hand, describe components that are needed but might be
`shared. Thirdly, properties are descriptions for which no
`inference is required to find the intended instance. For
`example, no further inference is required to find the price
`of VenturaPublisher. Properties generally describe
`objects such as numbers, booleans,or strings that are not
`components.
`is the constraint
`Another important facet of a slot
`expression. The constraint expression of a constraint C
`constrains the slot values of objects that can satisfy C.
`Thus,the printer constraint in Ventura_Publisher can only
`be satisfied by printers that have the value true for the
`property postscript-capability. The constraint expression
`may involveotherslot values as in the case of the memory
`slot in Ventura_Publisher. Here the value of the supplied-
`by slot of the memory must equal the value of the worksta-
`tion slot of
`the publishing package. This constraint
`expresses the fact that the memory requirement is on the
`computer on which the publishing package is to run; not
`on some other computer in the configuration. Before
`attaching a constraint, the inference engine makes a simple
`analysis of the constraint expression in whichit checks for
`equalities that might contradict slot values already bound
`in the goal.
`A constraint expression is a boolean expression using
`the logical connectives not, and and or, comparison opera-
`
`370
`
`3
`
`

`

`
`
`tors such as > and =, predicates such as instance-of, and
`expressions using an assortment of arithmetic and other
`operators.
`For the display slot, an interval is specified for the num-
`ber facet that specifies that a workstation has from one to
`two displays. This is in effect two constraints. XKEWB
`assumes that
`the values in a multiple-valued slot are
`intended to be different will never attach the corresponding
`constraints to the samegoal.
`The disk constraint is an example of a resource con-
`sumption constraint, The value of the consumes facet iden-
`tifies a slot in the type, ExtStorResource, and the facetlevel
`specifies a value. The meaning of this constraintis that the
`value of the slot bytesConsumedin an instance of ExtStor-
`Resource is equal to the sum ofthe levels consumed byall
`resource constraints that have that instance as a value. The
`followingis a possible definition of the resource:
`
`ExtStorResource (abstract) IS-A Resource
`levels
`bytesConsumed: Number
`
`ExtStorResource1 (individual) IS-A
`ExtStorResource
`
`requires
`diskDrive: DiskDrive
`constraint: diskDrive.capacity >
`bytesConsumed
`
`ExtStorResource2 (individual) IS-A ExtStorRe-
`source
`
`requires
`diskDrive1: DiskDrive
`diskDrive2: DiskDrive
`constraint: diskDrive2.capacity >
`(bytesConsumed-
`diskDrive1 .capacity)
`
`The specializations of ExtStorResource describe two
`different
`implementations of the resource, each con-
`strained to supply at least as much disk space as is con-
`sumed. This allows XKEWB to configure the external
`storage as either one or two disk drives. In addition, the
`level slot of a resource can have a maximum facet which
`restricts the sum ofthe levels used by the constraints shar-
`ing that resource.
`The use facet of a slot is also used to control when a
`constraint is attached to a goal. If the use of a constraint
`attached to a goal has the value exclusive, no other
`requires constraint may be attached to that goal. An exam-
`ple is a printer cable that makes exclusive use of the ports
`to which it will be attached.
`The final attachment mechanism is a context mecha-
`nism which restricts sharing of components. Every con-
`Straint is in a context that is generally inherited from the
`object containing that constraint. However, by specifying
`a containerfacet for a constraint, one can indicate a larger
`context
`for a constraint. For example,
`the software
`selected for a particular workstation would have con-
`straints that could share components in the context estab-
`lished by that workstation. One might, however, want to
`specify the network as the context for the printing require-
`mentso that the printer is not constrained to be a subcom-
`ponent of the workstation. The complement
`to the
`container facet is the setContainer facet which indicates
`that the selected componentis to establish a context of a
`certain type.
`
`5.0 Executing a Goal
`
`The properties of a goal are its attached constraints,its
`current choice, and its posted constraints. The current
`choice is a class in the knowledge base thatsatisfies all of
`
`WorkstationClass2 <q——.Workstation1
`Workstation
`
`aan WorkstationClass1
`
`ee PCClass4 Figure 1: Multiple Inheritance in the IS-A Hierarchy
`
`3DGraphics-Capability
`
`Workstation Class3
`
`WorkstationClass4
`
`371
`
`4
`
`

`

`
`
`the attached and posted constraints. Classes in the knowl-
`edge base are iabelled either abstract or individual. When
`the choice for a goal is an individual, that goal is satisfied.
`For example, a choice of WorkStation is abstract and
`requires further refinement, while a choice such as COM-
`PAQDESKPRO_386N1 if it is an individual, would mean
`that the goal is satisfied.
`In order to deal with multiple inheritance, executing a
`goal involves choosing a description from the most general
`common specializations of the current choice and the types
`of all attached constraints. The most general common spe-
`cializations of a set of classes C to be a set S of classes
`such that each element of S is a specialization (IS-A
`descendant) of every class in C, and no elementof S is a
`specialization of any other element of S. For an example of
`the use of multiple IS-A parents, consider a class Worksta-
`tion that is specialized into WorkstationClass1, Worksta-
`tionClass2,
`etc. Suppose also that
`some of
`these
`workstations have a 3-D graphics capability which is
`described by several constraints. Rather than duplicate the
`definition of these constraints in each workstation which
`has it, one can define a class 3DGraphcs-Capability and
`make those workstations that have the capability IS-A
`descendants of this class. This is illustrated in figure 1
`where WorkstationClass2 and WorkstationClass4 are the
`most general common specializations of Workstation and
`3DGraphes-Capability, while Workstation]
`is not since
`another commonspecialization subsumesit.
`From the most general common specializations, a class
`is a valid choice if it satisfies the constraint expressions of
`all attached and posted constraints. For example, the goal
`for printer would be satisfied by LaserPrinter if an
`attached constraint specified print-quality = letter. Posted
`constraints are often relevant as well. For example, for the
`choice Printer, the goal might have posted a constraint for
`an attached computer which has been specialized to an
`individual computer, say ModelX. This constraint might
`have the expression port-type = computer.port-type which
`specifies that the computer’s port type must be compatible
`with the printer’s. Clearly, a the printer class with port type
`centronics cannot be chosen if the computer’s type is
`serial. Note,
`that when the choices are not individuals,
`there will be slots that are not bound, so evaluation of the
`constraint expression will result in unknown. In this case,
`the class is allowed as a choice.
`Making a choice from the most general common spe-
`cializations of the current choice and attached constraints
`has the effect that constraints commonto a group of com-
`ponents are tested before each of those componentsis tried.
`That is, the algorithm uses the structure of the component
`
`1. COMPAQ and DESKPROare registered trademarks of Compag Com-
`puter Corporation
`
`hierarchy to determine commonconstraints. Whereas Cos-
`sack searched for common constraints from among all
`individual candidates for the goal, XKEWB isable to sim-
`ply pick them from the current choice. For example, the
`class GraphicsSoftware might have subclasses HighEnd-
`Graphics and LowEndGraphics where HighEndGraphics
`might have a constraint that requires a high resolution dis-
`play. Rather than trying each high end graphic package
`only to fail on the display requirement, XKEWB first spe-
`cializes GraphicsSoftware to HighEndGraphics and posts
`the requirement.If the constraint cannotbe satisfied, back-
`tracking will result in trying LowEndGraphics. This tech-
`nique, which will be called hierarchical partial choice can
`result in a great deal of pruning of the search space.
`As well as the early detection of contradictions,hierar-
`chical partial choice can limit the search space by provid-
`ing information that restricts the choices at a goal. For
`example,
`the goal to select a workstation might post a
`requirement for a cpu chip. The goal selection heuristics
`(discussed below) would favour specializing the cpu chip
`goal before the workstation goal, hence when it becomes
`time to select a workstation, the cpu chip will be more
`tightly constrained, say to 803867. Thus only specializa-
`tions of Workstation that are compatible with this choice
`need be considered. This is very important since the
`choice of cpu chip might have been constrained by the
`user either directly through an input constraint, or indi-
`rectly through a constraint on some other aspect of the sys-
`tem such as a software package.
`Once a choice has been made, any new constraints are
`posted. The new constraints are all constraints defined in
`the choice and ail of its IS-A ancestors that are not already
`posted constraints of the goal. The new constraints are put
`into the list NewConstraints, and the algorithm retumsto
`the constraint processing step.
`
`6.0 Backtracking, Goal Selection, and
`Preferences
`
`Should there be no valid choice,it is necessary to back-
`track. For the purposes of backtracking, the configuration
`process is a sequence made up ofthe operations“attach a
`constraint to a goal” and “makea choice for a goal”. If the
`previous step was “attach a constraint to a goal”, back-
`tracking involves attempting to make a new attachment.
`Note that creating a goal counts as an attachment and can
`only be tried once for a constraint. If a new attachmentis
`not possible, backtracking is again necessary. Similarly, if
`the previous operation was “make a choice for a goal”, a
`
`2. 8086, 80286, 80386 are trademarks of Intel Corporation
`
`372
`
`5
`
`

`

`
`
`new choiceis attempted. Again, if this fails, further back-
`tracking is necessary.
`Several heuristics are used to minimize backtracking.
`First, a choice is made for any new goals. Secondly, goals
`farthest (measured by the number of constraints in the
`shortest path) from the primary system goals are preferred.
`This has the result that choices for the innermost goals are
`tightly constrained (as described above.) Thirdly, the goals
`with the fewest posted constraints are specializedfirst. This
`is important because in general making an incorrect choice
`for a complicated component such as a workstation would
`result in much more retracting of constraints than would
`specializing the goal for a mouse.
`The nature of the configuration problem is such that no
`two users will agree on an objective function which the
`system should optimize. For examplc, one user will want to
`minimize cost while another will want to minimize the
`component count. Instead of a global objective function,
`therefore, in XKEWBthere is preference facct that con-
`straints may have that specifies an ordering of the possible
`choices for the attached goal. For example, a constraint
`might specify that the choice with the smallest price should
`be tried first. This is a heuristic only, especially in the con-
`text of hierarchical partial choice where the value of the
`property may not be available until near the end of the
`inference. For example, when specializing Printer and
`choosing between LaserPrinter and InkJetPrinter
`the
`prices would not be available. As well as encoding prefer-
`ences in individual constraints, a global default preference
`can be specified.
`While not providing “optimal” solutions, the local pref-
`erence technique provides good solutions. Dhar and Ran-
`ganathan [3] have observed that
`this technique is less
`brittle than a global optimization approach and also pro-
`vides more satisfying solutions. Also, another design goal
`behind XKEWB was to make generating configurations
`
`fast enough that the user could quickly generate several
`and choose the most appropriate.
`The preference heuristics are used only for ordering
`choices. No pruning is done by the algorithm, which there-
`fore will run in exponential time in the number of compo-
`nents in the worst case.
`
`7.0 User Interface
`
`The user interface to XKEWB makesit particularly
`easy to enter the constraints on the system to be config-
`ured, The interface makes use of a bitmapped display and
`a mouse, and under most conditions no typing is necessary
`to generate configurations. An approximation to the actual
`screen is displayed in figure 2. The boxes are mouse
`selectable and change colour when selected. Where the
`options are mutually exclusive, selecting an option will
`tum off the one already selected. Clicking on a selected
`word deselects it. Since screen real estate is limited, the
`options are spread over several logical pages; one for hard-
`ware and several for software options. Furthermore, there
`is a set of pages for each workstation being configured.
`Flipping between this pages can be donerapidly by click-
`ing on buttons in a control panel.
`As mentioned above,input to the algorithm is a set of
`constraints exactly the sameas those used within a compo-
`nent description. Thus the input to a configuration problem
`might be
`computer1: Workstation
`constraint: cpu = 80286 &
`softwarePackage[1] = dBASE IV'&
`softwarePackage[2] = Microsoft Excel?
`
`1. dBASEIVis a trademark of Ashton Tate
`2. Microsoft Excel is a trademark of Microsoft Corporation
`
`Next Configuration
`
`Select Workstation: 2&
`
`| SelectPage
`
`cpu:
`
`disk:
`
`Hisplay:
`network:
`
`
`
`
`
`Software:|Microsoft Excel} {Ventura Publisher| [dBASE IV
`
`
`
`Figure 2: The XKEWBUserInterface
`
`6
`
`

`

`
`
`igh MP
`
`MedMIPS
`
`LowMIPS
`
`32BitBus
`
`16BitBus
`
`CPU
`
`properties
`mips
`company
`constraints
`bus:Bus
`
`HighMotorola
`
`80386sx
`
`
`
`SoftwarePackagel
`constraints
`cpu: HighMIPS
`
`SoftwarePackage2
`constraints
`cpu: Intel
`
`properties
`width: 16
`
`Figure 3: A Partial XKEWB Hierarchy
`
`which asks for two work stations, specifying the cpu
`type and the desired softwarc. The idea behind the inter-
`face is that each conjunct in the above constraints can be
`selected by pressing buttonsin the interface. The first con-
`figuration is generated by pressing the Configure button
`and subsequent solutions can be generated using the Next
`Configuration button.
`
`8.0 Example
`
`Suppose the system is simply configuring a CPU chip
`and two software packages using the partial hierarchy
`describing CPU chips, software and a bus showninfigure
`3.
`
`For simplicity, assume that the system is attempting to
`configure two software packages, a cpu chip, and a bus
`from the input constraints c: CPU,sl: Software-
`Packagel, s2: SoftwarePackage2, and b:AT-
`Bus. Initial processing of these constraints results in four
`goals, respectively Gcpu, Gsl1, Gs2, and GBus. Execut-
`ing Gcpu results in an initial choice of the object CPU.
`Next the constraint bus is posted, then, in the attach step,
`it is attached to GBus. In the next execute step, one of the
`unexecuted goals is preferred over Gcepu. The system
`might pick Gs1, specializing it to SoftwarePackagel
`and posting the cpu constraint. This constraint is then
`attached to Gcpu. Similarly Gs2 would be executed
`choosing SoftwarePackage2 and posting a cpu con-
`straint which is subsequently attached to Gcpu. Next
`
`GBus specializes to ATBus. Now, Gepu,the only open
`goal, has types HighMIPS and Intel. The most general
`common specialization of these two classes is HighIn-
`tel and becomesthe choice for the goal. On the nextiter-
`ation, 80386sx_ is chosen because it is the only choice
`consistent with the fact that the bus constraint is bound to
`a 16bit bus.
`Althoughit is very simple, this example illustrates how
`XKEWB is able to focus on the correct CPU chip with no
`search through the space of configurations. Even in this
`example, the space could be quite large if the bottom of
`the CPU hierarchy wereto be filled in with descriptions of
`more chips.
`
`9.0 Conclusions
`
`XKEWB contains several areas of improvement over
`its predecessor, the Cossack system. These include 1) the
`introduction of resource constraints, 2) the context mecha-
`nism which allows the configuration of multiple comput-
`ers sharing resources, 3) an improved inference algorithm
`introducing hierarchical partial choice, and 4) an improved
`userinterface. Points 1 and 2 result in the ability to cover a
`much broader and moreinteresting range of configuration
`problems.Point3 results in a system thatis more complete
`since exhaustive search is used, and in a system that is
`muchfaster. This is due, in part, to the introduction of
`hierarchical partial choice. Tracing the execution of
`XKEWB showsthat the backtracking that occurs is local-
`
`374
`
`7
`
`

`

`
`
`References
`
`ized, that is, that for the examples that were chosen, no
`major jumps occurred. Point 4 results in a system that is
`particularly convenient to use.
`[1] Bowen, James, “Automated Configuration Using a
`Unlike rule-based systems such as XCONor hybrid sys-
`Functional Reasoning,”in Artificial Intelligence and its
`tems as described in [10] and [9] XKEWBis purely declar-
`Applications, ed, Cohn, A. G. & Thomas, J.R., pp. 79-
`ative: there is no need for rules describing how to put a
`106, John Wiley & Sons, New York, 1986.
`system together. The declarative representation is impor-
`[2] Davis, Randall, “Meta-Rules: Reasoning About Con-
`trol,” Artificial Intelligence, vol. 15, no. 3, pp. 179-222,
`tant for making the knowledge acquisition and mainte-
`1980.
`nance tasks manageable. Unlike the system described in
`[3] Dhar, Vasant and Ranganathan, Nicky, “Integer Pro-
`[1], XKEWB has a hierarchical representation which
`gramming vs. Expert Systems: An Experimental Com-
`enables the use of the hierarchical partial choice inference
`parison,” Communications of the ACM,vol. 33, no. 3,
`schemeforefficiently generating solutions. The hiearchical
`pp. 323-336, March 1990.
`representation is importantalso for efficiency in acquiring
`[4] Frayman, Felix and Mittal, Sanjay, “Cossack: A Con-
`knowledge.
`straints-based Expert System for Configuration Tasks,”
`An potential weakness of the technique is that in the
`in Knowledge-based Expert Systems in Engineering:
`worst case a great deal of backtracking could occur. One
`Planning and Design, ed. Sriram, D. & Adey, R. A.,
`approach to this problem would be to introduce somesort
`Sept. 1987.
`of dependency directed backtracking. A second approach
`[5] Goldstein, Ira P. and Roberts, R. B., “Nudge: a know!-
`might be to break a configuration problem into a set of
`edge-Based Scheduling Program,” in Proceedings of
`loosely connected subproblems. In practice, however, the
`the Fifth International Joint Conference on Artificial
`hierarchical partial choice technique in itself has been suf-
`Intelligence, pp. 257-263, Cambridge, MA,1977.
`ficient for generating solutions without major backtrack-
`ing.
`[6] McDermott, J., “Rl: A Rule-Based Configurer of
`Computer Systems,” Artificial Intelligence, vol. 19, no.
`A working version of XKEWB was implemented on a
`1, 1982.
`Xerox 1186 workstation in the Interlisp-D environment.
`(7] Mittal, Sanjay and Frayman, Felix, “Making Partial
`Knowledge bases for the Xerox PC and for the Xerox Doc-
`umenter! workstation were demonstrated. The PC knowl-
`Choices in Constraint Reasoning Problems,” in Pro-
`ceedingsof the Sixth National Conference on Artificial
`edge base contained about 150 abstract classes and 75
`Intelligence, pp. 631-636, Seattle, 1987.
`individual classes, while the Documenter knowledge base
`consisted of about 120 abstract and 100 individualclasses.
`[8] Mittal, Sanjay and Frayman, Felix, “Towards A
`Generic Model of Configuration Tasks,” in Proc