[Indigo]<KRL>document>rep-worlds!2

KRL-0 had a descriptor called a contingency which was used when a description applied only in a specific world. There was a "world filter" mechanism associated with the matcher (and the Seek and Describe functions) which enabled it to make certain contingencies "transparent" when operating. A description appearing inside a contingency whose world matched the current world was treated as though it appeared in place of the contingency. If a new description were to be added, and the current world was specified, the actual descriptor which was added was an embedding of the specified descriptor in a contingency for that world. The details of how worlds were dealt with in adding new descriptions were quite complex. For example, we might be adding a description with the current world being a world X, into a descriptor which was a contingency whose world is also X, or a sub or super-world of X. The interactions were never clearly worked out, and the mechanism was used sparingly, although sometimes to good effect, as in the cryptarithmetic program, which used hypothetical worlds to try out guesses.

In KRL-1, we have tried to provide a clear semantics for multiple worlds, so the operations of "filtering" and "embedding" descriptors can be described in terms of the semantic interpretation of description forms, and the use of inference rules. The main points are:

Most AI systems do not distinguish between these different uses of "worlds" or "context". In KRL, most of the mechanisms are similar for the two, but they are kept conceptually distinct. Discussion of concept systems is postponed to the end of this section, but many of the specific details of how worlds are handled are relevant to them.

In describing the fundamental semantic notions of KRL-1 in section 1.1, we simplified things by ignoring worlds. In fact, worlds are a central part of our understanding of representation <again, see Brian’s thesis for a deeper discussion>. They enter into the semantics in several ways:

* Some of the entities in any concept system are worlds: There is one fixed world (which might be called "the world of my thoughts") which must exist, and any number of others. These could include, for example, "the real world", "the world of mathematical objects", "the world of objects on this table as they were before the pyramid was put onto the block", or "the world as it would have been if Napoleon had been Italian".

* There are prototypes for describing worlds and describing the relationships between them: The relationships include things such as: "X is a world which changes over time," "X is a sub-world of Y", "X is a specific time-point which follows Z in a changing world that is Y", etc.

* There is a prototype for specifying a relationship of "ExistsIn" between an entity and a world: Existence is expressed as a relationship between entities (one of which is a world), rather than being specially treated by quantifiers. There are many implications of this for the logical properties of the system, but this isn’t the place to discuss them.

* Every belief (mapping, coreference, or implication) has a world as part of its specification: This was glossed over in section 1.1, where beliefs were expressed simply in terms of the mapping, coreference, or implication. In fact, the examples in Section 1 are technically incorrect in that they do not mention that every single one of the beliefs included a world (which was the same for all of them) and that the inference rules all include clauses that the beliefs they operate on must share a common world, and that the beliefs they produce share it as well. Inference rules for cutting across worlds are discussed below.

Header paragraph needed here on the general issues of how worlds are related to the syntax -- implicit vs. explicit, reasoning in worlds vs. talking about worlds. Currently I have a bunch of units here to provide the names, with explanations following later in the section.

# WorldStructure↑1
1: HasFunctional(backdrop, BackdropOf, self)
HasFunctional(MemberOf alternativeWorlds, PossibleWorldOf, self)
HasFunctional(self, UniverseFor, MemberOf alternativeWorlds)
HasFunctional(backdrop, IncludedWorld, MemberOf alternativeWorlds)
HasFunctional(MemberOf alternativeWorlds, IncludesWorld, backdrop)
self: A World
alternativeWorlds: SetOf(A World)
backdrop: A World

# TemporalWorldStructure↑1
1: HasFunctional(MemberOf states, StateOf, self)
HasFunctional(MemberOf events, EventOf, self)
self:↑2
backdrop:↑2 A World
2: FurtherSpecified(WorldStructure)
states:↑3 SetOf(A World)
3: FurtherSpecifiedSlot(WorldStructure, ’alternativeWorlds)
events: SetOf(An Event)

# Event↑1
1: HasFunctional(resultingState, Successor, precedingState, event)
HasFunctional(precedingState, Predecessor, resultingState, event)
self: MemberOf(EventsOf(My universe))
universe: A TemporalWorldStructure
precedingState: MemberOf(StatesOf(My universe))
resultingState: MemberOf(StatesOf(My universe))

