U.S. Department

of Commerce

National Bureau

of Standards

NAT'L INST. OF STAND & TECH

AlllDb EE52SE

NBS

publications

NBSIR 82-2505

AN OVERVIEW OF

EXPERT SYSTEMS

May 1982

Prepared for — lilC " National Aeronautics and Space

inn Administration Headquarters

Washington, D.C. 20546

o2-2iUb

lyo2

c. 2

NBSIR 82-2505

AN OVERVIEW OF EXPERT SYSTEMS

MATIUNAL UUKaAb

OP BTANOABUS

UBtAJtT

JUL 7 1^2

A

- - d

- -

I William B. Gevarter

U.S. DEPARTMENT OF COMMERCE

National Bureau of Standards

National Engineering Laboratory

Center for Manufacturing Engineering

Industrial Systems Division

Metrology Building, Room A127

Washington, DC 20234

May 1982

Prepared for: National Aeronautics and Space Administration

Headquarters

Washington, DC 20546

U.S. DEPARTMENT OF COMMERCE, Malcolm Baldrige, Secretary

NATIONAL BUREAU OF STANDARDS, Ernest Ambler, Director
s\n>»\i’i aiwujfA*!,

\i. t.f.iMA0»ATa "SO TRAsnrw

SBer t JUl

:'^;. 'r 4 i /_ !^-.,

^

^

m

-Ai ii'.i

Uf

(

i

1^ '''t

»tSs»-®:'»airJ

' -4^W: ^

'ift’tm ' .'£f

^' ^n<3l^iyl0

m':

t

•«•, !©•

u

3i

^'i:. #'

>S' @|» la..

"4kv 1.

a.

/2r„

li

3 I GS^

m m

% ^ iwai I ft

<*sf '-.-4

'r^-trii \

n

'• 'T
Preface

Expert systems is probably the "hottest” topic in Artificial

Intelligence (AI) today. In the past, in trying to find

solutions to problems, AI researchers tended to rely on search

techniques or computational logic. These techniques were

successfully used to solve elementary or toy problems or very

well structured problems such as games. However, real complex

problems are prone to have the characteristic that their search

space tends to expand exponentially with the number of

parameters involved. For such problems, these older techniques

have generally proved to be inadequate and a new approach was

needed. This new approach emphasized knowledge rather than

search and has led to the field of Knowledge Engineering and

Expert Systems.

This report provides a current overview of Expert Systems --

what it is, techniques used, existing systems, applications, who

is doing it, who is funding it, the state-of-the-art, research

requirements and future trends and opportunities.

This report is in support of the more general NBS/NASA

report, "An Overview of Artificial Intelligence and Robotics."

1
Acknowledgements

I wish to thank those people at Stanford University, XEROX

PARC, MIT and elsewhere who have been instrumental in developing

the knowledge engineering field, and have contributed time and

source material to help make this report possible. I particularly would like to thank Margie Johnson who has done a heroic job typing this series and facilitating their publication.

ii
TABLE OF CONTENTS

I Introduction 1

II What is an Expert System 2

III The Basic Structure of an Expert System 2

IV The Knowledge Base 6

V The Inference Engine 8

VI Uses of Expert Systems 10

VII Architecture of Expert Systems 12

A. Introduction 12

B. Choice of Solution Direction 18

1. Foward Chaining 18

2. Backward Chaining 18

3. Forward and Backward Processing Combined . . 18

4. Event Driven 19

C. Reasoning in the Presence of Uncertainty .... 19

1. Numeric Procedures 19

2. Belief Revision or "Truth Maintenance" ... 20

D. Searching a Small Search Space 20

E. Techniques for Searching a Large Search Space . . 20

1 . Hierarchical Generate and Test 20

2. Dependency-Directed Backtracking 21

3. Multiple Lines of Reasoning 21

F. Methods for Handling a Large Search Space by

Transforming the Space 22

1 . Breaking the Problem Down into Subproblems . 22

2. Hierarchical Refinement into Increasingly

Elaborate Spaces 23

ili
3. Hierarchical Resolution into Contributing

Sub-spaces 24

G. Methods for Handling a Large Search Space by

Developing Alternative or Additional Spaces . . 26

1. Employing Multiple Models 26

2. Meta Reasoning 26

H. Dealing with Time 26

1. Situational Calculus 26

2. Planning with Time Constraints 27

VIII Existing Expert Systems 28

IX Tools for Building Expert Systems 31

X Constructing an Expert Systems 34

XI Knowledge Acquisition and Learning 36

A. Knowledge Acquisition 36

B. Self Learning and Discovery 36

XII Who Is Doing It 38

XIII Who is Funding It 39

XIV Summary of the State-of- the-Ar t 41

XV Current Problems and Issues 43

XVI Research Required 46

XVII Future Trends 47

References 52
List of Tables

1. Characteristics of Example Expert Systems 13, 54

2. Summary of Characteristics of Systems in Table 1 ... 17

3. Existing Expert Systems by Function 29

4. Programming Tools for Expert Systems 32

List of Figures

1. Basic Structure of An Expert Systems 4

2. Expert Systems Applications Now Under Development . . 48

3. Future Opportunities for Expert Systems 49

V
-•T'

:S2

^" ’ >^.

'^:'- r^

' ^'- A »;ii%

' .'i - o' ' '-'^fe ”"

^.. - .v)i;-- -V'lt - .= -. -, - - - ,0

trtS' 1 is . <^ ’ -^ifi

, V ;A‘- i^v: <' t

=* I

*.—4., .^i?.

'r^;._^>v: ,^v.. ^

ri '

«i:

J.fe'l

, f f ;? ^ ^Wi *; ^ -i. I'V .v-H 4sj^-^

'r'^l

,'Bf* II

4 1 .7 }' ^ ,« ,

1 ^®". if f

j

4 -iirn ii

^n'<V*J*r^ I' * .,(•'

Skill'''

%

-

S',^^,.4

,w^. nxii
I . Introduction

In the 70's, it became apparent to the AI community, that

search strategies alone, even augmented by heuristic* evaluation

functions, were often inadequate to solve real world problems.

The complexity of these problems were usually such that (without

incorporating substantially more problem knowledge than had heretofore been brought to bear) either a combinatorial explosion

occurred that defied reasonable search times, or that the ability

• I to generate a suitable search space did not, exist. In fact, it

became apparent that for many problems, that expert domain

. • V y . K .

.

' r ‘I knowledge was even more important than the search strategy (or

inference procedure). This realization led to the field of

"Knowledge Engineering," which focuses on ways to bring expert

knowledge to bear in problem solving.** The resultant expert

systems technology, limited to academic laboratories in the 70's,

is now becoming cost-effective and is beginning to enter into

commercial applications.

*Heuristics are "rules of thumb," knowledge or other techniques

that -can be used to help guide search.

**One important aspect of the knowledged-based approach is that

the combinatorial complexity associated with real-world problems

is mitigated by the more powerful focussing of the search that

can be obtained with rule-based heuristics usually used in expert

systems as opposed to the numerical heuristics (evaluation

functions) used in classical search techniques. In other words,

the rule-based system is able to reason about its own search

effort, in addition to reasoning about the problem domain. (Of

course, this also implies that the search strategy is incomplete.

Solutions may be missed, and an entire search may fail even when

there is a solution "within reach" in the problem space defined

by the domain.)

1
II. What i s an Expert System?

Feigenbaum, a pioneer in expert systems, (1982, p. 1) states:

An "expert system" is an intelligent computer program

that uses knowledge and inference procedures to solve

problems that are difficult enough to require significant

human expertise for their solution. The knowledge necessary

to perform at such a level, plus the inference procedures

used, can be thought of as a model of the expertise of the

best practitioners of the field.

The knowledge of an expert system consists of facts

and heuristics. The "facts" constitute a body of

information that is widely shared, publicly available, and

generally agreed upon by experts in a field. The

"heuristics" are mostly private, little-discussed rules of

good judgment (rules of plausible reasoning, rules of good

guessing) that characterize expert-level decision making in

the field. The performance level of an expert system is

primarily a function of the size and quality of the

knowledge base that it possesses.

III. The Basic Structure of an Expert System

An expert system consists of:

1) a knowledge base (or knowledge source) of domain facts

and heuristics associated with the problem;

2) an inference procedure (or control structure) for

utilizing the knowledge base in the solution of the

problem;

3) a working memory - "global data base" - for keeping

track of the problem status, the input data for the

particular problem, and the relevant history of what

has thus far been done.

A human "domain expert" usually collaborates to help develop

the knowledge base. Once the system has been developed, in

addition to solving problems, it can also be used to help

instruct others in developing their own expertise.

Thus, Michie (1980, pp . 3-5) observes:

2
...that there are three different user-modes for an expert

system in contrast to the single mode (getting answers to

problems) characteristic of the more familiar type of

computing

:

(1) getting answers to problems — user as client;

(2) improving or increasing the system's knowledge -- user

as tutor;

(3) harvesting the knowledge base for human use — user as

pupil.

Users of an expert system in mode (2) are known as "domain

specialists." It is not possible to build an expert system

without one...

An expert systems acts as a systematizing repository over

time of the knowledge accumulated by many specialists of

diverse experience. Hence, it can and does ultimately

attain a level of consultant expertise exceeding* that of

any single one of its "tutors."

It is usual to have a natural language interface to

facilitate the use of the system in all three modes. Normally,

an explanation module is also included, allowing the user to

challenge and examine the reasoning process underlying the

system's answers. Figure 1 diagrams a typical (though somewhat

idealized) expert system. When the domain knowledge is stored as

production rules, the knowledge base is often referred to as the

"rule base," and the inference engine the "rule interpreter."

An expert system differs from more convential computer

programs in several important respects. Duda (1981, p. 242)

observes that, in an expert system, "...there is a clear

separation of general knowledge about the problem (the rules

*There are not yet many examples of expert systems whose

performance consistently surpasses that of an expert. And

currently, there are even fewer examples of expert systems that

use knowledge from a group of experts and integrate it

effectively. However the promise is there.

3
NATURAL

LANGUAGE

INTERFACE

>- 1 <r; <c LU

PQ 1— CO 0 «=c —1 0 PQ

<JD 1

<1: I

GO

CO

>-

CO

AX

CO CO

LU LU LU 1 1 CD

ID ZD OP

LU OP OP

CD 0 C=3 LU LU CO

LU LU CD CD 1 CO 0 LU

<c LU LU CD 0 OQ 1 OP «

LU LU 0 U_ 1 0

s: - - 4

FIGURE 1

BASIC

STRUCTURE

OF

AN

EXPERT

SYSTEM
forming a knowledge base) from information about the current

problem (the input data) and methods for applying the general

knowledge to the problem (the rule interpreter)." In a conventional computer program, knowledge pertinent to the problem

and methods for utilizing this knowledge are all intermixed, so

that it is difficult to change the program. In an expert system,

"...the program itself is only an interpreter (or general

reasoning mechanism) and [ideally] the system can be changed by

simply adding or substracting rules in the knowledge base."

5
IV. The Knowledge Base

The most popular approach to representing the domain

knowledge needed for an expert system is by production rules

