[Indigo]<KRL>document>match!1

With the concepts given so far, we are now in a position to informally define what is going on in the basic description manipulation processes. As in any computational system, there are three data structure primitives -- adding new data (CONS), finding existing data (CAR/CDR), and comparing structures (EQ). In describing KRL-1 we will often refer at an abstract level these three processes, rather than using the names of the specific functions which implement them. This is primarily because for each basic process, there is a collection of different function names, corresponding to different paramaterizations of what is to be done.

The informal specification does not make clear just how the input parameters are specified, or just how the result is returned. In fact, for each basic process there are a number of variants on just what is given initially and what kind of object you want back. The simplest analogy for this is with the CLISP iterative statetments, in which the arguments given can be selected from a variety of combinations, and the nature of the output depends, for example, on whether it contains JOIN, EVERY, or simply DO. Section ??? contains a detailed description of the alternatives.

The process of finding involves two primary inputs: an initial description of the object being sought, and a result description describing what we are after. These descriptions are in two different domains. The initial description is in the domain being modelled -- of people, dogs, biting, etc. The result description is in the domain of descriptions -- of the forms manipulated by a KRL system. Thus a typical example would be:

In this case, we are trying to answer the question "Who did Fido bite?" The question provides the initial description, and the result description asserts that we will not be happy with the answer unless it is a primary description (in our case, the one in the self slot for the unit for Sally). The great majority of cases in which we are doing finding involve a result description which is either A PrimaryDescription, A PointerCoreference, or one of the forms described below for dealing with sets and sequences of these. A PointerCoreference is essentially what our old Seek looked for -- a description of the object being sought as coreferent to an existing unit or primitive LISP entity.

The initial description contains all of the information necessary to begin the search. In many cases it will contain a MemberOf descriptor, if we are searching for the object in a known sequence or set. Thus, to find a woman in a list of people which was represented by the unit JuryList, we would have the initial description.

Note: the process can also be terminated by running out of resources, or by limitations set up on the kinds of inference and activation steps it is allowed to do. Section ??? describes the form and role of the process description which specifies these limits.

Of course, step 2a had better be guided by something other than blind search, or we will never find anything. In the examples above, there was always a specific instance unit (like Fido, or JuryList) which should be activated. In the case of JuryList we can make a further set of choices based on the fact that it is a sequence and that the initial description refers to its members. This leads to activating the units for each of its members in turn.

There is an important difference between the process as described here, and the process of Seeking in KRL-0. In KRL-0, the signal table was used to fully specify what could be done at any point. In KRL-1 we have separated the specification of allowable inferences from the specification of heuristics as to which ones to try when. It is still necessary to provide guidance, in order for the sytem to make the choice of iterating down the list, rather than going off and activating the prototype for Woman. But the guidance is within a precisely defined framework of activation and inference, rather than being an arbitrary set of manipulations based on specific combinations of descriptors.

The interpreter has built into it a number of generally useful heuristics (e.g. the one which would lead it to activate in turn all the members of a set or sequence when the initial decription includes a MemberOf description.) To these, the user can add any others, using event networks (the replacement for signal tables in KRL-1).

Reasoning in KRL-0 was centered around a "matcher" which used description comparison as a framework for organizing reasoning processes. This is equally true in KRL-1. The abstract process of matching involves two descriptions, called the pattern and datum, and two parameters, one indicating whether the pattern is to be treated as referring to an already known entity or not, and the other indicating whether we are looking for a known match in which there is pre-existing information which can verify it, or a possible match in which there is no information indicating that the datum could not match the pattern. The simplest form of output is an indication of whether the match was successful.

There are many elaborations on just how the match is set up, how it will run, and what kinds of results it will return. We have tried to deal with many of the issues of resource limitation, partial results, and binding which were discussed in the Overview but not implemented in any KRL-0 programs. Section ?? goes into these in detail.

The choices of the other parameters are determined by the presuppositions intended and the answer desired. If a known match is specified, then the comparison will succeed only if information identifying Fido as a biter of Sally can be found. This would be the case for most of the variations on the data base given above. If a possible match is specified, then all that is necessary is that no contradictory information can be found. Given a knowledge base corresponding to only the initial units for Dot, Bite, etc., the match would be successful. On the other hand, if we were asked whether Sally could possibly match the same pattern, the answer would be negative, since a biter must be an instance of Animal, and Sally is a Person.

This isn’t quite the full story, since the knowledge base as given does not specify that Animal and Person are mutually exclusive categories. In order for the match to work as just described, that information would have to be explicitly included.