# ThingInWorld↑1
1: HasFunctional(world, InWhichExists, thing)
HasFunctional(thing, ExistsIn, world)
HasFunctional(world, InWhich, thing, Quoted descriptionForm)
HasFunctional(thing, InWorld, world, Quoted descriptionForm)
Comment ("There is some funny stuff going on here concerning the entity vs. thing distinction, since this whole unit is at the meta-level. Do we need another functional argType Meta to do the meta-shifting of arguments?")
thing: A Thing
world: A World
descriptionForm: A QuotedDescriptionForm
beliefs: SetOf(A Belief with world = My world)
MeaningOf(A Description with
form = My descriptionForm
referent = My thing
world = My world)

This description uses the functional InWorld, to be explained later. It would appear in a knowledge base which includes an imaginary world in which Fido bites some woman. Neither the woman nor the biting need exist in the real world. The meaning of the description The biter from a Bite with bitten = A Woman includes specifying two entities other than the one for Fido (the bitten thing, and the event), a mapping relating them to Fido, and a further mapping relating the entity for the bitten thing to the prototype for Woman. Each form which appears as part of this description is in a world scope provided by the InWorld descriptor. In this case, for example, the descriptor A Woman, even though it does not itself include an InWorld functional, is interpreted as indicating a mapping whose world is ImaginaryWorld23. Note that the meaning of the entire description includes the beliefs that Fido, the woman, and the biting event all exist in ImaginaryWorld23.

The meaning of a descriptor form is formally determined both by its detailed contents and by the world scope in which it appears. This meaning includes both the mappings and coreference beliefs which are explicitly stated by the descriptor forms, and beliefs of existence of the entities in the associated worlds. Details of these meanings are given in section ?? <full specification of the semantics of the different descriptor forms -- yet to be written>

There are many issues to be discussed here: Inheritance of world stuff from prototypes to instances, the default that top level slot descriptions inherit the world of the unit, and the unit is defaulted to existing in the mental world (how does this interact with inheritance?): the question of whether the world scope should be thought of as specifying one world or a set of worlds: details of the InWorld functional, and explanation of why it is important to think of it containing a quoted description: general problem of world scope for quoted description forms:

What corresponds to the old idea of filters? Is it possible to get by just using InWorld forms for the arguments or does there need to be something more global? Can we operate in multiple worlds and multiple description systems at the same time? can concept systems be done in direct simulation mode at all?:

If worlds were completely unrelated to one another, all that would be necessary in reasoning about them would be a global "switch" which indicated which world was being talked about. This could just as well be done by having separate knoowledge bases, and is of course not the main use of worlds. KRL-0 did not go much beyond this level of "every world is its own world". It had a notation for world-dependent (contingent) descriptions, but it did not embody any particular notion of how worlds were related to one another, leaving this entirely up to the user. There was a primitive relationship of SubWorld which could hold between two worlds, and the user could provide a LISP predicate which decided whether it held between two worlds. The filtering mechanisms would accept descriptions from any subworld of the current world when matching.

In KRL-1, we have provided a much more specific set of facilities for dealing with worlds. There are a small set of standard relationships between worlds which are pre-defined in the system, and are treated specially in inference rules built in to the interpreter. The user still has the option of using the underlying notion of worlds (as described in the previous section) and providing explicit implications for all of the inferences which involve relating knowledge about two worlds, but we believe that the standardized mechanisms will serve for most purposes. These mechanisms can be thought of as a series of layers, beginning with the basic semantics given above, and working up to progressively more specialized facilities. The layers are:

The simplest kind of relationship between two worlds is for one world to serve as a backdrop for a second (call it the scene). Everything which exists in the backdrop world exists in the scene, and every belief about the backdrop world holds in the scene. Of course, the converse isn’t true. The associated inference rule is obvious: For any belief in the backdrop world, infer a new belief which is identical to it, but in the scene world. There are two different ways in which more than two worlds can fit into this picture:

In more usual terminology, we can think of the set of scenes as "alternative worlds" within the context of a single backdrop. It is also useful to have a way of talking about the structure which represents the collection of all the alternatives. Thus, for example, there can be entities existing in one or more scenes which do not exist in all scenes (and therefore not in the backdrop). For a given set of alternative worlds, we can say that all of these entities exist in the "world structure" corresponding to that set. In KRL-1 notation, we have:

At this level, there are no inference rules which relate alternative worlds to one other. The only rules are for hierarchical inheritance. A typical use would be for representing the effects of alternative choices in solving a cryptarithmetic problem. A world represents a partial assignment of values to letters (i.e. the world in which A is 3 and B is 6 is a different world from the one in which A is 3 and B has not been assigned). A world structure represents a set of alternative guesses for assignments of values to a letter. The backdrop for that structure is the world corresponding to a set of assignments to other letters. This backdrop world might in turn have been produced by a guess (i.e. it is a member of the alternative worlds for a prior world structure, with its own backdrop). The inheritance is straightforward -- beliefs about the problem (e.g. the fact that a particular value must be grater than 5) based on the set of assignments in the backdrop world must remain true in the world in which the new assignment is made.

Something on notation is neeeded here. Also a note on the difference between thinking of alternative worlds appearing in a data structure, and being implicit in a control structure (with forward pointer to discussion on reasoning below). CONNIVER (data structure) vs. MicroPlanner (control structure)

Built on top of the notions of alternative worlds and backdrops, there is a fruther set of inference mechanisms used for representing and reasoning about sequences of actions and states. The basic structure is a further specification of the general WorldStructure defined above, called a temporal world structure. A temporal world structure consists of:

# TemporalWorldStructure↑1
1: HasFunctional(MemberOf states, StateOf, self)
HasFunctional(MemberOf events, EventOf, self)
self:↑2
backdrop:↑2 A World
2: FurtherSpecified(WorldStructure)
states:↑3 SetOf(A World)
3: FurtherSpecifiedSlot(WorldSturcture, ’alternativeWorlds)
events: SetOf(An Event)

note -- we need to have the notation to say that the states and events exist in the world which is the TemporalWorldStructure. Also something more needs to be said on the philosophy of partial state descriptions, and state as an abstraction in the domain space, rather than as a set of knowledge about the situation in that state.

Abstractly, we can think of any two states as connected by some event (which may be a compound sequence of more primitive events) and any event as connecting two states. The actual entities in the system need not include all of the implied states and events, but only a subset about which useful information is known. The set of states and events are not constrained to form a line -- they form a partial ordering structure, in which the event connecting two states can be unknown, the relative ordering of two states can be unknown, etc. There can even be states and events in the sets for which no relationship is known to any others in either set.

As with the general world structure, there is an inference rule allowing anything believed in the backdrop to be inferred in any of the states. In addition, there is a set of standard mechanisms for stating inference rules which hold between states connected by an event. These give the user a set of alternative representation choices, since we believe that different choices will be appropriate for different knowledge bases (and for different sets of beliefs in a single knowledge base). The following section describes those mechanisms used for doing reasoning about temporal sequences without simulating them. The one after that describes the mechanisms for procedural simulation.

In a system for reasoning about temporal worlds, the inference rules are an answer to the question: "Which of the beliefs in a preceding state can I infer to still be valid in the state following some event?" In the AI literature, this has been referred to as the "frame problem" <see McCarthy, ref???>. The simplest possible answer is to have no built in inference rules which relate worlds. The only way a belief from a preceding state can be inferred in a successor state is if the user has provided a frame axiom -- an implication of the form: If you have a belief of form X in a state, and there is a successor relationship connecting that state to a second state via an event described by Y, then you can infer a corresponding belief in the second state. The axiom explicitly describes both the initial belief and the connecting event. The system then uses this implication just as it would use any other user-provided implication.

This scheme is adequate in a formal sense, but impractical as a way of organizing reasoning systems. There need to be specialized mechanisms for allowing states to inherit facts from prevous states without going through a full-scale deduction whose length is determined by the number of primitive events between them.

Many AI languages and systems (such as the planner-like languages) take a very different approach to reasoning about with time sequences, based on procedural inference. The states are organized into a tree structured hierarchy, linked by primitive events. There is an inference rule (usually built into the system in an efficient form) which corresponds to the rule for inheriting from backdrops to scenes. Of course, it can’t quite be the same rule, since the esssence of the situation is that the world is changing. If everything true at one moment remained true at the next moment, nothing would be happening. The rule instead is: Any belief which holds in the backdrop world (situation preceding the action) holds in the scene world (situation following the action) unless it directly contradicts beliefs known to hold in the scene world.

