Hoe. or the 1391 mm:
`Int. Conf. on Tools for AI
`San Jose. CA—Nov. I991
`
`Knowledge-based Configuration of Computer Systems Using
`Hierarchical Partial Choice
`
`Bryan M. Kramer*
`Department of Computer Science
`University of Toronto
`Toronto, Ontario, MSS 1A4
`kramer@ ai.torontoiedu
`
`Abstract
`
`As the complexity of computer systems grows, configu-
`ration expert systems become increasingly important 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-
`sition and maintenance advantages (over rule—based sys-
`tems) of a declarative system with an inference scheme that
`efi‘tciently 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 is
`designed to allow configurators to configure multiple com-
`puters in a network setting, the end user interface is 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 Willi
`the word processing software, and, does the 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 maintenance of config-
`uration knowledge and efficiently generating complex
`configuration do not appear
`to have been adequately
`addressed. This paper describes XKEWB, a shell for build-
`at:
`
`: This work was done while the author was with Xerox Canada Inc.
`
`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 some set 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 component restriction which states that
`there is some key component implementing each function.
`Under these restrictions, 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
`changes to 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
`XKEWB followed by several sections describing details of
`the system. Finally,
`the concluding section contrasts
`XKEWB with 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.
`Interrelationships between components or component
`classes are represented by slots with associated constraints.
`A constraint specifies which objects might fill the slot by
`either enumerating the possibilities or specifying a class
`whose instances might fill 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 have a slot called printer with a constraint specifying
`that the value must belong to the class Printer and a lisp
`expression that evaluates to true 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
`goal. 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 component that satisfies the constraints. When
`the choice is made, new constraints are posted, and the
`cycle continues.
`If no component satisfies 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 has the 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].
`When there 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 commitment in that a choice is made at ran-
`dom only when necessary.
`
`3.0 XKEWB
`
`Cossack had several weaknesses. The most important is
`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 of difficulty 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 inforrna—
`tion contained therein was not available to the inference
`
`engine. Finally, the representation lacked the ability to
`describe components that partially used other components
`(such as disk space) and to distinguish components
`belonging to different computers in a multi-computer set-
`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.
`When a 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 might result in a choice, Microsoft_Wordl 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’s representation language is more declarative
`and expressive than that used in Cossack. Components are
`
`1. Microsoft Word is a trademark of Microsoft Corporation
`
`369
`
`2
`
`

`

`represented using a frame representation1 with multiple
`and strict inheritance. Frames representing components are
`called classes and are organized in an IS-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
`component representation
`Workstation (abstract) lS-A Computer
`subcomponents
`display: WorkstationDisplay
`number: [1, 2]
`keyboard: WorkstationKeyboard
`disk: WorkStationDisk
`memory: Memory
`requires
`networkconnection:
`NetworkConnection
`
`Ventura_Publisher2 (individual) lS-A
`PublishingPackage
`
`requires
`printer: LaserPrintingResource
`constraint:
`printer.postscript-capability
`= true
`disk: ExtStorResource
`level: 657
`consumes: bytesConsumed
`memory: MemoryResource
`constraint:
`memorysupplied-by =
`workstation
`workstation: WorkStation
`properties
`pncez2000
`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 to attach
`newly posted constraints to goals either by finding an exist-
`ing goal that is compatible or by creating a new goal. The
`attaching step is important because it allows components to
`
`l. 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 fictitious
`
`be described independently of other components that
`might require the same resources, and yet results in config-
`urations where one component is 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 legal 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 components that
`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-
`nent constraint 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 Ventura_Publisher. 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 involve other slot 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 which it 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 same goal.
`The disk constraint is an example of a resource con-
`sumption constraint. The value of the consumes facet iden-
`titles 3 slot in the type, ExtStarResource, and the facet level
`specifies a value. The meaning of this constraint is that the
`value of the slot bytesConsumed in an instance of ExtStor-
`Resource is equal to the sum of the levels consumed by all
`resource constraints that have that instance as a value. The
`
`following is a possible definition of the resource:
`
`ExtStorResource (abstract) lS-A Resource
`levels
`bytesConsumed: Number
`
`ExtStorResource1 (individual) lS-A
`ExtStorResource
`
`requires
`diskDrive: DiskDrive
`constraint: diskDrive.capacity >
`bytesCon5umed
`
`ExtStorResource2 (individual) lS-A ExtStorRe-
`source
`
`requires
`diskDrive1: DiskDrive
`diskDriveZ: 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 of the 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 container facet 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-
`ment so 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 component is 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 that satisfies all of
`
`/
`
`Workstation
`
`3DGraphics-Capability
`
`\
`
`WorkStationClassl
`
`WorkstationClassZ ‘___ Workstation]
`
`WorkstationClass3
`
`WorkstationClass4
`
`PCClass4
`
`Figure 1: Multiple Inheritance in the IS-A Hierarchy
`
`371
`
`4
`
`

