The Formative Years
`
`by
`John McDermott
`Department
`of Computer Science
`Carnegie-Mellon
`University
`Pittsburgh, Pennsylvania
`15221
`
`that configures VAX-I 1
`program
`is a rule-based
`RI
`computer
`systems. Given a customer’s purchase order,
`it
`determines what,
`if any, substitutions and additions have to
`be made to the order to make it consistent and complete and
`produces a numnber of diagrams showing
`the spatial and
`logical
`relationships among
`the 90 or so components
`that
`typically constitute a system. The program has been used on a
`regular basis by Digital Equipment Corporation’s manufac-
`turing organization
`since January of 1980. Rl has sufficient
`knowledge of the configuration
`domain and of the peculari-
`ties of the various configuration
`constraints
`that at each step
`in the configuration
`process, it simply recognizes what to do;
`thus it requires little search in order to configure a computer
`system.
`task and the
`takes to the configuration
`The approach RI
`way its knowledge
`is represented has been described elsewhere
`[McDermott
`80a, MC Dermott 80b]. This article provides a
`detailed
`description
`of Rl’s design and
`implementation
`history. As will become apparent, only a part of the effort
`to
`develop an expert configurer
`for Digital dealt in a direct way
`with AI
`issues. The other, and in fact larger, part involved
`providing
`the ever widening circle of individuals who came in
`
`Equipment
`by Digital
`of Rl was supported
`The development
`of OPS4 and
`Corporation.
`The research
`that
`led to the development
`OPS5,
`the languages
`in which Rl
`is written, was sponsored
`by the
`Defense Advanced Research Projects Agency
`(DOD), ARPA Order
`No. 3597, and monitored
`by
`the Air Force Avionics
`Laboratory
`under Contract
`F33615-78-C-1151.
`The
`views and
`conclusions
`contained
`in this document are those of the author and should not be
`interpreted
`as representing
`the official
`policies, either expressed or
`implied,
`of Digital Equipment
`Corporation,
`the Defense Advanced
`Research Projects Agency,
`or
`the U.S. Government
`
`of why AI
`the program with an understanding
`contact with
`tools are appropriate
`for the task and why the use of AI tools
`demands a change
`in attitude
`toward
`the programming
`enterprise.
`
`Rl’s Development
`
`Rl’s development went through six distinct stages. During
`the first stage, December 1978 through April 1979, a strategy
`for attacking Digital’s configuration
`problem was formulated
`and a program with minimal knowledge of the configuration
`domain was written
`to demonstrate
`the potential
`of a
`knowledge-based
`approach. During
`the second stage, May
`1979 through September 1979, a large amount of knowledge
`was added
`to
`the program. October and November
`1979
`constituted
`the validation
`stage; Digital put RI
`through an
`test and determined
`that
`it was sufficiently expert
`extensive
`to be used on a regular basis to configure VAX-l
`l/ 780’s. The
`fourth stage, January 1980 through May 1980, was the period
`during which
`the question of how
`to
`integrate Rl
`into
`Digital’s organizational
`structure was seriously addressed for
`the
`first
`time. During
`the
`fifth stage, June 1980 through
`December 1980, the organizational
`plans that evolved during
`the previous stage were implemented. The sixth stage, which
`began in January 198 1 and has not yet ended, is the period of
`Digital’s
`initial self-sufficiency with
`respect to Rl.
`In
`this
`section, some of
`the more significant events that occurred
`within each stage will be described and the main lesson or
`lessons learned during each stage will be discussed.
`
`Initial Contact
`
`Digital
`
`differs significantly
`
`from most other computer
`
`Al MAGAZINE
`
`Summer 1981
`
`21
`
`AI Magazine Volume 2 Number 2 (1981) (© AAAI)
`
`AI Magazine Volume 2 Number 2 (1981) (© AAAI)
`
`CONFIGIT 1046
`
`1
`
`

