Deductive Retrieval Mechanisms for State Description Models

Introduction

This paper describes some modeling facilities that have been developed as part of a large Com­ puter Based Consultant system (CBC) being designed and implemented at the SRI Artificial Intelligence Center. The CBC is intended to serve the role of an expert consultant to a human apprentice doing maintenance and repair operations on electromechan­ is an exampl e of such a device that has been used during the early stages of the project. A complete overview of the project is given elsewhere in this

ical devices. The air compressor shown in Figure 1 volume in Reference 1.

The model s that we are concerned about in this paper could be descriptions of any environment of interest at specific instances in time. Each such description is said to model a "state" of the envi­ ronment, and a state can be transformed into a new state by the occurrence of an event that alters the environment. For the CBC, these models describe the state of the workstation including the device, tools ; test equipment , etc., and the events are primarily maintenance and repair operations per­ formed by the apprentice.

Programming facilities for querying state de­ scription mode ls and for updating them to reflect the occurrence of an event are vital in many AI systems, particularly those that do question an­ swering and those that do automatic generation and execution monitoring of plans. Planners , for exam­ ple, use these models to simulate potential

Richard E. Fikes Stanford Research Institute Menlo Park, California 94025

operator (event) sequences and investigate their consequences.

One of the goals for the CBC project is to have the system synthesize plans for transforming a device from any arbitrary state of assembly or disassembly into any other such state. This planning capability is required for component re­ moval or replacement operations and, in general, whenever a collection of assembly and disassembly operations are needed to help accomplish a task. We will refer to this planning domain for examples throughout this paper.

The modeling mechanisms to be described here are basically extensions and modifications of fa­ cilities typically found in recent planning pro­ grams implemented in languages such as CONNIVER (Ref. 2), PLANNER (Ref. 3), and QA4 (Ref. 4). The need for such additional knowledge representation mechanisms is evident as AI projects continue to move in the direction of considering more complex task domains. The presentations here are meant to add an increment to our ability to design and build such large systems.

Expressions and States

Our modeling system is implemented as an ex­ tension of the QLISP programming language (Ref. 5). [Note : QLISP is a direct descendant of the QA4 language and was designed to maintain QA4 language features while eliminating the inefficiencies in­ troduced by the QA4 interpreter. It is a set of functions loadable into the INTERLISP (Ref. 6) system, and QLISP "statements" are basically calls on these LISP functions. Hence, the user can freely intermix QLISP and LISP code. The control features that were lost by eliminating the QA4 in­ terpreter are currently being restored by making use of new control facilities provided by the IN­ TERLISP system (Ref. 7). I Each state description model can be thought of as a set of QLISP expres­ sions, with each expression having a truth value associated with it. An expression typically is a statement of a relationship among entities in the task domain such as objects, concepts, or other relationships. For example, the expression (CON­ NECTED PUMP PLATFORM) is a statement that the pump is connected to the platform, and the expression (FASTENER (CONNECTION PUMP PLATFORM) BOLT:l) is a statement that BOLT: 1 is a fastener of the pump­ platform connection.

Although each QLISP expression has a LISP­ style property list associated with it, we us e these property lists in our models only for truth values and bookkeeping information. Therefore, instead of putting GREEN as the value of the prop­ erty COLOR on the property list of PUMP, we would create the expression (COLOR PUMP GREEN) and put TRUE as the value of the property TRUTHVALUE on its property list. This convention creates homog­ enous models and allows a pattern matching program to associatively retrieve any relationship in a model.

The QLISP context mechanism allows the system to build and manipulate a collection of state de­ scriptions without having to create and maintain a complete copy of each state. A "context tree" is maintained in which each node denotes a state. To represent the new state that is produced by the occurrence of an event in some state Si, the system creates a new node in the context tree as a direct descendent of the Si node. All informa­ tion in state Si that is not explicitly changed in the new state is assumed to also hold in the new state. That is, each state inherits model infor­ mation from the state that is its parent in the context tree.

Querying State Description Models

Truth Values

A state description model is a source of in­ formation about a particular situation, and its primary use is as a data base for answering que­ ries about the situation. Our modeling system in­ teracts with its users (both people and programs) as if QLISP expressions with truth values attached were the only representations being used, even though the option exists for storing information in other forms. Hence, all queries from outside the modeling system concern the truth value of ex­ pressions in some given state.

When answering a query about a particular ex­ pression in some given state, the system searches for a truth value. The search begins with the ex­ pression's property list for the given state. If the property TRUTHVALUE has no value on that prop­ erty list, the property list for the given state's parent (in the context tree) is checked. The search continues in this manner until a value is found or until all the states in the context are conside-red. If no value is found, the search re­ turns UNKNOWN as its result.

Since any expression can be stored as the value of property TRUTHVALUE, this retrieval mech­ anism allows use of an N-valued logic. For exam­ ple, one could have "fuzzy" truth values repre­ sented as integers from -100 to +100. For our models, we currently are using a )-valued logic that allows the system to distinguish expressions that a re "known trut'," "known falst·," or 11 have un­ known truth value" in any given state. This is the simplist logic that meets a modeling system~

