The Architecture of Coherent Information System: A General Problem Solving System

1. Introduction

Our objective is to create a meta-system which can be used to generate intelligent information sys­ tems in different domains of discourse. The meta system is called the META DESCRIPTION SYSTEM (MDS). It has facilities to accept definitions of descrip­ tion schemas and descriptions themselves, of KNOWLEDGE -- about facts, objects, processes, and problem solving -- in a domain. A domain might be a disease system, a piece of mathematics, or computing systems themselves. The description schemas and descriptions of knowledge in a domain specialize the MDS to act as an intelligent information system for the domain. For a domain M, the information system associated with it is called the COHERENT INFORMATION SYSTEM of

M.

In our research we have two principal concerns: (i) How may one describe knowledge in a domain to a computer; what kinds of knowledge should a system have to exhibit intelligent behaviour; what operation­ al facilities are needed to accept and use such knowledge? (ii) How may the computer be made to use given knowledge automatically to solve problems in

the domain and .answer questions?

The MDS accepts and uses three kinds of know­ ledge: a) Structural knowledge pertaining to the form and syntax of descriptions. Descriptions may, 'of course, be strings of words in some language. The MDS will translate such descriptions to structures within a relational system. The relational system itself may consist of constants, variables, predicate symbols, function symbols, logical operators and quantifiers. The structural knowledge specifies the structure of the relational system used in a domain. b) Sense knowledge: Logical assertions pertaining to the sense in which structures are interpreted, and constraints on admissable structures beyond those specified in the syntax. And, c) Transformational knowledge: This pertains to the knowledge necessary to transform given descriptions of specific objects to new ones, according to specified criteria.

* This work was supported by a research grant from NIH, grant number RR-643.

THE ARCHITECTURE OF COHERENT INFORMATION SYSTEM:

* A GENERAL PROBLEM SOLVING SYSTEM

C. V. Srinivasan Department of Computer Science Rutgers University New Brunswick, New Jersey 08903

Corresponding to these three levels of knowledge there is a hierarchy of problem solvers, (CHECKER, INSTANTIATOR), THEOREM PROVER (TP) and DESIGNER, in order of increasing complexity. The (CHECKER, INSTAN­ TIATOR) system acts as a sophisticated data management system that establishes, maintains and updates the data base of models of specific objects in a domain in a manner consistent with the structural and sense knowledge. CHECKER can answer questions pertaining to any of the specific models for which the informa­ tion is either directly stored in the data base, or is directly derivable by evaluating a given logical assertion in a given context. The THEOREM PROVER adds power to the CHECKER in three ways: In certain cases it helps reduce the search effort of CHECKER by giving it advice based on deduced consequences of sense knowledge; where feasible it can warn the CHECKER of impossible situations in the generation and updating of models; it can also determine general truth values of assertions based on the structure and sense knowledge. The DESIGNER adds further power to the system by enabling the system to plan courses of actions using given action primitives (Transformation Rules) in a manner consistent with the facts of a problem. This hierarchy imposes a very useful classi­ fication of system facilities, and gives the system a considerable flexibility.

The descriptive language of a domain is itself specified in terms of the model definitions in the domain. Language analysis is thus looked at as a model building process. Most importantly, the model definitions in a domain may include definitions of Problem Solving States (PSS), relevent to the domain. The PSS may provide facilities to summarize the problem solving experience of the system. This sum­ mary may be used to intelligently guide the problem

solver.

This work on MDS and CI-systems may be thought of essentially as a further extension of the trend start­ ed by REF-ARF[l,2], QA4 [3], POPS [4], STRIPS [5,6], and PLANNER [7]. Its problem solving activity uses "means-end" analysis, a concept originally introduced in GPS [8], and function invocation schemes based on goals, introduced by PLANNER. CI-Systems have both the flexibility of PLANNER-like systems, and model based reasoning abilities of a GPS like system. The entire system depends on the way descriptive data structures are organized in a given domain. However, the availability of data structure and model defini­ tion facilities, and a separate data management sys­ tem makes it possible to completely isolate the data structure and data base details from the problem solving programs. This makes it possible to conceive of the meta system, the MDS, to create CI-Systems for different domains. It seems reasonable that, if the classes of possible models of objects in a domain could be described to a computer then, in principle, the computer should be able to make use of the des­ criptions for problem solving and language understand­ ing in the domain. In CI-Systems we show how (a) classes of models can be defined and (b) how the definitions could be used for language analysis and problem solving in the domain.

The principal contributions of the proposed architecture are:

1. A facility to use large data bases;
2. ii) A stratification of knowledge in a domain and the facility to use a highly flexible descriptive mechanism to describe objects and problems in a domain; the possibility of describing knowledge in a domain in a systematic way to a computer;
3. iii) The definition of the descriptive language itself in terms of the models the system can build in a domain; and
4. iv) The possibility of specializing the MDS to operate efficiently as a problem solving system in a domain of discourse.

The MDS is now being implemented in LISP 1.6. Some parts of it (see Section 3) are now ready. This paper is, therefore, a report on work currently in progress. It introduces the principal architectural concepts of MDS and CI-Systems in the context of an example, the Missionaries and Cannibals* (M&C) prob­ lem [9]. The structure of CHECKER and DESIGNER is explained. The operation of the THEOREM PROVER is discussed in [10]. In a subsequent paper the language processor will be discussed.

2. An Overview of the System Architecture

2.1. Templates and Their Instantiations

2.1.1. The Templates