The specification of the pattern as referring or descriptive provides information to the interpreter about what directions to search. If it is marked as referring, the system uses heuristics based on the assumption that there is already an existing record of an entity which fits the description (in this case, someone who bit Sally), and that the major form of reasoning is to find the primary description (using the process described above for finding) of this entity, and check whether it is coreferential with the datum. If the pattern is marked as descriptive, then the reasoning is based on going through the pattern’s meaning piece by piece (each belief) and seeing that it applies to the datum.

In the simple example used here, it would be somewhat problematical to specify that the pattern was referring, since the question would then carry the presupposition that one and only one thing had bitten Sally. In a specific context (see below) or a carefully controlled knowledge base, this might be reasonable. In fact, for many patterns, this is not a problem since they are based on units (like Person) for which only a single mapping can exist for a given instance. It is reasonable (in fact natural) to view the pattern as referring in the comparison:

As with the other processes, there are often many different forms which are based on the same semantic inferences. The difference lies in the heuristics which will be applied in deciding what should be tried. The match just above is semantically equivalent to:

But the heuristics are different. The first example would lead to placing a high priority on activing the unit for Female to get a look at its self description, while the second would place a higher priority on activating the unit for Sally. The two would eventually come to the same answer given sufficient resources and freedom to do all kinds of inferences and activations, but might well differ in cases where resources are limited and types of reasoning are restricted. In general, they would not provide conflicting answers, but one would provide an answer while the other indicated "Unknown"

3) Create an entity for the referent of the pattern, and add to the active context all of the description of it given by the pattern, with all of the beliefs and entities specially labelled as hypothetical. Include a hypothetical belief that this entity is coreferent with the datum

4) Search though the space of possible derived concept sets by doing inferences and activations. The hypotherical beliefs can be used in these inferences, but any belief derived from a set of beliefs including a hypothetical is itself marked as hypothetical.

The concept set includes a set of beliefs, not derived from hypothetical beliefs, which include a belief for each one in the initial set from the pattern, with the datum entity substituted for the pattern entity, in which case the result is Yes

There are differences between the processes for known and possible match not only in choosing the final answer, but also in the set of heuristics used in deciding what inferences and activations to try. In the case of possible match, the emphasis is on those things likely to produce contradictions, such as establishing that two coreferent entities either have different primary descriptions, or are instances in mappings from prototypes of conflicting categories. In the case of known match, the process is directed towards trying to infer non-hypothetical versions of the specific beliefs specified in the pattern. This will often involve looking at the units associated with prototype entities for mappings appearing in the pattern, looking for cross-linkages between slots (i.e. the description in one slot relates it to the contents of others) and for explicit procedural attachment telling how to identify the entities mapped from specific slots (see section?? below).

1) A quick consistency check was done to see if the new description was obviously incompatible with something already in the structure to which it was being added. In KRL-0 this consisted only of looking for multiple units appearing in a single description. A number of more general checks, both for coreference and category, are possible. This was used for a style of programming in which new things are asserted which are really hypothetical, and a resulting inconsistency indicates that the hypothesis is not valid.

In the framework presented above for KRL-1, these jobs belong in two different conceptual arenas. The consistency checking and triggering are essentially "semantic" in that they deal primarily with the set of entities and mappings implied by the meaning of the description, rather than with the syntactic forms or data structures in which it is couched. The permanent modification and trapping are more closely tied to the actual description forms, and the data structure operations which deal with those forms.

The interaction between these two kinds of processes was ill-specified in KRL-0. It was not clear what would happen if a Describe triggered an action, which in turn led to a contradiction at some later point. It was also not clear how triggering should interact with further specification. Since the code for triggering dealt with explicit descriptor forms and their associated prototype units, it did not extend easily to handle cases where a trigger associated with a unit high up in in the further-specification hierarchy needed to be activated when a perspective (or new slot filler) based on one of it descendants in the hierarchy was added to a description. This was one reason why the whole further specification mechanism was under-defined and difficult to use reasonably. In KRL-1, the meanings and forms are dealt with separately, making it possible to treat the operations in a more consistent way.

Consistency checking is a specialized case of description comparision, as described above. It is a form of "possible" match, in which only some of the possible inferences are to be tried. We have already discussed the basic notions involved, and will describe the details below when giving the syntax for the various functions which add descriptions. The triggering of demons, both triggers and traps, is also discussed below in a general section on servants and demons. The part of the process which is specific to this class of operations is the modification of description structures to incorporate new descriptions.