(also referred to as " S ITUAT I ON- ACT I ON rules" or "IF-THEN

rules"). Thus, often a knowledge base is made up mostly of rules

which are invoked by pattern matching with features of the task

environment as they currently appear in the global data base.

The rules in a knowledge base represent the domain facts and

heuristics - rules of good judgment of actions to take when

specific situations arise. The power of the expert system lies

in the specific knowledge of the problem domain, with potentially

the most powerful systems being the ones containing the most

knowledge

.

Duda (1981, p. 242) states:

Most existing rule-based systems contain

hundreds of rules, usually obtained by interviewing

experts for weeks or months... In any system, the

rules become connected to each other by association

linkages to form rule networks. Once assembled, such

network's can represent a substantial body of

knowledge .... An expert usually has many judgmental or empirical rules,

for which there is incomplete support from the available

evidence. In such cases, one approach is to attach numerical

values (certainty factors) to each rule to indicate the degree of

certainty associated with that rule. (In expert system

operation, these certainty values are combined with each other

and the certainty of the problem data, to arrive at a certainty

value for the final solution.)

Michie (1980, p. 6) indicates that the cognitive strategies

of human experts in more complex domains are based "...not on

6
elaborate calculations, but on the mental storage and use of

large incremental catalogs of pattern-based rules." Thus, human

chess masters may be able to acquire, organize and utilize as

much as 50,000 pattern-based rules in achieving their remarkable

performance. Michie (p. 20-21) indicates that such rules are so

powerful that only some 30 rules are needed for expert system

performance for a chess subdomain such as King and Knight against

King and Rook, which has a problem space size of roughly

2,000,000 configurations. He further observed for chess that the

number of rules required grows slowly relative to the increase in

domain complexity. Thus, in chess and other complex domains

(such as industrial routing and scheduling) it appears that wellchosen pattern sets may maintain control over otherwise

intractable explosions of combinatorial complexity.

7
V The Inference

.

The problem-solving paradigm, and its methods,

organizes and controls the steps taken to solve the

problem. One commonplace but powerful paradigm

involves the chaining of IF-THEN rules to form a line

of reasoning. If the chaining starts from a set of

conditions and moves toward some (possibly remote)

conclusion, the method is called for w ard chaining . If

the conclusion is known (e.g., it is a goal to be

achieved), but the path to that conclusion is not

known, then working backwards is called for, and the

method is b^clkwa^d chaj^nj^n£. (Heuristic Programming

Project, 1980, p. 6)

The problem with forward chaining, without appropriate

heuristics for pruning, is that you would derive everything

possible whether you needed it or not. Backward chaining works

from goals to subgoals (by using the action side of rules to

deduce the condition side of the rules). The problem here, again

without appropriate heuristics for guidance, is the handling of

conjunctive subgoals. In general to attack a conjunction, one

must find a case where all interacting subgoals are satisfied, a search for which can often result in a combinatorial explosion of

possibilities. Thus appropriate domain heuristics and suitable

inference schemes and architectures must be found for each type

of problem to achieve an efficient and effective expert system.

The knowledge of a task domain guides the problemsolving steps taken. Sometimes the knowledge is quite

abstract--for example, a symbolic model of "how things

work" in the domain. Inference that proceeds from the

model's abstractions to more detailed (less abstract)

statements is called inference. Always

when one is moving from more abstract symbolic

statements to less abstract statements, one is

generating expectations, and the problem-solving

behavior is termed ex£ectat_ion d£^ven. Often in

problem solving, however, one is working "upwards" from

the details or the specific problem data to the higher

levels of abstraction (i.e., in the direction of "what

it all means"). Steps in this direction are call d a_t

a

d£^ V e n . If you choose your next step either on the

basis of some new data or on the basis of the last

8
problem-solving step taken, you are responding to

events, and the activity is called ev^n^ ^1.1.

(Heuristic Programming Project 1980, p. 6).

As indicated earlier, an expert system consists of three

major components, a set of rules, a global data base and a rule

interpreter. The rules are actuated by patterns, (which match

the IF sides of the rules) in the global data base. The

application of the rule changes the system status and therefore

the data base, enabling some rules and disabling others. The

rule interpreter uses a control strategy for finding the enabled

rules and deciding which rule to apply. The basic control

strategies used may be top down (goal driven), bottomup (data

driven), or a combination of the two that uses a relaxation-like

convergence process to join these opposite lines of reasoning

together at some intermediate point to yield a problem solution.

9
VI . Uses of Expert Systems

The uses of expert systems are virtually limitless. They

can be used to;

* diagnose

* monitor

* analyze

* interpret

* consult

* plan

' design

* instruct

* explain

* learn

' conceptualize

Thus they are applicable to;

* Mission planning, monitoring, tracking and control

* Communication

* Signal analysis

* Command and control

* Intelligence analysis

* Targeting

* Construction and manufacturing

- design, planning, scheduling, control

Education

- instruction, testing, diagnosis

* Equipment

- design, monitoring, diagnosis, maintenance, repair,

operation, instruction

10
Image Analysis and Interpretat ioti

Professions (law, medicine, engineering, accounting,

law enforcement)

- Consulting, instruction, interpretation, analysis

Software

- Specification, design, verification, maintenance,

instruction

Weapon Systems

- Target identification, electronic warfare, adaptive

control

.

11
VII. Architecture of Expe r t Systems

A . Introduction

One way to classify expert systems is by function (e.g.

diagnosis, planning, etc). However, examination of existing

expert systems indicate that there is little commonality in

detailed system architecture that can be detected from this

classification

.

A more fruitful approach appears to be to look at problem

complexity and problem structure and deduce what data and control

structures might be appropriate to handle these factors.

The Knowledge Engineering community has evolved a number of

techniques which can be utilized in devising suitable expert

system architectures. These techniques* are described in the

following portions of this section.

The use of these techniques in existing expert systems is

illustrated in Table 1**. Table 1 describes the basic approach

taken by each of these expert systems and indicates how the

approach translates into key elements of the Knowledge Base,

Global Data Base and Control Structure. A listing of the systems

in Table 1, together with an indication of their basic control

structures, is given in Table 2.

Table 2 represents the expert system control structures in

terms of the search direction, the control techniques utilized

and the search space transformations employed. The approaches

*This chapter is largely derived from information contained in

the excellent tutorial by Stefik et al. (1982).

**Tables 1-1 to 1-4 are shown on the following pages. Table 1-5

to 1-17 are at the back of this report.

12
wB

(U

4-1 m

>^

c/3

W

hJ

PQ<H

4-1

)-i tUaXw

0)

f-HCL6

cdXw

4-1OWO

•rl 4J

03 •H

}-i <U

4-1 O

ccJ V4

C3 O

00

kT 3

4J

X 3

*H 3 O 3 3 'H 3 T5 X 3 3 3 > hJ X H 3 3 c3 3

C3 3 a 3

T3 3 3 3 3 X

kC

O

X 3

44

T3 33 M

a 3 6t 3 3 *H X

£3 4J 3 3

33 C/3 Pl C3 O1-4 • • H • • • • X C/3 o

CiC

M

13

M o H

H 3'X CJ

t/3 c/3 L-« z:

ZC

X

X

C/3 1-4 <;

60C

•Hc

•rlrt

CJ T3

n)&

5-1 O

Pl4

tcJ

(U 4J

to

54

(UC

(U60e w

cO CO

1—1 0) P-i 4-1

fl4 o

COH

23Wsw

hJw§

CO

4-1 to T3a

to5460O

54

4-1 O

0)CL

CO

CD

0)to 21

d

*H

CO54

4-1 03COO

03Q)

543

4-1 CJ3

54 4J

03

to T3

•rH3

CO U 1 a 3 1 3 3 o 3 O O

OO rH 3 3 3 O 3 O 44 3 3 3 H a X 3 X > 3 3 60 3 X

'H 3 3 T3 3 3 o 3 3 3 •H 3 X X O X X

TO 3 O 3 X 3 3 X 3 X T3 3 3 3 3 3 3 "H O •H X 3 3 T3 O

44 3 3 a 3 3 X 3 3 'H T3 3 X m X 3 3 3 O 3 3 3 3 3 3 O 3 •H 1—i 3 X CL O 60 3 3 3 O 3 X 3 3 3 3

PC o o 3 CL. •H

XX

60

•H

a

4-1

O

O 54 •H 44

T3

0)54Cl

54O

0303 !—5

c§

to 4J3 3

T3 3 O 3 X 3 3

x: 3 3 X X -3 O CL a 3 3 o 3 3 3 X 60

PC

X 3 O

CJ 3 < 3 3 X o X X O 3

Pi 3 3 3 X

P4 •H T3 CL 3 3 *H 3 Td < 3 TP X 3 3 r3 3 3 3 X 3 O 3 3 •H O a 3 & O 3 X X X 3 3 3>

•rH54

03 O

cO54

033

03 C3

CJ TJ

•H *H 'O "3 3 3 3 3

CmO 33

i'OU 3 03 3 3 1—I 'H CJ 3

4-1 XI 3 -H 3 03 3 3 3 3 3 3 3 H 33 3 3 3 aO 3 3 3 44

603 3 a33

60O3

4J 0 3 0 3 3 U

CJ3 CL 3 CL

O

CL 3 3 TO 1

spectrographs
INSTITUTION:

Stanford

University

Characteristics

of

Example

Expert

Systems

AUTHORS :

Lenat

w

c/5 o <

pq

c/5 H < Z H W < S O W

hJW <2

pq >4 O

i-J 2 o

T3C

CO

cO

QJc

0)00 1 4-4 00

4-1 CO c

CO 00 (U w t—1 0 w T) 0 • (U cc3 'H QJ )-i 'H >^ 0 O 0 4-4 cO

w

w (U *H • C

a

U5 CO o 00 4-1 rO CO 'H CO < cO (U cO 6 CO •H pq (U je w 6 o cu T3

T3 4-1 o 0) CJ t3 C4-I

W

H M-l jd •H o W

O 4-4 o O 0^ 4J CO CO >) CO <4-1 • W o Q) O 6 w CJ CO

cO CO •H CO cO 'H

r CO

