Page 1 of 72
`
`FORD 1017
`
`

`
`Introduction to
`Kno
`led
`
`Mark Stefik
`
`Morgan Kaufmann Publishers, Inc.
`San Francisco, California
`
`Page 2 of 72
`
`FORD 1017
`
`

`
`Sponsoring Editor Michael B. Morgan
`Production Manager Yonie Overton
`Production Editor Elisabeth Beller
`Editorial Coordinator Marilyn Uffner Alan
`Text Design, Project Management,
`Electronic Illustrations and Composition Professional Book Center
`Cover Design Carron Design
`Copyeditor Anna Huff
`Printer Quebecor Fairfield
`
`Morgan Kaufmann Publishers, Inc.
`Editorial and Sales Office
`340 Pine Street, Sixth Floor
`San Francisco, CA 94104-3205 USA
`Telephone 415/392-2665
`Facsimile 415/982-2665
`Internet mkp@mkp.com
`
`Library of Congress Cataloging-in-Publication Data is available for this book.
`) t::~
`I.,,,.
`
`ISBN 1-55860-166-X
`
`r-""i l'\
`
`0(!-+
`
`© 1995 by Morgan Kaufmann Publishers, Inc.
`
`All rights reserved
`
`Printed in the United States of America
`
`99 98 97 96 95
`
`5 4 3 2 1
`
`~~""'l
`,~:.--~-~1
`.<-''"'
`{
`No part of this publication may be reproduced, stored in a retrieval system, or transmitted in any form or
`by any means---electronic, mechanical, photocopying, recording, or otherwise-without the prior written
`permission of the publisher.
`
`Brand and product names referenced in this book are trademarks or registered trademarks of their respec(cid:173)
`tive holders and are used here for informational purposes only.
`
`Page 3 of 72
`
`FORD 1017
`
`

`
`on tents
`
`Foreword Edward A. Feigenbaum
`
`xiii
`
`Preface
`
`xv
`
`Notes on the Exercises
`
`xix
`
`INTRODUCTION AND OVERVIEW
`
`PART I FOUNDATIONS
`
`CHAPTER 1 Symbol Systems
`
`22
`
`1.1 Symbols and Symbol Structures
`1.1.1 What Is a Symbol?
`22
`1.1.2 Designation
`25
`28
`1.1.3 Causal Coupling
`1.1.4 Cognitive and Document Perspectives of Symbols
`1.1.5 Summary and Review
`32
`Exercises for Section 1.1
`32
`
`35
`1.2 Semantics: The Meanings of Symbols
`36
`1.2.1 Model Theory and Proof Theory
`1.2.2 Reductionist Approaches for Composing Meanings
`1.2.3 Terminology for Graphs and Trees
`44
`1.2.4 Graphs as Symbol Structures
`47
`1.2.5 The Annotation Principle and Metalevel Notations
`1.2.6 Different Kinds of Semantics
`55
`1.2.7 Summary and Review
`59
`Exercises for Section 1.2
`60
`
`30
`
`41
`
`50
`
`1
`
`19
`
`21
`
`v
`
`Page 4 of 72
`
`FORD 1017
`
`

`
`vi
`
`CONTENTS
`
`68
`
`71
`77
`80
`84
`
`1.3 Modeling: Dimensions of Representation
`1.3.1 Fidelity and Precision
`69
`1.3.2 Abstractions and Implementations
`1.3.3 Primitive and Derived Propositions
`1.3.4 Explicit and Implict Representations
`1.3.5 Representation and Canonical Form
`1.3.6 Using Multiple Representations
`85
`1.3.7 Representation and Parallel Processing
`1.3.8 Space and Time Complexity
`89
`1.3.9 Structural Complexity
`98
`1.3.10 Summary and Review
`101
`Exercises for Section 1.3
`102
`
`88
`
`107
`
`1.4 Programs: Patterns, Simplicity, and Expressiveness
`1.4.1 Using Rules to Manipulate Symbols
`107
`1.4.2 Treating Programs as Data
`110
`1.4.3 Manipulating Expressions for Different Purposes
`1.4.4 Pattern Matching
`114
`1.4.5 Expressiveness, Defaults, and Epistemological Primitives
`1.4.6 The Symbol Level and the Knowledge Level
`129
`1.4.7 Summary and Review
`130
`Exercises for Section 1.4
`131
`
`112
`
`1.5 Quandaries and Open Issues
`
`136
`
`CHAPTER 2 Search and Problem Solving
`
`147
`2.1 Concepts of Search
`2.1.1 Solution Spaces and Search Spaces
`2.1.2 Terminology about Search Criteria
`2.1.3 Representing Search Spaces as Trees
`2.1.4 Preview of Search Methods
`157
`2.1.5 Summary and Review
`158
`Exercises for Section 2.1
`159
`
`148
`153
`156
`
`165
`2.2 Blind Search
`165
`2.2.1 Depth-First and Breadth-First Search
`2.2.2 Top-Down and Bottom-Up Search: A Note on Terminology
`2.2.3 Simple and Hierarchical Generate-and-Test
`173
`2.2.4 A Sample Knowledge System Using Hierarchical
`Generate-and-Test
`180
`2.2.5 Simple and Backtracking Constraint Satisfaction
`2.2.6 Summary and Review
`193
`Exercises for Section 2.2
`194
`
`187
`
`117
`
`146
`
`171
`
`Page 5 of 72
`
`FORD 1017
`
`

`
`CONTENTS
`
`vii
`
`203
`2.3 Directed Search
`205
`2.3.1 Simple Match
`2.3.2 Means-Ends Analysis
`210
`2.3.3 Hierarchical Match and Skeletal Planning
`225
`2.3.4 Hill Climbing and Best-first Search
`2.3.5 Shortest-Path Methods
`232
`2.3.6 A* and Related Methods
`239
`248
`2.3.7 Summary and Review
`251
`Exercises for Section 2.3
`
`219
`
`259
`2.4 Hierarchical Search
`264
`2.4.1 Two-Level Planning
`2.4.2 Planning with Multiple Abstraction Levels
`2.4.3 Planning with Imperfect Abstractions
`275
`279
`2.4.4 Summary and Review
`280
`Exercises for Section 2.4
`
`271
`
`2.5 Quandaries and Open Issues
`
`287
`
`.,
`
`CHAPTER 3 Knowledge and Software Engineering
`
`3.1 Understanding Knowledge Systems in Context
`292
`3.1.1 The Terminology of Knowledge Systems and Expertise
`3.1.2 Knowledge Systems and Document Systems:
`Five Scenarios
`299
`3.1.3 Preview of Knowledge Acquisition Topics
`312
`3.1.4 Summary .and Review
`Exercises for Section 3.1
`312
`
`311
`
`291
`
`292
`
`314
`3.2 Formulating Expertise
`3.2.1 Conducting Initial Interviews
`3.2.2 Taking Protocols
`320
`324
`3.2.3 Characterizing Search Spaces
`3.2.4 Adapting Protocol Analysis for Knowledge Systems
`3.2.5 Summary and Review
`330
`Exercises for Section 3.2
`330
`
`314
`
`336
`3.3 Collaboratively Articulating Work Practices
`3.3.1 Variations in Processes for Interview and Analysis
`3.3.2 Documenting Expertise
`345
`3.3.3 Engineering Software and Organizations
`358
`3.3.4 Summary anq Review
`Exercises for Section 3.3
`359
`
`349
`
`327
`
`336
`
`Page 6 of 72
`
`FORD 1017
`
`

`
`viii
`
`CONTENTS
`
`365
`3.4 Knowledge versus Complexity
`3.4.1 MYCIN: Study of a Classic Knowledge System
`365
`3.4.2 The Knowledge Hypothesis and the Qualification Problem
`3.4.3 Summary and Review
`389
`Exercises for Section 3.4
`389
`
`3.5 Open Issues and Quandaries
`
`394
`
`PART II THE SYMBOl lEVEl
`
`CHAPTER 4 Reasoning about Time
`
`380
`
`403
`
`405
`
`407
`4.1 Temporal Concepts
`407
`4.1.1 Timeline Representations
`4.1.2 A Discrete Model of Transactions
`in the Balance of an Account
`408
`4.2 Continuous versus Discrete Temporal Models
`4.3 Temporal Uncertainty and Constraint Reasoning
`4.3.1 Partial Knowledge of Event Times
`412
`4.3.2 Arc Consistency and Endpoint Constraints
`4.3.3 Time Maps and Scheduling Problems
`416
`4.3.4 The Interface between a Scheduler and
`a Temporal Database
`416
`4.4 Branching Time
`421
`4.5 Summary and Review
`Exercises for Chapter 4
`
`423
`424
`
`410
`411
`
`414
`
`4.6 Open Issues and Quandaries
`
`427
`
`CHAPTER 5 Reasoning about Space
`
`432
`
`433
`5.1 Spatial Concepts
`5.2 Spatial Search
`435
`436
`5.2.1 Simple Nearest-First Search
`5.2.2 Problems with Uniform-Size Regions
`438
`5.2.3 Quadtree Nearest-First Search
`5.2.4 Multi-Level Space Representations
`5.3 Reasoning about Shape
`442
`5.4 The Piano Example: Using Multiple Representations of Space
`5.4.1 Reasoning for the Piano Movers
`444
`5.4.2 Rendering a Piano
`448
`5.4.3 The Action of a Piano
`450
`
`440
`
`437
`
`444
`
`Page 7 of 72
`
`FORD 1017
`
`

`
`ix
`
`460
`
`541
`
`543
`
`CONTENTS
`
`5.5 Summary and Review
`Exercises for Chapter 5
`
`452
`453
`
`5.6 Open Issues and Quandries
`
`458
`
`CHAPTER 6 Reasoning about Uncertainty and Vagueness
`
`461
`6.1 Representing Uncertainty
`6.1.1 Concepts about Uncertainty
`6.1.2 The Certainty-Factor Approach
`6.1.3 The Dempster-Shafer Approach
`6.1.4 Probability Networks
`483
`6.1.5 Summary and Conclusions
`Exercises for Section 6.1
`506
`
`461
`469
`476
`
`504
`
`517
`6.2 Representing Vagueness
`6.2.1 Basic Concepts of Fuzzy Sets
`6.2.2 Fuzzy Reasoning
`524
`6.2.3 Summary and Conclusions
`Exercises for Section 6.2
`532
`
`518
`
`531
`
`6.3 Open Issues and Quandries
`
`533
`
`PART Ill THE KNOWLEDGE LEVEl.
`
`CHAPTER 7 Classification
`
`543
`7.1 Introduction
`7.1.1 Regularities and Cognitive Economies
`54 7
`7.2 Models for Classification Domains
`7.2.1 A Computational Model of Classification
`7 .2.2 Model Variations and Phenomena
`549
`7 .2.3 Pragmatics in Classification Systems
`554
`7 .2.4 Summary and Review
`556
`Exercises for Section 7.2
`557
`
`543
`
`547
`
`7.3 Case Studies of Classification Systems
`7.3.1 Classification in MYCIN
`563
`7.3.2 Classification in MORE
`567
`7 .3.3 Classification in MOLE
`572
`7.3.4 Classification in MDX
`580
`7.3.5 Classification in PROSPECTOR
`7.3.6 Summary and Review
`586
`Exercises for Section 7.3
`586
`
`563
`
`582
`
`Page 8 of 72
`
`FORD 1017
`
`

`
`CONTENTS
`
`588
`7.4 Knowledge and Methods for Classification
`7.4.1 Knowledge-Level and Symbol-Level Analysis
`of Classification Domains
`589
`7.4.2 MC-1: A Strawman Generate-and-Test Method
`7.4.3 MC-2: Driving from Data to Plausible Candidates
`7.4.4 MC-3: Solution-Driven Hierarchical Classification
`7.4.5 MC-4: Data-Driven Hierarchical Classification
`7.3.6 Method Variations for Classification
`599
`7.4.7 Summary and Review
`602
`Exercises for Section 7.4
`603
`
`592
`593
`594
`596
`
`7.5 Open Issues and Quandaries
`
`604
`
`CHAPTER 8 Configuration
`
`608
`8.1 Introduction
`8.1.1 Configuration Models and Configuration Tasks
`8.1.2 Defining Configuration
`610
`612
`8.2 Models for Configuration Domains
`8.2.1 Computational Models of Configuration
`8.2.2 Phenomena in Configuration Problems
`8.2.3 Summary and Review
`620
`Exercises for Section 8.2
`621
`
`612
`615
`
`608
`
`609
`
`625
`
`8.3 Case Studies of Configuration Systems
`8.3.1 Configuration in XCON
`625
`8.3.2 Configuration in M1/MICON
`633
`8.3.3 Configuration in MYCIN's Therapy Task
`8.3.4 Configuration in VT
`640
`8.3.5 Configuration in COSSACK
`8.3.6 Summary and Review
`650
`Exercises for Section 8.3
`652
`
`647
`
`637
`
`8.4 Methods for Configuration Problems
`656
`8.4.1 Knowledge-Level and Symbol-Level Analysis
`of Configuration Domains
`656
`8.4.2 MCF-1: Expand and Arrange
`661
`8.4.3 MCF-2: Staged Subtasks with Look-Ahead
`8.4.4 MCF-3: Propose-and-Revise
`665
`8.4.5 Summary and Review
`665
`Exercises for Section 8.4
`666
`
`662
`
`8.5 Open Issues and Quandaries
`
`667
`
`Page 9 of 72
`
`FORD 1017
`
`

`
`CONTENTS
`
`CHAPTER 9 Diagnosis and Troubleshooting
`
`xi
`
`670
`
`670
`9.1 Introduction
`9 .1.1 Diagnosis and Troubleshooting Scenarios
`9 .1.2 Dimensions of Variation in Diagnostic Tasks
`9.2 Models for Diagnosis Domains
`673
`9.2.1 Recognizing Abnormalities and Conflicts
`9.2.2 Generating and Testing Hypotheses
`680
`9.2.3 Discriminating among Hypotheses
`690
`9 .2.4 Summary and Review
`700
`Exercises for Section 9.2
`701
`
`670
`671
`
`677
`
`711
`
`9.3 Case Studies of Diagnosis and Troubleshooting Systems
`9.3.1 Diagnosis in DARN
`712
`715
`9.3.2 Diagnosis in INTERNIST
`9.3.3 Diagnosis in CASNET/GLAUCOMA
`9.3.4 Diagnosis in SOPHIE III
`729
`9.3.5 Diagnosis in GDE
`737
`9.3.6 Diagnosis in SHERLOCK
`9.3.7 Diagnosis in XDE
`748
`9.3.8 Summary and Review
`759
`Exercises for Section 9.3
`761
`
`744
`
`724
`
`9.4 Knowledge and Methods for Diagnosis
`9.4.1 Plan Models for Diagnosis
`765
`766
`9.4.2 Classification Models for Diagnosis
`9.4.3 Causal and Behavioral Models for Systems
`9.4.4 Summary and Review
`768
`Exercises for Section 9.4
`769
`
`764
`
`767
`
`9.5 Open Issues and Quandaries
`
`771
`
`APPENDIX A Annotated Bibliographies by Chapter
`
`APPENDIX B Selected Answers to Exercises
`
`Index
`
`853
`
`776
`
`811
`
`Page 10 of 72
`
`FORD 1017
`
`

`
`Configuration tasks select and arrange instances of parts
`frotrl (l:set. Computational models for configuration are
`used for build-to~order manufacturing tasks and also for
`tasks such as planning and therapy recommendation.
`Incremental decision-making methods for configuration
`must cope with threshold effects and horizon effects.
`
`nfi ur ti n
`
`Introduction
`8.1
`A configuration is an arrangement of parts. A configuration task is a problem-solving activity
`that selects and arranges combinations of parts to satisfy given specifications. Configuration
`tasks are ubiquitous. Kitchen designers configure cabinets from catalogs of modular cupboards,
`counters, closets, drawers, cutting boards, racks, and other elements. Salespeople for home enter(cid:173)
`tainment systems must design configurations from tape decks, optical disk players, receivers,
`turntables, and other units that can play recordings from different media, as well as from video
`screens, speakers, and other units that can present performances to people. Computer engineers
`and salespeople configure computer systems from various computing devices, memory devices,
`input and output devices, buses, and software. Dieticians configure diets from different combina(cid:173)
`tions of foods. Configuration problems begin with general specifications and end with detailed
`specifications of what parts are needed and how they are to be arranged.
`A definitional characteristic of configuration, as we shall use the term, is that it instantiates
`components from a predefined, finite set. This characterization of configuration does not create
`new parts or modify old ones. Configuration tasks are similar to classification tasks in that
`instantiation includes the selection of classes. However, to solve a classification problem is
`merely to select one (or perhaps a few) from the predefined set of classes. To solve a configura(cid:173)
`tion problem is to instantiate a potentially large subset of the predefined classes. The search
`space of possible solutions to a configuration problem is the set of all possible subsets of compo(cid:173)
`nents. This is the power set of the predefined classes. Furthermore, multiple instantiations of the
`same part may be used in a solution, and different arrangements of parts count as different solu(cid:173)
`tions. Configuration problems are usually much harder than classification problems.
`
`608
`
`Page 11 of 72
`
`FORD 1017
`
`

`
`8.1
`
`Introduction
`
`609
`
`8.1.1 Configuration Models and Configuration Tasks
`
`Custom manufacturing and mass manufacturing are often seen as opposites. Custom manufactur(cid:173)
`ing tailors products to the specific and different needs of individual customers; mass manufactur(cid:173)
`ing achieves economies of scale when high-volume manufacturing techniques make it possible
`to reduce the unit costs of nearly identical products. An industrial goal common to many kinds of
`manufacturing is to combine the flexibility of custom manufacturing with the economics of mass
`production. An important strategy for this is to create lines of products that can be tailored to a
`customer's requirements by configuring customer-specific systems from a catalog of mass-pro(cid:173)
`duced parts. This approach has been called an a la carte or build-to-order marketing and manu(cid:173)
`facturing strategy.
`A la carte manufacturing requires special capabilities of an organization. For production,
`the required capabilities include the efficient means for managing of an inventory of parts, for
`bringing the parts together that are required for each order, for assembling the parts into prod(cid:173)
`ucts, and for testing the quality of the different assembled products. A well-recognized logistic
`requirement for this process is to accurately understand the customer's needs and to develop a
`prodgct specification that meets those needs. This step, which actually precedes the others, is the
`configuration step. The success and efficiency of the entire enterprise depends on configuration.
`Since flexible product lines can involve hundreds or thousands of different, configurable
`parts, there are many possibilities for errors in the configuration process. Errors in a configura(cid:173)
`tion can create costly delays when they are discovered at assembly time, at testing time, or by a
`customer. An effective configuration process reduces costs by reducing level of inventory, reduc(cid:173)
`ing the amount of idle manufacturing space, reducing the delay before customers' bills are paid,
`and better ensuring customer satisfaction.
`As these factors have been recognized, companies have sought automated and semi-auto(cid:173)
`mated configuration systems for routinely creating, validating, and pricing configurations to
`meet the differing requirements of their customers. One of the first and best known knowledge(cid:173)
`based configuration systems is the XCON system for configuring VAX computer systems
`(McDermott, 1981). Knowledge-based systems for configuration tasks are being built by many
`organizations.
`Configuration is a special case of design. In design the elements of the designed artifact are
`not constrained to come from a predefined set. They are subject only to the constraints of the
`manufacturing methods and the properties of the raw materials. The knowledge necessary for
`configuration tasks is more bounded than the knowledge for general design tasks. In general
`design tasks, the solution space is more open-ended. For example, designing a pickup truck from
`scratch is more open-ended than choosing options for a new one. In configuration tasks, much of
`the "design work" goes into defining and characterizing the set of possible parts. The set of parts
`must be designed so they can be combined systematically and so they cover the desired range of
`possible functions. Each configuration task depends on the success of the earlier task of
`designing configurable components.
`From a perspective of knowledge engineering, configuration tasks are interesting because
`they are synthetic or constructive tasks. They are tasks for which combinatorics preclude the pre(cid:173)
`-enumeration of complete solutions. Just as not all classification tasks are the same, not all config(cid:173)
`uration tasks are the same. Configuration models can be used as a basis for different kinds of
`tasks, not necessarily involving manufacturing and physical parts. For example, "configuring"
`
`Page 12 of 72
`
`FORD 1017
`
`

`
`610
`
`8
`
`CONFIGURATION
`
`therapies can be a part of a larger diagnosis and therapy task. Configuring alternative combina(cid:173)
`tions of steps for a plan can be an important part of a planning process. In such cases we refer to
`a configuration model for a task.
`Knowledge-engineering techniques are suitable for classification tasks and configuration
`tasks because most of the complexity in specifying how to carry out the task is in the domain
`knowledge rather than the methods themselves. The knowledge-level methods define roles for
`different kinds of knowledge and these roles help to control the way that the bodies of knowl(cid:173)
`edge interact and guide the search for solutions.
`
`8.1.2 Defining Configuration
`
`Selecting and arranging parts is the core of solving a configuration problem. Figure 8.1 presents
`an example of a configuration that is a solution to a configuration problem. In this example, the
`configuration has two top-level parts: Part-1 and Part-2. Each of these parts has subparts.
`
`Configuration-!
`
`Part-1
`
`Part-1-1
`
`Part-1-2
`
`Part-1-1-1
`
`~A
`
`B~
`
`Part-1-1-2
`
`Part-1-1-3
`-
`
`-
`
`A .... -A
`_Iiiii A w - ...
`
`B
`
`BL..-
`
`r B
`
`1111
`
`-
`
`--Ill A
`
`A
`·~
`
`---Ill B
`
`B
`Ill
`
`...
`A,..
`
`I
`
`Part-2
`
`I Ill
`A
`11 Part-2-1
`A
`
`B ~
`
`-
`
`....
`
`B ..
`
`Part-2-2
`
`B Ill-
`
`-
`
`111111 A
`
`...
`B ...
`c ..
`...
`
`I -
`
`D.,
`
`FIGURE 8.1. An example of a configuration using a port-and-connector model. In this figure, all compo(cid:173)
`nents are shown as boxes and the top-level component is Configuration-!. It has two parts, Part-1 and Part-
`2. The arrangement of the configuration is indicated by the part-of hierarchy, displayed graphically by the
`containment of boxes and by the interconnections among parts. Each part has a number of ports, labeled
`A,B,C, or D. For example, the B port ofPart-1-1-1 is connected to the A port ofPart-1-1-3.
`
`Page 13 of 72
`
`FORD 1017
`
`

`
`8.1
`
`Introduction
`
`611
`
`Configuration domains differ in their representations of arrangements. For example, Figure
`8.1 represents arrangements using a port-and-connector model. The ports on each part corre(cid:173)
`spond to the different roles that subparts can have with respect to each other. Like all models
`governing arrangements, a port-and-connector model constrains the ways things can be con(cid:173)
`nected. Components can be connected only in predefined ways. Ports may have type specifica(cid:173)
`tions indicating that they can be connected only to objects of a particular kind. Each port can
`carry only one connection.
`Variations in the search requirements and the available domain knowledge for different
`configuration tasks lead to variations in the methods. Nonetheless, certain regular patterns of
`knowledge use appear across many different configuration tasks. Configuration methods work
`through recognizable phases. They map from user specifications to abstract descriptions of a
`configuration, and they refine abstract solutions to detailed configurations specifying arrange(cid:173)
`ments and further requirements. We distinguish between solution expansion and solution refine(cid:173)
`ment phases, not to imply that they are independent, but to emphasize the distinct meanings of
`part requirement hierarchies, functional abstraction hierarchies, and physical containment hierar(cid:173)
`chies. Addition of required components is often a specialized process and can involve goals for
`both··correcting and completing a specification. Refinements of specifications include the consid(cid:173)
`eration of alternative arrangements as well as selection among alternative implementations. Con(cid:173)
`figuration methods must mix and balance several kinds of concerns and different bodies of
`knowledge.
`Figure 8.2 shows the relevant spaces for defining configuration problems. It is a useful
`starting framework from which we shall consider variations in the following sections. In some
`domains there is no separate specification language: Specifications are given in the language of
`
`N•----------------------------~----------------------------------------------------------------------------------
`
`Specifications
`
`0
`
`'
`'
`
`Configuration space
`
`Specifications
`
`\
`
`'
`Specification to
`•truoture m•tching
`
`Addition~~
`!
`
`specifications
`
`Abstract and
`partial solutions
`
`t t· Solution
`t and expansion
`t
`
`refinement
`
`Abstraction
`hierarchy
`
`Component
`hierarchy
`'
`'
`'
`
`FIGURE 8.2. Spaces in configuration tasks.
`
`~ m
`
`Arrangement
`' -
`~del
`
`Page 14 of 72
`
`FORD 1017
`
`

`
`612
`
`8
`
`CONFIGURATION
`
`parts and arrangements and the task begins with a partial configuration. In that case, we omit the
`boundary in the figure between the specification space and the configuration space. The outer
`oval in the configuration space signifies that the representations for partial and expanded solu(cid:173)
`tions are mixed together. Most configuration methods work incrementally on candidates,
`expanding the candidates to include more parts and refining the specifications to narrow the
`choices.
`By analogy with names for classification methods, the pattern of knowledge use suggested
`by Figure 8.2 could be called heuristic configuration to emphasize the use of heuristic knowl(cid:173)
`edge to guide the generation and testing of possible configurations. It could also be called hier(cid:173)
`archical configuration to emphasize the importance of reasoning by levels, both component
`hierarchies and abstraction hierarchies. For simplicity, we just use the term configuration.
`
`8.2 Models for Configuration Domains
`This section discusses what configuration is and what makes it difficult.
`
`8.2.1 Computational Models of Configuration
`
`To understand configuration tasks we need a computational model of the search spaces and the
`knowledge that is used. Our model has the following elements:
`
`' ... i A specification language
`,-. A submodel for selecting parts and determining their mutual requirements
`A submodel for arranging parts
`A submodel for sharing parts across multiple uses
`
`We begin by describing these elements generally and simply. We then introduce the "widget"
`domain as a concrete instantiation of a configuration model. We use this domain to illustrate rea(cid:173)
`soning and computational phenomena in configuration tasks. Afterward, we draw on the
`domains from the previous section to extract examples of kinds of knowledge and the use of
`knowledge.
`A specification language for a configuration task describes the requirements that configu(cid:173)
`rations must satisfy. These requirements reflect the environment in which the configured product
`must function and the uses to which it will be put. A specification may also indicate which opti(cid:173)
`mizing or due-process criteria should be used to guide the search, such as minimizing cost or
`space or preferring some possibilities over others. (See the exercises.)
`A functional specification describes capabilities for desired behaviors. For example, rather
`than saying that a computer configuration needs a "printer," a functional specification might say
`that the computer needs to be able to print copies. The printing function may be further special(cid:173)
`ized with qualifiers about speed, resolution, directionality, character sets, sizes of paper, color or
`black and white, and so on. One advantage of describing systems in terms of functions rather
`than in terms of specific classes of manufactured parts is that functions can anticipate and sim(cid:173)
`plify the addition of new classes of components to a catalog. When a functional specification
`language is used, the configuration process must have a means for mapping from function to
`structure.
`
`Page 15 of 72
`
`FORD 1017
`
`

`
`8.2 Models for Configuration Domains
`
`613
`
`A specification language is not defined independently of the other submodels. Some con(cid:173)
`figuration models use the same language for describing specifications and for describing config(cid:173)
`urations. This approach avoids the function-to-structure mapping by associating each part with a
`list of key functions. The most common approach is called the keymcomponent approach. This
`approach has two parts: (1) For every major function there is some key component, and (2) all
`the key components (or abstract versions of them) are included in the initial partial configuration
`that specifies a configuration. A specification is assumed to include all the key parts. To complete
`a configuration, a configuration system satisfies the prerequisites of all the key parts it starts with
`as well as the parts it needs to add to the specification, and it also determines a suitable arrange(cid:173)
`ment for all the included parts.
`A sub model for parts specifies the kinds of parts that can be selected for a configuration
`and the requirements that parts have for other parts. Some parts require other parts for their cor(cid:173)
`rect functioning or use. For example, computer printed circuit boards may require power sup(cid:173)
`plies, controllers, cables, and cabinets. A part model defines required-component relations, so
`that when a configuration process considers a part description, it can determine what additional
`parts are needed. Required parts can be named explicitly or described using the specification lan(cid:173)
`guage. Descriptions indicate which parts are compatible with each other and what parts can be
`substituted for each other under particular circumstances.
`A submodel for spatial arrangements provides a vocabulary for describing the place(cid:173)
`ment of parts and specifies what arrangements of parts are possible. Together, the arrangement
`model and the specification language form a basis for describing which arrangements are accept(cid:173)
`able and preferred. They make it possible to determine such things as where a part could be
`located in an arrangement, whether there is room for another part given a set of arranged parts,
`and which parts in a set could be added to an arrangement. Arrangement models constrain the set
`of possible configurations because they govern the consumption of resources, such as space,
`adjacency, and connections. These resources are limited and are consumed differently by differ(cid:173)
`ent arrangements. Arrangement models are a major source of constraints and complexity in con(cid:173)
`figuration domains.
`A submodel for sharing expresses the conditions under which individual parts can be
`used to satisfy more than one set of requirements. In the simplest case, part use is mutually exclu(cid:173)
`sive. For example, a cable for one printer cannot be used simultaneously to connect to another
`printer. For some applications, mutual exclusion is too restrictive, such as with software pack(cid:173)
`ages that may use the same memory, but at different times. The following exemplifies a range of
`categories of use and sharing for configuration systems:
`
`i'.'.i Exclusive use: Components are allocated for unique uses.
`''' Limited sharing: Parts can be shared between certain functions but not across others.
`~21 Unlimited sharing: A component can be allocated for as many different purposes as
`desired.
`Serial reusability: A component can be allocated for several different purposes, but only
`for one purpose at a time.
`Measured capacity: Each use of a component uses up a fraction of its capacity. The com.:.
`ponent can be shar~ as long as the total use does not exceed the total capacity. The electri(cid:173)
`cal power provided by a supply is an example of a resource that is sometimes modeled this
`way.
`
`Page 16 of 72
`
`FORD 1017
`
`

`
`614
`
`8
`
`CONFIGURATION
`
`Specification Language
`
`Key components
`
`in functional hierarchy ~ CAJ w w w
`
`A widget component
`
`Parts Submodel
`
`A-1 A-2
`
`B-1 B-2
`
`C-1 C-2
`
`D-1 D-2
`
`Part-A-1
`
`Part-B-1
`
`Part-C-1
`
`Required parts: 2 B's
`Size: Half slot
`
`Required parts: 2 C's
`Size: Half slot
`
`Required parts: None
`Size: Half slot
`
`Part-D-1
`
`Required parts:
`B & 2 C's
`Size: Half slot
`
`Catalog
`
`~ Part-A-2
`
`Part-B-2
`
`Part-C-2
`
`Part-D-2
`
`Required parts: 3 B's
`Size: Full slot
`
`Required parts: None
`Size: Full slot
`
`Required parts: None
`Size: Half slot
`
`Required parts: C 1
`Size: Double slot
`
`Arrangement Submodel
`
`Widget
`case -z_______;eft
`
`Extension plug
`
`(__
`
`Must occupy last
`unused top half slot
`of previous case
`
`Half slot Full slot
`
`Double slot
`
`Empty slots
`
`Right
`
`Extension case
`
`Sharing Submodel
`
`All parts are allocated for exclusive use.
`
`FIGURE 8.3. The widget model, W-1, illustrates phenomena in configuration problems.
`
`A particular domain model may incorporate several of these distinctions, assigning differ(cid:173)
`ent characteristics to different parts. Sometimes these distinctions can be combined. One way to
`model how different software packages could share memory would be to post capacity con(cid:173)
`straints indicating how much memory each package needs. The system allocation for serial
`usage would be determined as the maximum capacity required for any software package. This
`approach mixes serial reusability with measured capacity.
`fu summary, our framework for computational models of configuration has four sub(cid:173)
`models: a specification language, a submodel for parts and requirements, a submodel for ar-
`
`Page 17 of 72
`
`FORD 1017
`
`

`
`8.2 Models for Configuration Domains
`
`61.5
`
`rangement, and a submodel for component sharing. We return to these models later to describe
`variations on them and to identify the ways in which they use domain knowledge. In the next
`section, we instantiate our configuration model for the widget domain and use it to illustrate
`important phenomena in configuration tasks.
`
`8.2.2 Phenomena in Configuration Problems
`
`This section describes reasoning phenomena that arise in configuration problems. These phe(cid:173)
`nomena are illustrated in the context of the sample domain in Figure 8.3. Figure 8.3 presents W-
`1, a model for configuring widgets. We use W-1 to illustrate configuration phenomena in the fol(cid:173)
`lowing discussion and in the exercises at the end of this section.
`Widget requirements are specified in terms of the key generic components A, B, C, and D.
`The W-1 parts submodel provides a catalog with two choices of selectable components for each
`generic component. Thus, generic component A can be implemented by either A -1 or A-2, B can
`be implemented by B-1 or B-2, and so on. Each component requires either a half slot, a full slot,
`or a double slot. Figure 8.4 presents the rules for the widget model.
`·. When components are arranged in the widget model, there are sometimes unavoidable
`gaps. When configurations are combined, these gaps are sometimes complementary. For this rea(cid:173)
`son it is not always adequate to characterize the amount of space that a configuration takes up
`with a single number. Figure 8.5 defines several terms related to measures of space in the widget
`model. Occupied space refers to the number of slots occupied by components, including any
`required extension plugs