The operation of adding a description involves two central arguments (with parameters and process description as usual), specifying a new description and a structural position where the new description is to be added. The structural position indicates a data structure already in the knowledge base, which can be interpreted as a description whose referent is the same as the intended referent of the new description. The argument is a description of a data structure, not a description of a thing in the world domain of the new desctiption. This is similar to the status of the result description in the finding process described above. It is a description of the description which we want to find. In this case, the structural psosition is a description of the place (in the permanent structures) where we want to put the new information. We have a great deal of generality in specifying the structural position, but there are three standard cases which should cover almost all of the descriptions normally added (for reasons, see below). These are handled by three built-in functionals associated with the units for basic system objects such as units, slots, and descriptions. They are:

The SelfOf form indicates that the new description is to be added to the description in the self slot of the indicated unit. The SlotOf form indicates that the description to be modified is the top-level description in the indicated slot of the indicated unit. Note that SelfOf(x) is equivalent to SlotOf(x, self) but is abbreviated because it is the more common form. Finally, PrimaryFor calls for a finding process which begins with the given intial description, finds a primary description which represents the same thing (as described above), then adds the new description structure to that primary description.

Note that this does not commit us as to whether a biter can take part in more than one Bite (as pointed out above, many relations represented by mappings have a one-one nature not exibited by Biting). The procedure for adding new information needs to look at the unit for Bite to see whether it is declared as unique for a given biter. If not, the two new descriptions would be separate:

In neither case would the unit for Sally be changed. Of course, we could also do additions in which the structural position was SelfOf(Sally). There is a common case, in which we would want our knowledge that Fido bit a woman to be applied to the description of whoever it was he bit. In this case, we would do an addition with:

The process would first involve finding a primary description, using the initial description The bitten from a Bite with biter = Fido. As described in the section above on finding, this would use the information in the Fido unit and eventually return a primary description -- in this case, the self descripton from the unit for Sally (since the default is for top level slot descriptions to be primary). The modification would then be done to that unit, leaving the Fido unit unchanged, and resulting in:

Since KRL is completely self-describable, the user has the power to carry out this kind of direct intervention in the data structures to any degree necessary. It should be clear, however, that this is a dangerous venture, since there are a number of reasons (see discussions on footnotes, embedded implicit and descriptors, worlds and contingencies, etc.) why the data structures may not have the detailed form which would be expected in the simple case, even though they express a semantically equivalent description. In such cases, the addition done in the standard way (giving the structural position with SelfOf) will work correctly, while the more direct specification of the data structures will fail.

The following section is intended to give a general picture of the capabilities of the interpreter for the basic description operations. It is written in a top-down style, indicating the range of conceptual possibilities without giving details of implementation. In reading it, it is important to remember that it was written with the most complicated allowable cases in mind. It provides a conceptual framework for understanding what the formal properties of the operations are, but in the great majority of calls on the basic operations the mechanism is short-circuited:

* There is a compiler for the same operations (Match, Seek, Describe, etc.) which converts them into functions using immediate data accesses. For the great majority of calls, the compiled version would run without ever producing the large amounts of data structure and function calling implicit in the description below.

* Even for cases which cannot be fully compiled, there will be many combinations of parameters which limit the kinds of search and types of output so that specialized functions can be used, which again do not set up the full structure described below. The goal in building the system is to make the results of the compiled and specialized versions be exactly the same as those of the corresponding full-scale interpreted running of the same operation. Since the interpreted version can be specified clearly and formally, the user does not need to know the quirks of implementation.

Earlier, the basic description operations were described as using heuristic search, operating in a problem space whose states are belief sets (collections of mapping and coreference beliefs) and whose primitive operations are inference and activation. The interpreter is built directly on this notion, but is not based the standard techniques for deduction or problem solving. It is based on a style of goal motivated search which integrates goal directed and data directed styles of reasoning. It is likely that many KRL programs will eventually be organized in the same style, and can make use of many of the facilities built into the interpreter.

The reason that standard techniques cannot be successfully applied is that the problem space is loosely coupled. <Do Newell and Simon have terminology for this distinction??> In a tightly coupled space, there is a close correspondence between goals to be achieved and methods which will achieve them. The proto typical example is the robot problem solver, which has a method for "PutOn" whose predictable result is that one block will be on top of another. Most of the problems which have been attacked with GPS-like and Planner-like systems fall into this class. In tightly coupled spaces, goal-directed top-down exploration (either parallel or with backtracking) is feasible. The number of "plausible moves" at any point is small enough that the tree to be explored is of manageable size for the depth of solution desired. Data-driven computation (demons) are used only for noticing special conditions and doing bookkeeping.