need since state description models are inher­ ently incomplete, and it is important for the sys­ tem to be aware of what it doesn't know as well as what it does know.

Generators Instead of Backtracking

QLISP provides facilities for associalively retrieving expressions from the data base that match any given pattern, where a pattern is de­ fined to be an expression that may contain unbound variables. The QLISP statements for querying the data base use this pattern matching facility and are similar to the query statements found in PLANNER and QA4. They are designed to find a sin­ gle instance of a given pattern. To cause the pat­ tern matcher to continue its search and obtain another such instance, the user's program must re­ turn to the query statement via the language's backtracking mechanism (i.e., by "fa i 1 ing").

Using backtracking in this way to sequence through a class of expressions that all match a given pattern has severe limitations in that it ties the sequential production of each expression to the control structure of the user's program. ln particular, it requires that the same portion of the user's program be executed for each expres­ sion (namely, the statements immediately following the query statement). Also, since all the back­ trackable effects of that portion are being "un­ done" after each failure, it makes cumbersome the saving of results for each expression generated. Such a backtracking mechanism is best suited to a "generate-and-test" situation where the user de­ sires a single expression that not only passes the query statement's tests, but also passes addi­ tional tests included in the user's program.

We have adopted the CONNIVER solution to these limitations in our modeling system by pro­ viding functions that are generators of expres­ sions from the data base. For example, there is a generator version of the QLISP IS statement called GEN:IS that finds instances of a given pattern having truth value TRUE in a given state. Each time a generator function such as GEN:IS is called, it produces as many expressions as is con­ venient for it. These expressions are put on a "possibilities list" along with a "tag" that indi­ cates how the generator can be restarted when more expressions are requested, and this possibilities list is returned by the generator as its value.

If the function TRY:NEXT is called with a possibiJities list as an argument, it will remove the first expression from the list and return it as a value. lf the possibilities list contains no expressions, then TRY:NEXT attempts to produce n~w ones by using the tag to restart the generator. Since each call to TRY:NEXT can be made' from any­ where in the user's program, generators of this form successfully separate the production of a next data element from the processing that is done on each element.

Consider, for example, a set of queries con­ cerning which components are connected to the pump in sta te Si. They can be initialized as follows:

(SETQ PL (GEN :IS (CONNECTED PUMP--<:) Si)) .

Then whenever one of these components is needed, evaluation of (TRY:NEXT PL) will return a true in­ stance of the pattern (CONNECTED PUMP-~) and will set the value of the QLISP variable C to be the "found" componcn t.

We havl' imp lemcntcd progranuning facilities to support the writing and use of generator functions using INTERLISP FUNARG's. A FUNARG is a data ob­ ject that conceptually represents a copy of a funttion and a private data environment for that copy . .This FUNARG implementation allows the defi­ nition of a generator function to include a set of var.iables (i.e., a data environment) whose values will be saved and restored each time the generator is restart ed. These "own variables" allow the generator function to save pointers indicating where it is in its search for generatable items. The FUNARG is added to the possibilities list as the "tag" that TRY:NEXT uses to restart the gen­ erator. Included in the implementation are CONNIVER-style functions such as NOTE, AU-REVOIR, ADIEU, and TRY:NEXT, which make the definition and use of generators convenient and practical.