In KRL-1, we have not taken this as the primary approach. The underlying mechanisms for reasoning about temporal sequences are much closer to the notion of frame axioms, with some important differences discussed below. There do exist mechanisms for doing the kind of procedural modelling which is the basis for reasoning in planner-like systems, but they are thought of as specializations of a more general set of mechanisms for representing states and events. In order to explain this way of thinking, we will first review some features of the procedural approach. In particular, there is a fundamental difficulty hidden in the the phrases "directly contradicts" and "known to hold". There are two basic forms of the procedural approach:

Add-Delete lists: Associated with each action in the temporal world, there are three lists, called the preconditions, the add list and the delete list. Each of these describes a set of beliefs (usually in the form of simple propositions with variables correspondings to the arguments to the action). The inference rule can be stated in three parts:

This method works only in systems which maintain a minimal description of the world being modelled. Each action has to directly specify every fact which could be in the system which might be changed by the action. Thus, if we allowed relationships like RightOf or Touching to be expressed explicitly in a set of beliefs about a physical world, every action which moved things would have to include in its add and delete lists all the possible changes to these relationships. Note that the limitation is not on the complexity of the world being modelled, but on the complexity of the explicit knowledge which the system maintains. A very complex world can be modelled if everything which needs to be known about it can be kept in a minimal canonical form. This is sometimes the case with formal worlds (e.g. in mathematics or highly schematized plannning worlds), but is not the case for common-sense worlds.

* Updating with demon-driven forward inferences: Reasoning systems based on "Planner-like" languages use a procedual alternative to the notion of add-delete lists. Associated with each action there is a procedure, which includes actions for updating the set of beliefs. In the framework given here, they can be thought of as explicit commands to infer beliefs in the successor world. Some of these represented added beliefs (the Assertions), while others represent negations of beliefs in the predecessor world (the Erasures). In fact, in some systems (e.g. CONNIVER) the implementation directly reflects this.

The inference rule given above (Any belief which holds in the world preceding the action also holds in the world which is the successor of the action unless it directly contradicts beliefs known to hold in the successor world) is then applicable. However, the procedural formulation allows important extensions to the definition of the two key phrases:

* "...known to hold...": In the simple add-delete method, the only new beliefs known to hold in the successor worlds are the instatiations of elements on the add list. In a procedural system, there can be demons associated with the inferring of new information, which propagate its consequences in the form of other inferred beliefs. In the procedural framework, the set of beliefs "known to hold" can be defined as: The specific additions and deletions, plus all of the other additions and deletions caused by all of the forward inferencing triggered by them.

* "...directly contradicts...": In the simple add-delete method, a belief directly contradicts another only if they have the identical form, and one is marked true and the other false. There is no notion of quantification, so Fido doesn’t bite. and Fido bit Sally do not directly contradict. In a procedural system, a belief in the successor world can be said to "directly contradict" a belief in the predecssor world: Whenever the successor belief would be the first item found in the deductive search carried out by the system, and would terminate that search. This is far from the usual notion of contradiction, but achieves the desired result.

In the simple cases this procedural contradiction (or, perhaps better, precedence) is identical to the rule for add-delete lists. If the form (assertion) is found in the successor world, it prevents the inference based on finding the matching (possibly negated) form in the predecessor world. However, there are other useful cases. If in the predecessor world, we have x is At y, and in the successor world we have x is At z, then for some searches (e.g. in answer to the question "Where is X?") the new information will simply mask the old information. If the predecessor world supports a general belief that "All dogs bite" and the procedure associated with an action (such as giving Fido tranquilizers) includes asserting that in the successor world "Fido doesn’t bite", then in searching for an anwswer to "Does Fido bite", the specific information would take precedence over the general statement.

Systems based on procedural inference rules have been used successfuly in a number of applications. They have some important properties which we want to include in KRL systems. However, they suffer from a number of serious shortcomings, as has often been pointed out <see, for example the Pat Hayes paper -- ref???>. This is not the appropriate place for pursuing the arguments, but the following main points are important to understanding the KRL-1 mechanisms described below:

* They still depend on the programmer to provide explicit updating: In the simple add-delete method, each action had to specify all of the beliefs which could change. In the demon-driven procedural method, the changes can be the result of propagating forward inferences, but there is an equally strict requirement that the programmer must include a set of forward inference procedures which reach every belief which could be asserted, and which could be changed by an action. In practice, this leads to an arbitrary division in designing the knowledge base base between those relations which can be asserted (and whose updating therefore needs to be considered in specifying actions), and those which can be derived through backward chaining inferences, but will never be asserted directly.

* The inference rules are hard to understand: In order to know whether a specific belief from the preceding world will be inherited in the successor world, it is necessary to know the details of the reasoning process. In some cases, this allows some useful rules. For example, an enumeration procedure can be used by the system for finding facts to answer a given question. As one example, it might systematically first take more specific facts (with constants in place of variables), progressing to those which are less specific. Within this, it might order facts at the same degree of specificity by first considering the predicate, then the first argument, etc. Knowing the details of this procedure, the knowledge base designer can choose clever encodings which will make it possible to do natural forms of reasoning, such as recognizing exceptions to general rules, or giving priority to more recent information. Such reasoning heuristics are cleasrly important for AI systems. However by using the process as the underlying definition of the semantics of inference, such systems make it difficult to change the form of the stored knowledge, or the details of program operation without causing unwanted changes to the deductive rules of the system.

* Reasoning about time sequences can only be done by simulating the sequence: One of the major defects in a procedurally based system is that it confuses the notions of reasoning about sequences of actions and simulating sequences of actions. It is impossible use such a system in a straightforward way to answer the question "If Bobby is at the store and he goes to his house, is he then at the store?" In a simple add-delete list system, the reasoning for a single operation is simple. The delete list states explicitly that when X goes from Y to Z, X is not at Y in the resulting world. However, if a series of primitive actions is involved, it is necessary to build up the entire add/delete set for the sequence.

In a system which uses demon-driven inference to extend the notion of "known to hold", there is no way to know what demons would be triggered, without actually setting up the imagined situation and running them. Further, in setting it up we have to consider all of the alternatives for unspecified aspects. There may be demons whose actions depend on decisions which cannot be made on the basis of the facts given about the situation. This implies in turn, that (without setting up a structure to simulate all possible alternatives), the resulting updates cannot be trusted to refelect the true facts about the successor situation.

As a result of this limitation, the alternative world mechanisms provided by procedural systems have not been used in a direct way to reason about situations which involve actions, except for those where it could do a full simulation. In areas like robotics, for example, they are used only for idealized robots which can completely control their world, rather than realistic ones which have to plan in a context of incomplete information. Programs which have tried to do reasoning about actions <e.g. McDermott’s TOPLE, Sussman’s HACKER> incorporate ornate structures on top of the underlying mechanisms.

Returning to our original formulation of the problem, we need a way to represent states and events in a way which gives us control over the answer to: "What beliefs can be assumed true of a successor state on the basis of appearing in a preceding state?". The KRL-1 mechanism is in some sense a combination of the frame-axiom approach and the procedural approach. The two approaches differ in the default assumption about the completeness of the reasoning. The frame-axiom approach can be paraphrased: "Don’t assume it holds in the successor state unless you can explicitly prove that it is preserved by the action." The pure procedural approach is: "Do assume it holds in the successor state unless you have explicitly produced a contradiction in the course of carrying out the procedure for getting to that state".

This difference is one instance of the fundamental difference between a formal logic and a procedural reasoning system. In a formal logic, the only good formula is a true formula. In a procedural reasoning system, there is a strong attempt to avoid believing falsities, but there are also steps which allow beliefs to be added as a result of a failure to disprove them, without a corresponding success at proving them. <I believe this distinction has deep theoretical importance for a general understanding of thought, logic, the universe, etc. etc., but this is not the place....>. From this perspective, the rule for inferring beliefs across states in standard procedural systems is an extreme in one direction. It says not only "Assume it true if you can’t show that it’s false", but "Assume it true if you haven’t already showed that it’s false."

In KRL-1, a belief can be associated with any number of frame implications, each of which specifies a testing procedure. The rule for deciding whether a belief still holds is "Assume it true if it passes all of the tests". These tests can be given for a world structure as a whole, for specific states, for specific beliefs, or for classes of beliefs (e.g. mappings with a particular prototype). Each testing procedure is a form <we need to work out the details on this> which has as possible arguments: the belief (with its associated world); another world being tested, which is a state in the same world structure; and an event connecting the two states.