`

`the attached and posted constraints. Classes in the knowl-
`edge base are labelled 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—
`PAQ_DESKPRO_386N‘, 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 element of 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 WorkstationClassI, Worksta-
`tionClassZ,
`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 lS-A
`descendants of this class. This is illustrated in figure 1
`where WorkstationClassZ and WorkstationClass4 are the
`
`most general common specializations of Workstation and
`3DGraphcs—Capability, while Workstation]
`is not since
`another common Specialization subsumes it.
`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
`constrains 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 = computerport-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 common to a group of com-
`ponents are tested before each of those components is tried.
`That is, the algorithm uses the structure of the component
`
`1. COMPAQ and DESKPRO are registered trademarks of Compaq Com-
`puter Corporation
`
`hierarchy to determine common constraints. Whereas Cos-
`sack searched for common constraints from among all
`individual candidates for the goal, XKEWB is able 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 cannot be 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 803862. 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 all 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 returns to
`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 of the operations “attach a
`constraint to a goal” and “make a 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 attachment is
`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 choice is 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 specialized first. 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 example, one user will want to
`minimize cost while another will want to minimize the
`
`component count. Instead of a global objective function,
`therefore, in XKEWB there is preference facet 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 lnkletPrinter
`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 pnming 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 makes it 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
`turn 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 done rapidly by click-
`ing on buttons in a control panel.
`As mentioned above, input to the algorithm is a set of
`constraints exactly the same as those used within a compo-
`nent description. Thus the input to a configuration problem
`might be
`computen : Workstation
`constralnt: cpu = 80286 &
`softwarePackage[1] = dBASE Ivla
`softwarePackage[2] = Microsoft Excel2
`
`1. dBASE IV is a trademark of Ashton Tate
`2. Microsoft Excel is a trademark of Microsoft Corporation
`
`
`
`elec—tWorkstation: 2 H
`
`
`
`>;—-. .
`
`Next Confi_uration
`
`0p":
`
`disk:
`
`“Plat
`network:
`
`Software: Microsoft Excel
`
`VenturaPublisher
`
`dBASE [V
`
`Figure 2: The XKEWB User Interface
`
`373
`
`
`
`
`
`g,
`
`6
`
`

`

`
`
`HighMotorola
`
`Highlntel
`
`CPU
`
`properties
`mlpS
`comp?“
`constraints
`
`32BitBus
`l6BitBus
`
`Motorola
`
`
`
`SoftwarePackagel
`constraints
`cpu: HighMIPS
`
`SoftwarePackageZ
`constraints
`cpu: Intel
`
`- TBus
`properties
`width: 16
`
`Figure 3: A Partial XKEWB Hierarchy
`
`which asks for two work stations, specifying the cpu
`type and the desired software. The idea behind the inter-
`face is that each conjunct in the above constraints can be
`selected by pressing buttons in 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 shown in figure
`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, s1: Software—
`Packagel, 52:
`SoftwarePackageZ, and b:AT—
`Bus. Initial processing of these constraints results in four
`goals, respectively chu, Gs 1, G52, and GBus. Execut-
`ing chu 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 chu. The system
`might pick Gsl, specializing it to SoftwarePackagel
`and posting the cpu constraint. This constraint is then
`attached to chu. Similarly G32 would be executed
`choosing SoftwarePackage2 and posting a cpu con-
`straint which is subsequently attached to chu. Next
`
`GBus specializes to ATBus. Now, chu, the only open
`goal, has types HighMIPS and Intel. The most general
`common specialization of these two classes is High In—
`tel and becomes the choice for the goal. On the next iter-
`ation, 8038 63x is chosen because it is the only choice
`consistent with the fact that the bus constraint is bound to
`a 16 bit bus.
`
`Although it 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 were to 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
`user interface. Points 1 and 2 result in the ability to cover a
`much broader and more interesting range of configuration
`problems. Point 3 results in a system that is more complete
`since exhaustive search is used, and in a system that is
`much faster. This is due, in part, to the introduction of
`hierarchical partial choice. Tracing the execution of
`XKEWB shows that the backtracking that occurs is local-
`
`374
`
`7
`
`

`

`
`
`References
`
`[1] Bowen, James, “Automated Configuration Using a
`Functional Reasoning,” in Artificial Intelligence and its
`Applications, ed. Cohn, A. G. & Thomas, J. R., pp. 79-
`106, John Wiley & Sons, New York, 1986.
`[2] Davis, Randall, “Meta—Rules: Reasoning About Con-
`trol,” Artificial Intelligence, vol. 15, no. 3, pp. 179-222,
`1980.
`
`[3] Dhar, Vasant and Ranganathan, Nicky, “Integer Pro-
`gramming vs. Expert Systems: An Experimental Com-
`parison,” Communications of the ACM, vol. 33, no. 3,
`pp. 323-336, March 1990.
`[4] Frayman, Felix and Mittal, Sanjay, “Cossack: A Con-
`straints-based Expert System for Configuration Tasks,”
`in Knowledge-based Expert Systems in Engineering:
`Planning and Design, ed. Sriram, D. & Adey, R. A.,
`Sept. 1987.
`[S] Goldstein, Ira P. and Roberts, R. B., “Nudge: a knowl-
`edge-Based Scheduling Program,” in Proceedings of
`the Fifth International Joint Conference on Artificial
`Intelligence, pp. 257-263, Cambridge, MA, 1977.
`[6] McDermott, J ., “RI: A Rule-Based Configurer of
`Computer Systems,” Artificial Intelligence, vol. 19, no.
`1, 1982.
`[7] Mittal, Sanjay and Frayman, Felix, “Making Partial
`Choices in Constraint Reasoning Problems,” in Pro-
`ceedings of the Sixth National Conference on Artificial
`Intelligence, pp. 631—636, Seattle, 1987.
`[8] Mittal, Sanjay and Frayman, Felix, “Towards A
`Generic Model of Configuration Tasks,” in Proceed-
`ings of the Eleventh Joint Conference on Artificial
`Intelligence, pp. 1395-1401, Detroit, 1989.
`[9] Pierick, J., “A Knowledge Representation Technique
`for Systems Dealing with Hardware Configuration,” in
`Proceedings of the Fifth National Conference on Artifi-
`cial Intelligence, pp. 991-995, Philadelphia, 1986.
`[10] Wu, H., Chun, H. W., and Mimo, A., “ISCS A Tool
`Kit for Constructing Knowledge-Based System Con-
`figurators,” in Proceedings of the Fifth National Con-
`ference on Artificial
`Intelligence, pp. 1015-1021,
`Philadelphia, 1986.
`
`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.
`Unlike rule-based systems such as XCON or hybrid sys—
`tems as described in [10] and [9] XKEWB is purely declar-
`ative: there is no need for rules describing how to put a
`system together. The declarative representation is impor-
`tant for making the knowledge acquisition and mainte—
`nance tasks manageable. Unlike the system described in
`[l], XKEWB has a hierarchical representation which
`enables the use of the hierarchical partial choice inference
`scheme for efficiently generating solutions. The hiearchical
`representation is important also for efficiency in acquiring
`knowledge.
`An potential weakness of the technique is that in the
`worst case a great deal of backtracking could occur. One
`approach to this problem would be to introduce some sort
`of dependency directed b