VT (vertical transportation) is an expert
`system for handling the design of elevator
`systems that is currently in use at West-
`inghouse Elevator Company. Although
`VT tries to postpone each decision in cre-
`ating a design until all information that
`constrains the decision is known, for
`many decisions this postponement is not
`possible. In these cases, VT uses the strat-
`egy of constructing a plausible approxi-
`mation and successively refining it. VT
`uses domain-specific knowledge to guide
`its backtracking search for successful
`refinements. The VT architecture pro-
`vides the basis for a knowledge represen-
`tation that is used by SALT, an automat-
`ed knowledge-acquisition tool. SALT was
`used to build VT and provides an analy-
`sis of VT's knowledge base to assess its
`potential for convergence on a solution.
`
`Due to software problems at the typeset-
`ter, the publication of this article in vol-
`ume 8, number 4 was flawed. A corrected
`copy is reprinted here. –Ed.
`
`VT: An Expert
`Elevator Designer That
`Uses Knowledge-Based
`Backtracking
`Sandra Marcus, Jeffrey Stout, John McDermott
`I
`
`n some cases, plausible guessing
`combined with the ability to back-
`track to undo a bad guess can be the
`most efficient way to solve a problem
`(Stefik et al. 1983). Even least com-
`mitment systems such as MOLGEN
`(Stefik 1981a, 1981b) are sometimes
`forced to guess. In the course of
`designing genetics experiments, MOL-
`GEN tries to avoid making a decision
`until all constraints that might affect
`the decision are known. In some
`cases, this postponement is not possi-
`ble, and the system becomes stuck;
`none of the pending decisions can be
`made with complete confidence. In
`such a case, a decision based on par-
`tial information is needed, and such a
`decision might be wrong. In this case,
`a problem solver needs the ability
`either to backtrack to correct bad
`decisions or to maintain parallel solu-
`tions corresponding to the alterna-
`tives at the stuck decision point.
`However, if alternative guesses exist
`at each point, and there are many
`such decision points on each solution
`path, a commitment to examine every
`possible combination of alternatives
`proves unwieldy. Such complexity
`exists in the VT task domain.
`VT performs the engineering task of
`designing elevator systems. It must
`use the customer's functional specifi-
`cations to select equipment and pro-
`duce a parts configuration that meets
`these specifications as well as safety,
`installation, and maintenance require-
`ments. Because of the large number of
`potential part combinations and the
`need for customizing the layout to the
`space available in individual build-
`ings, VT must construct a solution.
`Like MOLGEN, VT tries to order its
`decisions so that they are made only
`when all relevant constraints are
`known; it guesses only when stuck.
`
`Unlike MOLGEN, VT's decisions
`about part selection and placement
`are so interdependent that plausible
`reasoning (guessing) is a major feature
`of its search for a solution. Thus, VT's
`problem-solving strategy is predomi-
`nantly one of constructing an approxi-
`mation and successively refining it.
`Systems that use plausible reason-
`ing must be able to identify bad guess-
`es and improve on these decisions in a
`way which helps converge on a solu-
`tion. VT is similar to AIR/CYL
`(Brown 1985) and PRIDE (Mittal and
`Araya 1986) in that it uses a knowl-
`edge-based approach to direct this
`search; that is, it uses domain-specific
`knowledge to decide what past deci-
`sions to alter and how to alter them.
`This approach contrasts with EL
`(Sussman 1977; Stallman and Suss-
`man 1977), an expert system which
`shares many architectural features
`with VT but which uses domain-inde-
`pendent strategies to limit the search
`during the backtracking phase. As
`with EL, the VT architecture makes
`clear the role that domain-specific
`knowledge plays in the system and
`the interconnections among decisions
`used to construct and refine a solu-
`tion. This architecture provides the
`basis for VT's explanation facility,
`which is similar to that of EL and the
`related CONSTRAINTS language
`(Sussman and Steele 1980), with some
`extensions. We have exploited the
`structure provided by this architec-
`ture even further by using it to man-
`age VT's knowledge acquisition.
`VT's architecture provides structure
`for a representation of its domain-spe-
`cific knowledge that reflects the func-
`tion of the knowledge in problem
`solving. This representation serves as
`the basis for an automated knowl-
`edge-acquisition tool, SALT (Marcus,
`
`SPRING 1988 95
`
`AI Magazine Volume 9 Number 1 (1988) (© AAAI)
`
`CONFIGIT 1032
`
`1
`
`

`