4-1 4-1 > 4-1 4-1 4J CO cu o c Q) CO (U a 0 CO CO t3

:z QJ 4J *r4 0 0) (U •H (U -H 6 •H w CJ 6 O e

OJ c 0 00

C (U 0 00 T3 1—1

•H CU 0 o 1—1

(U e CO

w 4-1 Pd o OJ •H .05 C 4-1 CO CO r—1

(U PM 4-)

(U U

CO XI

•Hc

CO

CJ

(U • 1-H CO

4-»

H aCO cu . 3 CJ

CO c

1—I o

Pm CJ o

CO 3

cu P u 3 3 4-J

4-J 4J 3 • cu CJ 3 00

CO 3 3 •r-) 3

•T—)CO 3 •H c 3 (U O 3

•H

O jd 3 o O u CO

C/3 00 3

cO CU 6 3 3

(U rH o •H P

X) Xi

p 4J •H •H Mm CO 4m

pc CO 3 O

CJ CO

X P < !m o (U 3 3 o CO CM 4-J u 3 u CO 3 •H

Pm c 4-t

u • *H 1—1

p 1 cu o cu CO • <1 6 c 3 4-J 4J c cu (U (U 3 CO 3 o rH a 00 X o x:

•H cu CO 6 u U CM 3

CO -C CO rCl 3 3 6 u p 4d 3

>M •H CO 3 CO 4J CO o • cO 4-J p

>. jd CJ 3 3 3

4-J V4

u 3 CO CM

4-» !m o u 4-J 6 o

PM CO cu cO cO 3 o X

CU 4-J

X (U -3 rH 4d 3 O cn 4-J cn 4-J 3 (3) cO C0 W

C/5 •• o

Pm o Oi M 3) H Pm

C_)

Pm

O COo

-H

J-( 4-1

W

QJ cO 4-) >6 0. O 0) (U O o (Owe •H CO O Q 6 CJ 14
INSTITUTION:

nmi

Characteristics

of

Example

Expert

Systems

AUTHORS :

McDermott c

00

•H

(0QJ O o

c/3 HaWSw

kJww

bOd

•H c o

QJ ttj > u

•H +J u ^ r o

cj nJ ^ H 4-1 <; CO o

is T3

C co

•H

4-1 cO3 • —or-

3 , s 4J rH

r-H 00 3 3 3

.c • 3 4-»

O

O V4 00 CO •H >< T3 -H 3 4-J 3 cu 00 3 4-1 o

P4J

O 3 •H 3 3 3 3 o

CO V4 3 B 3 4J

U 00 < 3 O o s X 3

pa

O 3 4-1 3 00 s

LW CL,

u T3 • u •H rH

td o B 3 CU (U 3 3 O CH 3 O o t3 > CO 4J O 4-1 3 4J O CO CJ o 3 3 w O 3

td 3 S-i

B ja 4J 3 E

•H

O CO o 3 •H

4-1 < «+-l o Jd M-l rili tH c J-i > u CO B 3 3 0

(U 0) 3 3 3 Cd ’H 5-4 tH

Cl 3 3 u 4-1 3 4J 4J (a, 3 o o t-H CU ja 3 iH ja M Cu 4-J

!-iO 3 ja 3 S 3 3 3 C o s <r Pd 3 3 Pd 3 CL, W 4-1

00 3 « •H 3

33 Jd M-l 4-J

S-4 3 0 3 O 3 O 4-J

4-J CJ 3 33 4-J T—\ E E 3 cd 3 o 3 •H 4-J

4-1 S-i 4-J 3 3 i-l 5-1 s 3 3 cd CO o CJ>

33 3 • 3

00 3 3 4J 3 4-J •H 3 3 • o 3 4-J 3 4-J o *H 3 4-1 tH ja 3 3 3

fH • 3 •H 3 o o u 3 -Q •H 3 •

L4-4 3 3 • ja • 3

33 Ca

O 3 3 3 > 3 3 Cli 3 3 O O 33

ja

O CJ 3 X

O E i-l 4-J 3 O 3 1—1 O

cc 3 O ja ja 3 <4-1 t3 u

<;

O •r4 4J *3 ja 3 33

4-J 3 3 3 •H 3 3 3 O

Pd

Ph

PLJ 3 3 •H 3 H 3 O

X

•H 3 3 • Jd •H • • Jd 3 O 3 E 00 3 <4-1 Cl, 3 3 4-1 4-J 4-J 3 3 3 3 3 Jd 4-J 3 3 3 '3 4-J •H 4-J 3 3 3 3 •H 3 3 m-4 ja ja E 3 •H 3 3 3 s ,3 3 4-1 3 4-J E O 3 o I—1 3 3 3 s ja O, 3 3, 3 a 3 3 4J E X E 3 4J 3

ja •H

O 3 CJ o o o 3 3 CJ 3 CJ -Q o 3, O -3 3 3

Cl, 33 i-l 4J 3 3 3 i-l 4J 4-J 4-1 4J s O

ad >-iO 3 3 3 3 3 o 3 3 3 CJ P-i S Cl, Pm i-I Q > 4J 3 33 ,—i X

S-i

U > • • • • • O 3

pa o 1—1

CM

m

m l3 CO 3

TJ]

(0 V-l e (u

Qj e

><; 4-1 o < W 4-1 > s W

(/) 3

0) CJ

>-l !-J M-l 3 cu CO O

00 iJ •H 3 e V-I 14-1 CL, O 0) 3 E M TO O O C4-4 )-l o o ' o 3

OJ3o

CL, 6o

CJ 15
Characteristics

of

Example

Expert

Systems
Table

2

Control

Structure

COdo

0)o

d co a e

OO 5-1 o

rdO CO

5-1 d

CO CO OJ S-i CAl H

o

d

4-) d

oo

uox^njosa^ XEDrqoaeaaTH

XuauiauTja^

suiaxqoa(j-qns oqur ^inaag

sx^POR ^idj^x^R

ao^xpa i^aoM^aR

SuTuosBaa JO saurxTlT^R

auauiaaruiuioa xseaq

§UTqaBaa:qDFg auaAaxs^

SuTSsanf) asax puB aaBaaua^

qojBas aAjasnBqxa

X K

^ X

X X

X

X

XX X

X

do

•H x: -u

<j a

t-i (U

to >-i 0)

• cn o

X

co

=1di

•HI «!

6l

cu

4-1 CO

M-lo

COo

•H

4-1 CO •H

CU +JO

cO

)-i cO X

cj)

uaATaQ auaAg

paBAi>ioBg puB paBAiaoa

paBw:qDBg

pjBMaoa

X

X X

X X 'X X X X X X X

CO CO • x:

4-1 CO a

•H •H u CO d d cu u

o CJ TJ t)D V4 CO d 0

cu i-4 •H cu cu V4 u CO •H P fH d 4-1 OJ d 4-1 d 4-t cu o O rH

'X •H CO •H bO CO •H CO 4-1 CO CO •H X £ cO M o •H • o O •H o •H d 4J 4J 4J • o *J •H B a rH B -d •H B a o O (U o (U CO •d cu cu •d o QJ 4-t T3 cu B p X d cu cu >, o (U -d rH cu cu -d eg CU X o o o lU rH a u Q S CJ w S X c:j S S o X C4i prf X w CO o

d

o

•H •

• 4-1 M

• CO cO • CU • H B u l-l D- d H a (U a

U cr O 60 d 4-t Vt

CO CU o Pm d (U d cu 'X •H 4-t CO <3 t)0 XJ bO bO M U

O CO d •H d 4-1 M d d d z d M o M CO • • •iH a O M d •H •H d d 1—1 M

H d M tH d cu 4-t &o d d bO bO CO CJ W) cO rH • S-i o •H cO •H d d •H •iH d CO X cO 4-t cO <3 o cO d d 4-t CO CO CO CO CO bO 4J tu •H CO d • d CU o o CO cu 1—1 1—1 cu (U •H CO o Q < c;j W X CLJ S Q O (X P O o CO o

X M

(X M

n

a c/3 >4 CO X w P-i M

X Q M !3 CO X

[ij 13 O 1 ai W Ibi >4 <3 H M P « <3 H pC2 C-D < CO

oo a 2: M c/o H 1—

1

CO P fX 2

>H w X X W S <3 tH PQ o O >4 w < CX

cyj o w O S CJ3 (X <3 s CO 3S CJ

17
used in the various expert systems are different implementations

of two basic ideas for overcoming the combinatorial explosion

associated with search in real complex problems. These two ideas

ar e : (1) Find ways to efficiently search a space,

(2) Find ways to transform a large search space into

smaller manageable chunks that can be searched

ef f iciently

.

It will be observed from Table 2 that there is little

architectural commonality based either on function or domain of

expertise. Instead, expert system design may best be considered

as an art form, like custom home architecture, in which the

chosen design can be implemented using the collection of

techniques discussed below.

B . Choice of Solution Pi r ect ion

^ • F orward Chaining

When data or basic ideas are a starting point, forward

chaining is a natural direction for problem solving. It has

been used in expert systems for data analysis, design,

diagnosis, and concept formation.

2 . Background Chaining

This approach is applicable when a goal or a hypotheses is a starting point. Expert system examples

include those used for diagnosis and planning.

3 . Forward and Backward Processing Combined

When the search space is large, one approach is to

search both from the initial state and from the goal or

hypothesis state and utilize a relaxation type approach to

18
match the solutions at an intermediate point. This approach

is also useful when the search space can be divided

hierarchically, so both a bottom up and top down search can

be appropriately combined. Such a combined search is

particularly applicable to complex problems incorporating

uncertainties, such as speech understanding as exemplified

i n HEARSAY 1 1

.

4 . Event Driven

This problem solving direction is similar to forward

chaining except that the data or situation is evolving over

time. In this case the next step is chosen either on the

basis of new data or in response to a changed situation

resulting from the last problem solving step taken. This

event driven approach is appropriate for real-time

operations, such as monitoring or control, and is also

applicable to many planning problems.

C. Reasoning i n the Presence of Uncertainty

In many cases, we must deal with uncertainty in data or in

knowledge. Diagnosis and data analysis are typical examples.

1 . Numer ic Procedures

Numeric procedures have been devised to handle

approximations by combining evidence. MYCIN utilizes

"certainty factors" (related to probabilities) which use the

range of 0 to 1 to indicate the strength of the evidence.

Fuzzy set theory, based on possibilities, can also be

utilized.

19
2 • Belief Revision or " T

r

uJbJi Maintenance”

Often, beliefs are formed or lines of reasoning are

developed based on partial or errorful information. When

contradictions occur, the incorrect beliefs or lines of

reasoning causing the contradictions, and all wrong

conclusions resulting from them, must be retracted. To

enable this, a data-base record of beliefs and their

justifications must be maintained. Using this approach,

truth maintenance techniques can exploit redundancies in

experimental data to increase system reliability.

D. Searching a Small Search Space

Many straightforward problems in areas such as design,

diagnosis and analysis have small search spaces, either because

1) the problem is small or 2) the problem can be broken up into

small independent subproblems. Often a single line of reasoning

is sufficient and so backtracking is not required. In such

cases, the direct approach of exhaustive search can be

appropriate, as was used in MYCIN and Rl.

E . Techniques for Searching a Large Search Space

1. Hierarchical Generate and Test

State space search is often formulated as "generate and

test” - reasoning by elimination. In this approach, the

system generates possible solutions and a tester prunes

those solutions that fail to meet appropriate criteria.

Such exhaustive reasoning by elimination can be appropriate

for small search spaces, but for large search spaces more

powerful technique are needed. A "hierarchical generate and

test” approach can be very effective if means are available

20
for evaluating candidate solutions that are only partially

specified. In these cases, early pruning of whole branches

(representing entire classes of solutions associated with

these partial specifications) is possible, massively

reducing the search required.

'•Hierarchical generate and test" is appropriate for

many large data interpretation and diagnosis problems, for

which all solutions are desired, providing a generator can

be devised that can partition the solution space in ways

that allow for early pruning.

In the "generate and test" approach, when a line of

reasoning fails and must be retracted, one approach is to

backtrack to the most recent choice point (chronological

backtracking). However, it is often much more efficient to

trace errors and inconsistencies back to the inferential

steps that created them, using dependency records as is done

in MOLGEN. Backtracking that is based on dependencies and

determines what to invalidate is called dependency-directed

(or relevant) backtracking.

This approach can be used to broaden the coverage of an

incomplete search. In this case, search programs that have

fallible evaluators can decrease the chances of discarding a good solution from weak evidence by carrying a limited

number of solutions in parallel, until which of the

Reasoning

solutions is best is clarified.
F . M ® f.£I. Space b^ j^np

the Space

1. Breaking the Problem Down Into Subproblems

a . Non-Interacting Subproblems

This approach (yielding smaller search spaces) is

applicable for problems in which a number of non-interacting

tasks have to be done to achieve a goal. Unfortunately, few

real world problems of any magnitude fall into this class,

b . Interacting Subproblems

For most complex problems that can be broken up into

subproblems, it has been found that the subproblems interact

so that valid solutions cannot be found independently.

However, to take advantage of the smaller search spaces

associated with this approach, a number of techniques have

been devised to deal with these interactions.

(1) F_ind a F^xed Sequence o^ £H^£££^ So Tha_t No

Interactions Occur

Sometimes it is possible to find an ordered

partioning so that no interactions occur. The Rl

system (see Table 1-3) for configuring VAX computers

successfully takes this approach.

( 2 ) Least Commitment

This technique coordinates decision-making with

the availability of information and moves the focus of

problem-solving activity among the available

subproblems. Decisions are not made arbitrarily or

prematurely, but are postponed until there is enough

information. In planning problems this is exemplified

by methods that assign a partial ordering of operators

22
in each subproblem and only complete the ordering when

sufficient information on the interactions of the subproblems is developed.

( 3 ) Constraint Proprogat ion

Another approach (used by MOLGEN) is to represent

the interaction between the subproblems as constraints.

Constraints can be viewed as partial descriptions of

entities, or as relationships (subgoals) that must be

satisfied. Constraint proprogation is a mechanism for

moving information between subproblems. By introducing

constraints instead of choosing particular values, a problem solver is able to pursue a least commitment

style of problem solving.

( 4 ) Guessing or Plausible Reasoning

Guessing is an inherent part of heuristic search,

but is particularly important in working with

interacting subproblems. For instance, in the least

commitment approach the solution process must come to a halt when it has insufficient information for deciding

between competing choices. In such cases, heuristic

guessing is needed to carry the solution process along.

If the guesses are wrong, then d e pe nd e n c y- d i r e c t e

d

backtacking can be used to efficiently recover from

them. EL and MOLGEN take this approach.

2 . Hierarchical Ref ine m ent into Increasingly Elaborate Spaces — Top Down Ref i nemen

t

Often, the most important aspects of a problem can be

23
abstracted and a high level solution developed. This

solution can then be iteratively refined, successively

including more details. An example is to initially plan a

trip using a reduced scale map to locate the main highways,

and then use more detailed maps to refine the plan. This

technique has many applications as the top level search

space is suitably small. The resulting high level solution

constrains the search to a small portion of the search space

at the next lower level, so that at each level the solution

can readily be found. This procedure is an important

technique for preventing combinatorial explosions in

searching for a solution.

3 . Hierarchical Resolution into Cont r i bu t i ng Sub-Spaces

Certain problems can have their solution space hierarchically resolved into contributing subspaces in which the

elements of the higher level spaces are composed of elements

from the lower spaces. Thus, in speech understanding, words

would be composed of syllables, phrases of words, and

sentences of phrases. The resulting heterogenous subspaces

are fundamentally different from the top level solution

space. However the solution candidates at each level are

useful for restricting the range of search at the adjacent

levels, again acting as an important restraint on

combinatorial explosion. Another example of a possible

hierarchical resolution is in electrical equipment design

where subcomponents contribute to the black box level, which

24
in turn contribute to the^system level. ^

S imilar ly#^ examples

(S( ,.can be found in architecture, and in spacecraft and aircraft

design^, ^ rpft Jt al", A -

- p/^i: jt « 1/4 i. 1/ /jio i j ''I - tioj '

, do e- " m&&

^oi'a^fco.'q ^:p iiab trtT Xut>13t1iib V’«v' »J| X»6offi

tn

«.T03 BjWfro.'q iiab *rtT .iXUbll

P-^VliXqmla vl^«9 ip t««

* \wa»j :aa v>aiV:

9d. n«o *aQ 9 dtT ob oi

/atl^llHl Ulan *»i‘i. t

'itoi'<< w

''«

Jl a _S||r 1'*' ijl a •

^ i rt oq , X « !1 » V © a

'i.- xf/i ,Xavrf»i itP.Xrfosq 9^n

|M|»«nfii4'i. c 4 \ X t ^ .d nl b» 5 v a^Xoi ftjem

n

P''*'

' V;j‘ , , 4,XDqK^ So «»no6 '»X;3^Jf4

'jt

-

* ’

' '^ ' “ ^ -ia .'. '* '

' 'ts^

'

'

'

' ' '•'''>;<• ^4pfllX»^l6 oi'4»4oft'd:iqq* &a» eoiloXioi sriT »tXi9 i“olXqx#> afeiJ 4^iv

1r

- ''- ' '. • 'a?t. :

' •' ' •

'..

' -

'' '

' ^"', ' "

.^-V; - . «««a^ i*.

'i .

• yi^mli r6 s^juiUt diLw ^

,:J

.V, l^'- . ,

' a_u j-ugxj^ Xiyioi 3 t^b;U 8

:>«>? x< xip6Piqq*' \r>*B» 9tiu3Bui.utjt9d ^4rtoiiW^ia

‘ • "'’ '-

' ei*'

'

, . ®'"‘ V

' % " fr^a AaoiioA a»on#t<p»8 ettXiHda#iq;#2 joV a»YeB bna

. .'< • . •' - ^ n .r.

' : . '

, :#» %, ' '

, *^’ .

> doirtw »* io jpaowoo ©<U ar^u^^l .e^taaSlA tlod:}

r ‘^ -V

, ^ . -

,

h /k?rtv n*dv ©&A^%rib
G . M e_t h o d£ f.o£ 1 a Search S£a c e by D e v e_l o£ i. n£

Alternative or Additional Spaces

1 . Employing Multiple Models

Sometimes the search for a solution utilizing a single

model is very difficult. The use of alternative models for

either the whole or part of the problem may greatly simplify

the search. The SYN program is a good example of combining

the strengths of multiple models by employing equivalent

forms of electrical circuits.

2 . Meta Reasoning

It is possible to add additional layers of spaces to a search space to help decide what to do next. These can be

thought of as strategy and tactical layers in which meta

problem solvers choose among several potential methods for

deciding what to do next at the problem level. The

strategy, focusing and scheduling meta rules used in

CRYSALIS and the use of a strategy space in MOLGEN fall into

this category.

H . Dealing with Time

Little has been done in the way of expert systems that deal

with time explicitly. The following are approaches to dealing

with time in terms of time intervals.

1 . Situational Calculus

Situational calculus was an early approach by McCarthy

and Hayes (1969) for representing sequences of actions and

their effects. It uses the concept of "situations" which

change when sufficient actions have taken place, or when

new data indicates a situational shift is appropriate. Sit26
uations determine the context for actions and, through the

use of "frames,"* can indicate what changes and what remains

the same when an action takes place. VM uses the situation

approach for monitoring patient breathing.

2. Planning with Time Constraints

NOAH was an early parallel planner which dealt with

interacting subgoals. The method of least commitment and

backward chaining initially produced a partial ordering of

operators for each plan. When interference between subgoal

plans was observed, the planner adjusted the ordering of the

operators to resolve the interference to produce a final

parallel plan with time ordered operators. DEVISER (Vere,

1981) is a recent derivative of NOAH which extends this

parallel planning approach to treat goals with time

constraints and durations. The principal output of DEVISER

is a partially ordered network of parallel activities for

use in planning a spacecraft's actions during a planetary

flyby

.

*A frame is a data structure for describing a stereotyped

situation

.

27
VIII. Existing Expert Systems

Table 3 is a list, classified by function and domain of use,

of most of the existing major expert systems. It will be observed that there is a predominance of systems in the Medical and

Chemistry domains following from the pioneering efforts at

Stanford University. From the list, it is also apparent that

Stanford University dominates in number of systems, followed by

CMU, MIT and SRI, with a dozen scattered efforts elsewhere.

The list indicates that thus far the major areas of expert

systems development have been in diagnosis, data analysis and

interpretation, planning and design. However, the list also

indicates that a few pioneering expert systems already exist in

quite a number of other functional areas. In addition, a substantial effort is underway to build expert systems as tools

for constructing expert systems.

DENDRAL (Lindsay et al., 1980), which produces molecular

structural representations from mass spectrogram data, has been

the most widely used expert system. It has subsequently been

generalized to CONGEN to produce a set of structural candidates

from whatever constraining data is available.

Feigenbaum (1982, p. 16) states that the most knowledge

intensive system is INTERNIST, a medical diagnosis system which

considers almost 500 diseases and contains over 100,000 pieces of

knowledge

.

28
0) S bO

bO

m P • M (D • c • pi P P p 0 PP rP • G

•H • CO P p pS

p

p> Eh CO -p 1 p 0 • ^ P> 0 p P 0

p>M <U -H Cm = Pi 0 Cm •H • bO 0^ C 0 P C

-P s -P cc3 Cm cc3 CO pi <P -P C • P C « 0 CO cc5 EH CO M P> • • CO M P • P p 0

bO CO P • • P 0 • P EH EH pi p P 0) M 0 • • P — • (—1 K Cm M M P p ctJ CO C • • •r~l c • >H

nj s cd 0 P W K

CO

SI ^ o o0 ccJ • • p -P p p p C • o3 p p

EH 0) CO

M

M

p *rJ

p

p • c K K p C 0 0 M 0 • CO CO p cd <M Cm • p 1—1

cr; c C

CO ccJ ccJ ccj 0 P p

>H CO CO

12: <1-1 ^ o

CO

D

EH

CO * EH M G W s s E<

d)p SiK

M PlH

K c p M CO P u :=) < 0 CO P < Eh >H Oh Q

•H 0 S s P CO H oc «c

CO

K

M 0 CO > P EH M < Q < 0 P S 0 < K rH W < s s a < P w P P 0 CJ> K s c5 CO >H W 0 w w H H 0 K < s EH

Eh

Qp 0 s W p s

OuMQ

i-q

K < s CO w p

CO

w CO

p

K s s Q 0 s w s K l-H w s w s

CJ >H 0 0 < « CO < C5

p

w CO s w 0 EH

H

p

p

Q

CU >H CO s CO > p 0 <

CO

m

w 1 s Eh «< Q p H o s

on

>>wG0) -p

w

•H

CO

(U CO cd P bO CO 1—1

l>» P CO c cdC CO CO CO bO 0 P CO P CO 0 CO c p •H CO •rH •rH !>» C •rH cd cd p •H G :=i E •H CO CO P •rH p

Eh

p CO

p •H

p dJ

p bo E CO <l) (U >3 c <L)

p

p bO cd iH cd •H ccJ (L)

p

p rH c C

CD

r—1 0 0 E p <u

p P P p

p CO cd 0) l>3 P rH P CL) 0 p c bO p c c 0 1—1

CD P X CD cd >5 1—1

•H

p

p

p 0 0 C s •(H s P P w c c pin P P >5 cd CD p p EH CD P l>j CO CO p = p P CO H •H bO P p bO p cd P CO 0 cd T3 cd rH

bO cd CJ

p 0 CO CO 0 CO 1 CO 0)

G 1(H

p

pC 1s c G •H •H 1—1

o3 0 0 <D 0 p cc3 cc5 0 <U cd 0 (p •H 0 p 0 G G 0 p 0 0 •H P P •rH •rH 0 0 p c p 0 p p 0 <u 0) d) <u (U 0 *(—1

•H c 0 CO

p •rH •H cd

p 0) CD

CO 2 P c5 P P C5 P l-H cd plH >5 cc3 0 E E —1 w 1—

*H S 0 0 c P 0 p CO E p (L) CD

p 0 X 0 •H c p 0 P 0 *H P p •g^ w 0 OJ CD G 0) CO p P CD CD CD p 1 s s cc3 CD cs 0 W CO EH P C

S-. Pl, nj

t>

nJ

p!P^GO

CJ) co

•(H -po3 CO p E

•rH 0 0

CO

p

p S ft Cm 0

CO 1—1 p 0 C •rH cd 0 CO bO bO C 0 CO C p •rH P c 0

•rH 0 < c CO c •rH •rH •rH p C M bO c c p

CJ to cd fH •rH c p 0 c cd -P P cd CO cd cc3 ft

Di •rH cd

CC <v rH 0 X

p 0 Q cc5 < Q Oh P w

29
ocM• • • • c D m D p D o 1—1

•H 'O o TJ t3 • tJ

p> Pi

p Pi Pi IS Pi

pi

D

O +4

O o . o

-p S ~ Cm c Cm Cm

m Cm •H O o C o C C • C

p> c\3

u cd cti CQ cj

M P> +5 P> P C CO B CO CO CO M 0) 4^

tn W • • • • • P W p M p t/3 p W P Pi p p p d p

Pi 0)

H TJ Pi

M Pi

p S Pi

O fjc

K

C

O

—

O S o

Cm

p

p cd P CO P o p

p t:s

C pi p=: £P

p

C o c C

<l3K ci5p cd Clj c6 P' p p • P P p p P P —

CM CO

C\

-p

G

H (U

Hp

H

H <d 1—1 * w s H EH S L(0

p •=ri

B P P P s H o p

K

H P H s P •H

(U <C P P s o KQ

H

W

p

HW < o P o S p

p < P « P < > o P M

K P < p CO P p P M o (D

wK < P W < O P H

XO < K s o p

K -P

>5 < K

p P CO P w P C

H

M

O P p W W > < P P #S

cc(7\ Oo

oowG

PQ<

&H

w cd c P

•H cd

tJD

p c Q

C c CO o o

•rH CO 0) o rH o to to •rH

C P o o *H CO B p •rH •rH P •rH C •H c p X cd CO CO CO cd

CO cc3 P cc3 cc3 1—1 o o o P P

CJ -P CO 1—1

cd

M 1—1CdC 1—1

Cd

H CO 13 •H *H

C

O

p

M tsO Cd >> cd P o 0) p < 0 cd cd CO tiO O

cc5 0) o > CO P o •H •HC o P c P = < (D 1—1 o Q o 1—1

•H <D c K cd tn EH o o (U

cd

D (U P (D 1—1 1—1

(U P B -P c P d P o cd cC 1—1

CO o cc3 P H c C p d •H o O cd cd Q S O p cc3 (U o P c •rH •rH CJ cd

OJ o 0) •H ^3 s o P P •rH o

<u cd o p J-i

O Sh OJ o P p S o cd P o p 2 <u CO p P P o S

d) 0) 1—1

cd

p

H o CO •H >•5 p to o c c cd (U o o Ch CO •H •rH p bO a; p P to C P C ccJ •rH Cd •rH p ^ o p CO o P 1—1

*H (U •rH CO £d

O CO

p

p Cd cd P CA

cc3

p (D P S p 1—1 a i-l P o (D to CO —

<D Jh •rH

C < P S-i 0) o P W) O < o CO <u o cd p C C CO •H <u X p cd cd

C

H •H •H

p icD P cd 0) cd

O +0 !U > (D c; P P Ch cd •H P 1—! O p P cd (D P (U 4d p O oj P < 0 Ch »—1

!C| (U P o o O C •H P p 0) bO 0) cd c c tiO C (U e CO o P cd K m o •H o to O c c X S p o CO 2 D CO M X H M *

30
IX. Tools for Building Expe r t Systems

To aid in the building of expert systems, special

programming tools have recently begun to be developed. These are

listed in Table 4. The most ambitious is AGE (Attempt to

Generalize). AGE (Nii and Aiello, 1979) has isolated a number of

inference, control and representation techniques from a few

previous expert systems and has reprogrammed them for domain

independence. AGE, itself an expert system, also guides people

in the use of these modules in constructing their own

individualized expert systems. AGE also provides two predefined

configurations of components. One called the "Blackboard

framework” is for building programs that are based on the

Blackboard model, as was used in HEARSAY II. The Blackboard

model uses the concepts of a globally accessible data structure,

called a blackboard, and independent sources of knowledge which

cooperate in forming hypotheses. The other predefined

configuration, called the "Backchain framework," is for building

programs that use backward chaining production rules like those

used in MYCIN.

31
Table 4

Tool

OPS 5

EMYCIN

KAS

ROSIE

AGE

HEARSAY

UNITS

Programming Tools for Building Expe r t Systems

Organ! zat ion

CMU

Standford U.

SRI

RAND

Stanford U.

Ill USC/I nf orma t ion

Sciences

Institute

Stanford U.

Nature

A programming language builton top of LISP

designed to facilitate

the use of production

rules

.

A domain independent

version of MYCIN, which

accompanies the backward

chaining and explanation

approach with user aids.

Supervises interaction

with an expert in

building or augmenting an

expert system knowledge

base in a network form

implemented for PROSPECTOR.

A general rule-based programming language that

can be used to develop

large knowledge bases.

Translates near-English

into INTERLISP.

A sophisticated expert

system to aid users in

building expert systems.

A generalized domainindependent extension of

HEARSAY II. Includes a "context" mechanism, and

an elaborated "blackboard" and scheduler.

A knowledge representation language and interactive knowledge acquisition system. The

language provides both

for "frame" structures

and production rules.

32
Table 4 (continued)

Proqramming Tools for Building Expert Systems

Tool Organization Nature

TEIRESIAS Stanford U. A expert system that

facilitates the interactive transfer of

knowledge from a human

expert to the system via

a (restricted) natural

language dialog.

33
X. Constructing An Expert System

Duda (1981, p. 262) states that to construct a successful

expert system, the following prerequisites must be met:

there must be at least one human expert acknowledged to

perform the task well

* the primary source of the expert's exceptional

performance must be special knowledge, judgment, and

experience

* the expert must be able to explain the special

knowledge and experience and the methods used to apply

them to particular problems

* the task must have a well-bounded domain of application

Randy Davis (MIT) at IJCAI-8I* noted that a good expert

system application:

* doesn't require common sense

* takes an expert a few minutes to a few hours

* has an expert available and willing to be committed.

Hayes-Roth (198I, p. 2 ) adds that "...the problem should be

nontrivial but tractable, with promising avenues for incremental

expansion.

Having found an appropriate problem and an accessible

expert, it is then necessary to have available an appropriate

s y s t e m - b u

i

1 d i ng tool, such as those described in the last

chapter. Realistic and incremental objectives should then be

set. Major pitfalls to be avoided in developing an expert system

are choosing a poor problem, excessive aspirations, and

inadequate resources.

*The International Joint Conference on Artificial Intelligence,

Vancouver, August 1981.

34
The time for construction of early expert systems was in the

range of 20-50 man-years. Recently, breadboard versions of

simple expert sysems have been reported to have been built in as

little as 3 man-months, but a complex system is still apt to take

as long as 10 man-years to complete. Using present techniques,

the time for development appears to be converging towards 5 manyears per system. Most systems take 2-5 people to construct, but

not more. (It takes one to two years to develop an engineer or

computer scientist into a knowledge engineer.)

Randy Davis (at IJCAI-81) indicated that the stages of

development of an expert system can be considered to be*:

1. System design

2. System development (conference paper level)

3. Formal evaluation of performance

4. Formal evaluation of acceptance

5. Extended use in prototype environment

6. Development of maintenance plans

7. System release.

*Thus far, no current system has completed all these stages.

35
X I . Knowledge Learning

^ A cquisition

The key bottleneck in developing an expert system is

building the knowledge base by having a knowledge engineer

interact with the expert(s). Expert systems can be used to

facilitate the process. Some of these expert systems are

indicated in Table 3, with the KAS system being elaborated upon

in Table 1-7.

The most ambitious of these systems is TEIRESIAS (Davis and

Lenat, 1982) which supervises interaction with an expert in

building or augmenting a MYCIN rule set. TEIRESIAS uses a model

of MYCIN’s knowledge base to tell whether some new piece of

information "fits in" to what is already known, and uses this

information to make suggestions to the expert. An appropriate

expert may not always be continuously available during the

construction of the expert system, and in many cases may not have

all the expertise desired. In these cases other approaches to

acquiring the needed expertise is desirable.

B . Self - learning and Discovery

Michie (1980, p. 11) observes that "The rule-based structure

of expert systems facilitates acquisition by the system of new

rules and modification of existing rules, not only by tutorial

interaction with a human domain specialist but also by autonomous

'learning*." A typical functional application is

"classification," for which rules are discovered by induction for

large collections of samples (Quinlin, 1979). Michie (1980, p.

12) provides a list of examples of various "learning" expert

systems.

36
DENDRAL, for obtaining structural representations of organic

molecules, is the most widely used expert system. As the

knowledge acquisition bottleneck is a critical problem, a METADENDRAL expert system (outlined in Table 1-8) was written to

attempt to model the processes of theory formation to generate a set of general fragmentation rules of the form used by DENDRAL.

The method used by META-DENDRAL is to generate, test and refine a set of candidate rules from data of known molecule structurespectrum pairs. For META-DENDRAL and several of the other

learning expert systems, the generated rules were found to be of

high quality (Feigenbaum, 1980 and Michie, 1980).

Another attempt at modeling sel f- lea r n i ng and discovery is

the AM Program (Davis and Lenat, 1982) for discovery of

mathematical concepts, beginning with elementary ideas in set

theory. AM (outlined in Table 1-2) also uses a "generate and

test" control structure. The program searches a space of

possible conjectures that can be generated from the elementary

ideas in set theory, chooses the most interesting, and pursues

that line of reasoning. The program was successful in

rediscovering many of the fundamental notions of mathematics, but

eventually began exploring a bigger search space than the

original heuristic knowledge given to it could cope with. A more

recent project - EURISKO - is exploring how a program can devise

new heuristics to associate with new concepts as it discovers

t hem

.

37
XII. Who Doing It

The following is a list by category of the "principal

players" in expert systems. In each category, the listing

roughly reflects the amount of effort in expert systems at that

institution. Stanford University is the major center of effort

in expert systems.

Un iversities

Stanf ord

MIT

CMU

and scattered efforts at perhaps a dozen other universities.

Non-Profit

SRI

RAND

JPL

Government

NRL AI Lab, Washington, D.C.

NOSC, San Diego, CA

Ind ustr i al

Fairchild

Schlumberger

Machine Intelligence Corp., Sunnyvale, CA

Xerox PARC

Texas Instruments

Teknowlege, Palo Alto, CA

DEC

Bell Labs

IntelliGenetics, Palo Alto, CA

TRW

BBN

IBM

Hewlett Packard, Palo Alto, CA

Martin Marietta, Denver, CO

Hughes

AMOCO

JAYCOR, Alexandria, VA

AIDS, Mt. View, CA

Systems Control, Inc., Palo Alto, CA

38
XIII. Who i^s F unding It

To date, the government has been the principal source of

funds of work in expert systems. The funding sources in the

government for expert systems, roughly in decreasing order of

expenditure, are:

DARPA

NIH (National Insitutes of Health)

NSF

ONR

NLM (National Library of Medicine)

AFOSR

uses

NASA

DARPA and NIH have been the primary funders of expert systems to

da te

.

Obtaining precise figures for funding of expert systems (ES)

is virtually impossible because ES is not carried as a separate

funding category. In addition, expert systems are often embedded

in other AI systems such as image understanding systems.

Further, with artificial intelligence becoming heavily knowledgeoriented, a substantial portion of current AI systems and

activities can be viewed as having expert system components.

Nevertheless, a rough estimate of the current total U.S.

government yearly funding for expert systems research and

development would be in the order of 10 million dollars. Of this

expenditure, approximately several million is spent by DARPA to

support basic research.

NIH funds the AIM (Artificial Intelligence in Medicine)

network (NIH, 1980) and its users at a little over three million

dollars a year. This nationally shared computing resource is

devoted entirely to designing AI applications for the biomedical

39
sciences. The community of projects using this resource is

expert systems oriented. Approximately one third of the three

million dollar expenditure in the AIM area can be considered to

be for direct research, the balance being for applications,

experimentation and system support.

NSF, focussed more on basic research, funds approximately

one million dollars per year in the expert systems area. Other

government agencies probably spend another two to three million

dollars per year to support a variety of potential applications.

Finally, government contractors using IRAD (Independent

Research and Development) funds (associated with their prime

contracts) probably spend another one to two million dollars a

year in this area.

40
XIV. Summ ary of the State-of-the-Art

Buchanan (1981, pp. 6-7) indicates that the current state of

the art in expert systems is characterized by;

* Narro w dom ain of expe r t i se

Because of the difficulty in building and maintaining a large knowledge base, the typical domain of expertise is

narrow. The principle exception is INTERNIST, for which the

knowledge base covers 500 disease diagnoses. However, this

broad coverage is achieved by using a relatively shallow set

of relationships between diseases and associated symptoms.

(INTERNIST is now being replace by CADUCEUS, which can

diagnose simultaneous unrelated diseases).

' Lim ited kno w ledge representation languages for facts and

relations

* Relatively inflexible and s tyl i zed input-output languages

* Stylized and 1 imi ted explanations by the systems

* Laborious construction

At present, it requires a knowledge engineer to work

with a human expert to laboriously extract and structure the

information to build the knowledge base. However, once the

basic system has been built, in a few cases it has been

possible to write knowledge acquisition systems to help

extend the knowledge base by direct interaction with a human

expert, without the aid of a knowledge engineer.

* Single expert as a " knowledge czar."

We are currently limited in our ability to maintain

consistency among overlapping items in the knowledge base.

Therefore, though it is desirable for several experts to

41
contribute, one expert must maintain control to insure the

quality of the data base.

In addition, most systems exhibit fragile behavior at the

boundaries of their capabilities, so that occasionally even some

of the best systems come up with wrong answers. Another

limitation is that for most current systems only their builders

or other knowledge engineers can successfully operate them.

Nevertheless, Randy Davis (at IJCAI-81) observed that there

have been notable successes. A methodology has been developed

for explicating informal knowledge. Representing and using

empirical associations, four systems have been routinely solving

difficult problems - DENDRAL, MACSYMA, MOLGEN and PUFF - and are

in regular use. The first three all have serious users who are

only loosely coupled to the system designers. DENDRAL, which

analyzes chemical instrument data to determine the underlying

molecular structure, has been the most widely used program (see

Lindsay et al., 1 98 0 ). Rl, which is used to configure VAX

computer systems, has been reported to be saving DEC several

millions of dollars per year, and is now being followed up with

XCON .

In addition, as indicated in Table 3, several dozen systems

have been built and are being experimented with.

42
XV Current Problems and Issues

Buchanan (1981, p. 11) states, "Because of the increased

emphasis on large knowledge bases, the three issues of

explanation, acquisition and validation are becoming critical

issues for expert systems."

Explanation

Explanation is needed because users cannot be expected to

know or understand the whole program.

Knowledge Acquisition

Feigenbaum (1982, p. 13) states, "...knowledge acquisition

is the criticial bottleneck problem in Artificial Intelligence."

Knowledge acquisition is difficult and time consuming. The most

difficult part is helping the expert to initially structure the

domain. The knowledge engineer takes an active role in the

knowledge acquisition process - interpreting and integrating the

experts answers to questions, drawing analogies, posing counterexamples, and raising conceptual difficulties.

Duda (1981, p. 264) observes, "Past efforts to speed

knowledge acquisition have been along three lines; (1) to develop

smart editors that assist in entering and modifying rules, (2) to

develop an intelligent interface that can interview the expert

and formulate the rules, and (3) to develop a learning system

that can induce rules from examples, or by reading textbooks and

papers." Duda also notes "...that it is difficult for experts to

describe exactly how they do what they do, especially with

respect to their use of judgment, experience, and intuition...

We need to develop more expressive languages that allow the

expert to articulate more of the nuances and details of thought

43
processes." Diverse sources of knowledge are also often

required, but there is currently no good way to integrate these

sources in reaching a solution.

A few k no w 1 e d g e- a c q u i s i t i on systems do exist, such as

TEIRESIAS, that are interactive and se m i - a u t om a t i ca 1 ly steer the

expert to the needed piece of knowledge to introduce into the

expert system under development. However, these existing

knowledge acquisition systems have only been used to expand and

improve a knowledge base after a vocabulary and knowledge representation had already been chosen and upon which the basic

knowledge base had already been built. The knowledge-acquisition

problem remains extremely difficult and a major impediment.

V al idation

All complex computer programs tend to have errors and are

therefore difficult to certify. At the moment, empirical studies

(such as has been used to validate MYCIN as a superior

diagnostician and therapist) may be the best we can hope for.

However, the credibility of the system can be increased if the

system is made intelligible and understandable, so that the user

can be made responsible for the system and be able to modify it

to his or her own satisfaction. More fundamentally, a methodology of validation needs to be developed.

Other problems are;

Lack of Adequate and Appropr iate Hard w are

Feigenbaum (1980, p. 10) stated that "...applied AI is

machine limited." This is still true, though special LISP

44
machines and more general large, fast computing machines are

beginning to become available.

I nadegua te Special Kno w ledge Engineering Tools

Though software packages such as EMYCIN and OPS-5 are

beginning to become available, there is much room for improvement

and extension to capture more of the existing expert systems

approaches and architectures and make them readily available to

the new expert systems builders. Further, the concepts and

techniques thus far developed need to be systematically drawn

together and synthesized into higher-order patterns, so that a firm base for future systems can be built, and reinventing the

proverbial wheel can be avoided.

Orderly Developm ent and Transfer

To capture the interest of domain experts and develop a major expert system requires continuous funding over several

years, which has not always been available. Further, there is as

yet no orderly system in the research funding agencies for

effectively taking a successful research project and moving it

on to appropriate applications.

Shortage of Kno w ledge Engineers

The field is relatively new and few knowledge engineers are

currently being trained by the universities. Because of the huge

number of potential applications, shortages of knowledge

engineers currently exist and probably will continue to exist

for some time.

45
XVI Research Required

Buchanan (1981, pp. 8-14) indicates that research is required to develop;

* Improved knowledge acquisition systems

’ Learning by example

* Better explanation systems and friendlier user interfaces

* More adequate knowledge engineering tools

* Better expert system architectures and inference

procedures

* More efficient and workable techniques for working with

multiple experts and knowledge sources

More adequate methods for dealing with time

* The ability to make appropriate assumptions and

expectations about the world

* The ability to exploit causal physical and biological

models and couple them with other knowledge

* General methods for planning

Analogical reasoning

* Methods for coupling formal deduction into expert systems

* Parallel processing approaches

* Better knowledge representation methods

46
XVII Future Trends

Figure 2 lists some of the expert system applications

currently under development. It will be observed that there

appear to be few domain or functional limitations in the

ultimate use of expert systems.

Figure 3 (based largely on Hayes-Roth IJCAI-81 Expert System

tutorial and on Feigenbaum, 1982) indicates some of the future

opportunities for expert systems. Again no obvious limitation is

apparent

.

It thus appears that expert systems will eventually find use

in most endeavors which require symbolic reasoning with detailed

professional knowledge - indeed most of the world's work. In the

process, there will be exposure and refinement of the previously

private knowledge in the various fields of application.

Feigenbaum (1980, p. 10) states that, "The gain to human

knowledge by making explicit the heuristic rules of a discipline

will perhaps be the most important contribution of the knowledgebased systems approach."

On a more near-term scale, in the next few years we can

expect to see expert systems with thousands of rules. In

addition to the increasing number of rule-based systems we can

also expect to see an increasing number of non-rule based systems

as not all problems are homogeneous enough to be readily cast in

the production system framework. We can also expect much

improved explanation systems that can explain why an expert

system did what it did and what things are of importance.

By the late 80's, we can expect to see intelligent, friendly

and robust human interfaces. Much better system building tools

47
Figure 2

Expert System Applications Now Under Development

Medical diagnosis and prescription

Medical knowledge automation

Chemical data interpretation

Chemical and biological synthesis

Mineral and oil exploration

Planning/scheduling

Signal Interpretation

Military threat assessment

Tactical targeting

Space defence

Air traffic control

Circuit diagnosis

VLSI design

Equipment fault diagnosis

Computer configuration selection

Speech understanding

48
Figure 3

Future Opportunities for Expert Systems

Building and Construction

Design, planning, scheduling, control

Equipment

Design, monitoring, control, diagnosis, maintenance

repair, instruction.

Command and Control

Intelligence analysis, planning, targeting, communication

Weapon Systems

Target identification, adaptive control, electronic

warfare

Professions

(Medicine, law, accounting, management, real estate,

financial, engineering)

Consulting, instruction, analysis

Education

Instruction, testing, diagnosis, concept formation

and new knowledge development from experience.

Imagery

Photo interpretation, mapping, geographic problem-solving.

Software

Instruction, specification, design, production, verification,

maintenance

49
Figure 3 (continued)

Home Entertainment and Advice-giving

Intelligent games, investment and finances,

purchasing, shopping. Intelligent information

retrieval

Intelligent Agents

To assist in the use of computer-based systems

Office Automation

Intelligent pystems

Process Control

Factory and plant automation

Exploration

Space, prospecting, etc.

50
should also be available. By 1990, we can anticipate knowledge

acquisition systems which, after being given a basic domain

context, can rapidly guide a human expert in forming the needed

expert system knowledge base. Somewhere around the year 2000,

we can also expect to see the beginnings of systems which semiautonomously develop knowledge bases from text. The result of

these developments may very well herald a maturing information

society where expert systems put experts at everyone's disposal.

In the process, production and information costs should greatly

diminish, opening up major new opportunities for societal betterment .

51
References

1. Michie, Donald, "Knowledge-based Systems," University of IL

at Ur bana-Champaign , Report 80-1001, Jan. 1980.

2. Feigenbaum, E. A., "Knowledge Engineering: The Applied Side

of Artificial Intelligence," Computer Science Dept., Memo

HPP-80-21, Stanford University, July, 1980.

3. Feigenbaum, E. A., "Knowledge Engineering for the 1980's,"

Computer Science Dept., Stanford University, 1982.

4. Nii, H. P., and Aiello, N., "AGE (Attempt to Generalize): A

Knowledge-Based Program for Building K n o w 1 e d g e - B a s e

d

Programs," Proceedings of the Sixth International Conf

.

on

A£t^^^c^a]^ (IJCAI-79), Tokyo, Aug., 20-23,

19 7 9 , pp. 64 5- 6 5 5.

5. Buchanan, B. G., "Research on Expert Systems," Stanford

University Computer Science Department, Report No. STAN-CS81-837, 1981.

6. Hayes-Roth, F., "AI The New Wave - A Technical Tutorial for

R&D Management," (A I AA- 8 1- 0 8 2 7 ) , Santa Monica, CA: Rand

Cor p . , 1981.

7. Duda, R. 0. "Knowledge-Based Expert Systems Come of Age,"

By t

e

, Vol. 6, No. 9, Sept. 81, pp . 238-281.

8. Heuristic Pr ogr a mm i ng Project 1980 , Computer Science Dept.,

Standford University, 1980.

9. Stefik, M., et al., "The Organization of Expert Systems: A

Prescriptive Tutorial", XEROX, Palo Alto Research Centers,

VLSI-82-1, January 1982.

10. Quinlin, J. R., "Discovering Rules by Induction from Large

Collections of Examples," in Expert S^p_tem£ ^n the

M icro- Electronic Age

,

D. Michie (Ed.), Edinburgh: Edinburgh

University Press, 1979, pp. 168-201.

11. Davis, R, and Lenat, D. B. K no w ]^e dpe- B a^e d _in

Artificial Intelligence

,

New York: McGraw-Hill, 1982.

12. Lindsay, R. K., et al., App^^ca^^on^ o^ Ap_t^^^c^ai^

I^njt e ]^l^_ippn c e ^pp Op3.an_ic Chempppp^ Zll®

New York: McGraw-Hill, 1980.

13. McCarthy, J., and Hayes, P. J., "Some Philosophical Problems

from the Standpoint of Artificial Intelligence," in M achine

Intelligence 4^, Meltzer, B., and Michie, D. (Eds.)., Halsted

Press, 1969, pp. 463-502.

14. Vere, S., Pl£££i££. ££ 5liill^£££ £11^ ££££.£i£Il£ Z££

Activities and Goals, Pasadena, CA : JPL, Nov. 1981.

52
— p r '•^r* Seeds of Artificial Intelligence;

No. , 80 - 2071 ,. Bethesda, MD; NIH Div. of st^sl^fci^our ces |

sfir^ ,:1 '^: ’.

..

’'vJiilli‘'''L i'

CSi

'• t r NIH Publ.

'tv: ^5 If

-f M - 't .W sfc::? alts.

fi- V ^ ,^'V' t?. o*_ Cf w B «*

T- ,4.? . »' L-.^. 3 i^tle iJl‘->A, »: H O i!» ... I» o . sji -tT'-i » »jw Mi '

Sait ^ ri#&

ilai.

‘ - - t V )»> . Ns

--.-- --K/v

' # ® ' T

u UiSi . M

' 4

g? t» £ ^ ,

. ». U , v89 .TO

i

58 p ,#

iv #>^>. 0’’P. & g

•4 -•« P S?. .,.,.'6 < atl»S'.S5 5 .s^ . 3’.

' »'S

, #' to . U.,P‘^-M:.,S tffJS' ^ ' Si ft' «»Tf .*'*^ |{r 8

ar

el 3 » u fi

Vrf COi u U ' j-jA. to 'i't;|.f ft r ‘n 'T!’'B 5 ®'"Q .«'.; ,,

. j}..*—V '& w 'A. u ,V’ i» .,

'fe‘» !i a ..^: "mis S:S .1

f*» M' ' C

1,3 '.'iiT'.'"'.®.,. ‘ft* -

’ » p

e.s:s,,:.'o 8 :S

,!

' It".' 9- ® ' 2" f* •Oi !j« , , n « ^. :‘*ft Q W P- ‘••cf’ CT''0 ’<t .{iH —te. ft*®

.. up ,.:<0 ft, q M» Min'i* '#, ' th 6. •- Ic Vr 'O’. to' to

to to-

'• *A'..o, '‘.q,. K- w. . 5 TM 6 “.. 'ft ft' to

tf' t? £?r *sr-'^ t? Ih:' ? s Iv ? ?' S’' 3: r sa t

MA , Mi, .Ui UK to

t' '*^

'. '*•* 'Rm.i '^'or,!TM-. ’’1. —

1

«•' ' ^ .7T .»

"* , L/ln4f:^ ft ft* o u J to ft^-'

'.' ” >4 to ft to o ft*.^

I .... ,„. .to &.V.S ft, to iav -< 8* ,'"...'" ''Jii^..

_ .

<1M ^ ftl *tf ,*< to M (V I
Characteristics

of

Example

Expert

Systems

H

M

s

C/I

c; w

C 1 'H

cn

r—

H

tt n)

l-l C

u\ c

i-J H

f-H

CO

2:o

M

H

H

I—

i

H

2:

I—

I

CO

zc

54
INSTITUIION:

Stanford

University

Characteristics

of

Example

Expert

Systems

AUT1K1RS:

Clancy

FUNCTION:

Computer-Aided

Instruction

(CAI)

55
I W

pq<H

mE0) 4-1 mw

4-J

!-i 0) a-XwaEp3 Xwa

<Mu

cfl JZoo 3

cru

<C0) t>0 T30) soc H • • 2 • CO O

2^H 1—1

UJM o H

H pr CJ CO a: 2 >*• a: 2

u:) h-1<; 2