FUNARG's do not provide a complete co-routine (process ) facility because the control environment is not saved between calls, and therefore each re­ start necessarily returns control to the beginning of the function. Our experience with generators, however, has indicated that making available a FIRST:CALL? predicate function that can be called from inside a generator to distinguish initial calls from restarts r emoves essentially all of the hindrance caused by not having a saved control en­ vironment. Hence, this implementation of genera­ tors is simple and effective and can be made available in most LISP systems.

The Query Functions

We can now describe our model querying mech­ anism. Query functions are available called DEDUCE:ONE, DEDUCE:EACH, DEDUCE:ALL, REFUTE:ONE, REFUTE:EACH, and REFUTE:ALL. Each of these func­ tions takes a pattern and a state as arguments. The DEDUCE functions find instances of the pattern that are true in the given state, and the REFUTE functions find instances of the pattern that are false in the given state. The :ONE functions find only a single instance and are not restart­ able; the :EACH functions are generators and re­ turn possibilities lists; and the :ALL functions

return a list of all the findable instances.

Known truth values are usually not all explic­ itly stored in a model. Instead, the user typi­ cally provides derivation functions that compute them when they are needed. These functions may em­ body formal theorem proving strategies or simply be statements of implicational rules derived from the semantics of the task domain. They serve to extend each model in the sense that, from the calling program's point of view, the derived in­ stances of a pattern are indistinguishable from in­ stances actually found in the model.

Our query functions are similar to a PLANNER or QA4 GOAL statement in that they first use the pattern matcher to find suitable instances of the pattern in the data base and then, if more in­ stances are needed, they call user supplied func­ tions to attempt derivations of the desired in­ stances. These functions are assumed to be generators that produce derived instances of the pat tern.

For example, a deduction function in the CBC system finds and generates true instances of pat­ terns of the form (POSITIONED ·-x ·-Y) by using DEDUCE:EACH to find true instances of the pattern (ATTACHED $X $Y), since components that are ATTACHED are assumed to be POSITIONED. Also, a refutation function finds and generates false in­ stances of patterns of the form (POSITIONED ··X -Y) by using DEDUCE:EACH to find true instances of the pattern (REMOVED $X $Y), since components that are REMOVED are assumed to be not POSITIONED.

Such derivation functions are the user's pri­ mary means of expressing the semantic links among the relations occurring in the state description models. Also, they can provide an interface to in­ formation that is stored in representations other than QLISP expressions. That is, it may be much more convenient and efficient to store some infor­ mation in arrays, trees, or on disk files; deduce and refute actions serve as the access functions to these alternate data bases.

Storage and Retrieval of Action Functions

The first element of each nonatomic expres­ sion in the model is assumed to be the name of a relation (or a QLISP variable that is to be bound to a relation). Therefore, the DEDUCE and REFUTE functions can use relation names as an index to de­ termine which derivation functions should be called. Accordingly, we associate with each rela­ tion two lists of derivation functions that can de­ rive instances of patterns that begin with the re­ lation. One list contains the "deduce actions" used by the three forms of DEDUCE and the other contains the "refute actions" used by the three forms of REFUTE.

This simple indexing technique is used as an alternative to "pattern directed invocation" of the actions (which is available in QLlSP).

Pattern directed invocation, where a pattern is as­ sociated with each action function and a pattern matcher determines which actions are applicable whenever a query is made, is a useful technique in many situations, but its power and importance should be looked at realistically. In this situa­ tion the indexing scheme seems preferable even though it has the disadvantages that an action's local variables do not automatically get bound to elements of the pattern and additional tests may be needed in an action to determine if it is appli­ cable to the pattern.