`Welcome to VT —- The Elevator Design Expert System
`1. INPUT
`Enter contract information
`2. RUN
`Process the input data
`3. SHOW
`Display output information
`4. EXPLAIN Explain the results of a run
`5. SAVE
`Save data for the current contract
`6. EXIT
`End this session with VT
`Enter your command [ INPUT ]: <cr>
`
`Figure 1. VT's Top Level Menu.
`
`GR 24364
`
`INPUT GD DUTY
`Car:1
`Type of loading
`1.
`Machine
`2.
`Machine location
`3.
`Power supply
`4.
`Capacity
`5.
`Speed
`6.
`Travel
`7.
`Platform width
`8.
`Platform depth
`9.
`Counterweight location
`10.
`Counterweight safety
`11.
`Compensation specified
`12
`Action [ EXIT ]:
`
`ADMINISTRATION CENTER
`
`PASSENGER
`GEARED
`OVERHEAD
`208-3-60
`3000
`250
`729
`70
`84
`REAR
`NO
`NO
`
`Figure 2. Completed Sample Input Screen.
`
`McDermott, and Wang 1985; Marcus
`and McDermott 1986, Stout et al.
`1987), which has been used to build
`VT. SALT elicits from experts all the
`knowledge VT needs in order to
`design elevators and represents that
`knowledge in a way which enables
`VT's problem-solving method to use
`it. SALT's knowledge representation
`can also be used to assess the adequa-
`cy of the knowledge base for conver-
`gence on a solution.
`The next section, "What VT Does,"
`presents VT mainly from a user's
`point of view. "The VT Architecture"
`describes the VT architecture in
`detail, with respect to problem-solv-
`ing, explanation, and knowledge
`acquisition. "Management of Knowl-
`edge-Based Backtracking" describes
`how SALT's knowledge base analysis
`supports VT's domain-dependent
`backtracking. "Comparison to Other
`Constructive Systems" compares VT
`to other expert systems that perform
`design, planning, or scheduling tasks.
`"VT's Performance" reports some of
`VT's performance characteristics.
`
`What VT Does
`VT is used by Westinghouse Elevator
`engineers to design elevator systems
`to customer specifications. VT has
`enough domain knowledge to perform
`the design task unaided. VT also has
`an interactive capability which allows a
`user to directly influence its decisions.
`
`The Engineer's Task
`Westinghouse Elevator design experts
`receive data collected from several
`contract documents. These data are
`transmitted to the engineering opera-
`tion by the regional sales and installa-
`tion offices. Three main sources of
`information exist: (1) customer
`requirement forms describing the gen-
`eral performance specifications, such
`as carrying capacity and speed of trav-
`el, and some product selections, such
`as the style of light fixture in the cab;
`(2) the architectural and structural
`drawings of the building, indicating
`such elements as wall-to-wall dimen-
`sions in the elevator shaft (hoistway)
`and locations of rail supports; and (3)
`
`96 AI MAGAZINE
`
`the architectural design drawings of
`the elevator cabs, entrances, and fix-
`tures. Because all this information is
`not necessarily available at the start
`of a contract, the engineer must some-
`times produce reasonable guesses for
`incomplete, inconsistent, or uncertain
`data to enable order processing to ten-
`tatively proceed until customer verifi-
`cation is received. (These guesses are
`in addition to whatever guesses might
`be required during a problem-solving
`episode based on these data.)
`Given this information, experts
`attempt to optimally select the equip-
`ment necessary and design its layout
`in the hoistway to meet engineering,
`safety code, and system performance
`requirements. This task is a highly
`constrained one. A completed elevator
`system must satisfy constraints such
`as the following: (1) there must be at
`least an 8-inch clearance between the
`side of the platform and a hoistway
`wall and at least 7 inches between the
`platform side and a rail separating two
`cars; (2) a model 18 machine can only
`be used with a 15, 20, or 25 horsepow-
`er motor; and (3) the counterweight
`must be close enough to the platform
`to provide adequate traction but far
`enough away to prevent collision with
`either the platform or the rear hoist-
`way wall (by an amount dependent on
`the distance of travel).
`The design task also encompasses
`the calculation of the building load
`data required by the building's struc-
`tural engineers, the reporting of the
`engineering and ordering data required
`for the field installation department
`and regional safety code authorities,
`and the reporting of the mechanical
`manufacturing order information.
`
`A Quick Look at VT in Action
`VT is comprised of several distinct
`parts, described briefly in the sample
`interactions which follow. VT
`prompts appear in boldface. User
`replies appear in bold italics.
`Figure 1 illustrates the top menu,
`where the user indicates what VT is
`to do. The INPUT command allows
`the user either to enter data on a new
`job or to modify data from an existing
`job. The other modes use previously
`input data. VT displays a default com-
`mand in brackets at the bottom of the
`
`2
`
`

`

`screen that the user can issue by hit-
`ting a carriage return (<cr>). Users can
`also issue single or multiple com-
`mands by typing only a portion of a
`command word or the number in
`front of it.
`VT's input is menu driven, allowing
`entire screens of questions to be
`answered at once by providing
`defaults wherever possible. The input
`mode also provides consistency
`checking of data and a general ques-
`tion-asking mechanism that is used
`throughout VT. A completed sample
`input screen is shown in figure 2.
`Prompts for data appear on the left,
`defaults and input on the right.
`Using a simple command language,
`the user can confirm some or all val-
`ues shown, enter or modify values, or
`register uncertainty about values.
`Fourteen of these data menus current-
`ly exist in the INPUT portion of VT.
`Once all the data have been entered,
`the user returns to the top menu, at
`which point the data can be saved for
`future use (SAVE) or used immediate-
`ly in the design task (RUN).
`As VT runs, it tentatively con-
`structs an elevator system by propos-
`ing component selections and rela-
`tionships. At the same time, VT spec-
`ifies constraints with which to test
`the acceptability of the resulting
`design and tests each constraint
`whenever enough is known about the
`design to evaluate it. Whenever con-
`straints are violated, VT attempts to
`alter the design (for example, by
`selecting more expensive equipment)
`in order to resolve the problem. We
`refer to these alterations as fixes. VT
`reports any such constraint violation
`and the fix that is made, as in figure 3.
`There are two types of fix reports.
`The report shown for MAXIMUM-
`TRACTION-RATIO is the more com-
`mon version. It mentions the con-
`straint that was violated, describes
`the degree of the violation, and lists
`the corrective action taken. The fix
`report describing the change to CAR-
`RUNBY is a special case. This version
`is used when VT makes an initial esti-
`mate for a value in order to calculate a
`precise value for it. The value of the
`constraint is the precise value; the
`estimate is simply changed to this
`value.
`During a noninteractive run, VT
`
`The CAR-RUNBY (estimated to be 6) has been changed to 6.125.
`The MACHINE-SHEAVE-HEIGHT (estimated to be 30) has been changed to
`26.
`The CWT-STACK-WEIGHT (estimated to be 4316.25) has been changed to
`4287.36.
`The MAXIMUM-TRACTION-RATIO constraint was violated. The TRAC-
`TION-RATIO was 1.806591, but had to be <= 1.783873. The gap of
`0.2272000E-01 was eliminated by the following action(s):
`Decreasing CWT-TO-PLATFORM-FRONT from 4.75 to 2.25
`Upgrading COMP-CABLE-UNIT-WEIGHT from 0 to 0.5000000E-01
`The MINIMUM-MAX-CAR-RAIL-LOAD constraint was violated. The MAX-
`CAR-RAIL-LOAD was 6000, but had to be >= 6722.295. The gap of 722.3 was
`eliminated by the following action(s):
`Upgrading CAR-RAIL-UNIT-WEIGHT from 11 to 16
`The MINIMUM-PLATFORM-TO-CLEAR-HOISTWAY-RIGHT constraint was
`violated. The PLATFORM-TO-CLEAR-HOISTWAY-RIGHT was 7.5, but had
`to be >= 8. The gap of 0.5 was eliminated by the following action(s):
`Decreasing CAR-RETURN-RIGHT from 3 to 2.5
`The MINIMUM-PLATFORM-TO-CLEAR-HOISTWAY-LEFT constraint was
`violated. The PLATFORM-TO-CLEAR-HOISTWAY-LEFT was 7.5, but had to
`be >= 8. The gap of 0.5 was eliminated by the following action(s):
`Decreasing CAR-RETURN-LEFT from 25.5 to 25
`The MAXIMUM-MACHINE-GROOVE-PRESSURE constraint was violated.
`The MACHINE-GROOVE-PRESSURE was 149.5444, but had to be <= 119.
`The gap of 30.544 was eliminated by the following action(s):
`Increasing HOIST-CABLE-QUANTITY from 3 to 4
`The MINIMUM-HOIST-CABLE-SAFETY-FACTOR constraint was violated.
`The HOIST-CABLE-SAFETY-FACTOR was 8.395078, but had to be >= 10.
`The gap of 1.60492 was eliminated by the following action(s):
`Upgrading HOIST-CABLE-DIAMETER from 0.5 to 0.625
`The MINIMUM-MACHINE-BEAM-SECTION-MODULUS constraint was
`violated. The MACHINE-BEAM-SECTION-MODULUS was 24.7, but had to
`be >= 24.87352. The gap of 0.1735 was eliminated by the following action(s):
`Upgrading MACHINE-BEAM-MODEL from S10X25.4 to S10X35.0
`The CHOICE-SET-HOIST-CABLE-DIAMETER constraint was violated. The
`HOIST-CABLE-DIAMETER was 0.625, but was constrained to be 0.5. The
`HOIST-CABLE-DIAMETER became a member of the set by the following
`action(s):
`Upgrading MACHINE-MODEL from 28 to 38
`
`Figure 3. Constraint Violation and Fix Report.
`
`uses its own knowledge base to decide
`how to remedy constraint violations.
`This knowledge base represents engi-
`neering practices that Westinghouse
`plans to make standard. The RUN can
`also be done interactively, in which
`case VT asks for confirmation of each
`fix before it is actually implemented.
`If a particular fix is rejected by the
`user, VT can either find another fix or
`provide a list of all possible fixes and
`ask the user to suggest a particular
`one. Records are kept of user over-
`rides. These overrides are taken into
`
`consideration by the system main-
`tainers when modifying the knowl-
`edge base. The overriding of a VT-pro-
`posed fix by the user might indicate
`that a standard does not yet exist on a
`decision VT makes. It might also be
`the result of outside factors that were
`too transitory to make it into the VT
`knowledge or data base, such as a
`temporary surplus or a shortage of a
`particular equipment model.
`On completion of the run, control
`returns to the top menu, at which
`point the user normally goes into
`
`SPRING 1988 97
`
`3
`
`

`

`ures 4 and 5 are representative of the
`sixteen SHOW screens that currently
`exist; the user accesses these screens
`by a tree of menus similar to the
`input menu.
`If the user sees something unusual
`while in SHOW (for example, an
`unexpected value), the EXPLAIN
`mode can be used to determine the
`cause. EXPLAIN can also be used by
`relative novices to understand how
`VT performs the design task.
`The user interacts with VT's expla-
`nation facility by asking questions.
`The type of information given in the
`explanation depends on the type of
`question asked. VT's explanation
`facility currently provides several
`types of queries that can be asked
`about individual system values. These
`query types are discussed in detail in
`the next section. The sample interac-
`tion in figure 6 demonstrates some of
`the tools the explanation facility pro-
`vides, including the use of VT's lexi-
`con of synonyms for system value
`names.
`The only major part of VT that is
`not visible in figures 1-6 is VT's
`database. The database is read only
`and primarily contains data about
`pieces of equipment and machinery
`that VT must configure. Each piece of
`equipment has its own table; the rows
`of each of these tables represent differ-
`ent models of the equipment from
`which to choose, and the columns
`represent attributes relevant to the
`type of equipment. These attributes
`can be restrictions on each model's
`use (for example, maximum elevator
`speed or maximum load supported by
`the equipment), values of equipment
`attributes (for example, height and
`weight), or lists of model numbers of
`compatible pieces of equipment.
`Calls to the database indicate which
`table is to be used and what value is
`to be returned. This value can be
`either the name of the particular
`model or the value of one of its
`attributes. A call might also include
`an arbitrary number of constraints on
`the values of each column.
`In the event that multiple entries in
`the database satisfy all the constraints
`in a call, each table is ordered along
`an equipment attribute (for example,
`size) to indicate a preference or priori-
`ty. The entries in a table are examined
`
`ADMINISTRATION CENTER
`Governor: B5B Support: STEEL
`Governor Cable: 0.375
`Length: 2130
`Hoist Cables: (3)-0.5
`Length: 1089
`Compensation: 3/16-CHAIN
`Length: 993
`Car sling: 2.5B-18
`Crosshead Beam: W8X18
`Platform Thickness: 6.625
`Sling Weight.......... 292
`Platform Weight....... 738
`Safety Weight......... 465
`Cab Weight............1668
`Misc. Weight.......... 434
`Total Car Weight......3609
`Counterweight Weight: 4824
`Subweight Weight:
`Buffer Reaction Car: 26437
`Cwt: 19296
`Machine Weight: 1700
`Guide Shoes..Car: 6-R Cwt: 3-R
`Heat Emission in M.R.: —-
`Buffer.......Car: OH-1 Cwt: OH-1
`Cable Hanger —-
`Stroke.......Car: 8.25 Cwt: 8.25
`Safety to Pit: 42
`Safety.......Car: B1 Cwt: —-
`Press RETURN to continue [ MENU ]: show layout cwt
`
`Travel: 729
`Openings: 6
`Stops: 6
`Sheave: 30
`Machine: 28
`Deflector Sheave: 20
`Groove: K3269 Pressure: 90.03
`Angle of Contact: 159.09
`Traction Ratio: 1.79
`Machine Load: 11691
`Motor H.P.: 20
`Power Source: —-
`Power Supply: 208-3-60
`4287 Rails........Car: 16 Cwt: 11
`
`Figure 4. Show Screen for Layout Specs.
`
`SHOW LAYOUT CWT GR 24364
`
`ADMINISTRATION CENTER
`
`12.5
`
`5.75
`
`18.25
`Cwt Space
`
`85.5
`Hoistway
`
`28
`
`Cwt BG
`
`9 7
`
`2.25
`
`Platform
`
`Overall Cwt Height 138
`537
`Cwt Assembly Weight
`Cwt Subweight Weight 4287 Maximum Subweight Weight 5273
`Total CWT Weight
`4824
`Cwt Stack Height 87
`Maximum Stack Height 107
`Maximum Building Tolerance: 1 Stack Percent 81
`Press RETURN to continue [ MENU ]:
`
`Figure 5. Show Screen (Layout CWT).
`
`SHOW mode. SHOW allows users to
`view data a screenful at a time. Some
`of the screens are intended for just
`such a review, and others are intended
`
`as input data for other Westinghouse
`systems (such as manufacturing-ori-
`ented programs, cost estimators, and a
`computer-aided drawing system). Fig-
`
`98 AI MAGAZINE
`
`SHOW LAYOUT SPECS GR 24364
`Loading: PASSENGER
`Capacity: 3000
`
`Speed: 250
`
`Operation: 1C-2BC-ERL
`
`4
`
`