56
00I w

PQ

<:H

hJQ2WOI <HW

03e

0)

4-» 03 CO

4J

Vj

(UaXw

Due

COXw

03U

'H

4J

03 •H

VuO

4-1 a

cd

CO s:o

CO

CO

4-1 *H

03

0)>c2

T3

>-i O

M-lc

cO 4J CO2O

C-l CO2 e3

cOCa

0)

•I-0)

t:cD

CCD

cc 3: c3

CO

CO

DO

QJOC

(U *H

}-l CUDuXwBo

)-( 4-400C

*HD

i-4 cO

CU uJH

C-J 2 g2HO§H

CO§H2Oo

Pl4 o

COH2W

iJW

>-'

4-4 X 3 3 3 4J 3 w

c/3 <

PQ

4-4 3 3 1 33 3 0 3 •4 U 3 3-4 t3 3 3 3 3

<1C—1

X) 4J •44 3 0 3 0 3 C3 -4 c(-'1 •H 3 C3u 4-4 »—I 3 3-4 3 3 4—4 a •D 4-4 B 2 4-4

4-4 <C

P44

COu 3 W 3 -D 3 3 33 3-4 •4 3

03 3 4J 3 B

4J 0 3 00

4-4

~1 3-4 3 0 3 3 3 4—4 0 3 Du 3 Du -H 3-4 03 3 -X W Du CM 2 M 1 1

CU

4-1 cOM

03

(3 • CU 4J 00 03

03

r.

y c

CO t3 >H (3 Pu cO 3 W) 3

3-4 c 4J 3 1 M •H 3 3 • •4 3 N X3 4—1 3 nd

W

c/3 <3

PQ 3 •H •4 3 3 3

DuU 33 3-4 3 3-4 3 3 3 3 0 0 g 3 3 X3

00

g 3 0 •4 00 00

W0 3 •4 > 3 3

•4 CO 00 4-4 3 •4 •4

.. 4-4 3 3 N

N 4—4 WT

3-4 3 XI . •4 4J 3 •4 •4 0 3-4 c 3 4-4 3 2 1-H 4—1 e CM Du CO M 3 3 4-4 3 3 0 3-4 t4 3-1 B 3-4 •4 3 3 cO 3 3 00 B 3 0 3 M 4J 3 3 3 0 3 3 Pm 4—1 3 CO 3 3 3-4 3-4 3 Du 3 4 3-4 00 CM CM 00 W

C4C| 1 1 1

03

4-4 r-H O 3o

4-4 3

(U 1—I

03

OB

cO

03C 03

3-4 H

CODuB

4-4 3

3-4 03 4-4 03 O (—I (U 3 Du 5-4 03I 03 03

4-4 5-4 cO 3

T3 4-4

'O 3 C 3-4 CO 4-4 O 03

cO cO

C 03

DO uD

03 3 -H 4-4 4-434-4

cO 0) cO 4-1 D 00 4-4 O

03

D

D 4-4 03 •> CU O

00

4J

O 03 H 03

03

03

CO 4—I

3-4 3

4-4 3-4

D

03

C > 3

•H

O

00 3

4-4o

03

5-4 •H3

DuB33

4-4 CJ3

Du

03 57

date

rules

to

better

fit

the

evidence.
o

4-1 Xiau

X

n3 (U • 0) i-i • c CO 0) to

0) • M

C

>. <u a; (50 o > u •H •H

•H cO 4-1 XI 4-1 4J 4-J CO

CD CO 4J

4-1 3 (U CJ C cO 4-1 (U

OJ rC o CO a. > CO 4J w w 0) CO 0) owHZWSw

ijw§

/«*S 1 • (U 3 )-l • CO u O 1 o 1 O 3

(U c cO •H 3 M-l »-l

u 3 B (U iJ U 3 3 3 • 4J

to 3 CO 3 •rH 00 CO

a 3 "O iJ J3 3 u

»r-l CO

u iJ 3 •H 3 •rH CO X3 o- c •H 3 B •H 4-) )4 O QJ CO •H 3 O rH

•H !-i CO rH 3 3 u CO o >4 3 3 4J • •H •H 3

<u 3 O o 3 3 3 3 •rH cx CO a •H rH 3 4-» 3 O 00 u 4J J-I X e cO C4 6 o

M-t c !*: 3 3 3 u rH o QJ 3 0) 4-1 4J 3 3 4J 00 o e 3 4J CJ a 3 3 3 •tH (0 (U nl 3 3 3 3 4J 3 •H 3 U O 3. 3 3 3 3 >>

OJ 3 3 (J

X 3 3 3 3 3 -3

CO CO P4

w cO

B >4 Pil '3 P-i 33

I—1 W • 3

CD 3 3 < 3

pn 1—1 3 • 3 O 3 w 3 •H 3 3 o 4-1 3 r-4 o 3 3 r-l 3 w O N 3 14 1

•H •HI—1 3 o •H 3 3 a 3 •H 3 3 3 4-J 4-1 >4 3 •H 3 3 3 3 4-J X H M CO) H —or3 3 3 •H 4H U B 1 1 • 3 • 3 3 3 o 4-J 3

4-J 3 3 •H

a 3 M-l 3) 3 4-J 6 • w CO O 3 3 3 3 4-1 4J u TJ 3 4J 3 •H 4J • 3 3 rH CO a X 3 3 3 O X 4-J 4J 3 CO > S

•H 4-J CO

M 3 3 •rH 3

4-> 4J > 3 3 & 3 3

CO CO

a 4-J •H •H 3 3 a 3 3 CO 3 O 3 3 X.

/-*s rH 3 X 3 3 4-J o

r-i 3 3 3 4-J

X CO 3 3 CO

CO

O 3 3 3 3 B 4J 3

•H •H 3 3 O 3 •H 3

4J 4-J 3 3 O 4-J 3 rH 4-J 3 3

•H CO

O 4-4

O 3 a

O 3 3 •H X) CO 4-1 3 X 3 4-1 •H 4-J 4-J 3 CO 3 u 3

•H CO 3 4-J rH 3 3 CO 3 CO 3 CO N •H 3 3 O 3 3

CO •H CO E 3 4-J •H CO TO 3 rH 3 •H CO 4-J X 3 3

-C

O cO

O rH 3 4J •H 3 a 3

4-J •H •H 3 CO 3 00

•H 4J 4-J 4-J 4J 4-J 3 3 o CN s X •H CO 3 CO rH CO 3 •rH 3 3 4-» 3 4-J cO 3 TO 4J

4-J 4-J •H

a

B 3 CJ 4-J 3 o CO 3 3 3 3 •H •H 3

cO

O 3 a 3 3 00 3 CO 3 a

u 3 CO

X 3 3 o 3 CO 3 3

c/o 3 W Dd rH CcJ -3

a o5 • • . ¥ rH CN ro <0* LO 3 1 X C>0 CM 3

i-i •H o 3 3

CO 00 • 3 3 a 00 3 M-4 00 3 rH o o o *H O 3 3 CO 3 3 1—1 3 4J 'H CX a 3 CM o O B CO X 3 •H 3 'H 3 0) (V 3 3 C *3 3 •H 4-J •H 3 3 •H CM 3 3 CO 4-J 3 3 rH 'H 3 X O CO 3 M o 3 X a B CO CL X) 58
mE

OJ

4-1 W

(/) oI—II w

kJ<H

4-1

)-4 QJO-Xw

(U rH

c-EXw>4-1 omo

•H

4-1 W

V4

QJ 4-> CJa

j-i

cfl x:u <o

UJH

CO

>-CO

IC3 naMo

C-lc

to

4.1 ooH

CO

x: 4 < O

CO co

CO

4-1 CO Q,

2f) O

CJz

CJu

59
ww<H

WG

<um

><

CO

•u

0)D-Xw0) f—i