The concept of TEMPLATES, the devices used to specify structural knowledge is central to the entire system architecture. Templates classify objects in a domain into objects of different kinds and~· Each template specifies a certain description struc­ ture. Thus, in the M&C problem (see Table I) PLACE, PEOPLE, VEHICLE, etc. are different kinds of objects. The template for PLACE, for example introduces two relation symbols: occupants and position of. The pair of relation symbols (occupants, occupants of) for example, are inverses of each other in the sense that in instances of PLACE and PEOPLE the relations (PLACE occupants PEOPLE) and (PEOPLE occupants of PLACE) will always appear together in the data base of models. PEOPLE is just a list of PERSONS. An instance of ~ classification occurs in the PERSON template. A PERSON can be a MISSIONARY or CANNIBAL. In MDS type classification always reflects distinc­ tions in the way objects are used. The templates thus specify the structure of the relational system for a domain: the relation symbols to be used in the description of various kinds of objects in the domain, and the kinds of objects that a relation symbol may relate.

Given such templates, one may use the INSTANTIA­ TOR to create descriptions, which are instances of the templates. Such instances might be specified to the system. in some external language, which is trans­ lated to the internal representation in the relational system. Or, the system itself might generate an instance of a template when called upon to do so. In either case, to complete the instantiation of a tem­ plate, all the relation symbols defined for the tem­ plate should be assigned values. These values will

* There are three missionaries and three cannibals on one bank of a river. They want to go to the other bank. There is only one boat available. It can carry only two people at a time. The cannibals at a shore should not outnumber the missionaries at the same shore. Find a way of transporting them.

TABLE I: TEHPLATES FOR THE M&C PROBLEM

1. PLACE: (occupants PEOPLE occupants of), CCl (position of VEHIL position), CC2
2. PEOPLE: (elements PERSON elements of)
3. VEHIL: (elements VEHICLE elements of)
4. PERSON: (type PTYP type of) (occupant of PLACELl occupant), CC3
5. PTYP: HISSIONARY, CANNIBAL
6. PLACELl : (elements (PLACE, VEHICLE) elements of)
7. PLACEL: (elements PLACE elements of)
8. VEHICLE: (pilots PEOPLE pilots of)

(position PLACE position of)

(cango to PLACEL destination of)

(capacity INTEGER capacity of)

(occupants PEOPLE occupants of), CC4

[CCl] (*! occupants ((PEOPLE X)(*! occupants X)

(((NUMBEROF MISSIONARY X) ~

(NUMBEROF CANNIBAL X))v

((NUMBEROF MISSIONARY X) is O))))

[CC2] (*! position of ((VEHICLE X)(*! position of X)

• (X cango *!)))