`

`from best to worst, and the first entry
`satisfying all the constraints is the
`one from which the return value is
`obtained.
`
`The VT Architecture
`VT solves its problem by constructing
`an approximate elevator design and
`successively refining it. The process
`of constructing an approximate design
`is forward chaining. Each step in this
`phase extends the design by proce-
`dures that use input data or results of
`prior decisions to determine a value
`for a design parameter. Some of these
`steps embody heuristic knowledge
`about how to propose an approximate
`design extension. These steps are
`needed when the decision is under-
`constrained or when it must be based
`on partial information. As VT builds a
`proposed design, constraints on the
`elevator system are specified whenev-
`er enough information is available to
`determine their values. The control in
`this constructive phase is data driven;
`any step can be taken as soon as the
`information called for by the proce-
`dure associated with the step is avail-
`able. As it extends the design, VT also
`builds a dependency network that
`records for each value which other
`values were used to obtain it.
`The dependency network developed
`during the forward-chaining construc-
`tive phase is enough to identify all
`contributors to a violated constraint
`and the value it constrains. These
`contributors represent potential
`points to backtrack to in order to
`revise the proposed design. However,
`domain expertise is needed to indicate
`what changes in the proposed design
`are least costly in real-world terms.
`Although it is not possible to assign a
`dollar cost to each revision, domain
`knowledge determines which of the
`potential alterations are legal as well
`as the order of preference among the
`legal ones.
`Demons are used to check for con-
`straint violations; whenever enough is
`known about the proposed design to
`supply values for both a constraint
`and the value it constrains, they are
`compared. Whenever VT detects a
`constraint violation, it tests the effec-
`tiveness of suggested changes in order
`of decreasing preference rating. As VT
`
`GR 24364
`
`ADMINISTRATION CENTER
`
`EXPLAIN
`Explain: how car runby
`The CAR-RUNBY was determined by a fix.
`The CHOICE-SET-CAR-RUNBY constraint was violated.
`The CAR-RUNBY was 6, but was constrained to be 6.125.
`The CAR-RUNBY was changed from 6 to 6.125.
`How[ CHOICE-SET-CAR-RUNBY ]: <cr>
`The CHOICE-SET-CAR-RUNBY (6.125) = PIT-DEPTH (72) - [ PLATFORM-
`HEIGHT (6.625) + SAFETY-HEIGHT (9) + CAR-BUFFER-HEIGHT (28.75) +
`CAR-FOOTING- CHANNEL-HEIGHT (3.5) + CAR-BUFFER-BLOCKING-
`HEIGHT (18)]
`How [ PIT-DEPTH ]: <cr>
`The PIT-DEPTH (72) was input by Bob Roche on 25-MAR-1985.
`How [ PLATFORM-WEIGHT ]: safety height
`The SAFETY-HEIGHT (9) was determined by a database lookup.
`It was found in the HEIGHT column of the SAFETY table.
`It met the following constraints:
`MODEL = SAFETY-MODEL (B1)
`How [ SAFETY MODEL ]: <cr>
`The SAFETY-MODEL (B1) was determined by a database lookup.
`It was found in the MODEL column of the SAFETY table.
`It had the SMALLEST HEIGHT that met the following constraints:
`MAX-SPEED > SPEED (250)
`MAX-PLATFORM-WIDTH >= PLATFORM-WIDTH (70)
`MIN-PLATFORM-WIDTH <= PLATFORM-WIDTH (70)
`How[ SPEED ]: what if safety model B4
`The SAFETY-MODEL is currently B1.
`If it were B4, the following major changes would occur:
`PROPOSED:
`NAME:
`ACTUAL:
`155.563.
`MACHINE-GROOVE-PRESSURE
`114.118
`1.76682.
`TRACTION-RATIO
`1.80679
`52.835.
`CWT-OVERTRAVEL
`49.835
`27652.4.
`CAR-BUFFER-REACTION
`26709.4
`88.148.
`CWT-STACK-PERCENT
`84.1122
`20627.0.
`CWT-BUFFER-REACTION
`19684
`94.3184.
`CWT-PLATE-QUANTITY
`90
`5156.76.
`CWT-WEIGHT
`4921.0
`6913.11.
`CAR-BUFFER-LOAD
`6677.35
`3913.11.
`CAR-WEIGHT
`3677.35
`20.
`DEFLECTOR-SHEAVE-DIAMETER
`25
`17.125.
`CAR-BUFFER-BLOCKING-HEIGHT
`18
`(3)-0.5.
`HOIST-CABLE-MODEL
`(4)-0.5
`6.
`CAR-RUNBY
`6.125
`B4.
`SAFETY-MODEL
`B1
`Would you like to see ALL values which would change [ NO ]: <cr>
`Would you like to implement this [ NO ]: <cr>
`How [ MACHINE-GROOVE-PRESSURE ]: safety load
`There is more than one SAFETY-LOAD:
`1. SAFETY-LOAD-CAR-SIDE-CAR-TOP
`2. SAFETY-LOAD-CAR-SIDE-CAR-BOTTOM
`3. SAFETY-LOAD-CWT-SIDE-CAR-TOP
`4. SAFETY-LOAD-CWT-SIDE-CAR-BOTTOM
`Which would you like to know about?
`[ SAFETY-LOAD-CAR-SIDE-CAR- TOP ]: 2
`
`Figure 6. A Sample Interaction with the Explanation Facility.
`
`SPRING 1988 99
`
`5
`
`

`