C-6

caXw

l4-j owo

•H

i-l M

•H0) •uo

CO

cO u

CO

Pm

h-l PSH

CO

cq<

p4

bo

>MCO

PS

PSoM

C-M H

CO

PS

4-1 o

TO

)M

cuo

cO CO

CO

PSoH

PO

MC

*HCc

cO 1—!

PmOMH

CJ

PSPD

pH 60
INSTITUTION:

SRI

w

hJ

PQ<H

05e

05 4J

CO>,

C/5

cua,Xw

exE

toXw

05 •H

(UO

to

CO s:u o

T3

l-i 0)CJ

to

C/5

C/5

c/: oXHX<

01c

'Hc

::

CO t—'

P25OMH

CJ

25X

61
w

PQCH

we

(U jj

CO

C/D

4-J (1) aXwae

COXw

C3

T3M *v< s O c w 4-4 *r4 bO o C 4-4 *r4 hJ CO QJ CO o 4-1 4-J OJ s 40 CO Q zoM • • H • • z • • C3 40 O s H Dd 1-4 w M O H H &H z O

C/D CO

H

>4 Z Z

C/D

M < z o bO • •H . 3 O 1 3 9 4J • •H u 3 O

CO • bO z 3 z bO u 3 CJ 3 •iH 4J H O c •H 03 3 1 4-1 3 O CL 0) CO 3 r—1 3 3 3 z o B 3 4J 3 O >-i T3 z (-4 4-1 o z >-i U 3 H CL 4J * 3 o 1 'Z Cl CO •H bO 3 3 z 3

4-J s Z •u 4J 3 ' 3 Z c P CJ 3 •H • •H 3 • o •H o •H z B s 3 z 3

oi cO o 4-1 3 u 3 3 H C4 3 3 4-1 3 3 J-i Cl Z 4-> 4J •H > o O Z 3 % 3 o W CO 3 3 3 3 3 4J Z u Ci cO 3 r—1 3 3 Cl 3 3 4-4 0 (U 3 3 3 3 4J 3 •H o z Z z Z P4 3 z B Q

01

w CO QJ CO CO c CO 4-1 < o CO CJ PQ *H 0) QJ 4J 3 4-4 < 3 bO 4-4 • H QJ 3 < O U-t U o Cfl O »-l 3

•H •H z 1—I

0) 03 < CO >-4 z C4 z •H O 4-J 4-1 o 4-J 4J CO z u cn 'T3 3 o cO •H 3 O Z z 3 CLJ 1 3 bO