At first glance, these tests are like frame axioms. A test states some conditions which must be met in order to carry the belief from a predecessor state to the successor. The difference is that it is procedural. It does not state a set of logical conditions whose validity proves that the belief still holds, but gives a procedure to be run. In some cases, the success of that procedure might reflect the success of a proof, but in other cases it might reflect the inability to find a counter-proof, or even just the inability to find an immediate contradiction.

It is important to distinguish between a frame implication (which says whether an belief which held in the predecessor state an be trusted), and a description which allows a valid belief to be derived in the successor state. The ability to recognize that a belief from a previous state is no longer necessarily valid is not the same as the ability to update it. If the frame implication test fails, it does not mean that the negation of the predecessor belief holds. It simply means that the inheritance of beliefs from state to state cannot be used to justify believing it. In this case, the system could try to derive the belief "from scratch", inferring it from other beliefs which hold in the successor state.

Given this basic facility, it is possible to construct reasoning methods which are anywhere along the spectrum. At the frame-axiom end, each testing procedure calls for a full proof. At the procedural end, the testing procedure corresponds to the process for looking up assertions in a tree structured context, as described above. To do an add/delete system, the procedure would chain through the series of adds and deletes.

It is also possible to use frame implications to test explicit dependencies <see McDermott’s rings, or Susssman and Stallman’s dependency driven backtracking>. An individual description can be labelled (using a meta-description) as depending on another description which held in its world. The frame implication can say "If all of the facts I depend on are true in the new world, then I’m true". In fact, a more sophisticated form of dependency can be used, in which the programmer chooses a set of things which a particular mapping is likely to depend on. These are described generically in the frame implication, which has the form: If the instantiations of the following facts are identical in the predecessor state and the successor state, then assume that I’m true in the successor state. <need example -- I believe this is an idea worth pushing, and maybe some more text is called for here>.

* Frame implications do not need to handle backdrop beliefs: In KRL there are separate mechanisms for inheriting backdrop beliefs (which are the things assumed constant) and frame-inherited beliefs (things which could have but did not change since a previous temporary state). The choice of what to consider unchangeable (backdrop) is up the knowledge base builder, and can differ for different subworlds. It can be manipulated so that the frame implication mechanism does not bear the burden of checking the great majority of beliefs in any reasoning process. This in turn makes it feasible to use more sophisticated (and therefore costly) procedural tests.

* Frame implications can describe the linking event in a general way: A frame implication is not necessarily associated with a primitive operation in the changing world (as is the case with add-delete lists or demon updates). For example, a frame implication could say that the information concerning the location of a block was still valid if "the connecting event could be viewed as a sequence of events none of which involved objects in its quadrant of the table". The user could provide tests of this sort (and the associated descriptions of the actual events) to let the system do "rough" reasoning, followed by more precise checks when necessary.

* Frame implications can be associated with worlds as a whole, prototypes (in several ways -- see below) or individual descriptions: This is a lot of flexibility, if we can figure out how to take advantage of it. Again, the idea is that you can have a quick 90 per cent solution and handle the hard cases with a more complete but more expensive procedure.

* Frame implications are heuristic: It is possible to let the system run with a set of frame implications which simply don’t cover all the possible details (the potato in the tail-pipe), and sometimes say that a belief still holds in a world where it really doesn’t. If this can be integrated with facilities for going back and changing mistaken descriptions, it should make it possible to do interesting kinds of schematic planning (a la Sacerdoti). The ability to attach specific dependencies in the footnotes should contribute to being able to unwind mistakes.

Reviewing the different examples which we have come up with over the years, there seem to be three different methods of representing facts which are true in some worlds, but not others. These can be labelled: Changing value, changing viewpoint, and changing entity set. We will illustrate them in a simplified BLOCKS world in which every block has a color (which does not change) and is supported by some single block, which changes over time as things are moved around. There is some state in the world structure (labelled S1) in which Block1 is supported by Block2.

Changing value: We could have a unit for Block with a slot for its supporter which is labelled as a changing value. For any instance of Block, there is an entity which is its color, and another entity which is its supporter. That supporter will be coreferential with different specific blocks in different states of the world structure:

Changing viewpoint: We could have a unit for Sitter which is a prototype for objects which sit on something (their supporter). In this case, we could say that a particular mapping with Sitter as its prototype and Block1 as its instance is a belief in one state, but not another.

Changing entity set: We could have a unit for SupportRelation which is a prototype for a relationship between objects. The fact that one block supports another in a given state is reflected by the existence in that state of an instance of Support. A single such instance could exist in several states, while not existing in others.

Each of these three methods makes some types of reasoning more direct. The changing value method provides a way of talking about the abstract entity which is "the value of the slot" without talking about the value in any specific state. In conjunction with compiling, it provides the most direct and efficient way of keeping track of changing beliefs. The changing entity set method (the third) provides the most direct way of talking about the relationship itself. Since there is an instance of the relationship, descriptions can be added to it (in the domain, not at the meta-level) giving information, for example, about when it began, what event ended it, what other relationships were true as a result of it, etc. The changing viewpoint method forces all of this kind of information to the meta-level (as information about beliefs), but is more efficient in not generating new instances for the relationships.

A frame implication appears in the KRL-1 structure as a footnote, which is a functional using one of the functional names: MapAppliesIf, ValueSameIf, DescriptionAppliesIf, and BeliefHoldsIf. The argument in each ase is a LISP expression which uses the variable EVENT freely. This will be bound to a description of a system event (see section on interfacing LISP expressions with system events) based on:

# FrameImplicationTest
worldStructure: A TemporalWorldStructure
predecessor: A World
StateOf(My worldStructure)
successor: A World
StateOf(My worldStructure)
event: An Event with
precedingState = My predecessor
resultingState = My successor
EventOf(My worldStructure)

It is necessary to attach the frame implications in a different place in the structure for each of the three methods above for representing beliefs about facts which change. These are in addition to general implications which can be associated with the world as a whole (using BeliefHoldsIf), and specific ones associated with individual descriptors in the instance (using DescriptionHoldsIf). In updating any one belief, it is carried forward to the new state if it passes all of the associated tests. There can be a general filter, and more specific ones for particular units and slots. The mechanisms for providing the implications are:

* For changing values: A description associated with the prototype entity for the slot (which exists in the scenario world), attached via a ValueSameIf footnote to the slot. It can be viewed as saying (if the test is passed): If this prototype entity is coreferential with an entity existing in the predecessor world, then it is coreferential with that same entity in the successor world.

* For changing viewpoints: A description associated with the prototype entity for the unit, attached via a MapAppliesIf footnote to the unit. It says: If a mapping exists with this prototype in the predecessor world, then one exists with the same instances in the successor. This carries with it the fact that the associated entity exists in the successor

* For changing entity sets: A description associated with the prototype entity for the relation unit, attached via a MapAppliesIf footnote to the unit. It says: If a mapping exists with this prototype in the predecessor world, then a corresponding mapping with the same relation instance exists in the successor. This carries with it the fact that the entity for that relation instance also exists in the successor

The semantics of multiple worlds has been described so far as operating in a knowledge base where each belief is part of a data structure which explicitly identifies its world. The entire sequence of states is expressed, and the reasoning process is in no way linked to following a succession of steps related to the succession of states in the world. This is the most general facility, and is for cases where the ability to explicitly deal with several alternative worlds is important.

A large and useful subclass of representation problems can be dealt with under the assumption that it is only necessary for the system to be able to reason about a "current" world, keeping it updated as things change. The memory of past states and events is not needed, or can be kept in only a schematized form. This class includes most of the domains in which procedural updating has been used (e.g. most of the BLOCKS world programs, including SHRDLU). The goal in KRL-1 has been to make the efficiency of this approach compatible with the completeness and clear semantics of the explicit-world approach in which each frame implications need to be used to determine that a belief holds across an event.

There are three steps of simplification, with some reasoning power given up at each step, in exchange for a gain in storage or processing efficiency. They are integrated in a style which allows a knowledge base to contain a mixture of all three, with different parts of the knowledge handled differently.