[CC3] (*! occupants of.#.is 1)

• [CC4] (*! occupants.#. s .capacity of *!)

be specific instances of objects within the data base.

Thus for the M&C problem one may create instances of PLACE's called RBANKl and RBANKZ, a VEHICLE called BOAT, and as many MISSIONARIES and CANNIBALS as nec­ essary. Each PERSON will be the occupant of some PLACE and the VEHICLE itself will be at one of the PLACEs. We have not, however, introduced any of the conditions of the problem. Not all instantiations of the templates of the M&C problem would represent legal situations. The necessary additional constraints are introduced by the sense knowledge. Every relation symbol in a template may have a Consistency Condition (CC) associated with it. CCl in Table I is associated with the symbol "occupants". It says that the CANNIBALs at a PLACE cannot outnumber the missionaries. The symbol "*!" in CCl refers to the current instance of PLACE ·at which the CC might be evaluated. It is called the anchor; (PEOPLE X) stands for "(YX) (X is PEOPLE)". All CC's have the form: "(*! r P(X))" where *! is the anchor, r is a relation symbol occurring in the template associated with*!, and P(X) is some logical predicate. The predicate P(X) is said to be anchored at the (template, relation symbol) pair. Thus, the predicate in [CCl] is anchored at (PLACE, occupants).

In [CCl] notice that"(*! occupants X)" is itself a term in its predicate. This has the following sig­ nificance: For a PLACE like, say RBANKl, if the system is told to set (RBANKl occupants y) for some y, it would first construct the combined list of existing occupants of RBANKl and y, and then verify the predi­ cate. CC's of this kind are called declarative CC's, as opposed to the other kind, called imperative CC's, like, say (for a hypothetical template PERSON!) [CSl] (*! sibling ((PERSON! X) (NOT (Xis *!)) (X child of.father of*!)))

(CSl] may be used to find the siblings of a PERSON! in terms of the child of and father of relation symbols. The CHECKER is used to evaluate CC's. We shall dis­ cuss the evaluator in Section 2.2.

The significant points to be noted about CC's are the following:

• (i) the knowledge represented by the CC's is of a different kind from the structural knowledge, specified by the templates.

• (ii) Each CC is specifically associated with a particular relation symbol. A relation symbol, say "likes", might be quite different in the context (HUMAN likes SOMETHING), from (CATTLE likes SOMETHING). A CC is invoked and interpreted only within the parti­ cular local context of its anchor, within the overall structure of descriptions.
• (iii) The logic of the CC's is highly dependent on the structures specified by templates. Also, for a given system of templates there may be more than one way of choosing and anchoring the CC's. Further, for a given domain, there will undoubtedly be several ways of defining the templates and its associated CC's. These different definitions will correspond to different ways of representing the knowledge in the domain. The MDS provides facilities to experi­ ment with different choices. At present we have no formal guidelines to make these choices intelligently. The particular choices made in a domain will have an effect on system efficiency.

2.1.2 Instantiation of Templates

We shall call an instance of a template as the model of the object instantiated. Thus, the model of RBANKl will be an instance of PLACE. Every triplet (x r y) (where r is a relation symbol) appearing in the model x should be dimensionally consistent: That is, for some templates M and T, where x is an instance of Mandy i~ an instance ofT, either (M r T) occurs in M, or (T r M) occurs in T, where r is the inverse of r. There are a few relation symbols which are system wide, like temp.late of, name of, elements of, arguments of etc., which can appear with all instances in the data base, and need not be defined in the tem­ plates.

The model of RBANKl will be a vector of five pointers, say (Pt ,P ,P ,P ,P ) corresponding to o n eo o po the relations template of, name, elements of, ~­ pants and position of, respectively. Pto will point to a pair (P~ ,P 2 t ), where P~ points to the PLACE 0 2 0 0 template, and Pt to possibly local conditions (LC's) associated with 0 RBANK1. P will, of course, point to "RBANKl". Let r be any Bne of the remaining relations: P will point to a quintuple of the form 1 2 3 r4 (#,Pr,Pr,Pr,Pr)' called the descriptor unit of P (orr). The elements of the descriptor unit afe the following:

Descriptor Unit

• P 4 : Pointer toy such that (RBANKl r y) is true, r or pointer to list (y) such that (RBANKl r z) is true for every z E y. We shall write this as (RBANKl r (y)).
• P 2 : To local conditions on values of (RBANKl r). r
• P;: ~~~~~~~~~1 l;s~)iy~ss~~~e~hat for every z E y,
• pl: r To TR's (Transformation Rules) local to (RBANKl r), called LTR's.
• #: The number of elements in the list, set or triplet pointed to by P~.

. + ' Every P 1 will have an inverse, say P 1 , which will r · t4 r 4 point back to RBANKl; P is the same as P +, The 1 2 r +1 +2 r 1 inverse of (Pt ,Pt) will be (Pt ,P ), where P o o o to to is the same asP. (i for instance); Pi will point to RBANKl from PLACE template.

A pqinter in a model can have one of four values: NS(Not Stored), NEI (Not Enough Informat i on), NIL, or an address (or value). Initially all pointers in a model are set to NEI. A list, set or tuple will have NEI as an element if it is incomplete. Templates thus specify the data structures of models in a do­ main. They provide the basic framework for the organ­ ization of domain dependent knowledge. They also play a major role in the specification and use of problem solving programs in a domain, as we shall see in Sections 2.2 and 2.3.

There are about fifteen different kinds of tem­ plates in the MOS. Variations in the structure of descriptions may be specified by defining, what are called variable templates. Exceptions to the CC's may be specified by associating local conditions (LC's) with specific instances of templates. An LC may be a conjunctive LC (CLC) or a disjunctive LC (DLC). A model should satisfy ((CC A CLC) v DLC) at each one of its relation symbols. Similarly, trans­ formation rules (TR's) for changing a model rna~ local to a model (LTR) or may be associated with tem­ plates themselves.

In addition to the CC's associated with pairs (H, r), where M is a template and r is a relation symbol, r may also have Properties (PR) defined for it, which apply to all occurrences r within the rela­ tional system. A typical such property is the trans­ itivity property. For a model m, the PR's are used to identify objects y, such that (m r y) is true, but is not stored in the data base.

All problem solving programs communicate with the data base via the INSTANTIATOR and CHECKER. Tem­ plates also provide a way of classifying and storing the CC's, LC's, TR's and LTR's. Every CC (LC) is anchored at (m, r) where m is a template (or model) and r is a relation symbol (relation) defined on m. The DON-list of a CC (LC, TR, or LTR) is the list of (m.,r.) on which it depends. The DET-list of a pair (m;r) 1 is the list (m.,r.) of pairs which depend on (m,r). So also, the 1 DEf-list of a TR (LTR) is the list of (m.,r.) which are affected by the TR (LTR). The DON ana 1 DET lists are stored with each CC, LC, TR and LTR. Also, every pair (m, r) will have a pointer to its associated CC, LC, TR and LTR.

2.2 Evaluation of Consistency Conditions

2.2.1. The Logic of CHECKER

The evaluation of CC's, LC's and PR's will in­ volve searching of the models in data base. The conditions themselves specify the search paths. The anchor"*!" may be used to optimize this search. One can write small efficient programs (say, about 3K PDP-10 words of compiled LISP code) to evaluate these conditions. (Alternatively one may compile each CC and PR individually.) The CHECKER is the interpreter for CC's, LC's and PR's. It uses the G function (G for Get) of the INSTANTIATOR to retrieve objects from data base. G does the following:

• (Ql) G (X r ?) {y J (x r y)} (This may include NEI), or NIL or NEI.
• (Q2) G(X r y) YES, NIL or NEI
• (Q3) G(X ? y) p, NIL

where pis a relation path (r 1 ,r 2 , ... ,rk) joining X andY (the shortest one). G JUSt looks up the data base using the templates. If the answer is NS, NEI, or if NEI is included in the answer, then G will in­ voke the CHECKER to evaluate the associated CC's, LC's and PR's. This evaluation may cause the NEI to be removed and possibly add new elements to (y).

The CHECKER operates on a three valued logic system having truth values T (TRUE), F (FALSE) and ? (NEI). The logic of CHECKER is shown in TABLE II. For a given predicate P, besides returning its logical value (one ofT, ?, F), the CHECKER also returns seven other quantities, all of which will be subexpressions of P. These are explained below.

useful are given below. The logic of these functions is shown in Table II.

Let ~ and ~ denote valuations of the variables i.n P. Assume in what follows, that a certain task k was done either by the THEOREM PROVER or DESIGNER, and the outcome of the task k depended on P. Also,

TABLE II: LOGIC OF CHECKER

Literal x ~x denotes the value of x.

~X TR~(x) FR~(x) R~ (x) TP~(x) FP ~ (x) NTP~(x) NFP~(x) " T ? F v T ? F ~X ~~X

Propositions: P, Q. Let X denote one of TR, FR, R, TP, FP, NTP, NFP. Then

Also """ and "v" are synunetric:

The various functions are defined below for (P "Q).

In all the following functions assume that ~ is a particular valuation of the variables in P. ~(P) = T, For?.

TR~(P): True Residue of P. The subexpression of P that caused ~(P) = T.

FR~(P): False Residue of P. The subexpression of P that caused ~(P) =F.

R~ (P) : Residue of P. The subexpression of P that caused ~(P) = ?.

T~(P): True Part of P. The subexpression of P that evaluated toT. ~(P) itself may beT, F, or ? .

F~(P): False Part of P. evaluated to F. ?. The subexpression of P that ~(P) itself may beT, F, or

Not True Part of P. The subexpression of P that evaluated to For ?. ~(P) itself. may be T, F, or ? .

NF~(P): Not False Part of P. The subexpression of P that evaluated toT or ?.

The various residues and parts of P are used in the planning phase of DESIGNER to summarize past experiences of the system. In the THEOREM PROVER the residues are used to guide the problem solving search. The properties of these functions that make them at the time k was attempted, ~ was the valuation of the variables in P. At a later time, a new valuation ~ of the variables P was obtained, and the system had to decide whether to attempt k for the new valuation.

1. (VP)(V~)(V~)(HTRlji(P)) =;> HP)).

If ~(TR~(P)) is true then try k again.

(VP) (\1'~) (\1'~) (~HFR~(P)) ~ ~HP)).

2. Do not try k if ~(FR~(P)) = F.

1. (VP)('v~)0~)((HNTPw(P)))(HTPw(P)) ~HP)).

A goal k could not be reached for valuation ~ because ~(P) = F. Then try and find a~ for which ~(NTPlji(P))(~(TP~(P)) is true. This is used to break up a goal into subgoals, in means-end analysis.

4.

(\IP) (\1~) (~~) CCHR~(P))) CHTP~(P))) HP))

Here goal k could not be reached because lji(P) = ?, and the unknown parts of Pis given by Rlji(P). Then find a ~ (build new objects) for which ~(Rlji(P)) and (~(TP~(P)) are true. This is used in means-end analysis, and in the THEOREM PROVER.

2. 2.2. What CHECKER and INSTANTIATOR can do; What more is needed

The CHECKER and INSTANTIATOR together act as a fairly sophisticated data base management system.

The CHECKER makes sure that data entered into the data base is consistent, and also keeps track of what additional data is needed to complete the des­ criptions of objects with respect to the templates. The templates for a domain describe the structure of the data base for the domain. The CHECKER uses this structure to guide the INSTANTIATOR to create and retrieve items in the data base selectively.

The limitations of the CHECKER arises in the auto­ matic guidance it can provide in the updating pro­ cess. The CHECKER has facilities to interpret individual CC's and to recognize the relation symbols whose value in the data base might be affected as a result of a change made at one place in the data base. CHECKER keeps track of the relation symbol, by cataloging the relation symbols in terms of their appearances in the various CC's. In general, a change in the value of one relation symbol might propagate through the data base to a series of other relation symbol values. As long as any given in­ stance of the value of a relation symbol does not repeat itself in this series, CHECKER will have no problems. It can execute the series of necessary changes without ever having to go back to a value that it had previously changed within the sequence.

CHECKER simply performs search in the data base, and logical combinations of search. It has only sim­ ple facilities to keep track of alternate choices in search paths, and choices in possible valuations of relation symbols. Also, CHECKER can handle only constants as possible valuations for relation symbols. When the number of alternatives is large or when loops occur in an updating chain, the CHECKER, if left to run will keep assigning new values to the relation symbols involved until a consistent set of valuations is obtained, or until all known possibil­ ities are exhausted. The only choices it can generate are those that are already available . in the data base, or those that may be obtained by evaluating specific consistency conditions in specific local contexts. It does not have the capability to deduce logical consequences and make use of them to find contradic­ tions where possible. To do this general theorem proving capability is necessary. The essential difference between the CHECKER and a THEOREM PROVER (TP) is the following: Whereas the CHECKER can assign as values to relation symbols only specific constants in the data base, the TP can assign as values, variables with specified logical properties. The TP can carry with it the logical properties assigned to variables and use them in making new assignments as it goes along. Resolution based theorem proving systems have this capability built into the unifica­ tion algorithm [see Nilsson, 1971].

In MDS the CHECKER will invoke the TP whenever it does not find enough information in the data base to evaluate a CC at a particular anchor, or whenever the validity of an assertion is to be proven univer­ sally; not merely with respect to the facts known about the specific objects in the data base. The CHECKER will call the TP also when it recognizes a loop in an updating chain.

The deduction process and the control structure of the TP in MDS is different from that of a resolu­ tion based system. (see [10]).

2.3. The Dynamic Aspects of Modeling: The Transforma­ tion Rules and Their Interpretation

2.3 .1. The Primitives

There are about twenty primitives that enable one to do programming in a backtracking environment. The primitives are classified as shown in Figure lA. The ECP's (Environmental Control Primitives) in Figure lA are used to establish a control environment (cenviron) within a scope. The execution of func­ tions within the scope are affected by it. See Table III for a description of the ECP's. The SCP's are the sequential control primitives like GO, COND, etc. There are seven active primitives, GOAL, ASSERT, DELETE, CANDO, IFDON, TRY and BIND. The execution sequences for the GOAL and other active commands are shown in Figures lB and lC. GOAL in­ vokes appropriate definitions from data base, and does "means-end" analysis when necessary. ASSERT arid DELETE issue I and D commands to the .INSTANTIATOR, when successful. All primitives, other than the con­ trol primitives, may have CANDO, IFDON and TRY func­ tions associated with them. A primitive can be executed only if its associated CANDO's are satisfied. If a primitive fails then one may try its associated TRY functions. If a primitive is successful then its associated IFDON's should be executed. Only if the IFDON's are also successfully completed may the primitive return success to its parent. Let us follow the operation with an example.

2. 3.2 . Interpretation of the Active Primitives

The syntax of the various active primitives is shown in Table IV. The DESIGNER is the interpreter for the primitives. Consider, for example, the <dimension> (See syntax of <dimension> in Table IV) of the GOAL function TRl in Table V:

The function call that will cause this TRl to be invoked is

((PEOPLE X) (GOAL (RBANKS2 occupants X)))

Let us follow the interpretation of this function call, as specified in Figure lB.

1) Find Possible Bindings

The CHECKER is used to bind variables in a <dimension> statement. We shall assume that the <proposition> in the GOAL-clause is always in dis­ junctive normal form. In the above case X wililbe bound to (M 1 M2 M3 Cl C2 C3). If the CHECKER returns NEI, or a loop is encountered then the TP may be . in­ voked to complete the bindings. Unless the IDB~· clause (see Table III for an explanation of the IDS­ clause) is present the TP will creat new objects, if necessary, to complete the bindings.

2) Find Initial Conditions

This is done by checking whether the GOAL is already satisfied in the data base for specific bindings of variables. In the case of our example, this will bring out the fact, (RBANKl occupants lMl M2 M3, Cl C2 C3)). This will cause the following invocation pattern to be built: ((PEOPLE (Xl + (Ml M2 M3 Cl C2 C3))) (PLACE (X2 + RBANKl) (X3 + RBANK2) (X2 occupants Xl) ~ <bindings> - 3> (GOAL (X3 occupants Xl))) <fn-clause>

[lC) SEQUENCING FOR FUNCTIONS OTHER THAN GOAL FUNCTIONS

Let b be the <bindings> and g the <proposition> of the <fn-clause>. The cannonical form of an invo­ cation pattern (also a <dimension> after binding the variables) is

(<bound quantifiers>((b 1 g 1 v ... v (b g))) where each b. and g. is a conjunction ~tmterms, possibly witR OPNL, 1 IFND, IDB or* clause~et D be an invocation pattern and D. any <dimension> in the data base. D. and Dare s~id to match, (D.~ D) if there exist biffdings for the variables in D7 such that for some b .. in D. and bk in D (b. ;==') b ) 1 and (g .. =} g ) , and 1 fn addttion b .. is tru~Jin t~e data ba~~- T~e b . . will be the inttial conditions. The invocation pt6cess will retrieve all D. that match D. 1

If no such functions, D. , are available then the DESIGNER will force the GOAL 1 by issuing the appropriate ASSERT and DELETE commands. These will cause their associated CANDO's to be executed. If the CANDO's succeed then the corresponding I and D commands will be tried. This will cause the associated CC's to be evaluated at the given bindings of the variables, say~. If the CC's are not satisfied then the NTP~ (Not True Part of ~ ) and TP (True Part) will be issued as subgoals. If the~CANDO's are not satisfied then the goal will be abandoned.

In general, both the binding and invocations processes will return more than one possible course

(1) FUNCTION DEFINITION FORMS

• (A) GOAL FUNCTIONS:

<gfn-defn> + (<dimension><body>); <dimension~+ (<bindings><fn-clause>); <body>+ <fn-call >l<body><fn-·call>; <fn-clause> +(GOAL <proposition>); <bindings>+ <predicate> I (OPNL <predicate>) I (IFND <predicate>) I(IDB <predicate>) l<bindings><bindings>; <proposition> + <propositional expression which may include OPNL, IFND, !DB, and * clauses>; (B) CANDO and IFDON STATEMENTS and TRY FUNCTIONS <cifn> +CANDO I IFDON; <cifn-defn> + (<cifn><dimension><cibody>); <cibody> + <cistnt> I <cibody><cistnt~ <cistnt> + (<dimension><TRY-fn>) I (<bindings><TRY-fn>) <TRY-fn> + (TRY <bindings><body>). (2) FUNCTION CALLS <fn-call > + <TRY-fn>l (OPNL <body>) I (IFND body) I (IDB body) I (SUP <fn-clause>) I (SUSPEND) I (ACTIVATE <dimension>) I<COND-stnt>l (GO <label>) I (BKTRK <label >) I<BIND-stnt> (This is like SET in LISP) I <dimension> I (PROC <bindings><body> I (ASSERT <bindings> <proposition>)) I (DELETE <bindings><propositions>)).

of action. In both these cases the problem solver needs to be guided intelligently in making its choices. The DESIGNER has some built-in facilities for intel­ ligent selection of choices from a set of alternatives. The Problem Solving State (PSS) provides this guidance. This is discussed in the next section.

2.3.3. The Problem Solving State

The PSS itself is defined by templates. The PSS template is shown in Table VI. This table is self­ explanatory. Every time the DESIGNER invokes a func­ tion or executes a <fn-call > it will create an in­ stance of PSS corresponding to the function. The net­ work of all such PSS instances is the problem solving protocol. The CC's associated with the PSS template provide the necessary guidance to DESIGNER. Of particular interest are the CC's associated with the bindings and alternates (see Tables VI) relations. Let us call these [CCB] and [CCF], respectively. These CC's will specify the choices of current bindings and current function. Two important notions that make this possible are the notions of similarity of two PSS instances, and cc summary of a PSS instance.

cc summary : (CCS): A CCS is a record of evalua­ tions of CC's,branching condit i ons, CANDO conditions and binding conditions, made during the tenure of a PSS instance. For each sequence of conditions evaluated, the CC-summary will contain : The TRUE RESIDUEs of the conditions evaluated if the condi­ tion evaluated to TRUE, the FALSE RESIDUE, NOT TRUE PART and TRUE PART if the condition evaluated to FALSE, the RESIDUE if the condition evaluated to NEI. It will also have the outcome (fn-state) of the PSS instance in which the condition was evaluated, and specific variable bindings if any in terms of the kinds and types of objects used. All variable bind­ ings in the CC-summary of a PSS will be specified in terms of the variables that appear in the bind­ ings of the PSS. The concept will become clear in the example considered below. The Consistency Condi ­ tion [CCB] uses CC-summaries.

The general rule is: Pick for bindings the same kind and ·~ of objects t hat previously succeeded in sim1lar PSS 1nstances; do not pick the ki nd and~ of objects that previously failed. Use cc-summaries to check whether a chosen binding is likely to succeed. If no bindings could be picked by the above rules, then pick arbitrarily.

(TRl) GOAL FUNCTION DEFINITION. IT SAYS, "PICK UP SOME PEOPLE Y, POSSIBLY AS MANY AS THE VEHICLE WILL HOLD, LOAD THE VEHICLE WITHY, AND TAKE THEM TO Q". "PROC" IN THE STATEMENT BELOW STANDS FOR PROCEDURE. IT IS SIMILAR TO PROG IN LISP, BUT DIFFERS FROM PROG IN THE SENSE THAT PROC HAS BACKTRACKING. (((PEOPLE X) (PLACE P Q)(P occupants X)(GOAL(Q occupants X)) (REPEAT (Q occupants X) (PROC ((SOME VEHICLE V) (SOME PEOPLE Y)(OPNL(Y ~.is.capacity of V))(Y among X)) 1. (ASSERT (V occupants Y) (NOT (P occupants Y))) 2. (ASSERT (V position Q) (NOT(V position P))) 3. (ASSERT (V occupants. are. occupants of Q) (NOT(V occupants Y)))))) (TR2) CANDO CLAUSE FOR LOADING A VEHICLE. IT SAYS, "UNLOAD THE VEHICLE FIRST. IF THERE ARE MORE PEOPLE THAN THE VEHICLE CAN HOLD THEN DROP SOME AND TRY AGAIN. IF THE VEHICLE IS NOT AT THE SAME PLACE AS THE PEOPLE ARE, THEN BRING IT TO WHERE THEY ARE. EACH TRY STATEMENT IS PRECEDED BY THE CONDITIONS, ON WHOSE FAILURE THE TRY WOULD BE ATTEMPTED. (CANDO ((PEOPLE X)(PLACE P) (VEHICLE V) (P occupantsX)(ASSERT(V occupants X) (NOT(P occupants X))) 1. (ASSERT (V osition P)) 2. ((PEOPLE Z V occupants Z) (ASSERT(P occupants Z) (NOT(V occupants Z)))) 3. ((X ~· .£·capacity of V) (TRY ((SOME PEOPLE Y) (Y among X) (ASSERT(V occupants Y) (NOT(P occupants Y)))) (IFDON(KILL(ASSERT(V occupants X)(NOT(P occupants X)))))))) (TR3) CANDO CLAUSE ASSOCIATED WITH BRINGING A VEHICLE FROM A PLACE P TO Q. IT SAYS, "GET A PILOT AND TAKE THE VEHICLE. IF PILOT CANNOT BE REMOVED GET SOME ONE TO GO WITH HIM". (CANDO ((VEHICLE V) (PLACE P Q) (V positionP) (ASSERT(V position Q)(NOT(V positionP)))) 1. ( ((SOME PERSON Y) (V pilot Y) (V occupant Y)) lA. (TRY ((SOME PERSON Z) (V pilot Z) (P occupants Z) (ASSERT (V occu1ants Z) (NOT(P occupantsZ))))) "' lB. (TRY((SOME PERSON X Y) ((V pHCN X)v V pilot Y)) (P occurants (X Y)) (ASSERT(V occupants(X Y OT(P occupants (X Y)))) ))

TABLE VI: PSS TEMPLATE

(dimension (intl. state (bindings (alternates (cc-summary (fn-state (cenviron (history (type (final-state (successor (predecessor (conditions DIMN) MODEL STATE) BINDINGS) PSSL) <dimension> of the function Initial State of Model All possible variable bindings and current bindings CCSL) FNSTATE) CENVIRON) PSSL) PSSTYP) MODELSTATE)' PSSL) PSS instances of possible alternates; also the currently active function summary of CC's evaluated during the active tenure of fn Function States: ACTIVE: SUCCESS, FAILURE, SUSPENDED The Control environment Previous instances of PSS with the same dimension Any useful type classification of PSS Model changes done by the PSS instance Possible successor functions PSSL) List of parent functions CONDN) Conditions appearing in REPEAT, COND and other such statements that caused the current PSS to be invoked '----------------------------------

To define the notion of similarity of two PSS states we need some additional concepts. Let k be an arbitrary PSS instance defined as follows:

k : (dimension Dk) (bindings Bk) (initl-state Ik) (alternates ~, ) (fn-state Sk) (cenvirons Ek) (ct-summary ccSk)(history Hk) (Type Tk) (final-state FSk) (successor Uk) (predecessor ~) (conditions Ck) . .

Let Vk = {X 1 ,x 2 , ... ,X } be the var1ables appear1ng in the <dimension>, Dk: . L~t Dk itself be_ (QkPkFk) where Qk is the <quant1f1ers> of Dk, Pk 1ts <propos1tion> and Fk its <fn-clause> (see Syntax of <dimension> in Table IV). Let lik = { (x. + A.) I 1 $ i $ m} be a specific binding of the 1 vari~bles in Vk such that 8k(Pk) is TRUE. The bindings Bk is the set of all such Sk. The initial-state, Ik, 1s a conjunction of terms defined on the variaoles in Vk and possibly some constants in the data base. Let Nk = {N 1 ,N 2 , ... ,N} be the constants in Ik. In each PSS instance k, I~ is the same as the final-state of its predecessor, together with whatever might have been added by the function invocation process per­ fgrmed in k, all expressed in terms of the variables in Vk and constants in Nk. For every 8k E Bk 8k (Ik) is true for the given constants 1n Nk. Not all of the constants in Nk might be used in the PSS instance. The used ones are precisely those that a~pear in the CC-summary of the PSS instance. Let Nk denote the used ones in k.

Two PSS instances K and J are similar if (i) They have the same dimension, Dk=D 3 . Thus VK=V 3 , and K and J are in the same history list, HK = H 3 . Also, the~ of K is equal to the~ of J. (ii) They have the same control environment, Ek=Ej, and

(iii) VK,NK, satisfy one or more of the cc-summar­ ies in J, for some binding Sk £ Bk. So also, VJ,NJ satisfy one or more cc-summaries in K for some b1nd1ng e 3 c BJ"

To understand how these work let us consider the solution of the M&C problem.

2.3.4 M&C Problem Solution

The sequence of possible function calls is shown in Figure 2. Each box in Figure 2 is labelled to indicate its correspondence to the functions in Table V. The boxes are numbered 1 through 15. For a ~~~t:~~~-number i, let Ki denote its associated PSS

Suppose we are at the beginning, and are at box 3 in Figure 1. Then the following sequence of actions might happen (follow arrows in order):

The indicated I and D commands are returned by the ASSERT function, TRl·l (see Table V). This will cause [CC4) and [CCl) to be evaluated, and the following cc-summaries to be returned to box 3 (since box 3 is still active)*:

Here K is the PSS instance at which the evalua­ tion took piace. The variable bindings are indicated only in terms of the kinds and~ of objects used. T and F are the CC evaluation outcom41s, and Fail is the outcome of K 4 · Notice that moving these two cc-summaries to K 3 maKes it still possible for K 3 to use these, because the variables P and V have in K 4 the same bindings as they do in K 3 and none of the terms appearing in the CC's have changed in value between K 3 and K 4 .

The failure of K 4 brings us back to K 3 . Now the choice of next bindings to be tried will be guided by [CCB). Either a (M,C) or a (C,C) will succeed. A more interesting case is the following .

* We shall use M for Missionaries, C for Cannibals, Fail for Failure, T for True, SUC for success, and F for False.

Now suppose that (Ml,Cl) are already on RBANK2. This would have caused the following series of successful cc evaluations:

All these cc-summaries would now be available at box 3 of Figure 2, since PROC would have been still active during the whole course of events.

After this, PROC will be reinvoked because REPEAT will have been still active. The new instances of PSS for boxes 3 and 4 will be created . These will be similar to the previously created instances. The BOAT is now at RBANK2. The CANDO clause, box 5, (statement TR2 in Table V) will now cause the BOAT to be brought back to RBANKl with a pilot, who in this case will have been the missionary Ml. This time, when a new pair of PEOPLE are picked from RSANKl, the system will already check for the satisfaction of the successful path of CC executions, depicted by the summaries (CCS4'), [CCSl'), [CCS2), (CCSl' '] . Picking another (M,C) will in this case. fail; (C ,C) will succeed in satisfying the cc-summaries. Thus, with anticipation the system will pick the right candidates likely to lead to success . From here on the availability of the cc-summaries, and the guidance provided by [CCB] will enable the system to always pick the right candidates. The following solution will be obtained:

Step (5) in the above solution is caused by box 14 in figure 2.

2.3.5. Summary

Thus, the DESIGNER provides the high level control structure necessary to pass on to the CHECKER the right CC's to be evaluated, and to the INSTANTIA­ TOR, the right model changes to be done. The DE­ SIGNER programs themselves are independent of the descriptive data structures used. Again the templates and INSTANTIATOR provide a desirable isolation. The PSS itself may be changed for different domains of discourse, or different problem~· In this sense, the templates and the rules of transformation, to­ gether with the PSS specialize the MDS to a given problem, or a given domain of discourse. The problem solving control structures are driven by the domain dependent data. The CHECKER, TP, DESIGNER, and IN­ STANTIATOR are all part of the MOS.

Most importantly there is a significant strat­ ification of knowledge in a domain, as seen by the system. Domain dependent knowledge is made available to the system as templates, as CC's or as TR's. The PSS templates play a particularyly important role. Depending upon how and where a given piece of domain dependent knowledge is specified the system uses it differently.

The relative isolation of the problem solving and model management pro~rams from the descri~tive data structures themselves, make the concept of MDS feasible. The facility to arbitrarily specify des­ criptive data structures as well as non-deterministic programs makes the system highly flexible and power­ ful. The CHECKER and INSTANTIATOR provide the basic foundation. These two systems are small systems (about 2K PDP-10 words for INSTANTIATOR and 3K for CHECKER), and the programs here can be made very efficient. These features give promise that the proposed system architecture could operate in the context of large data bases. By defining the tem­ plates carefully the MDS system can be specialized to operate efficiently in a given domain. The structure of MDS is described in the next section.

3. The Meta Description System

The block diagram of MDS is shown in Figure 3. In this figure DL(D), T(D), and K(D) are, respectively, the definitions of Descriptive Language, Templates and Knowledge (CC's and TR's) in a domain D. The LINGUIST, TEMPEST, and QUEST are, respectively, the subsystems that accept these definitions and create representations for them. The TEMPEST is now a working system (about 8k of PDP-10 words of compiled LISP 1.6 programs). The CHECKER and INSTANTIATOR are presently under construction.

The data in DL(D), T(D), and K(D) specialize the MDS for the domain. The rest of the block diagram is self explanatory.

4. Concluding Remarks

We have introduced the basic concepts of CI­ Systems and the MOS. The OI-Systems provide a basis for the definition of the concept of machine under­ standing in terms of models that a machine is capable of building in a domain, and the way the models are used. The understanding exhibited at the problem solving level of CHECKER is relatively simple under­ standing. A deeper level of understanding is exhibited in the kinds of problems that the Theorem Prover can solve (see [10]). At the level of DESIGNER the level of understanding is very sophisticated. Tne system is able to plan and build procedures to solve problems.

In this paper we have discussed only a part of the problem solving aspects of the system; the workings of the CHECKER and DESIGNER. The operation of the langu­ age processor will be discussed in a subsequent paper.

We are proposing the use of DL(D), T(D), and K(D) to transfer domain dependent descriptive knowledge to a computer. We have briefly indicated how such des­ criptive knowledge could be used to solve problems in a domain automatically.

The specification of DL(D), T(D) and K(D) in a domain will, of course, require a very good under­ standing of the concepts and problems in a domain. There are several domains where, at present, such understanding is available. The MDS provides a way of transfering this understanding to a computer. The study of a CIS for the MDS itself might throw light on the problem of making a computer build its own templates to suitably model and reorganize a known corpus of knowledge in a domain.

There is much work to be done to make the MDS a viable system. It is necessary to develop a working system first. We are presently involved in this task.

References:

• 1.) Fikes, Richard Earl, "REF-ARF: A System for Solving Problems Stated as Procedures," J. Art. Intel. 1(1) 1970.
• 2.) Fikes, Richard Earl, "A Heuristic Program for Solving Problems Stated as Nondeterministic Procedures," Doctoral Thesis, Carnegie-Mellon University, 1968.
• 3.) Derksen, J., Rulifson, J.F. and Waldinger, R.J., "The QA4 Language Applied to Robot Planning," AFIPS Conference Proceedings, Vol. 41, Part II FJCC 1972, pp. 1181-1187.
• 4.) Gibbons, Gregory Dean, "Beyond REF-ARF: Toward an Intelligent Processor for a Nondeterministic Programming Language," Doctoral Thesis, Carnegie­ Mellon University, 1973.
• 5.) Fikes, Richard Earl, Nilsson, Nils J., "STRIPS: A New Approach to the Application of Theorem Proving to Problem Solving," J. Art. Intel. 3(1) pp. 27-68, 1972.
• 6.) Fikes, R.E. , Hart, Nilsson, N.J. : "Learning and executing generalized Robot Plans", J. Art. Intel. 3(1972), 251-288.
• 7.) Hewitt, C., "Description and Theoretical Analysis (using schemata) of PLANNER: A Language for Proving Theorems and Manipulating Models in a Robot," Ph.D. Thesis, Dept. of Mathematics, M.I.T., Cambridge, Mass. 1972.
• 8.) Newell, A., Shaw, J.D., and Simon, H.A., "Report on a General Problem-Solving Program for a Computer," Information Processing: Proc. Intern!. Conf. Information Processing. p. 256-264, UNESCO, Paris. (Reprinted in Computers .. and · Automation, July 1959)
• 9.) Amarel, S., "On Representations of Problems of Reasoning About Actions," Machine Intelligence 3 D. Michie, ed., Edinburgh University Press, pp. 131-170. 1968.
• 10.) Srinivasan, C.V., "On the Organization and use of Knowledge in a Coherent Information System" RUCBM-TR19. Dept. of Computer Science, Rutgers University, New Brunswick, N.J. 08903.