S-4 z 3 3 3 1 3

t—1

0) 4J 1—1 • •H 3 3 O

0) z •H 3 bO )-i 3 O •H

w > o 3 3 s 3 iJ

QJ •H > 4-> 3

1—1 bO 3 bO 3 O 3 3 U

PQ 1 C

O 3 3 o Z Z bO

CO •H CO •H 3 3 > o w U > cO • > 3 •H 3 z

0) 1—1 0) CO rH bO z 3 3 o B o Cl 4J o O B V4

CO 3 3 !-i ;-i •iH 3 z 4-1 1 o •H 1 O o 4J iH

g •H

B 4-1 3 B 4-J 4-1 3 z z s O QJ )L 3 3 o 3

•H 1—1CO

u I—1 3 3 J-i •iH K> >-4 Z !-i w Z 3 3 3 z 3 Z o O 3 O tH rH 4J z Cl X !-4 u O u 3 3 3 3 4J w Z cO o z Z Z •H 3 3 os

(U x:

4-1 Occa

T>

(U

1—1 > 1 3 bO 3 QJ z >. z X 3 3 3 • > 1 3 Cl Cl 3 3 Z •H 3 z 3 Z 3 3 3 Z o I—1 3 Z 3 O > • 3 Z 3 3 z Z 3 Z 3 4-J 3 CO 3 'H Z 3 3 3 3 3 3 B 3 3 3 Z Z Z Z 3 3 CO 0) 3 •H Z 3 3 B & 3 Z 3 rH O rH 3 z Z Z o 3 3 3 CO Z 3 3 3 3 3 3 O

:3 & o o o 3 0 B Z 3 z bO 3 z 3 O u o 3 3

nd 3 O z 3 3 u o 3 3 3 C Z • 3 •H z cO o z 3

(0 3 3 Z 3 bO

B 4-4

a 3 3 3

iZ 3 Z 3 3 3 u

O Cl bO 3 3 •Z z rc 3 3 3 bO •H 0 0 3 *Z 3 3 CJ O •H Z O 3 > 4-1 3 •z 3 E

•H < *H 3 3 Z 3 rZ c bO 3 z 3 Z o Z Z 'H o 3 o •H 3 4J 3 3 3 I—1 z pi 3 z 3 z 5 3 3 C 3 Z 3 z pul 3 3 Z z z 1 4-J Z 0) 3 z • o z Pu Z 3 z 3 E C 3 e bO o o 3 z z < 3 O 3 z Z 3 QJ Z 4J 3 3 z Z 3 3 3 Z •H 3 4-J 3 3 3 3 3 O *H 3 z a Z •H •z *z O 3 3 o Z 3 3 3 3 o •iH 3 P z TO 3 tZ

•H 3 z o z 4-J •z

g 3 3 3 z 3 z 3 z 'H z 4-1 O • •z Z O bO 3 Z 3 3 Z 3 Z 0 3 u z 3 Z > 3 3 E 3 • 3 3 z CO Z 3 3 Z z iZ > 3 3 I—1 z O 3 3 z 4J O 3 z 3 3 o 3 1—1 3 3 3 Z 3 rH CO z z O 3 3 3 Z Z B > 3 Z •H E CO 3 3 3 Z 3 3 z O z z 3 Z 3 o QJ 3 3 3 3 z Z

bO 3 z o o 3 3 3 c z 1—1 3 3 Z 3 3 3 1—1 z z z 3 z 'Z CO z Z z & Z Dd 3 c^ , o e

CD

M v-t *H bO fj !-i H m QJ (U

OD ^ C CL

(U o X

=1

g t>0 01 62
w

hJ<H «B

<u

4-J cn

c/3 4-1

5-l <uClXw

CLeC3Xw

14-1 o

COo

CO •H

(U

4-1 CJ

cO

}-i

cc! x:

C-3

>-< C4iwH

cn

HM22CH

cn2

a)0) I—I

<u ol3

cnddB

to

CO3

c/3

cno d

00 'H

(00) QoMHaX

63
ptl o

w

H

zg

M

hJU

s 1 S3 o. a. « H O 3 4J’ o 4J a

B . 0) «M O B j= O Jj u u 4-> . CO u H u •o c o • 4J • •H •H » .

, •) O JQ &0 CO bO g 3

Q •H c iH C 5 1 fv* *J t3 •H C 1-t O V

C_4 m c (A 3 .H o 1—1 • C C3 CA *J 3 ^ 4S

1-1 0) )-i *3 4J CO O