A loosely coupled problem space is one in which an operation may end up achieving any of a number of goals, in a way which could not be predicted without doing the operation. A prototypical heuristic search problem which falls closer to this end is chess playing. A program will look into a move because it satisfies one goal (or some general criterion), and discover that it has a number of other effects, some desireable and others undesireable. In fact it has often been pointed out that a major weakness of most chess programs is the lack of top-down goal-directed activity.

In a loosely coupled space, the work done in exploring one branch can often used along another branch. Since there is a many-many mapping between goals and methods, a path taken in an effort to satisfy one subgoal may end up satisfying other subgoals. In most to-down problem solving schemes, it is difficult to take advantage of this property. The system will have scheduled other operations (especially if it includes parallelism) to meet the goals which were serendipitously satisfied along the other path, and it takes a fair amount of bookkeeping to notice at the appropriate time that somebody else has done the work. In the case where the intended goal was not met, but others were as side effects, the path is usually abandoned totally. It is difficult to keep it around as a sub-plan for meeting the goals it does achieve, while finding another way of achieving its intended goal.

Many of the difficulties in sharing goals and achievements in traditional domains such as robot planning and game playing arise from the fact that the problem space is <I need a term for this>. Having done an operation, the world has changed in ways which may turn out to be incompatible with achieving the eventual goal. Therefore, the problem solver must choose one specific path, although in its search it may explore others. It cannot keep any results which were achieved along a path if that path required an operation which was rejected for an alternative.

Theorem provers, on the other hand, operate in a monotonic problem space. The primitive operation is making a deduction, and the states are sets of formulae which have been deduced. Having made any particular deductive step, the theorem prover may not be any closer to its eventual goal, but it has also not done anything which has to be "undone" in order to meet that goal. It can therefore operate in a much more data-directed way, taking advantage of noticing combinations of formulae which look likely to lead to something, without having to integrate them into a top-down goal structure. Instead of searching among alternatives for a "correct" path through the space, the problem solver wanders along a single path, hoping to eventually stumble across a state in which the goal is met.

The KRL-0 matcher was essentially top-down. Given two descriptions to compare, it had a set of methods to try, based on the types of the two descriptions. This structure was not well suited to the type of problem space. In general, the operations available (e.g. use the description in the self slot of a unit which is pointed to) will potentially satisfy many different goals. The work being done along different branches (e.g. matching all of the different descriptors in the pattern) shared a large number of common operations. The number of different strategies which might lead to eventually satisfying a given goal was tremendous. As a result, only a few of the possible combinations were dealt with, and these in a generally ad hoc manner.

In order to understand the full operation of the matcher, we will begin with the simplest version, and extend piece by piece. In the simplest version, the process can be thought of as "aligning" the two structures given as its arguments -- a pattern and a datum:

For each descriptor at the top level of the pattern structure, a corresponding descriptor must be found at the top level of the datum structure(i.e. one of the same type and with identical top-level sub-structure, such as the prototype of a map-descriptor or pointer of a coreference). If the pattern descriptor has internal structure (e.g. a map-descriptor with filler pairs, or an enumeration with descriptions of the elements) the process is done recursively, trying to align the corresponding parts of the pattern and datum descriptors. The process succeeds if every piece of the pattern has been successfully matched.

There are a number of directions in which the idea of alignment has been extended. The extensions are partly orthogonal, but there are a number of interactions between them which will be discussed in detail below. As a quick overview of what is to come, the following list may be useful.

binding: The pattern can specify through meta-descriptions that some of its anchors and descriptors correspond to names which act as a kind of matcher variable. As a side-effect of the match, each of those variables is bound to a data object corresponding to the datum anchor or descriptor aligned with the anchor or descriptor to which it was attached.

structure-changing actions: The pattern can specify through meta-descriptions that some of the corresponding datum anchors and descriptors are to have modifications done to them. After the match has succeeded and all bindings made, all of these actions are carried out. They may in turn trigger other actions recursively.