* Linear sequences and the notion of a current world: The first step is to add a current world to a temporal world structure. At any given time, the system is operating with one of the states in the alternative world set designated as the current world. There is a mechanism <should this be special, or just triggers set of in Describe??> which allows an event to be described as the "next event" in the world. As a result, a new state is created, added to the state set, described as the result of the designated event happening in the previous current state, and designated as the new current state. This all that is done at this level. All beliefs are still labelled explicilty with the states in which they hold, and any inferences to be done about the new state must be done using frame implications. However, since all state-to-state transitions correspond to single events, and all states in the state sets must be linked by a chain of these, the frame implications can be written in a simpler way.

* Replacement of descriptors: There are two major reasons for using a notion of "current world". One (see the next paragraph) is to avoid having to do the reasoning which is called for by frame implications each time a belief is to be used in a successor state. The other is to save storage, by storing only the information relevant to the current state, rather than keeping the entire history of the world. In order to facilitate this space saving, a temporal world structure which has a current world can be declared as "unhistorical". The result is:

This means that the only record of previous states is that of beliefs which no longer hold, and that once a belief has been used in a state, further uses will not needed to do the frame implication testing, since the descriptor will have been replaced with a current one. On the other hand, each belief is still marked explicitly with the last state in which it was shown to be valid, and this allows sophisticated frame implication tests to be used.

It is not necessary to give up all use of frame implications in order to gain the efficiency of demon-directed updating. In any case where the set of changed beliefs is small compared to the number of old beliefs which remain valid and will be used, it is advantageous to actually do some updating when the event occurs. This can be done selectively by having a set of demons and a no-op frame implication test associated with those parts of the knowledge structure which will be updated explictly by demons. (for example the set of mappings giving the basic locations of objects in a block world). These beliefs will then be inherited without complex procesing. All other beliefs can be given full-fledged frame implication tests which check to see if they are still valid.

* "current world" as a description in long-term structures: The final step is to give up the explicit use of frame implications, and assume that the programmer will assume the burden of updating all facts consistently. If a temporal world structure with a current world is designated "self-updating", then:

* Associated with the "next event" description, the knowledge base builder must provide a set of demons which are responsible for updating all places in the knowledge base where outmoded information exists. This updating uses a form of Describe which replaces the contents of the old descriptors with the information valid for the current state. This may include simply removing an old descriptor.

This solution is more or less equivalent to the standard procedural solution (without backtracking). It is useful, for example, when the knowledge base reflects a situation taking place as the system is running. It will be used extensively in the mechanisms which describe the internal structures and processes of the KRL system itself.

Note that if multi-processing is used, there are timing problems in an updating system, since the procedures which were supposed to do the updating might be waiting on an agenda when a process that needs their results is run. There are several solutions, the most straightforward of which is to organize the agenda so that other processes are "relatively continuous" with respect to updating -- i.e. all of the updating happens in a flash before anyone can get confused.

# ConceptSystem↑1
1: HasFunctional(MemberOf beliefs, BeliefOf, self)
HasFunctional(MemberOf entities, EntityOf, self)
HasFunctional(MemberOf descriptions, DescriptionIn, self)
entities: SetOf(An Entity)
beliefs: SetOf(A Belief)
descriptions: SetOf(A Description with
system = My self
referent = MemberOf(My entities)
meaning = SubsetOf(My beliefs))

# EntityInConceptSystem↑1
1: HasFunctional(system, Describing, thing, Quoted descriptionForm)
HasFunctional(thing, DescribedBy, system, Quoted descriptionForm)
HasFunctional(formInSystem, Translation, system, Quoted descriptionForm)
HasFunctional(entityInSystem, CorrespondingEntity, system, thing)
Comment ("This still has the meta-shift problem. It also needs to specify the world scoping in the place where the functionals appears. THis wasn’t necessary for the multiple world forms, since they throw that information away. really do believe that all this indirection is necessary to keep interactions between multiple worlds and multiple belief systems straight. This unit provides the way to link entities to the things within a system itself. The stuff on things, entities, etc. needs straightening out")
thing: A Thing
system: A ConceptSystem
descriptionForm: A QuotedDescriptionForm
entityInSystem: EntityOf(My system)
formInSystem: A DescriptionForm with system = My system
worldInSystem: EntityOf(My system)
DescribedBy(My system, A World)
beliefs: SetOf(BeliefOf(My system))
The meaning from a Description with
system = My system
form = My formInSystem
referent = My entityInSystem
world = My worldInSystem