P CJ O <U (A •H . H

E 3 O CL JZ <0 U CO o o Ut O..U 0) cd 01 U T3 CL O CO > CO -0^-

1—1 iH M-l 1 Q. C •d

(U iH d) O •o 3 0) c

> CO > c •

1 0) cO • U3CO

a; •H 0) (A d) CA e 3 (0 tH 4^ f-M rH • CL c O U CO 0) c 0) u o U 01 W CO

0) c > CO 1-1 « Xi iH 0) Mm na o> d) U-) O *4J o CO JC C •H 0) CO X CO CL 4J H

o >

0) >^ • CAD V

CO 1-1 0

0) a W -o (1) AJ (A J= i- > o CO

0)

tA V4 U-l ^ 1-1 o> 4J c CO X CO o f-1 CA H* fo p V u

<D O iJ •H 0> • CA 3 J-* pC 4J -O P -Q x: U CO CO o CO a G

O

u o 1-1 u •H •ra ^ •o -w r S

O U 0 D- 'd o 3 c 1 CO *o B o

CL CO O CL Q> CL CA d) tQ o. c M 5)

d) 0 U >v CD 00 C o o O 0) a: ^ 0^ CA U X Oi < 1-1 H O ^ CO

J-i E CO l-l CA

0) CA o •d 3 CO Li 4J 0) 4J d > P *H d CO M-t 1 CA 0 CO G X d 00 1 1