`

`its
`it allows
`flexibility
`the degree of
`in
`manufacturers
`rather
`than marketing a
`customers
`in component
`selection;
`number of “standard
`systems” with a limited number of
`options, Digital markets processors with a relatively* large
`number of options, and allows the customer to tailor a system
`to his needs. One result of this strategy
`is that most of the
`systems it sells are one of a kind, and consequently each poses
`a distinct configuration
`problem. Since configuring computer
`systems is time-consuming,
`Digital made several efforts
`to
`develop a computer program
`that could perform
`the task.
`None of these attempts were successful, and in retrospect,
`it
`seems clear that the lack of success was due to the fact that the
`task is knowledge
`intensive and thus extremely difficult
`to
`program with
`traditional
`software
`tools.
`Early in 1978 Sam Fuller, who was then a faculty member
`in the Computer Science Department
`of CMU, accepted a
`position at Digital. As he became aware of the problem
`that
`Digital was having with automating
`the configuration
`task, it
`occurred to him that a knowledge-based approach
`to the task
`might make the problem
`tractable.
`In the Fall of 1978, he
`proposed
`both
`to Herb Shanzer,
`the manager at Digital
`responsible for solving the configuration
`problem, and to the
`production
`system group at CMU
`that they meet to discuss
`the possiblity of CMU developing a program
`that could do
`the configuration
`task. Mike Rychener and I went to Digital
`in December of 1978 to meet with Shanzer. After spending
`half a day being
`told about
`the nature and scope of the
`configuration
`problem, Rychener and
`I agreed
`that
`the
`problem had characteristics which made a knowledge-based
`approach appropriate. We proposed
`that Digital support an
`effort at CMU
`to develop a configuration
`expert Shanzer
`wanted
`to believe that we could develop such a program, but
`didn’t
`(at
`least not enough
`to provide
`funding). We then
`offered
`to develop a simple prototype
`system within a few
`months
`that would demonstrate
`the feasability of a know-
`ledge-based approach. After some discussion, it was decided
`that we should
`focus our attention
`on
`the problem
`of
`configuring VAX-l
`l/780
`systems (rather
`than
`tackling
`the
`bigger and more serious problem of configuring PDP-11
`systems). Shanzer offered
`to make whatever
`information we
`needed available
`to us and appointed Dick Caruso, an
`engineer who had worked on the configuration
`problem,
`to
`coordinate
`the information
`transfer After returning
`to CMU,
`Rychener and I decided to take a two-pronged
`approach
`to
`the problem. Rychener would work on developing a program
`with a general understanding
`of computer architecture, while
`I focused on developing
`the promised prototype. Rychener’s
`work resulted in IPSML, a system that supports the symbolic
`description and manipulation
`of computer structures at the
`PMS (processor-memory-switch)
`level [Rychener 791.
`During December,
`I spent several days at Digital
`learning
`the rudiments of the configuration
`task. Caruso had done a
`great deal of work
`in attempting
`to uncover the structure of
`the task. He had broken
`the task up into a number of smaller
`subtasks and had generated descriptions
`of
`the kinds of
`actions called
`for within
`each subtask. After
`I had a
`reasonable understanding of the structure of the configuration
`task, Caruso gave me two VAX-l
`l/780 configuration man-
`
`22
`
`Al MAGAZINE
`
`Summer 1981
`
`the
`about
`information
`a wealth of
`uals which contained
`details of the task After discussing the content of the manuals
`with him,
`I went back
`to CMU
`to build
`the prototype
`configurer.
`the
`implement
`to use to
`language
`The
`issue of what
`configuration
`program was never in question. One of the
`appeals of the configuration
`task was that it would give us an
`opportunity
`to build an OPS production system for a non-toy
`task. The OPS
`language has been described at
`length
`elsewhere [Forgy 81, Forgy 771; it is a general-purpose,
`rule-
`based
`language which provides a rule memory, a global
`working memory, and an interpreter
`that
`tests the rules to
`determine which ones are satisfied by a set of the descriptions
`in working memory. A
`rule
`is an
`IF-THEN
`statement
`consisting of a set of conditions
`(patterns that can be matched
`by the descriptions
`in working memory) and a set of actions
`that modify working memory. On each cycle, the interpreter
`selects one of the satisfied rules and applies it. Since applying
`a rule results in changes to working memory, different subsets
`of
`rules are satisfied on successive cycles OPS does not
`impose any organization
`on
`rule memory;
`all
`rules are
`evaluated on every cycle If more than one rule is satisfied (01
`can be instantiated
`in more than one way) on a given cycle,
`OPS uses a set of conflict
`resolution strategies to determine
`which rule to apply From Rl’s point of view, it often makes
`no difference which
`rule is applied; RI does, however,
`rely
`heavily on the special case strategy. Given two rule instantia-
`tions, one of which contains a proper subset of the data ele-
`ments contained by the other, OPS will select the instantiation
`containing more data elements on the assumption
`that
`it is
`specialized
`for the particular situation
`it is in
`In OPS4, the
`version of OPS used to implement
`the initial version R 1, con-
`dition elements are represented as lists of constants and
`and variables.
`There are four characteristics of the configuration
`strongly
`influenced
`the design of RI:
`
`task that
`
`the configurer
`if prerequisite
`
`incomplete;
`frequently
`l Orders are
`to an order
`must add components
`components are missing.
`l The data that a configurer needs consists of descrip-
`tions of each of the components on an order (together
`with descriptions of any components
`that might need
`to be added).
`large number of constraints on how
`l The relatively
`components
`can be associated are conditional
`on
`characteristics of the components and on the ways in
`which already configured
`components
`have been
`associated.
`into a set
`task can be decomposed
`l The configuration
`of loosely coupled,
`temporally ordered subtasks.
`
`is
`l/780
`The number of components supported on the VAX-l
`quite
`large (about 400 in December 1978). Since RI would
`need access to descriptions of both the set of components on
`an order and any components
`it might have to add, it was
`decided that the descriptions of components should be stored
`in a data base that R 1 could access Each description
`is a set of
`
`2
`
`

`

`attribute/ value pairs; Rl can access these descriptions by
`name or by specifying a partial description of a component.
`Since the constraints on how components can be associated
`are conditional
`on the characteristics of components and on
`the current state of the configuration,
`it was decided
`that
`descriptions
`of
`the components
`ordered and of partial
`configurations would be held in working memory and that
`each of the constraints would be formulated as an OPS4 rule.
`Since the constraints are subtask specific, the rules would be
`placed into groups on the basis of the subtask to which
`they
`were
`relevant. This would allow each rule
`to presuppose
`certain
`things about
`the current state of the configuration,
`thus reducing
`the number of condition elements required
`in
`each rule. It was assumed that Rl’s basic strategy would be
`Generate and Test, that
`is, that some of the rules associated
`with each subtask would propose extending a partial configu-
`ration
`in a particular way, and that other rules would examine
`the proposed extension and either accept or reject it.
`Implementing
`the initial version of R 1 was straightforward
`The
`information
`that
`I had gotten
`from Caruso about
`the
`configuration
`task
`(augmented with occasional
`telephone
`conversations) was sufficient
`to write a program
`that could
`correctly configure
`simple orders. This prototype
`program
`had about 250 rules and
`took about
`three man-months
`to
`develop. An English translation of one of the rules is shown in
`Figure 1. In April 1979 the program was demonstrated
`at
`Digital
`to a group of about 60 people and was received with
`guarded enthusiasm. Though no one was convinced
`that the
`program could be extended so that
`it could configure
`really
`complex orders,
`the program showed enough promise
`that
`Digital decided
`to support
`further work on it.
`It seems almost unbelievable
`to me now
`that we almost
`focused our initial efforts on the PDP-11 world rather than on
`the VAX-l
`l/780. Though
`it did not become clear until
`later
`just how fortuitous
`our choice was, it is worth making
`the
`point here since if we had focused on a PDP-11,
`it is likely
`that RI would never have found a home at Digital. The VAX-
`11 nd PDP-I 1 configuration
`tasks,
`in
`the abstract, are
`essentially
`identical
`But
`the PDP-11
`problem
`is more
`complex
`for
`two reasons:
`
`that are supported on
`l The number of components
`PDP-11 systems is more than an order of magnitude
`larger
`than
`the number currently supported on the
`VAX-l 1; thus tackling
`the PDP-I 1 task would have
`required attending
`to many more details right
`from
`the beginning.
`of VAX-11
`the configuration
`on
`l The constraints
`systems are more specific (less ambiguous)
`than the
`contraints
`for the PDP-11 systems; thus fewer rules
`are required
`for
`the VAX-l 1 task.
`
`It has turned out the the VAX-l 1 task was a perfect size. It
`requires enough
`knowledge
`so that a program
`that can
`perform
`the task is interesting But the amount of knowledge
`required
`for the task and the specificity of the configuration
`constraints
`is such that the problem does not push very hard
`on state-of-the-art
`knowledge-engineering
`techniques.
`
`I
`
`PUT-UB-MODULE-6
`
`IF:
`
`AND
`
`AND
`
`TBITH
`
`IN
`
`IS
`CONTEXT
`THE MOST CURRENT ACTIVE
`PUTTING UNIBUS MODULES
`IN THE
`BACKPLANES
`IN SOME BOX
`IT HAS BEEN DETERMINED WHICH
`MODULE TO TRY TO PUT
`IN A
`BACKPLANE
`IS A MULTIPLEXER
`AND THAT MODULE
`TERMINAL
`INTERFACE
`IT HAS NOT BEEN ASSOCIATED
`PANEL SPACE
`AND THE TYPE AND NUMBER OF BACKPLANE
`SLOTS
`IT REQUIRES
`IS KNOWN
`AND THERE ARE AT LEAST THAT MANY
`SLOTS AVAILABLE
`1M A BACKPLANE
`OF THE APPROPRIATE
`TYPE
`AND THE CURRENT UNIBUS
`LOAD ON THAT
`BACKPLANE
`IS KNOWN
`AND THE POSITION
`OF THE BACKPLANE
`THE BOX
`IS KNOWN
`
`I
`
`THEN:
`
`ENTER THE CONTEXT OF VERIFYING
`PANEL SPACE FOR A MULTIPLEXER
`
`From Novice to Expert
`
`be-
`initial demonstration
`several people at RI’s
`Though
`lieved that it was in Digital’s
`interest to support
`further work
`on
`the program. Dennis O’Connor
`(representing System
`Manufacturing)
`emerged as RI’s principal sponsor. O’Connor
`established a steering committee consisting of himself, Sam
`Fuller
`(representing Central Engineering), and Lou Reagan
`(representing Order Processing Administration).
`Kent Mc-
`Naughton,
`a member of O’Connor’s group, was asked to
`coordinate
`the project.
`problem at Digital
`The magnitude
`of
`the configuration
`created a certain amount of pressure to move beyond
`the
`demonstration
`stage as quickly as possible. Since I lacked an
`understanding
`of the complexity of the task, it was difficult
`for me to estimate just how long it might
`take to develop the
`program
`to a point where its performance was comparable
`to
`that of skilled humans. The initial version of RI appeared to
`have most of the basic knowledge needed;
`that
`is, it could
`configure
`simple systems correctly. On
`the basis of
`the
`number and kinds of mistakes
`it made on more complex
`orders,
`I guessed that
`it had about half
`the knowledge
`it
`needed, and suggested that an adequate version of Rl could
`be developed within
`four or
`five months. After
`some
`discussion,
`that suggestion somehow became a commitment
`to deliver to Digital, by the end of September, a program
`that
`(1) could correctly configure at least 75% of the orders it was
`given, and
`(2) could be easily modified
`or extended
`to
`configure any orders that
`it configured
`incorrectly. We met
`this deadline with a day and a half
`to spare.
`
`Al MAGAZINE
`
`Summer 1981
`
`23
`
`3
`
`

`

`those five months actually had two distinct
`The task for
`parts. It was clear that a considerable amount of knowledge of
`configuration
`constraints would have
`to be added
`to
`the
`program and that some of the knowledge
`the program had
`would have to be modified;
`this is the part of the task that
`CMU committed
`to. The other part of the task was to extend
`the data base of component descriptions.
`In May 1979, there
`were 420 components supported on the VAX-l 11780; the data
`base used by the initial version of Rl had fewer
`than 100
`component
`descriptions. Caruso was assigned
`the task of
`producing a complete data base Since Digital had no single
`source containing all of the information
`required (8-10 pieces
`of information
`about each component), and since much of the
`information was not in machine readable form, collecting
`the
`information was time-consuming. About
`three man-months
`of effort were required
`to create the complete data base.
`The task of extending RI’s configuration
`constraint know-
`ledge proceeded
`in parallel with the data base creatoin
`task
`There were two senses in which Rl’s constraint knowledge
`was incomplete.
`(1) the sets of
`rules that enabled RI
`to
`perform particular
`subtasks were sufficient
`for simple sys-
`tems, but needed
`to be augmented
`to handle
`systems
`consisting of components with more complex
`interrelation-
`ships. (2) Rl had no knowledge of how
`to configure some
`types of components, and thus needed to acquire sets of rules
`that would enable it to perform
`the subtasks implied by those
`component
`types. My approach
`to extending RI’s knoweldge
`base was esentially the same as the approach
`taken by other
`expert system builders
`[Feigenbaum
`771. Rl was given a
`number of orders
`to configure.
`Its output was shown
`to
`configuration
`experts who were asked
`to evaluate
`the
`adequacy of
`the configurations. When an expert
`found a
`problem, we would
`talk about
`it. Such discussions always
`resulted in the characterization
`of the situations
`in which Rl’s
`actions were inappropriate,
`and an indication of what actions
`would be appropriate. Ordinarily, especially in the beginning,
`a considerable amount of configuration
`knowledge came to
`light during each interaction with an expert. Thus after each
`interaction
`several rules could be written; one to correct the
`problem manifestation and a number of others which, though
`not directly related to the problem at hand, were associated, in
`the mind of the expert, with the problem situation By the end
`of September 1979, Rl had a database of 420 component
`descriptions and its rule memory contained about 750 rules
`The fact that Rl’s knowledge
`tripled during this stage came as
`something of a surprise. Though
`it had been clear in May that
`RI’s knowledge was incomplete, still RI was able to correctly
`configure systems. It is interesting
`that Rl needed twice as
`much knowledge
`to deal with special situations as it did to
`perform
`the basic task.
`this stage that the method Rl
`It became apparent during
`uses is Match
`[Newell 691. As mentioned, an initial assump-
`tion had been that Rl would use Generate and Test as its
`principal problem solving method. Each set of rules included
`a rule whose function was to test to determine
`if the current
`subtask had been accomplished.
`In the demonstration
`version
`of RI, each of these rules was a (vacuous) general case of the
`other rules associated with
`the subtask and thus fired only
`
`24
`
`Al MAGAZINE
`
`Summer 1981
`
`I assumed
`rules had been applied.
`after all other applicable
`that as the system was developed,
`(I) at least some of these
`rules would have to be modified so that they could recognize
`when
`the goals of their subtasks had been achieved and (2)
`other test rules would have to be added that could recognize
`when an
`incorret
`configuration
`was being generated and
`inititate actions
`that would get Rl back on the track. As it
`turned out, neither of these was necessary.
`The
`important
`lesson learned during
`this stage is that
`Match
`is an appropriate
`problem solving method
`for some
`class of domains. The configuration
`task is constructive;
`it has
`the following
`characteristics:
`
`l
`
`It is possible to impose a partial ordering on the set of
`components
`to be configured such that if the compo-
`nents are configured
`in
`that order,
`they can be
`configured without any backtracking.
`l The partial ordering can be defined, dynamically, on
`the basis of
`the
`total
`set of components
`to be
`configured and the associations already made among
`those components.
`
`to configure a set of components
`Because it is possible
`correctly, without
`backtracking,
`if enough
`knowledge
`is
`brought
`to bear at each step to determine which component
`should be configured next, there is no need within any subtask
`to
`test whether
`a just configured
`component
`has been
`configured correctly. Furthermore,
`since each subtask extends
`the configuration
`in whatever ways are appropriate within the
`confines of
`the subtask,
`there
`is no need
`for a rule
`to
`determine whether
`the goal of the subtask has been accom-
`plished. When none of the rules associated with the subtask
`are satisfied, all that can be done has been done. One positive
`consequence of the use of the Match method
`(in addition
`to
`the elimination
`of search) was that adding knowledge
`to RI,
`once it was extracted
`from
`the experts, was straightforward.
`Since each rule defines
`the set of situations
`to which
`it is
`relevant, if a rule is applicable,
`it should and will fire (unless it
`is a general case of some more specific rule that fires first and
`changes the current situation so that the more general rule is
`no longer applicable).
`
`Validation
`
`put Rl
`1979, Digital
`During October and November
`through a formal validation procedure. The purpose of this
`test was to determine whether RI was expert enough
`in the
`configuration
`task to be used in place of human experts The
`validation process consisted of giving RI
`the 50 most recently
`booked orders and having a group of six experts carefully
`examine Rl,‘s output
`for correctness. The experts were given
`orders in groups of 10; they spent 8 hours on the first order, 2
`hours on the second, and then about
`I hour on each of the
`other 48. After checking a group of 10 orders, they forwarded
`errors due to incorrect configuration
`knowledge
`to me and
`errors due to inaccurate descriptions
`in the component data
`base to Vaidis Mongirdas,
`the engineer who replaced Caruso
`when Caruso moved
`to another
`job at Digital. The problems
`
`4
`
`

`

`were fixed and the incorrect orders rerun with tha next group
`of 10.
`impressed with Rl’s perfor-
`The experts were extremely
`mance. RI made 12 mistakes (all of which were easily fixed) in
`configuring
`the 50 orders All but two of the mistakes were at
`a level of detail below that at which humans responsible
`for
`configuring systems work out the configurations
`The team of
`experts pointed
`out
`that
`in addition
`to providing more
`detailed configurations
`than the human configurers, R 1 (even
`with its still imperfect knowledge) was likely to do a better job
`than the humans singe they are subject to lapses of attention.
`The conclusion drawn
`from
`the validation process was that
`Rl should begin to be used on a regular basis in at least one of
`the Final Assembly and Test (FA&T) plants and that
`its use
`should be extended
`to other FA&T plants as soon as this was
`feasible.
`less than a man-year’s effort, Rl had
`With something
`developed
`to a point where it could begin to be used in place
`of human experts. Though RI’s task domain was very narrow,
`the configuration
`task has a considerable amount of complex-
`ity and thus requires a significant amount of knowledge.
`It is
`unlikely,
`I
`think,
`that a program
`using more
`traditional
`software
`tools could be developed
`in anywhere near the same
`time
`frame. Aside
`from
`the
`fact
`that
`the
`task
`is highly
`conditional
`(there are, on the average,
`three possible paths
`that could be followed on each of the typically 1000 steps in
`the
`task), a program
`that can perform
`the
`task must
`necessarily be developed
`incrementally. Given the amount of
`knowledge
`required and
`the
`fact
`that
`the knowledge
`can
`apparently be extracted from
`the experts only as they see from
`mistakes
`the program makes what knowledge
`is lacking,
`it
`would seem that any attempt
`to develop a program
`that is not
`strongly
`recognition driven would be doomed
`to failure
`
`Organizing
`
`to use Rl
`
`first year of RI’s
`the
`during
`The concern at Digital
`development was almost exclusively with whether and how
`well Rl would be able to perform
`the configuration
`task.
`Little attention was paid to the question of how RI would be
`integrated
`into
`the system, configuration
`and assembly
`process. At
`the end of
`the validation
`stage, this question
`became prominent.
`There were
`two
`issues that had
`to be
`attended
`to:
`
`l
`
`to find a way to begin to
`for Digital
`It was important
`use RI that would disrupt
`the existing process as little
`as possible and
`that would provide a framework
`within which Rl’s
`configuration
`expertise
`could
`grow.
`to establish a group able
`for Digital
`do It was important
`to continue
`the development of Rl and to extend its
`capabilities
`to other computer systems (eg, the PDP-
`11).
`
`In each of
`The issue of use was relatively easy to deal with.
`Digital’s FA&T plants, people called technical editors confi-
`gure each system to be built and give their configuration
`
`to technicians who actually assemble the systems in
`diagrams
`one of Digital’s FA&T plants The person who had been the
`technical editor
`for VAX-I
`l/780 systems became Rl’s “super-
`visor.” The
`role of
`the supervisor was to examine Rl’s
`configuration
`diagrams
`for correctness. Correct output was
`given
`to
`the
`technicians
`for use in assembly Data base
`problems were
`reported
`to and
`fixed by Mongirdas;
`rule
`problems were
`reported
`to and
`fixed by me during my
`monthly
`visits to Digital
`the develop-
`to continue
`The issue of establishing a group
`ment of R 1 was more problematic. Several months were spent
`in attempting
`to define
`the functions
`that
`the group would
`perform,
`determining where
`the group should be located
`within Digital’s organizational
`structure, and searching for a
`set of individuals, particularly a manager, who could form the
`nucleus of the group.
`It became clear that
`the group would
`have three principal
`functions:
`
`l data collection
`. program maintenance and development
`l process development
`
`involve extending Rl’s data
`task would
`The data collection
`base of component descriptions-the
`task that the engineers
`assigned to help with Rl’s development had been doing all
`along. the program maintenance and development
`task would
`involve making modifications
`to Rl’s rules as inadequacies in
`its knowledge were discovered and extending RI so that it
`could configure
`systems other
`than
`the VAX-l
`l/780. The
`people performing
`this task would essentially take over the
`role that CMU played;
`to do this, it would be necessary for
`them to have a solid understanding
`of the OPS language. The
`third
`task, process development, was the least well defined.
`It
`was clear that
`in order for RI
`to be an effective tool,
`it was
`necessary that
`it be easily accessible to people in a number of
`different Digital
`organizations
`(eg, manufacturing,
`engi-
`neering, sales). The process development
`task was to invent
`ways of facilitating
`information
`flow.
`While Digital was concerning
`itself with organizational
`matters, Rl was reimplemented at CMU. The impetus for the
`reimplementation was the availability of OPS5, a new version
`of OPS. OPS5 differs
`from OPS4 primarily
`in the way the
`conditions of a rule can be expressed
`In OPS4, a condition
`element is represented as a list of symbols; in OPS5, it may be
`represented either as a list of symbols or as an object with
`associated attribute/ value pairs. If an attribute name appears
`in a condition element,
`it is interpreted by OPS5 as the name
`of a working memory element
`field. A condition element
`is
`instantiated
`by a working memory element
`if each value
`(constant or variable)
`in the condition element
`is equal to or
`can be bound
`to the symbol in the working memory element
`in the specified field OPS5 is a significant
`improvement over
`OPS4 both
`in ease of use and in the intelligibility of the rules.
`Since the only difference between OPS4 and OPS5 is in the
`way in which conditions are expressed, it would have been
`possible, in a few weeks time,
`to simply translate
`the OPS4
`rules into OPS5. However, during
`the course of developing
`Rl, a great deal of knowledge was added
`that Rl was
`
`Al MAGAZINE
`
`Summer 1981
`
`25
`
`5
`
`

`

`this
`for. Although Rl had been able to handle
`unprepared
`massive intrusion of new knowledge,
`it resulted in a consider-
`able amount of redundancy, some cases of many rules where a
`single general rule would do, and some cases of doing easy
`things the hard way. Moreover,
`in the initial version of RI the
`knowledge
`required
`to perform
`two subtasks was not repre-
`sented in the form of rules; instead, LISP routines
`that could
`do
`the subtasks were
`invoked by rules which
`recognized
`situations
`in which
`the subtasks were germane. At the time,
`since the experts swore (falsely, it turned out) that all of the
`knowledge
`relevant
`to these subtasks was on the
`table,
`it
`seemed appropriate
`to put the knowledge
`in an algorithmic
`form. Given
`these problems,
`it appeared
`that a serious
`reimplementation
`effort would be likely to have the effect of
`making clearer precisely what knowledge Rl had, and thus
`make the task of maintaining
`and extending Rl easier.
`Brigham Bell, Barbara Chessler, and Tom Cooper worked
`with me at CMU on the reimplementation
`of Rl;
`the effort
`took about
`four man-months. The resulting program,
`though
`it had some capabilities
`that
`the OPS4 version
`lacked,
`consisted of about 500 rules (two-thirds
`the number
`that the
`earlier version had). About 100 rules, those that
`tested to
`determine whether a goal had been achieved, were simply
`eliminated. Another 50 rules, those that accessed the data base
`to gain
`further
`information
`about a component,
`could be
`eliminated
`because OPSS’s attribute/ value
`representation
`makes it possible to match against only part of a component
`description;
`thus each relevant description could be accessed
`once and stored as a single working memory element. Since
`about 25 rules were added
`to the new version
`to provide
`additional capabilities, and another 25 to replace the function-
`ality of the LISP routines, about 150 rules were eliminated by
`reducing
`redundancy,
`finding
`appropriate
`generalizations,
`and simplifying
`configuration
`strategies.
`I was surprised both by the length of time the reimplemen-
`tation
`took and by the significantly smaller size of the new
`version
`It appears necessary
`in domains
`such as
`the
`configuration
`domain
`to develop programs
`incrementally. But
`incremental
`addition
`of knowledge
`(given our current
`ignorance of how to build programs
`that can learn) is likely to
`result in a knowledge base that is convoluted and thus, from a
`human maintainer’s point of view, less intelligible
`than it might
`otherwise be. Once much of the knowledge
`relevant
`to a
`domain has been extracted
`from experts, significant gains in
`intelligibility
`can be achieved by reimplementing programs on
`the basis of the more complete picture.
`It is not clear in Rl’s
`case how many reimplementations
`will be necessary. But as
`will become evident below,
`it is likely
`that
`the number
`is
`greater
`than 1.
`
`A Foundation
`
`to Build On
`
`By May 1980, the functions and structure of the group that
`was to be responsible
`for
`the development of RI had been
`defined. Arnold Kraft was selected
`to manage
`the group
`which was to consist, during
`its first year, of 12 people.
`In
`addition
`to Kraft,
`there were to be three people responsible
`for data collection,
`five responsible
`for program maintenance
`
`26
`
`Al MAGAZINE
`
`Summer 1981
`
`for process develop-
`and development, and three responsible
`ment. By August, seven of these people had been hired and the
`rest were in place by December. The people responsible