match tables: As in KRL-0, the alignment process is parameterized by providing a signal table which has responses used to control the different decisions made during the process. This table is a specific argument to the individual call to the matcher. It can abe built up out of standard tables (which provide a complete set of responses) and "fragments" each of which deal with one specific aspect. For example, what we have called "can match" is a combination of a match table which limits resources somehow (e.g. the SimpleMatchST) along with a response to the ValueForAlign signal which returns a successful binding set if the match was terminated for resource reasons, rather than finding a conflict.

LISP value returned: Rather than having a standard value returned, there is a signal which is probed in the match table before returning and its value used as the value to return. For each of the standard match tables there is a specific response, and there are match table fragments for standard variations on these.

following links for the datum: We think of the matcher as operating on a datum structure, but the structure used need not actually appear initially. As the Alignment proceeds, descriptors in the datum are used to derive further descriptors, subject to the limitations imposed by the particular match table. This is done by keeping a record of a set of links along with any datum description being aligned. The link specifies the place to go for further descriptors, and the context (world and substitution instance) needed for interpreting what is found there. Descriptors found by following these links are treated as through they had been in the original datum for purposes of finding information, but not for making stuctual changes.

conflict checking -- posts and categories: The category hierarchy is used to keep track of the categories associated with pattern anchors, and with the datum anchors (including those from following links) to which they are aligned. Checks are made to be sure these are consistent. Also, checks are made to discover when an anchor is described as referring to two distinct objects.

structure building for describing: Describing is treated almost exactly like matching, in that the pattern structure is aligned with the datum structure as far as possible with no actions being taken. The difference (which is specified by using the DescribeSF fragment in the match table -- see below) is that when doing a describe, when the alignment is stopped (due to resources, depth, etc.) and if values for all of the bindings have been found, then all those parts of the pattern which were not aligned with datum elements which actually appeared in the datum anchor are copied into the appropriate places (causing triggering, etc.)

resource limitation: There is a signal given for each of those aligner operations which could be thought of as using resources. The signal table can use these to modify resource counts and decide whether to continue. A binding is provided at the top level of the call to the matcher for an arbitrary description structure which the user wants to maintain for keeping track of things.

subgoal structures for satisfying the pattern: The internal structure of the aligner is based on a notion of goals and subgoals in a straightforward way. The operation includes setting up goals, probing a signal associated with a specific way of trying to achieve them, and going ahead if the signal says OK. The user is free to prevent methods from being tried (by responding SKIP), or to set up additional subgoal structures as part of the signal response. The user has access to the full data structure environment in doing his, so the goal structure manipulations can be as clever as the user wants to make them.

triggering of procedural attachment: There are triggers and traps (e.g. ToMatch, ToEnumerate) which are associated with specific goals set up in alignment (e.g. aligning a map descriptor, binding the elements of a set). These are probed in the same way as the signals, except that they are indexed by a specific unit and slot to which they apply, and are only probed for goals involving that slot. They have the same power to manipulate the goal structure as do the signal responses.

defaults: When descriptors are derived by a link from a prototype, and they were marked as Default in the prototype, there is a signal UsingDefault which checks to see if they should be used at all. If so, the only time their origin is noted is if a conflict occurs in doing a Describe, in which case they are ignored. Note: this needs to be implemented.

The data structures organized around a goal tree, a both-way-linked tree of Goal datatype instances. In general, there is a goal for each anchor and descriptor (recursively) in the pattern, and this provides the basic tree structure. The goal tree contains both AND and OR nodes. Each Goal contains information about what needs to be done, what the operands are, the links which have been found and those which have been tried, and the results which have been found at that node or propagated up the goal tree. A simplified version of the process is:

3. This goal goes through a SETUP phase, during which its internal structure (e.g. the descriptors in the pattern anchor) is used to create subgoals, and simple successes and failures are discovered. This is done recursively on the subgoals which get created. At the end of this phase, either the entire goal has succeeded or failed, or there remains a tree of all those goals which were set up and could not be immediately resolved.

4. A control loop is entered which cycles through the active goals until the top-level goal is satisfied, or resource bounds are reached. On the first cycle for a goal, the descriptors in its datum are used to find results or potential links (e.g. a coreference). If a goal goes through this first cycle without finding results, then the servants associated with that goal type are invoked before any links are followed. On subsequent cycles all of the links added in the previous cycle are followed, potentially finding results or new links. If on any cycle nothing new happens for any goal, this is signalled.

5. If the alignment was successful, all of the actions are taken. Data structures representing bindings and actions are passed up the tree and combined as the individual goals which produce them succeed. Note that no actions happen until the top level goal has succeeded. There is also a mechanism for passing partial results.