1 3 3 3

• CA B 0) >1 3 3 3 iH u iH c >1 d CO >1 3 3 0,

0) •

»

JJ CO J= CA X CA CO U •H X CA d

pC 3 3

bO 60 c M 4J 0) d u-l 3 Li D 1 CO LI d d

•d c d CO O CO CA 3 o u 3 o d *d na d

U-l 3X3 •H B a CA CL 4J d u 4J X > U-l Li o Li pC to 0 X 4J 3 U Ec 4J p ,d

- p o CO o. 3 Li o 0 c O Li 3 CO 0) iH c f (U 4J • d CL c rH CD c 4J 3 s 0

•H >1 >1 Q< X

u

o (D CA CO d E O CA d >^ O 60 G o G Dp

4-1 4J U >% O. c U d E d &0 CL (U d“ CD X •H P d o 1-1 o SH * u-l CO iH •* C X 1 M CJ *d WD d tH d 3 3 4J 1-i u •H u • o O CD o pC M iH CO 3 "3

t— d iH Li pd CA j: XI CA CO d U > c U cO E d

•H d LI LI Ll

<u u i-H CA d CO CO d CA lH O 3 CO g d p U CO Li d

Li -Q CO 3 C O t oo o d (A E •3 r-l •3 X. CO ”3 .H 4J iJ o 4J o d d • 0) o O iH d •H d 5 s CO U-) X5 Li CO •H O L iH Li U Li 3 r-l p d U-l CA U-l pO pC X c

U-l *d pC

52 d CO o d • >1 Li O >1 g o X M o d u p E LI e d 3 4J P 60 *3

60c •m tH M-l E CA Mh 3 to 3 D. a CL u-l CO a*H CO

CO 3 O

p a

3

p

d

d* CA

Li O O CL Odd

O CA CO

CO C/J CO

kJ u: iH CM CO so US 1 1

1

I c CA 'V d

CO CA c iH (X >>

Li d d d d G

>> pC d V 4J > d to CO rH

tH

fH

4J 4J 4-1 O X d p^ c a O d U d rH •H CO

CO CO 4-1 E Cl o CO U Li (0 CO o pC 4-4 CA d

•H L» Li c 4J CA o 1-1 o X CA CA CO 3 d CO a Li o u -Q d CL O pC LI d to d LI

Li CO O *Ta U CO a na o

CO

CA c 4-1 1 cO TD 4J •H c C CO

Li d c CL o iH CO c CO o *0 d d 4-1 d O Li Xt o •H d V4 iH 0 c E 4.J CL c CA CA •o 4J to G pC d d d CL CO d CO d CO •T3 o na c CA Li 'V CO o U d CA 4J d pD o CL d d a CO U CA d fH < d to pC CA CO C iH 1-1 d U C.I o o LI CO o CO -o U-l C.I CL 0 Cd cc E Li iH d CL iH 1-1 c 0 o u c fH

Cu d d S E d 4J Li CO u-l d X «D

fH 4J CO Li u CA 4-1 • < pD d /—

s

iH • E X CO d O c d fH O pC CA CO E o CO a tH c o •H 4J d rH

Li S—p' d C 0 4-1 fH CO 1-1 LI CO > d CL O to 4J 4J d d Li iH 4-1 u d > CA CO •H 4J o U c d to U CO rH d CA d tH CL CA o pD •H > iH c d a fH d JC d CA CO pO d d •H Li d pC CA 4J > T? pC E CA iH d U CA o d

d pC d d LI C o »H pO O cO -C

«H u CO pC o •H o >% CO U CO d CO 4J

CO L 4J pO Li Li E o

d CO CL to Li CO o d d Li d a.

Li O d o Lt o c c CO a Li pC CA O CA >*

4J CA LI CO a 1-1 CO CJ s—

'

U-l LI U^ -C

1 1 S>1

- u E 3 Ex

1

3 0 X O i-( c X CJ 4J 1 tH 1 Cl o P U-l "H *H •

(0 X u-l 60 O X h 3 rH CO t-i o P O 60.*H D. P pD d o *H p -3 O CD a. 60 P *H 3 "3 -H d d o. to P O X >4 3 X pC X 3 rH c 3 iH O P 3 LI 4J 3 d iH X 60 3 60 >

O > rH U P 3 *3 "H *H

Cd a fH d d iH 3 3 3 X iH >v Cd rH *0 l-l -3 ^4 p W 3

> d d OP 60 3 3 4J 4J >> X U-l 3 >mH I d Cd •o c X CJ P. 4J 3 M CA

4-1 > c d iH CA 3 3 P 3 3 Cd •H d •d iH 3 T3 *H 3 fH o 4J 4J iH iH O U 3 3 60 iH O X > X iH Vj X X CA -3 P C <d d d • iH U 3 O M 3 1-1 d r CA *d CA O M 3 X -3 E G d rH d H 3 3 U U-l U p B d C M X d Li c 3 3 P O 3 3

O -C Cd Cd 4J > CJ d i-i 3 3 O.

CJ o d LI P "3 d X -d rH C Li .H U-l U-l O P Uu •

CA CA 4-1 p^ii Li to O 3 0 0 1-13 0 — Cd u 0 c •H CL P 4J CO CO d d O d CA a 0 X 3 3 3 3

Li iH d d CA ^0 iH 4J C 3 60 3

'd a X CO H -3 O H P iH d u d 3 3 1-1 3 1-1 X

> Cd > • • • d 4J 3 4-1 4J 4J iH

cd o cd fH CM cn CA 3 M 1-1 P 3 ti X pD X X CU X -3 1-1 l-i O

Iu

Q) nac

a e>o c ^ tH a -o

0) c

0) (0 a 4J CO CA

64
INSTITUTION:

w<£h

cne

(U 4Jm

>.

OJ(XXu

CUe

COX

fd

>-4 0) 4-1 o

cO

CO rCo

Pn

oi

u

(U

Vj

>-l (U5o

kJ

oo

Cio

:=> < co

•U

cO

4-1 QJau

(U

cOcwzoMHozzz

65
SYSTEM:

CRYSALIS

TABLE

1-17

INSTITUTION:

Stan

.

fgrd

.U

niv^

sL

t

jr

Characteristics

of

Example

Expert

Systems

AUTHORS

:

Englemore

&

Terry

FUNCTION:

Data

Interpretation

66
NBS-1 14A IRE V. 2-BC) U.S. DEPT. OF COMM. 3. Publication

May 1982

BIBLIOGRAPHIC DATA

SHEET (See instructions)

1. PUBLICATION OR

REPORT NO.

NBSIR 82-2505

2. Performlnt Orcan. Report No

4. TITLE AND SUBTITLE

AN OVERVIEW OF EXPERT SYSTESM

5. AUTHOR(S)

William B. Gevarter

6. PERFORMING ORGANIZATION (If joint or other than MBS. see instructions)

NATIONAL BUREAU OF STANDARDS

DEPARTMENT OF COMMERCE

WASHINGTON, D.C. 20234

7. Contract/Grarft No.

S. Type of Report & Period Covered

9.

SPONSORING ORGANIZATION NAME AND COMPLETE ADDRESS (Street, City. State, ZIP)

10.

SUPPLEMENTARY NOTES

(321 Document describes a computer program; SF-185, FIPS Software Summary, is attached.

11.

ABSTRACT (A 200~word or less factual summary ofmost significant information. If document includes a significant

bibliography or literature survey, mention it here)

This report provides an overview of Expert Systems - currently the hottest

topic in the field of Artificial Intelligence. Topics covered include what it

is, techniques used, existing systems, applications, who is doing it, who is

funding it, the state-of-the-art, research requirements, and future trends and

opportunities

.

12. KEY WORDS (Six to twelve entries; alphabetical order; capitalize only proper names; and separate key words by semicolon s) Applications; Artificial Intelligence; Expert systems; Forecast; Intelligent

computer programs; Knowledge engineering; Machine Intelligence; Overview; Research;

State-of-the-Art ; Funding sources.

13. AVAILABILITY 14. NO. OF

PRINTED PAGES

[Xj Unlimited

73

1 1 For Official Distribution. Do Not Release to NTIS

1

1 Order From Superintendent of Documents, U.S. Government Printing Office, Washington, D.C.

15. Price 20402.

(231 Order From National Technical Information Service (NTIS), Springfield, VA. 22161 $9.00

USCOMM-DC 6043-P80
80

vf,J(5 :4-'M

. ..^

<o>^ 1 ...

(! 0< z ZE r.

y='^y \rfr "’my^ 'lO

1

. 3

. TAOS «^305i35a i

3:TTtTtf|^0 l4A.£fJTi

• Jrt,“ V. *^r ’.y><IW|ji'inl«^ mj I . «iV>.« ^ ' a

' M,

ny»i»i*««i^

t

*0 U' ’'^^','2:^5 ''-.i.,si V

I

.« 'J

l>fr' >; -'j^ .i!' '';y 'f-'^ '.

i> ...Ji’i

’

•'-*1

. ; . ^ . ;* “ • -

‘ ^

' '*

'

!C? ft

"*>i i I.

< ^

> I"!

v„

•C . t

'* V’' • * fi •*

' a « A u fn -i ! i. T u u ^ 3 :t u« 4A«$i's 4ti» iU 5 = 5»|tOa 1.(1 •( a . Mr«A*?'-Q ^ iivt .n.o ,iiwr£fKfi42 ^^6t

: ' -:i rri^)/i . ,.

v> -<

V. .'• o- y

»*• -I

.J. .;aTQ« lei f

'yj H-"

, r\f.

:> ii i :> :^ ~« -j ; -ii;'- w*/"

. ^j'lW :^ (•.Ij.i- '; ("'ji '•^'l-

''

' V’*- • V *4nsi c?ij'#97 ;‘ 'fj '?';•.

|v. . •‘f r,^ >C/Ci { J

. ’i .

• \»« ' w'!^jr. 4

'‘ •' .Ul:’

W.k .f"'' Jiu • . . '••'» t: i'i' 1 . (1 i; ‘^rtlv^v

,«S*

. 7^1 'k

' If.t

' ^

1*: "' H

^ ,, ,.

, i. 1

•

\4‘, ^

lA

•' ‘ ij

- - '$

*

I?

>S-

* '*'

•" m «!

:hi V"; >-:•'' - <v. u> % ^;»Clln>4'it^^T’»*TI^.CT7ft ''

;

€.\7)HCr. 'Vi. “ibi

1 . c .tj -suer |7oA-*':7 - !^^ ' ^7"' ’"

, '

,

” ^""P'r Jia/CnA A txt y- • ' "' • •

'

»n

•vaO >^«U

j .Xf «i(l '. .5.1*0 tni;’' 1

'*4 U? <tO;*l _j

.rc- 'fi

. i- ,(;.i .’ dJ>DlV'i‘5«. H;.* I Ir.'iu.fRW . ; Yi

I 6.fv.

II >ii» ii ii>i^

it'" « M

iilr.

1