AGE (Attempt to Generalize): A Knowledge-Based Program for Building Knowledge-Based Programs

1. INTRODUCTION

This paper reports the goals and the current status of the ACE project.· Appendix I contains a protocol of a user solving a specific problem using ACE. The Intent of the protocol Is to show ACE from the user's point of view. The main body describes the motivations for and the description of the facilities in ACE.

1.1 @bjec:tives

The general goal of the ACE project Is to demystify and make explicit the art of knowledge engineering. It Is an attempt to formulate the knowledge that we knowledge engineers use In constructing knowledge-based programs and put it at the disposal of others In the form of a software laboratory.

The design and lmplementatton of the ACE program is based primarily on the experience gained in building knowledge­ based programs at the Stanford Heuristic Programming Project In the last decade. The programs that have been, or are being, built are: DENDRAL, meta-DENDRAL, MYCIN, HASP, AM, MOLCEN, CRYSALIS [9), and SACON (2l Initially, the ACE program will embody artificial intelligence (AI) methods used in these programs. However, the long-range aspiration Is to integrate methods and techniques developed at other AI laboratories. The final product Is to be a collection of bulldtng­ blocll programs combined with an inttlligmt front-md that will assist the user In constructing knowledge-based programs. It Is hoped that ACE will speed up the process of building knowledge-based programs and facilitate the dissemination of A I technlq ues by: (I) packaging common A I software tools so that they need not be reprogrammed for every problem; and (2) helping people who are not knowledge engineering specialists write knowledge-based programs.

The task of building such a software laboratory for knowledge engineers Is divided Into two main sub-tasks:

1. The isolation of techniques used in knowledge-based systems. It has always been difficult to determine if a particular problem solving method used In a knowledge-based program is special" to a particular domain or whether it generalizes easily to other domains. In existing knowledge-based programs, the domain specific knowledge and the manipulation of such knowledge

· This research was supported In parts by the Defense Advanced Research Projects Agency under ARPA Contract No. MDA 903-77-C-0322 and the National Institutes of Health Grant No. RR-00785.

• using A I techniques are often so closely coupled that It Is difficult to make use of the programs for other domains.
• Guiding the user in the initial application of thm techniques. Once the various techniques are Isolated and programmed for use, an Intelligent agent Is needed to guide the user In the application of these techniques.

1.2. User Profile

The design of the ACE system would depend, to a great extent, on the type of users we expect will benefit most from using ACE. Initially, ACE is designed for AI scimtists familiar with current problem solving techniques, and who can program in tht INTERLISP languagt [19) (since ACE is implemented in INTERLISP); and ar~ familiar with production-rule representations of knowledge [5]. In other words, AGE Is initially aimed at people who could conceivably write knowledge-based programs themselves.

For the person In this category, the advantages of using ACE are twofold:

1. The basic system components are already programmed (e.g., rule Interpreters and other control mechanisms, traces, explanation modules, and other components basic to many systems).
2. ACE allows the user to experiment with different problem solving techniques without extensive reprogramming.

Eventually, ACE will be able to help the less knowledgeable or less experienced person.

1.!1. Outline of the Paper

The term "knowledge engineering" is being used more frequently to refer to the process of writing application programs using primarily AI methods. The historical context In which knowledge engineering arose and the nature of the work are described by Feigenbaum [9]. Section 2 contains a brief description of the task for the ACE program within the context of knowledge engineen' work. It is followed by an overview of the facilities in the current version. Section i contains a short description of an organizational method by which frameworks are decomposed to form a basis for a software laboratory. It is followed by a summary section.

2. TASK FOR THE AGE SYSTEM

Currently there are several projects that aim to provide prepackaged tools for knowledge engineers (UNITS [18), EMYCIN [2]) or to provide programming languages (KRL [il AIMDS [17]). In preprogrammed packages, all, or most, of the paradigm, system design, and implementation choices have been made by the package designers. In languages none, or very few, decisions have been made for the user. Neither approach guides the user In the design and the construction of knowledge.:.based programs. ACE has been conceived to bridge the gap between these two extremes--to provide some guidance In the what, why, and hor11 of programming; plus some preprogrammed problem-solving frameworks.

Ideally then, ACE Is an attempt to define and cumulate knowledge-engineering tools, with rules to guide In the use of these tools. It must itself be a knowledge-based system containing knowledge about building knowledge-based programs, combined with a facility that allow the user to explore and experiment with various concepts and techniques. It must provide the user with a variety of prcprogrammed modules, allow her to modify them and to add her own. And above all, It must be able to produce running programs. How the ACE system Itself Is organized for modularity will be described In Section '!. In the next section we describe a framework currently available to the user to construct her knowledge-based program.

3. PROFILE OF THE CURRENT AGE SYSTEM

To correspond to the two general research goals described In the Introduction, the ACE program Is being developed along two separate fronts. The first of these fronts is the development of tools to help the user build a variety of knowledge-based programs--the generality front. The second front Is the development of intelltgtr.ct in the interaction between the user and the ACE program; I.e., moving from dialogues on how to ust the tools In ACE to what tools to uu-­ the how-to-what spectrum described by Feigenbaum [9].

U. Currently Implemented Tools

The building-block components currently available to the users have been carefully selected and modularly programmed to be useable In combinations. The current ACE system alms to provide the user with a framework useful for incremental hypothesis formation, known as the Blackboard Model [8, 131 It can be described as follows:

1. There is a global data base (the blackboard) that Is used as a means of communication and Interaction among the KSs;
2. There are diverse knowledge sources (KSs) that are kept separate and Independent; and

S. The KSs respond to changes in the blackboard.

The paradigm Itself does not specify the structure of the data base, the representational form of the KSs, nor the response mechanisms. When a model Is translated into a program, various architectural and implementation decisions are made by the designers, and programs that usc the same paradigm may have different organization and behavior. For example, although HEARSA Y-11 [13] and CRYSALIS [7] use the Black!:: · :d model, the basic architecture, knowledge repre~entation, and knowledge utilization techniques differ. The differences can be attributed to many factors: the nature of the problem (understanding speech signals and Interpreting x­ ray crystallographic data); implementation language; real-time constraints; noise level of data; quality and amount of available knowledge; and, last but not least, the designers' tastes.

In ACE the Blackboard-based program design has been Implemented to allow nexibillty In representation and In the application of other rroblem solving methods within the framework. It consists o three major components:

1. The Blackboard: The blackboard contains hypotheses In a hierarchical data structure; It represents the task domain In terms of a hierarchy of analysis levels of the task.
2. The KSs: The KSs contain the knowledge of the task domain (which the user must provide) that can perform the analysis. The KSs are represented as sets of production rules.
3. The Control: The control component contains mechanisms that allow the user to (a) specify the conditions for the Invocation of the KSs and (b) to select Items on the blackboard for focus of attention [10].

In the remainder of this section these rnt'l'lponents will be described In more detail.

U.l. Blackboard

The combined process of KS selection and Incremental changes to the blackboard is viewed as a general process of hypothesis formation consistent with the following definition:

An hypothesis can be generated [11):

1. deductively, using support from above--this support can be
2. theoretical support (or mode 1-based support),
3. support from more inclusive hypotheses that have independent evidential support; or
4. inductively, using evidential support from btlow.

This definition suggests that the most natural way to represent hypotheses Is in some form of a hierarchy. The structure of the hierarchy may be strict; it may be nat consisting possibly of only two levels--input data and its translation; or, it may be complex, consisting of many related hierarchies (often referred to as blackboard planes [7]). Currently ACE can represent all of the above forms of hierarchy. An hypothesis Is represented as hierarchically organized hypothesis elements integrated by links that represent support from above--called the txptetatlon­ linlt, or support from below--called the reduction-Unit (see example 1).

EXAMPLE/: Hypothesis structure in CRYSALIS [7]

Molecules, superatoms and atoms are hypothesis 1 eve ls names.

·r· and ·e· represent reduction- and expectation-links.

An hypothesis eltrntnt is a named node in rite hypothesis structure that represents an aggregation (summary, interpretation, etc.) of lower level hypothesis elements. Each element contains Information In the form of attribute-value pairs that are meaningful at that particular hypothesis level (see example 2). These Information are Inferences generated by the rules in the KSs and can, In turn, be used for further hypothesis formation.

EXAMPLE 2: A possible hypothesis element In CRYSALIS

Hypothesis level: ATOMS

Hypothesis element name: ATOMS-18

Inferred attribute-value pairs:

Atom.name Sulfur

Location

(12.3 13.6 24.2 +· .82)

Bonded to HEHE·1

Partof

(OR CYS14 CYS17)

Bondtype Hydrogen

In some problems all the hypothesis elements needed to solve the problems are known a priori. In other problems the number of hypothesis elements in the solutions are not known In advance. For example, In PUFF (a program to diagnose pulmonary function disorder [12]) all the possible disease states which account for specific patient data are known In advance. On the other hand, In cryptogram problem (see Appendix I) the number of letters, words, parts of sentence, etc. are not known . until a specific cryptogram Is being solved. To accommodate both types of solution space, ACE allows the user to generate and name hypothesis elements in advance, generate and name them dynamically, or generate them in some combination.

The hypotheses are generated by inference rules in the KSs. What the KSs look llke and how they work are described next.

5.1.2 Knowledge Representation

Knowledge representation in ACE Is based on the premise that there are at least four broad categories of knowledge that are needed to solve problems:

1. knowledge of specifics,
2. knowledge of ways and means of dealing with the specifics,
3. knowledge of universals and abstractions in the task domain [3], and
4. of. knowledge of problem solving and knowledge utilization methods In the task domain.

Within the framework of Incremental hypothesis formation using the Blackboard model, an attempt has been made to help the user Identify, represent, and utilize these diverse types of knowledge.

Domain knowledge In ACE represents the knowledge necessary to accomplish the goals of the user's program. This knowledge reflects the knotuledge of specifics and the knowledge of ways and means of dealing ruith the specifics. The knowledge Is represented as production rules [51 These rules are organized into sets called the Knowledge Sources (KSs).

Know ledge Sources

A Knoruledge Source is a mega-chunk of knowledge consisting of a labeled set of rules that are a priori deemed to belong together. Ho!IJ the rules within a KS is organized and what rules are included In a KS depend on, the intended role of the KS In the overall problem solving plan. For example, a KS may be organized to represent models--in which case all rules are grouped . around some objects or concepts, much like schemata or frames. Or, a KS may be organized around events--In which case all rules which, for example, process input data, are grouped together. In order to solve problems within the framework of the Blackboard model, KSs must place their Inferences on the Blackboard. In other words, KSs must generate hypotheses using rules that:

1. add or modify hypothesis element(s), or
2. add or modify relationships between elements by
3. analyzing data (support from below),
4. speciallzlng or instantiating a more inclusive hypothesis element (support from above), or
5. generating expectation(s) from
6. models, or
7. more Inclusive hypothesis elements that must be verified by data.

Each KS has associated with it: (a) preconditions (a list of events) for its Invocation; (b) a list of dotted pairs of hypothesis levels that It spans; (c) list of links generated by It; (d) "single" or "multiple" hit strategy to be used for the rules, and (e) a facility for v.ariable bindings to set local context, to simplify expressions In the rules, to avoid multiple evaluations of the same expression, and to allow communication between the condition and the conclusion halves of a rule.

ACE allows the use of just one KS in the user's program If desired. Whether a single KS is sufficient to solve a problem or not, depends on the characteristics of the problem and on the formulation of the KS. MYCIN [16] Is an example of a program that has an equivalent of one KS; all the rules are chained in a goal-directed fashion to represent a line of reasoning meaningful in that domain.

The set of domain-specific KSs may be manipulated In many ways by other higher level KSs [6, lofl The higher level knowledge may reflect both the knowledge about ways and means of dealing with the specifics, knowltdgt of problem­ solving methods uuful in the task domain, and knowledge about other knoruledge in the domain. These higher-level KSs are often integrated into the Control component described later.

Rules

A rule in ACE Is a chunk of knowledge written In a syntax comprehensible to ACE. Each rule consists of a left-hand-side (LHS) and a right-hand-side (RHS). The LHS specifies a set of conditions or patterns for the applicability of the rule (I.e. premises). The RHS represents the implications or conclusions to be drawn under the situation specified in the LHS.

To be consistent with the various ways In which hypothesis elements can be generated, the current implementation of the RHS can:

1. add elements to the hypothesis; or add or modify the values of the attributes of elements or the relationship between elements;
2. generate expected elements or values of (or relationship between) elements In the hypothesis;
3. generate goals to establish some elements, or values or links, within hypothesis elements.

Rule Credibility

The domain rules that generate hypotheses are, more often than not, judgmental and uncertain. A credibility valut, or weight, can be associated with the rules to renect uncertainty. AGE provides means of associating weights (certainty values, probability, etc.) with inferences generated by the RHS of rules. It also provides some pre-programmed procedures for the manipulation of these weights, for example, an algorithm to compute Certainty Factors (CF) from MYCIN. For users who need different algorithms, ACE provides mechanisms for Integrating user-provided algorithms.

EX AMPLE J: Integrating weights

Note: The rules used in this example, and some others, are based on PUFF rules [ 12). From pulmonary function test data, the PUFF program determines if a patient Is normal, has obstructive airway disease (OAD), restrictive lung disease (RLD), or other pulmonary function-related diseases; and the severity of the diseases. It further determines if OAD is of type emphysema, asthma, or bronchitis. ("R V" In the example refers to a measurement-­ residual volume.)

Weigllt-adjusttr: SADJWT (MYCIN algorithm) Rule to be e!XZluated: 1f (TYPE · OAD) 6 (RV > 228) then (PROPOSE (SEVERITY SEVERE .8)) H,potllesis element be fort rule evaluation: hypo-element name: DISEASE-85 type: (OAD .8) severity: (SEVERE .6) H,potlltsis element after rul1 evaluation: hypo-element name: DISEASE-85 type: (OAD .8) severity: (SEVERE .92) <·-···

Rule Evaluators

The applicability of a rule is determined by how the premises In the LHS are evaluated. The term "applicability" can have a different definition for different problems--It may mean that all or some of the premises In the LHS need be TRUE, or that the premises require more complex evaluation. The user can define this "applicability" In the form of a function to serve as the "LHS evaluator." Some pre-programmed LHS evaluators are available; for example, a type of threshold evaluator used In MYCIN.

EX AMPLE 4: LHS Evaluator: lAND MIN (This function Is similar to the one used in MYCIN where evidence with less than .2 value is Ignored.)

Hypothesis element name: DISEASE ·83 disease: (OAD .8) subtype: (EMPHYSEMA .1) sever 1 ty: (SEVERE . 6) Rul1 1: 1f (1sa disease OAD) and (isa subtype EMPHYSEMA) then ··· Rul1 2: 1f (1sa disease OAD) and

(grdeg severity MODERATE) then ···

Using IANDMIN, only Rule 2 is found applicable within the context of the given hypothesis state.

Example 5 shows how the features described thus far are represented within a KS. Note that some relevant features (e.g. credibility computation) reside outside the KS, because they are relevant to all the KSs In the user program.

Examp11 , .. A KS Summary (ACE version of PUFF)

--Knowledge Source: OAD·SUBTYPERULES Precondition: (OAD-DEGREE) Inference levels: (from · to) (DISEASE · DISEASE)

Links between levels: NONE Hit strategy: (MULTIPLE) Local variable bindings: NONE [other relevant information 1f LH S -evaluator: SANDMIN Wt-adjusttr: SADJWT] (GREQDEG (SVALUE OAD DEGREE) MILD) (GREQDEG (SVALUE PATIENT DIF·DEF) MILD) (GREQ (SDATA TLC·BB:OBS/PRED) 118) (GREQ (SDATA RV/TLC:OBS/PRED) 18) then PROPOSE change.type MODIFY hypo-element OAD attr-val/link (SUBTYPE EMPHYSEMA .9) (FINDINGS "OAD, diffusion defect, elevated TLC and RV together indicate Emphysema·) event.type OAD-SUBTYPE comment (Rule 31 of (MYCIN version)

U.S. Knowledge Utilization and Control Mechanisms

As mentioned earlier, the Invoking of higher level knowledge about the arpropriate use of problem solving methods and the Invoking o other domain-specific knowledge appropriate to the situation, are both accomplished in the Control component. Until recently, very few attempts had been made to express control Information explicitly. Davis [6) addressed the problem of expressing knowledge about other knowledge in production rule form and called it meta-knoruledge. Nii [ li) attempted to distinguish Inference-generating KSs and knowledge-utilization KSs by organizing the KSs themselves into a hierarchy. In AGE, we have tried to provide concepts and mechanisms whereby users can express different types of higher level knowledge. The structure of the Control component Is described below very briefly (see Appendix II for more detailed description). Whether the whole structure is sufficiently general to handle a variety of problems is still under study.

There are several system components grouped under the heading of Control. The various sub-components can be individually specified or programmed by the user. In order to simplify the designing process for the user, ACE provides pre­ programmed components where appropriate. The control components that need to be specified are:

1. Input data format,
2. initialization function,
3. processing method to be applied to each inference step,
4. <f. rules or procedure to select the next step to be processed,
5. rules to select the relevant KS to process the selected step,
6. termination condition, and
7. post-processing function.

Components I and 2 deal with getting input data and performing setup operations in the user's program. The data can be brought in from a file or typed in from a terminal. The data elements are bound to names prespecifled by the user. Within the initialization function the user may preprocess the data or perform other initialization activities--the only requirement for ACE is that the Initialization function return a name of the first KS to be invoked.

Components 3-6, called the control kernel (Figure 2), constitute the core of the Blackboard control component. The primary functions of the control kernel are to select and invoke the appropriate KSs and to select the focus of attention within the blackboard. The control in the user's program is a simple loop:

1. Rult tll4luatton: In the invoked KS each rule is evaluated according to the user specified LHS-Evaluator (sec. 3.1.2). When the LHS meets the evaluation criteria, i.e. evaluates to True, the rule is flrtd.
2. lnf~rtnce gtntratton: Fired rules either (I) PROPOSE change in the hypothesis (this change is made in the hypothesis and is also placed on the Event-list), (2) Indicate that some change in the hypothesis is EXPECTed to occur (this expectation is placed on the Expectation-list), or (3) indicate that the hypothesis needs to ACHIEVE a particular value or a state (this goal is placed on the Coal­ list). Each of these actions is called a Sttp.
3. Focus of attention: Within the Step-selection module, select a step (an event, an expectation or a goal) and a hypothesis element or data to process next. Within the KS-selection module, choose a KS relevant to the selected step, and invoke that KS. (The KS may have associated with it a prousstng method; e.g., a KS may require a bac~ward­ chalning mechanism (or the rulea to achieve a goal.) [go to /]

Components 5 and 6 deal with terminating the kernel control loop and processing the completed hypotheses. One characteristic of the Blackboard model is that there Is no prescribed way that the Incremental hypothesis formation process terminates short of running out of relevant KSs. Thus, the user needs to specify the ronditions under which the processing Is to terminate; ACE monitors for the occurrence of these conditions. In the postprocessing function, the user may perform any further processing she wishes, for example, print the current hypothesia.

Control Macro·

Since the specifications required for the control kernel are quite complex, ACE provides control macros, currently one for tvtnt­ drtvtn control and one for txptctation-drivtn control.

Evtnt-Drlvtn Macro: Event-driven hypothesis formation is characterized by incremental formation of hypothesis elements from evidence found in data or in lower level hypothesis elements. The elements can be processed by rules either on the basis of first-in-first-out, first-In-last-out, or best-first. These correspond roughly to breadth-, depth-, and best-first processing of the hypothesis space. When an element is chosen to be processed, it Is called a focused element. The event-type associated with the focused element helps determine which KS Is to be Invoked In the future.

1. <rule> modifies the hypothesis and causes an event (with
2. If <event-type> · <KS-precondition> then Invoke the KS. [Co back to I]

The control loop for the Event-driven macro Is: associated event-type).

Expectatton-Drlvtn Macro: Within an expectation-driven system, expectations In the hypotheses are generated by the rules. These rules are normally grouped around objects and their properties, similar to a schema (frame) organization. They usually form models of objects from which other properties can be Inferred or can be expected to occur. For example, a rule of the form:

1f (1sa disease oad) & (isa severity severe) then (expect RV >288) (expect RV/TLC.RATIO >28) etc.

has a schema-like flavor and produces expectations that need to be verified.

In order to determine If an expectation has been met, or can be met, the user must provide an txptctation matching function. ACE always checks to see if the expected situation has occurred either in data or in the hypothesis (i.e. performs a passive match of expectation).

The control loop for the Expectation-driven macro Is:

1. <rule> generates an expectation.
2. If an expectation is met, then modify the hypothesis as specified. This action generates an event.
3. If <event type> · <KS precondition> then Invoke the KS. [Co back to step I]

For most problems, both the expectation-driven (or model based) and the event-driven (or data-driven) methods are needed In some combination. For the sake of completeness the control components from which the macros were created are described In Appendix II.

3.2. The Intelligent Front-end in ACE

ACE assumes that the user neither knows nor understands the concepts and implementations of the various program components described above. It is the task of the front-end to guide the user in constructing a program using the component parts. Currently the tnttlligtnct in the front-end Is limited to: (a) a tutor subsystem that allows the user to browse through the textual knowledge base, and (b) a design subsystem that ~uides the user through each step of program specification. An unfamiliar· user is always Introduced to ACE by way of the tutor subsystem.

The textual knowledge base contains (a) a general description of the building-block components at the conceptual level, (b) a description of the implementation of these concepts within ACE, (c) a description of how these components are to be used within the user's program, (d) how they can be constructed by the user, and (e) various examples. The information Is organized In a network to represent the conceptual hierarchy of the components and to represent the functional relationship among them.

The design subsystem guides the user in dtslgn and constr.uction. The knowledge necessary for ACE to accomplish this task. Is represented In a data structure in the form of an AND/OR tree that, on one hand, represents all the possible structures available In the current ACE system; and, on the other hand, represents the decisions the user must make in order to design her program. Using this schema, the design subsystem can guide the user (in the guided design mode) from one design decision point to another. At each decision point, the user has access to the textual knowledge base, to advice on the decisions to be made at that point, and to acquisition functions that aid the user In specifying the appropriate component. The user also has direct access (in the unguided design mode) to various acquisition and editing functions.

The reader Is referred to Appendix I which contains extensive examples of the various interactions currently possible in ACE.

4. DECOMPOSITION OF FRAMEWORKS

A It hough the Intention of this paper does not include discussion of the architecture of ACE itself, we briefly describe some of the motivation behind the decomposition of problem­ solving frameworks into interchangeable parts.

Our concept of a software laboratory is a facility in which the users are provided with a variety of preprogrammtd problem­ solving frameworks--similar In spirit to designs of prefabricated houses. The user augments and modifies a framework to develop her own programs. ln order to provide such a facility, a framework. must be built with parts that can be "unplugged" and replaced. Each framework is decomposed into self­ contained modules, creating a hierarchically organized set of component parts. These parts in turn are interpreted or evaluated by "various" managers. As an example, a part oi the decomposed Blackboard framework. is shown below:

EXAMPLE 6: Blackboard Model Decomposition

Theoretically, then, each module (with all of its subparts) Is replaceable. For example, the whole RHS-Manager can be replaced if the user wants a definition of the RHS of rules different from the one we currently provide.

However, complete modularity Is not achieved, because some of the modules are not Independent. From a practical stand point the greatest barrier to replacing some of the modules Is in their Inaccessibility. Nevertheless, as In prefabricated houses, every module can be modified or replaced--some changes are more costly than others in terms of time and detailed knowledge of the implementation needed. In general, those parts nearer the bottom of the hierarchy are more accessible and easier to change. For example, the definition of ADD (add a new hypothesis element) can be changed by simply redefining the ADD function. Or, another function that makes changes to the hypotheses in a different way can be added. On the other hand, the LHS- and the RHS-Managers are not Independent. For those components that are independent, and easily modified or replaced, ACE provides some aids for making changes-­ acquisition functions and descriptions in the textual knowledge base. For those more difficult to change, we provide less aid with the Intention of discouraging novice users.

In order to have a useful software laboratory, we need to provide the user with diverse tools--some tools need to be nexible in their utility while others need to be fine-tuned for specific use; and some tools require substantial skill In their use while others do not. By organizing the program modules by their utility and providing easy access to those that are general and easy to use (but allowing skilled users access to all modules), we hope that the laboratory can be useful to a wide range of users.

5. SUMMARY AND CONCLUDING REMARKS

ACE is an experimental program currently running on PDP10 at the SUMEX-AIM Computing Facility at Stanford University. The immediate goal of the project is to provide software tools with which a knowledge engineer can reduce the time It takes to build knowledge-based programs. The longer range goal is to aid people less knowledgeable In AI methods to build knowledge-based programs. We have taken a small step toward reaching these goals by exploring the various ways in which Blackboard-based programs can be built, and by Implementing a set of parts from which such a program can be built.

In the process of building ACE, we have used it to write some programs: CR YPTO, a program that solves cryptogram problems; a portion of a bidding strategy problem in bridge games; two different versions of PUFF [9,12)--one using the Event-driven control macro and another using the Expectation-driven control macro [15l Since the domain­ specific knowledge for PUFF already existed and was being used in EMYCIN, the ACE version took about a week to bring up--time to reorganize the existing rules Into KSs and to rewrite the rules in ACE rule syntax. Currently, the CRYSALIS program [7) is being rewritten using ACE.

To the extent that we have been able to use ACE to develop some programs, we feel encouraged to continue with further development. However, there are still many issues that need to be explored In the current work-- the adequacy of the user Interface and debugging facility; generality of the current functional breakdown of the Blackboard model; sufficiency of the current rule syntax and semantics to express a wide range of knowledge; adequacy of the production rule representation itself for a variety of tasks; reliability of the system; etc. We have made no progress in providing a facility for explanation within the object program; we need more basic research in this area before such a facility can be implemented.

APPENDIX 1: Building Knowledge·Based Program with ACE

Introduction

This appendix shows the ACE system from an user's point of view. We have included an example program with parts of actual protocols to illustrate various (acilities.

Cryptograms

The problem used as an example is translating cryptograms. The cryptogram solution consists of a four level hierarchical hypothesis structure. The rules to solve cryptograms were provided by a human "expert". The task for CRYPTO is to take a "newspaper" cryptogram (10 to 20 words long, about 100 letters) and using a set of heuri~tics, translate it into an English sentence. For example, the cryptogram "GSHSUO CI DXDV BSS CLESVBFGB BS HD NCGU HJB ISLD JGNCGU EDSEYD EVSXD BZF.B BZDVD'I IBCVY F RDP SR JI PZS FVD BSS ILFYY." translates to "Nobody Is ever too Important to be kind but some unkind people prove that there's still a few of us who are too small." The word boundaries and punctuation are given. There Is a one-to-one correspondence between the cryptletters and their translation, and no letter translates to Itself.

Typical run

An ACE user typically builds a knowledge-based program over a period of time, conducting many hands-on sessions. In ~he first session the user gets acquainted with the system, learnmg the different components available and the system conventions, and discovering what Information she must provide (i.e., what to think about before the next session). During the next few sessions the user designs and builds her program. Finally, the user Iterates on checking out the program, running It, and modifying it.

TUTOR: Tilt TUTOR subsystem is described in Section J.2.

[after tilt user logs on, AGf. begins by determining if the ustr nttds a tutorial]

Are you already familiar with this system?: No

This and all subsequent sessions will be recorded.

The record will go on your directory as DRIB<name><date>.

Following is a list of AGE conventions which may be useful. [ducription of AGE user conventions]

[canned text on othtr topics]

What follows Is a tutorial session to acquaint you with AGE. [T lit following text describes the organization of the AGE on-ltne manual]

Each topic in the AGE system has one or more modifiers attach to it. A modifier may be a descriptive word (e.g. Hypothesls.­ element) or it may be one of the following:

ISA: Definition or definitional description.

FORM IS: Representation or structural description. FORMEDBY: How <topic> is generated or created internally during the user program execution. TOSPECIFY: Description of the acquisition function. CEN: generally accepted description. ACE: definition or description as Interpreted for AGE.

[canned text on further topics]

[The following interaction shows cross-referencing] ---There are some pre-assembled control structures available for convenience. (See CONTROL.MACRO)

References are: Hypothesis.structure Control.macro Do you want to see them now?: y HYPOTHESIS.STRUCTURE Y/N:: y The hypothesis structure in AGE Is hierarchically organized. There may be more than one hierarchy in the hypothesis (generally known as blackboard planes). Each hierarchy consists of linked hypothesis elements, HYPOTHESIS.ELEMENT, abstractions. grouped Into levels of

[Tutorial session is eventually terminated.]

This ends the AGE tutorial session. From this point on you will be given a menu of tasks to select from. To start, I suggest you begin with the DESIGN task.

DESIGN: RefiT to section J.2 for a dttailtd description of tht Design subsystem.

What do you want to do next?

Tasks available are: [Thtst art top level taslcs in AGE]

name description

Tutor

Browse

Design

SAve

Getsys

Check

Run

SYsout System explanation.

Browse thru the AGE manual.

Create the user program.

Save the user program on a file.

Get the user program from a file.

Check syntax of the user program.

Execute the user program.

Save everything (ie. SYSOUT)

:: design

Create the user program. What Is the name of your system?:: CRYPTO [AGE determines if there alrtady exists a program by that namt]

Do you want a Guided design session, or Unguided session?

:: g [Only a minimal number of consecutivt /lttm that uniqutl'

identifies the prompt is needed.]

Beginning DESIGN and ACQUISITION: You will need to design and specify three major components of your program: the hypothesis structure, the domain-specific rules, and some control Information.

You may begin working on K nowledge.domain-rules Control Hypothesis.Structure

During this design session, In addition to specifying or editing components of the system, you may also ask for ADVICE, more INFORMATION from the manual, or to QUIT the session.

What do you want to do next? Your options are: Hypothesis.structure Knowledge.domain-rules Control Advice Information Quit Type H/K/C/U/A/1/Q: a [asking for advict]

Specify the hypothesis structure first; It will aid you In structuring your problem. Then enter some domain- rules, followed by control information. Within the control specification, choose system-provided control methods to see how your rules work. More rules can be added or more sophisticated control can be specified later.

HYPOTHESIS: See Section J.J.J for a general discussion of tht Hypothesis .

CRY PTO uses a four-level structure, as shorun in Figure AI. At the highest level (SENTENCE) thtrt is ont named node CRYPTOGRAM, ruhert information inferrta about the whole cryptogram will bt stored. At the WORD ltvtl, tltments WORD/ to WORDn art created dynamically for tach word of tht cryptogram; and at the LETTER level, elemtnts LETTER/ to

LETT ERJ to LETT ERm for tech letter.

What follortJs is an txamplt protocol of tilt acquisition of tilt hypothesis structure for C~Y Pro.

The user Is asked for the names of levels of hypothesis elements, and for the names of the attributes at each level. The level names must be unique; the attribute names need only be unique within a level. When ACE asks for attributes, only attributes should be given and not the names of the links between two levels. ACE will start from the highest level,

What do you want to do next? ::Info [ask for information] Select a topic. ::hypothesis.tospecify Function: (HYPO) LEVELl.

Do you want to work on Hypothesls.structure?:: y Aqulring HYPOTHESIS.STRUCTURE Name of LEVELl ? A level name can be any literal atom not already used for the name of another level. Type Done to quit. :: sentence Attribute? Attributes must be unique within a level. :: words Attribute? [etc.] Name of LEVEL2? :: wurd [misspelled namt--to bt corrected later] Attributes? :: letters [TIll remainder of hypothtsls acquisition and tdtttng dtltttd.] :: print [print tilt ltypotlttsls structurt] LEVELl - SENTENCE WORDS · NIL ENGLISHWORDS · NIL LETTERS · NIL LEVELZ · WURD [mtsptlltd ltuel namt]) LETTERS · NIL ENGLISHWORD · NIL ORDREINSENTENCE · NIL [missptlltd] POSSIBLEWORDS · NIL LEVELl · LETTER CRYPTLETTER · NIL ORDERINWORD · NIL RELFREQ? · NIL

KSa: Rtfer to Section J.J.2 for a general dtscription of tilt KSs as ustd in AGE. Tilt protocol shows tilt partial acquisition of tr11o KSs. The specification of tach KS begins wltlt somt declarative information nttded to tllaluatt tilt rults in tltt KS. Then tilt user Is prompted for parts of tlte rults. Tht first KS Is a stt of rules that look at tlte whole cryptogram. It is calltd once after tnlttaltzation and any time thmafttr to find a new part of tltt cryptogram to focus on. This KS assumes that certain Information already exists in the hypothesis structure as a result of initialization. Tilt first rule looks for one-lttter words which could tither bt A or /, with A mort likely than I.

You need to specify: Rule.evaluator Knowledge.sources Control You may modify: Hypothesls.structure

[AGE kttps track of what has and has not b11n sptcifltd] What do you want to do next? :: kn What Is the name of the KS you want to create or add rules to? :: wholesentencerules [New knowledge source] What events Invoke this knowledge source? :: always [AirtJays means cny tvtnt can bt a prtconditlon to tilts knowltdgt source] Between which Hypothesis levels does this KS make Inferences? From? :: Jetter To? :: alphaletter From? ::none Which links are used to record inferences made by this KS? :: possiblevalue [Posstbltvalut links will connect elements from tilt lttter levtl to posstblt llalues in tilt alphalllttr ltutl] Inverse link? :: posslblevalue/of Link? :: assigned value [Assigntdvalut links will connect positiutly assigned values from tilt alpltaletters to tilt cryptlttters on tilt letter ltutl] · Inverse link? [etc.] Do you want to use multiple or single hit strategy for this KS? You can specify Onceonly with Single or Multiple. :: single onceonly [Stnglt to flrt only ont rule and One~only to mark tltat rule so that It won't b1 fired again] Local variables can be defined as (variable value) or (variable). Define a local variable. :: (wordnodes (Svalue 'cryptogram part)) [Stort tlt1 node names for the word nodes in WORDNODES. Tilt function IVAL.UE rttri1v11 thos1 names by following the ·part· link from tilt CRYPTOGRAM nodt] Define a local variable. :: (word) Define a local variable. [etc.]

What is the first condition? Type None when done. [TIlls problem tnvoluts starches which art awkward with till current rule syntax and requtrts extenslut L.tsp cod1. Stt Exampl1 'for tlt1 mort usual use of rul11.l

· · ( aetq word (for wd in wordnodes there is (and (eg (length ($VALUE wd letters)) 1)

(null (Svalue wd englishword) [loolclng for a word of lengtll /,not already assigned a value] Next condition? :: none Next, you will be prompted for the RHS of the rule. PROPOSE, EXPECT, COAL, or LOOP? ::? propose [ask about PROPOSE] PROPOSE Is used to change the hypothesis structure. :: prop [spectflcatlon of PROPOSE follows] ch.type:: supersede [replace current value] hypo-element:: word [of word element] attr-value:: (englishword 'a) [wltll ·a·] link-node:: none event.type:: assign word [name of tll1 1vent it generat1s] comment:: (a one letter word is most likely 'a') PROPOSE, EXPECT, COAL, or LOOP? :: propose (more tllan one action allowed in the RHS] [ttc.l link- node:: (assignedvalue 'a) [change the relational/ink] event.type:: asslgnletter comment:: (assign the letter 'a' to the cryptletter) PROPOSE, EXPECT, COAL, or LOOP? :: none More rules?:: no What Is the name of the next KS you want? :: flll-lnrules (New knowledge source] [some declarative lnfcrmation deleted] PROPOSE, EXPECT, COAL, oc LOOP? ::? loop [aslc about LOOP] LOOP is used to indicate an iterative action, either PROPOSE, EXPECT, or COAL. If LOOP Is used, you will be prompted for the name of an Iteration variable and the name of a list of values on which to repeat the action. :: loop Iteration variable? :: ol Name of the list to be Iterated on? :: otherletters PROPOSE, EXPECT, or COAL? :: propose [remainder of rule acquisition delttt] CONTROL: Refer to Stctlon 4 and Appendix II for discussion of lnowledgt uttltzatlon and control mechanisms. T h1 overall strategy for solving cryptograms Is to focus on a particular word or a combination of l1tt1rs that lias ·potlnttar; work on tll1 focussed lttm and follow through on all the ramifications, wlllcll In turn may gmtratt a new focus. :: control · Control specification: Currently there are three methods of specifying the control Information. Two are macros which require minimal specification, EVENT -DRIVEN-MACRO and EXPECTATION-DRIVEN-MACRO. The third method, DET A ILCONTROL, involves detailed specifications of several subcomponents. New additions to design Control.macro. Event-driven component: (Detailcontrol Control.macro.expectation-

driven)

[When a node is chosen, it opens other nodes tllat rtqu.lrt fu.rtlur spteiflcatlon] What do you want to do next? :: detail Detailed Control Specification: There are several components grouped under the heading of DETAILCONTROL. To simplify the designing process, ACE provides default specification where appropriate. The components that need to be specified are: I. Input data format: INPUTFORMAT, 2. Initialization function: INITIALIZATION, 3. processing method to be applied to each step-type, 4. rules to select a step to be used as the current focus, 5. rules to select relevant KS (or procedure) to process the selected step: (3,4,5 part of KERNEL), 6. termination condition: TERMINATION, and 7. post processing function: POSTPROCESSING. New addition to design component: (Inputformat Initialization Controi.Kernel Termination Postprocessing) What do you want to do next? :: inputform The input data you use In your system will be stored on an Implicit level of the hypothesis structure called INPUTDA TA. A function IDATA is available to access the data. At the beginning of each run you will be asked to input (from a file or TTY:) the actual data associated with each data name. First name? :: lnputcryptogram Next name? :: done What do you want to do next? :: initial You must provide a function that will return, as its value, the name of the first KS to be invoked. Within this function you may do any processing you whish. [NEW FUNCTION] What would you like to call your initialization function? :: crypto-initlallzation Your initialization function must return the name of a KS. Please define CRYPTO-INITIA LIZA TION (CRYPTO-INITIALIZATION (LAMBDA NIL [TIIis line provided by AGE] (prog (cg) (cg ~ (Sdata 1nputcryptogram)) (f111-1nlevels) (computerelfreqs) (return 'wholesentencerules) What do you want to do next? :: terminate You must provide a function which will determine when to terminate vour program. What is the name of your termination function? :: crypto-quit [deflnl CRY PTO-cy.J IT function In the sam1 manner at abovt] What do you want to do next? :: post

you can provide functions for printing the results, translating the results into a more readable form.

Take up this option or bypass it? [optional component] :: take

What would you like to call your postprocessing function? :: decodedprint

[Define DECODEPRINT]

What do you want to do next?

:: control.k

This function allows the user to specify various options which determine how events, expectations, and goals will be processed. First we will look at the event processing Information.

Do you want to enter kernel Information now?:: y Which event selection method would you like to use? LIFO and FIFO are available or you can write your own function. Type LIFO, FIFO, or function name. :: ?

The Event-selection Is used to decide which event from the event list to process next. LIFO chooses the last event added. FIFO chooses the earliest event. You can provide your own function. For example, bestfirst might depend on the weights associated with each event.

:: lifo

Name an event type to be collected.

.. fill-In

:: done

The control rules are used to determine what step type to proces next. Each control rule consists of a condition and a step type.

STEPTYPE:: event CONDITION:: expectatlonlist STEPTYPE:: expectation CONDITION:: none

USER FUNCTIONS: The final information the user must provide is the names and definitions of the functions used in tile rules or called from other user-defined functions. The user can name and define functions one at a time or load them from files.

EDITING: Thert art two ways to edit: (1) by calltng the appropriate editing function from Unguided design session or (i) during the Chtelt-out session. The Chtek subsystem described beloriJ.

SYSTEM CHECKOUT: The Check subsystem does a syntax chtclt on tilt user created program. It finds errors in the designed structures and points out missing, but required, information. Check also allows the user to edit the errors as they are found by calling the appropriate editor.

What do you want to do next? : check Check syntax of the user program. checking hypothesis levels- ALPHALETTER .. . checking knowledge sources -FILL-INRULES .. . Warning: 2 events not used as preconditions ASSIGNWORD FILL-IN [they riJtll be used by KSs to be defined later] I syntax errors In the user program. Do you want to edit the errors now?:: n RUNNING: One~ all tht information is specified, the user can run her program In two modes, debugging mode or normal mode. In debugging mode, AGE prints a tract of the control flow shoriJing the rules evaluated, the actions taken, and the steps and focuses selected. In normal mode, AGE only prints the input data and the results.

A complete run will begin with a request for input data. Next the user's initialization junction which returns a KS name is evaluated. That K S Is the first to be interpreted and starts the control loop, which will continue until the termination condition is met. Finally, the postprocessing function is called. The following is a sample run of the CRYPTO program. We have deleted a large section of the protocol to save space.

What do you want to do next?:: run [top level prompt] Execute the user program. Do you want to input data from a file or from a terminal? (filename or TTY:):: crypto-datal [Input from a f ile] ((INPUTCRYPTOGRAM (GSHSUO CI DXDV BSS CLESVBFGB BS HD NCGU HJB ISLD JGNCGU EDSEYD EVSXD BZFB BZDVD'I IB RDP SR JI PZS FVD BSS ILFYY)))

Knowledge source invoked · WHOLESENTENCERULES [W HOLESENTENCERULES is tilt KS name returned by the initialization function. ]

Left hand side of applicable rule - ((SETQ WORD (for WD in WORDNODES thereis (AND ··. (Jlrst rule to fire, word/7, letter7 J, is probably · A". Two events result, ASSIGN LETTER and ASSIGNWORD]

NAME OF NEW EVENT: ASSIGNWORD NAME OF NEW EVENT: ASSIGNLETTER ******************************* NEXT STEP: EVENT [choose the next step- EVENT]

FOCUS EVENT-(ASSIGNLETTER(LETTER73)(ASSIGNEDVALUE A WHOLESENTENCERULES EVZ NIL)

(Since the ASS ION LETTER event rvas added to tilt EVENT LIST last, it is the next focus event under tilt depthfirst (LIFO) selection method. When there are no further ramifica­ tions of ASSIGNEDLETTER, ASSICNWORD will become the focus event.]

Knowledge source invoked - FILL-INRULES Left hand side of applicable rule - ((SETQ OTHERLETTERS (for L in CRYPTLETTERNODES join [find other letters with same cryptvalut as letttr7 J FILL-IN those letters with value "A"]

NAME OF NEW EVENT: FILL-IN ******************************* NEXT STEP: EVENT

FOCUS EVENT - (FILL-IN (LETTER92) (ASSIGNEDVALUE A) (ASSIGNEDVALUE A) EV13 NIL) [lttter92 was assigned last, thus with a depthfirst selection method, it becomes the new focus .] [etc. ]

[T lit rest of the protocol continues in the same manntr until termina.ted.J

Summary

One common question asked about the CRYPTO system is, "When CRYPTO makes an Incorrect assignment, can CR YPTO back up?" The answer Is no. There is no back-up or alternative hypothesis capability. In CRYPTO we believe that with enough rules and with the POSSIBLEVALUE attributes and weights, the system wlll always make the correct assignments. This belief stems from the sessions recorded with ~he exper! newspaper cryptographer, who never needed to back up. The expert never guessed at a value or tried to confirm or contradict a guess by looking at its ramifications. However, we do recognize that the concept of alternative hypotheses Is a powerful one, and we expect to add facilities to ACE to allow them In the future.

APPENDIX II: SUMMARY OF THE CONTROL KERNEL

The Control Kernel consists of several components (Figure Bl) each of whtch must be specified by the user. The sequence of actaons whtch are taken within the Kernel is described below.

1. Invoke rules (CONTROLRULES) to select the next step-type to process--EVENT, EXPECTation,or GOAL;
2. If the selected step-type is EVENT, then
3. (a) Select an event, (SELECTIONHETHOD provided by the user);
4. (b) Collapse the EVENTLIST by deleting/merging events referring to identical attributes and values of the events specified by the user (COLLECTIONRULES);
5. (C) ·Select a KS (EVENTRULES generated by AGE from the KS preconditions).
6. If the selected step type is a goal (ACHIEVE), then
7. (a) Select a goal (SELECTIONHETHOD);
8. (b) Evaluate to determine if the goal has been met (MATCHER).
9. (b) If not, apply a goal-seeking method ( SEEKMETHOD).
10. (d) If the goal has been met, execute the remainder of the RHS of the rule that generated the goal.
11. If the selected step-type is EXPECT, then
12. (a) Select an expectation (SELECTIONMETHOD);
13. (b) Evaluate to determine if the expectation
14. has been met (MATCHER),
15. (c) If so, process the expected event by executing the remainder of the RHS that generated the expectation.