`(1) MACHINE-MODEL step:
`IF a value has been generated for SUSPENDED-LOAD, and
`there is no value for MACHINE-MODEL,
`THEN look in the database in the MACHINE table for the entry with the
`SMALLEST WEIGHT whose listing for MAX-LOAD is greater than the
`SUSPENDED-LOAD.
`Retrieve the value under MODEL for that entry and assign that value to
`MACHINE-MODEL.
`Leave a trace that SUSPENDED-LOAD contributed to MACHINE-MODEL.
`Leave a declarative representation of the details of the database call.
`
`soon as a value for SUSPENDED-
`LOAD is made available; then uses
`this value to supply MACHINE-
`MODEL. Leaving a trace of the contri-
`bution adds to the dependency net-
`work used by the truth maintenance
`system in backtracking. Leaving a
`declarative representation of the
`action taken by this rule is used by
`the explanation facility.
`To see how this step might interact
`with others, consider the two steps
`shown in figure 8.
`According to the control shown in
`
`Figure 7. Machine-Model Step.
`moves through the list of potential
`fixes for a constraint violation, it first
`tries every individual fix at a given
`preference level. Next it tries to com-
`bine each fix at the current preference
`level with those of greater or equal
`preference.
`Once VT identifies a change to
`explore, it first verifies that no con-
`straints on the changed value itself
`are violated by the change. It then
`makes the proposed change and works
`through the implications according to
`its knowledge about constructing a
`proposed design. (Constraints can be
`numeric or symbolic, and procedures
`for determining values often involve
`nonlinear functions such as selections
`from the database.) VT continues this
`procedure until it has enough knowl-
`edge to evaluate the originally violat-
`ed constraint. If a proposed change
`violates the constraints, it is rejected,
`and another selection is made. This
`lookahead is limited because it only
`considers constraints on the changed
`value and the originally violated con-
`straint. The purpose of this lookahead
`is to limit the work done in exploring
`the implications of a proposed guess
`until VT has reason to believe it is a
`good guess. Once a good guess has
`been identified, VT applies a truth
`maintenance system; that is, it uses
`the dependency network constructed
`during the forward-chaining phase to
`identify and remove any values that
`might be inconsistent with the
`changed value. VT then reenters the
`data-driven constructive phase for
`extending the design with the new
`data.
`
`A Detailed Look at Problem Solving
`In order to better illustrate how VT
`
`100 AI MAGAZINE
`
`(2) MACHINE-SHEAVE-DIAMETER step:
`IF a value has been generated for MACHINE-MODEL, and there is no value for
`MACHINE-SHEAVE-DIAMETER,
`THEN look in the database in the MACHINE table for the entry whose listing
`for MODEL is the same as MACHINE-MODEL.
`Retrieve the value under SHEAVE-DIAMETER for that entry and assign that
`value to MACHINE-SHEAVE-DIAMETER.
`Leave a trace that MACHINE-MODEL contributed to MACHINE-SHEAVE-
`DIAMETER.
`Leave a declarative representation of the details of the database call.
`(3) MACHINE-GROOVE-PRESSURE-FACTOR step:
`IF a value has been generated for HOIST-CABLE-DIAMETER, and there is no
`value for MACHINE-GROOVE-PRESSURE-FACTOR,
`THEN compute 2 * HOIST-CABLE-DIAMETER.
`Assign the result to MACHINE-GROOVE-PRESSURE-FACTOR.
`Leave a trace that HOIST-CABLE-DIAMETER contributed to MACHINE-
`GROOVE-PRESSURE-FACTOR.
`Leave a declarative representation of the details of the calculation.
`
`Figure 8. Sheave-Diameter and Pressure-Factor Steps.
`
`arrives at a solution, we describe the
`forwardchaining and backtracking
`done in a small portion of the sample
`run. The detail focuses on steps lead-
`ing to the specification of MACHINE-
`GROOVE-PRESSURE and its con-
`straint MAXIMUM-MACHINE-
`GROOVE-PRESSURE and follows the
`backtracking initiated by a violation
`of this constraint.
`A step to extend the proposed
`design specifies a value for a design
`parameter, often using results of deci-
`sions already made. For example, the
`step to select the model of the
`machine that moves the elevator car
`can be given the English translation
`shown in figure 7.
`The first line of this step specifica-
`tion sets up the forward-chaining con-
`trol. This rule is eligible to fire as
`
`figures 7 and 8, step 1 must be applied
`before step 2 because step 1 creates
`the conditions under which step 2 is
`satisfied. If step 3 is satisfied at the
`same time as either of the other steps,
`it does not matter which procedure is
`applied first.
`The machine moves the elevator by
`turning the machine sheave. The
`machine sheave contains grooves that
`grip the hoist cables which support
`the elevator car. Some pressure is
`required, but if the pressure on each
`individual cable is too great, there is
`excessive wear on the cables. Steps 1
`and 2 are on the inference chain that
`produces a value for MACHINE-
`GROOVE-PRESSURE. This value is
`the result of a calculation using MAX-
`T O T A L - L O A D - C A R - S I D E ,
`MACHINE-SHEAVE-DIAMETER, and
`
`6
`
`

`