However, the indexing scheme has the following advantages: (1) the use of the actions is made more efficient by significantly reducing the need for pattern matching; (2) each list of deduce and refute actions is typically quite short so that the user can easily determine an appropriate ordering of each list and similarly can determine where on the list a new action should be inserted; (3) and, finally, we have found that associating semantic information directly with each relation is a con­ venient way to conceptualize and localize the se­ mantic information in the system. With this orga­ nization, the set of action functions associated with a relation specify essentially all the seman­ tic information that the system knows about that relation.

Saving Derived Results

Overview

When a model query causes derivations to be attempted, we want the results of those deriva­ tions to be stored and retained in succeeding states as long as they remain valid. In this way the system achieves the maximum benefit from deri­ vations and minimizes unnecessary rederivations. It is a simple matter to store a result in the state where a derivation is done, but more care must be taken if the result is to be made avail­ able in other states. In this section we will de­ scribe a set of mechanisms designed to provide max­ imum retention of derived information with a mini­ mum of bookkeeping overhead.

A model query is an attempt to find true (or false) instances of a given pattern. Each time such an instance is determined, our DEDUCE and REFUTE query functions save the derived result by assigning a truth value to the instance (i.e., put it as the value of TRUTHVALUE on the expression's property list) so that the value will not have to be rederived if it is needed again. For example, if a deduce action for ASSEMBLED determines that the pump is assembled by querying the model about each of the pump's components, then the expression (ASSEMBLED PUMP) will be assigned a truth value of TRUE.

If a query is one of the :ALL forms, or if it is an :EACH form and the generation continues until all derivable instances of the pattern are pro­ duced, or if the query pattern contains no unbound variables (and therefore has only one possible in­ stance), then the system also records the fact that all instances of the pattern have been derived. Then, if the same query is repeated, the system will know that the action functions cannot find any new instances and can therefore prevent ill-fated attempts at rederivation. For example, if during a query all the components that are positioned with respect to the pump have been found as instances of the pattern (POSITIONED PUMP ~c), then when that in­ formation is requested in a later query, derivation functions such as the one that looks for components attached to the pump will not be recalled.

These "set completeness indicators" are also frequently useful to indicate the case where there are no derivable instances of a pattern. For exam­ ple, if all derivation attempts are unsuccessful at determining whether the pump is assembled, then the set of derived instances is empty and marked as com­ plete.

Saving and Maintaining Derived Instances

Our algorithms for maintaining these saved de­ rived results in succeeding states depend on avail­ ability of the "support" for each derivation. The "support" for a derived instance is defined to be those expressions from the model that are used as axioms in constructing the derivation. For exam­ ple, if an action function queries the model for the locations of two objects and concludes that one of the objects is above the other, then the loca­ tions of the two objects form the support set for the result. Actually, since any model query may re­ turn a derived result, the support set for the "above" result would be the union of the support sets for the two location expressions.

The user supplied deduce and refute actions are responsible for computing and storing support for each derived instance that they find. In al­ most all cases this is an easy task. For example, if an action embodies the implication "X implies Y," then the action can simply fetch the support for X and attach it to Y. GET:SUPPORT and PUT:SUPPORT functions are provided for performing these support set manipulations.

Functions are also provided for deduce and re­ fute actions to call when they have derived a truth value for an instance of the query pattern and have determined the support for that derivation. These functions add the expression to the current possi­ bilities list (remember that action functions are generators), set the truth value (i .e., TRUTHVALUE) of the instance, put the support set on the in­ stanee's property list, and put a pointer to the in­ stance on the property list of each member of the support set. Use of these functions to "note" de­ rived results implies that derived truth values can be found by the pattern matcher's search through the data base at the beginning of a model query, and each expression that supports a derivation will have on its property list a pointer to the ex­ pressions that it supports.

A derived result remains valid in succeeding states as long as its support remains valid. We therefore have the system do the required mainte­ nance on derived instances in new states by in­ cluding with the standard model updating functions (described below) the following facility. When­ ever an expression with a known truth value has its truth value changed during a model update, the truth value of each of the expressions that it sup­ ports is set to UNKNOWN in the new state. The truth values of these "supportees" may not in fact have changed in the new state, but the derivations that made the truth values known are no longer valid. Hence, if a model query in the new state needs to know one of the deleted truth values, a new derivation must be attempted. For example, if (ATTACHED PUMP P~TFORM) is the support for (POSITIONED PUMP PLATFORM) and a detach pump from platform action causes a new state to be created, then the truth value of (POSITIONED PUMP PLATFORM) will be set to "unknown," the pump may still be in position on the platform, but the justification for the earlier conclusion about the pump's posi­ tion is no longer valid.

The mechanism we have described thus far is effective, easy to use, and efficient for saving and maintaining derived truth values of expres­ sions that are instances of a query pattern. Each derived instance is assigned a truth value, the support pointers are established, and when a state transition invalidates the derivation the derived truth value is deleted.

I Saving and Maintaining Complete Sets

Consider now the maintenance of the "complete­ ness" indicators that are attached to patterns when all derivable instances have been found. Specifying the support for such indicators poses some subtle problems, because the completeness de­ pends not only on the validity of the derived in­ stances but also on whether any other instances are derivable. This latter consideration implies that if any change should occur in a succeeding state that could possibly allow some action func­ tion to derive a new instance, then the complete­ ness indicator should be removed from the pattern in the new state. For example, during the deter­ mination of all the components that are positioned with respect to the pump, some deduce action may have looked for components that are attached to the pump. Therefore, any succeeding state pro­ duced by an action that attaches a component to the pump will cause the removal of the complete­ ness indicator from the derived positionings. Each der i,ved instance wi 11 still be va 1 id in the new state; only the completeness of the set is in doubt.

We have approached this problem of the valid­ ity of completeness indicators by keeping a record of all the model queries made during a derivation. If any of these queries will produce different re­ sults in a new state (i.e., a different set of de­ rived instances), then the action functions that made the original derivation may behave differ­ ently in the new state and in particular may de ­ rive a different set of instances. Therefore , to maintain the completeness indicators we record during a modei query (i.e., a call on one of the DEDUCE or REFUTE functions) all the other model queries that occur.

Consider a query to find instances of a pat­ tern PO during which are executed queries Ql, Q2, ·.. , Qn to find instances of patterns Pl, P2, .·. , Pn. The system records for each query Ql whether it is a deduction or a refutation and the pattern Pi associated with it. If all derivable instances of PO are found, then PO is given a com­ pleteness indicator, the set of derived instances is put on its property list, the queries Ql, .·. , Qn are put on "state transition test lists," and a pointer to pattern PO is put on the property list of each of the patterns Pl, ... , Pn.

Whenever an expression with a known truth value is having its truth value changed during a state transition, a test is made to determine if it matches the pattern of any query on the appro­ priate state transition test list. If a match oc­ curs, the completeness indicators of the patterns pointed to by the matching pattern are removed since this state transition may affect the com­ pleteness of those derivations. This entire mech­ anism is built into the DEDUCE, REFUTE, and model updating functions, so that the user who writes ac­ tion functions need not be aware of it.

In Sulllllary

To sulllllarize, our model querying mechanisms provide for the automatic derivation of truth values for pattern instances when they are not ex­ plicitly stored in the model, for the saving of all such derived results so that similar later que­ ries will not reinitiate the derivation functions, and for the maintenance of such saved results. Also, an important side effect of these mechanisms is that each derived instance has the support for its derivations computed and stored with it. Such support information has many uses because it indi­ cates precisely which statements in the state model a particular precondition, subgoal, or ac­ tion depends on (Ref. 8).

State Transitions

Updating Functions

The models of state changing operators that a system works with must contain sufficient informa­ tion about the effects of each operator so that they can he simulated and a description produced of the expected resulting state. As in most planning systems, we are assuming that the appli­ cation of an operator in some state SO is modeled by producing a new state Sl that is conceptually an updated copy of SO (i.e., Sl is a direct descen­ dent of SO in the QLISP context tree). The ef­ fects of the operator are indicated by asserting, denying, and deleting expressions in the new state Sl.

In our modeling system we provide the fol­ lowing set of model updating statements:

(SIM:ASSERT <expression · . <State>), (SIM:DENY <expression > <State>), and (SIM:DELETE <:pattern"> <State >).

SIM:ASSERT (SIM:DENY) changes the truth value of the given expression to TRUE (FALSE) in the given state. SIM:DELETE changes the truth value of all expressions that match the given pattern to UNKNOWN in the given state. These statements also call a set of user supplied functions (like PLANNER antecedent theorems) that typically make additional changes in the new model that are di­ rect results of the assertion, denial, or deletion being done. These user supplied functions play an important role in simplifying operator models in that they allow the user to express in one place side effects of particular assertions, denials, or deletions that always occur no matter what opera­ tor does them. In this way, these side effects do not have to be repeated in each operator that

causes them to occur.

As in the case of the DEDUCE and REFUTE func­ tions (and for similar reasons), we have elected to store the user supplied updating functions on each relation's property list. Hence, a relation can have a list of ASSERT:ACTIONS, DENY:ACTIONS, and DELETE:ACTIONS. These lists indicate how a model updating operation should proceed for an ex­ pression having the given relation as its first element.

The standard model updating functions (as found in QA4, PLANNER, QLISP, CONNIVER, etc.) ap­ ply user supplied functions only after the expres­ sion's truth value has been changed. Often it would be convenient to have user supplied func­ tions applied before the expression's truth value is changed as well as after. For example, if a re­ lation like LOCATION has certain uniqueness prop­ erties, then any assertion of an expression con­ taining that relation (such as (LOCATION BOLT:l 3 4 5)) can automatically be preceeded by a denial (such as (SIM:DENY (LOCATION BOLT:l --LOC))). By allowing the programmer to specify such an auto­ matic d('nial in an assert "pre-action," we remove the necessity for specifying the denial each time such an assertion is done.

We provide for both "pre-actions" and "pos t­ actions" during model updating by giving the pro­ grammer the option of specifying when the truth value of the expression will be changed. This is done by including an asterisk (*) in the action list. The asterisk indicates when in the course of applying the actions that the expression's truth value is to be changed . Hence, all actions preceeding the asterisk are "pre-actions" and all actions following the asterisk are "post-actions."

When the updating functions encounter the as­ terisk in the action list, they also perform the maintenance operations on derived results. This means that if the expression had a known truth value and that value is being changed, then all the expression's supportees must be deleted. Also, the state transition test lists are checked to de­ termine if any set completeness indicators should be removed.

Model Updating Using Deduce and Refute Actions

The information in many deduce and refute ac­ tions can also be used to determine the secondary effects of assertions and denials. We would like for the system to make use of this information during model updating so that the user does not have to duplicate it in updating functions. For example, if the user has written a deduce action that embodies the rule "X implies Y," then we do not want him to also have to write a deny action for Y that removes from the model any truth values that could be used to derive X. The information necessary to do these changes at the appropriate

time is included in the original deduce action.

Consider a consistency checking procedure that would make Ufe of deduce and refute actions and that could be applied as a standard part of model updating. We can describe this procedure by indicating how it would work for denials. The truth value of the expression being denied would be set to UNKNOWN and an attempt would be made to deduce the expression. If this attempt produces a successful derivation, then the new state contains support for the truth of the expression even though it is being denied. The inconsistency can be eliminated by removing the support for the deri­ vation. If the support set has exactly one expres­ sion in it, then that expression can have its truth value reversed. (This is the "X implies Y" case where denying Y is implying that X should also be denied.) The reversed truth value would be stored as a derived result with the original expression that is being denied (Y) as its support. When the support set contains more than one expres­ sion, we know that at least one of the expressions must have its truth value reversed, but we do not know which one(s). Therefore, the best we can do is set to UNKNOWN the truth values of all the sup­ port expressions.

If the system knows which relations are changeable by events and which ones are true in all states, then it can decrease unnecessary deletions by removing the unchangeable expressions from the support set before considering deletions or a truth value reversal. After the support for the deriva­ tion ha s been r emoved, a new derivation is at· tempted and the process is repeated until no new

derivation can be found.

This upd:lt i ng procedure docs not guarant ee consistt·ncy in the new statt· nor docs it prevent l.1ter changes to tht· state from introducing new in­ consistencies. llowever, it docs automatically take care of many model updating details and it removes all existing inconsistencies in the state that are discoverable by the system's deductive machinery. If the system cannot derive the facts from which an inconsistency follows, then the inconsistency is ir­ relevant and can safely be ignored.

Obviously, there are situations in which this procedure initiates computationally expensive deri­ vations and causes many unnecessary deletions. lienee, it must be selectively applied. We have put the entire process under user control by allowing individual specification of which deduce and refute actions are employed to determine truth value dele­ tions -and reversals during model updating. This is done by providing a function UPDATE:WITH that takes a deduce or refute action and an expression as ar­ guments, and is used to specify an assert or deny action.

Nott· th:lt using an "X implies Y" deduce ac­ tion as a deny action for Y is not the same as writing a deny action for Y that simply denies X. The difference is that in the latter case X would be deni ed each time Y is denied, and the deny ac­ tions associated with X would then trigger off other assertions, denials, and del e tions. Such a process could clutter up the model with many irrel­ evant implications of the denial of Y. However, in the former case where the deduce action is used as the deny action for Y, no changes are made in the model if X cannot be derived; and if X can be de­ rived, only the supporters of the derivation are changed. This means that only those truth values that are actually inconsistent with the denial of Y arc changed; no irrelevant implications are stored.

The Re lations AND, OR, and NOT

AND, OR, and NOT are "built into" our modeling sys tem in the sense that deduce, refute, assert, deny, and delete actions have been written for each of them. Whenever possible, conjunctions, disjunc­ tions, and negations are decomposed into more primi­ tive forms by the action functions. For example, the assert action for AND also asserts each of the conjuncts, and the deduce action for NOT strips off the NOT from the que ry pattern and attempts to re­ fute the remaining pattern.

The refute actions for AND and OR translate the query into a call on DEDUCE:EACH by using the

rules:

((NOT Xl) AND ··· AND (NOT Xn)) implies (NOT (Xl OR ··· OR Xn), and ((NOT Xl) OR OR (NOT Xn)) implies (NOT (Xl AND ·.. AND Xn) ·

The deduce actions for AND and OR have an impor­ tant role to play in that ~1ey are the overlords of the derivations of each conjunct or disjunct. They could each be expanded into full problem solving executives that would make use of co­ routine facilities to explore alternative deriva­ tions in parallel and semantic information to de­ termine the order in which conjuncts or disjuncts are considered. We have experimented with only un­ sophisticated versions of these actions, but the important point to note is that the query mecha­ nism gives those actions control over the deriva­ tion so that the option is there to expand them

when needed.

Summary

We have described a set of programming facil­ ities for building, maintaining, and querying state description models. These facilities are useful in systems such as planners, question an­ swerers, and simulators. They allow the storage and retrieval of statements with true, false, and unknown truth values, and provide a programming en­ vironment that allows derivation rules embodying the semantics of a task domain to be easily addt·d as functions to the system. These rules can also be used to assist in modeling the effects of an operator that creates a new state. Facilities. are provided to save the results of these derivation functions, and to delete the results in new states where the derivations are no longer valid. Finally, the semantics of conjunctions, disjunctions, and negations are provided as a part of the system.

Acknowledgments

Many people at the SRI AI Center have contrib­ uted to the development of this system. I wish to especially thank Marty Rattner, Earl Sacerdoti, and Georgia Sutherland for their important help. The work reported herein was sponsored by the Advanced Research Projects Agency of the Department of De­ fense under Contract DAHC04-72-C-008 with the U.S. Army Research Office.