`HOIST-CABLE-QUANTITY. Step 3 is
`on the inference chain that produces a
`value for MAXIMUM-MACHINE-
`GROOVE-PRESSURE. This value is a
`function of the MACHINE-GROOVE-
`MODEL, the SPEED the elevator will
`travel, and MACHINE-GROOVE-
`PRESSURE-FACTOR. Once values for
`both MACHINE-GROOVE-PRES-
`SURE and MAXIMUM-MACHINE-
`GROOVE-PRESSURE are available,
`they are compared. Because the con-
`straint is a maximum, the constraint
`is flagged as violated if the value of
`MACHINE-GROOVE-PRESSURE is
`greater than the value of MAXIMUM-
`MACHINE-GROOVE-PRESSURE.
`Flagging the constraint as violated
`causes VT to shift control into fix
`exploration.
`As a first step in exploring remedies
`for the constraint violation, VT pro-
`poses potential remedies. For this par-
`ticular violation, a propose-fix step for
`the VT knowledge base looks as
`shown in figure 9. (This is an abbrevi-
`ated listing of fixes for MAXIMUM-
`MACHINE-GROOVE-PRESSURE. We
`return to a complete treatment of this
`example in "Management of Knowl-
`edge-Based Backtracking.")
`Downgrading the MACHINE-
`GROOVE-MODEL to one that grips
`the cable less increases the allowable
`MAXIMUM-MACHINE-GROOVE-
`PRESSURE. Increasing the HOIST-
`CABLE-QUANTITY distributes the
`load and decreases the actual
`MACHINE-GROOVE-PRESSURE on
`each groove. VT's domain expert felt
`these two potential fixes would be
`practical to attempt. Of the two fixes,
`the first is preferable.
`VT first considers a downgrade of
`MACHINE-GROOVE-MODEL by try-
`ing to select the next higher groove
`according to the preference ordering.1
`If there is such a preferred groove, VT
`determines what the MAXIMUM-
`MACHINE-GROOVE-PRESSURE for
`this groove is. If this value is not less
`than the value of MACHINE-
`GROOVE-PRESSURE, VT tries to
`downgrade the groove model further.
`When there are no longer any models
`to try (there are only two groove mod-
`els), VT considers an increase of
`HOIST-CABLE-QUANTITY
`by
`adding 1 to its current value. It first
`checks to see whether this quantity is
`
`IF there has been a violation of MAXIMUM-MACHINE-GROOVE-PRESSURE,
`THEN try a DOWNGRADE for MACHINE-GROOVE-MODEL which has a
`preference rating of 1 because it CAUSES NO PROBLEM.
`Try an INCREASE BY-STEP of 1 of HOIST-CABLE-QUANTITY which has a
`preference rating of 4 because it CHANGES MINOR EQUIPMENT SIZING.
`
`Figure 9. A Propose-Fix Step.
`
`larger than the MAXIMUM-HOIST-
`CABLE-QUANTITY (which in any
`application is never more than six
`cables). If not, VT then recomputes
`the MACHINE-GROOVE-PRESSURE
`using the new HOIST-CABLE-QUAN-
`TITY to see if this quantity brings the
`pressure under the maximum. If it
`does not, VT tries adding another
`hoist cable and repeats the procedure.
`If VT exceeds the MAXIMUM-HOIST-
`CABLE-QUANTITY before bringing
`MACHINE-GROOVE-PRESSURE
`under its maximum, it then attempts
`a combination of the two fixes. If
`none of the specified fixes resolve the
`violation, VT has reached a dead end
`(that is, the constraint violation can-
`not be corrected). In the sample run
`shown previously, the proposed design
`already employed the preferred groove
`at the time of the constraint violation;
`adding a single hoist cable was the
`selected remedy.
`Once VT finds the fix it wants to
`implement, it uses the dependency
`network built during the forward
`chaining to remove any values that
`depended on the one it changed. It
`then returns to the forward-chaining
`phase with the new HOIST-CABLE-
`QUANTITY and continues.
`
`A Detailed Look
`at the Explanation Facility
`Every decision VT makes must be jus-
`tifiable to the user. This condition is
`provided for by making a record of
`each decision as it is made. The
`dependency network built for VT's
`truth maintenance system can pro-
`vide the foundation for a very useful
`explanation facility (Doyle 1979; Suss-
`man and Steele 1980). This network is
`augmented by the details of the con-
`tribution relation, for example, a
`description of an algebraic formula or
`the relation between values required
`by a precondition. In addition, VT
`records adjustments to the proposed
`
`design that it makes, such as fixes of
`constraint violations. The explanation
`facility pieces these individual actions
`together to describe VT's line of rea-
`soning.
`VT's explanation facility does more
`than just examine past decisions; it
`also performs some hypothetical rea-
`soning to demonstrate the effect of
`alternative decisions the user sug-
`gests. Hypothetical explanations are
`relatively simple to construct given
`the VT knowledge representation.
`What the system must do in order to
`answer hypothetical queries is closely
`related to how it resolves constraint
`violations.
`Explaining Past Decisions. The how
`query is probably the most fundamen-
`tal and can be thought of as as