Learning Strategies by Reasoning about Rules

1. Introduction

The current generation of automated reasoning systems is characterized by very sophisticated inference mechanisms but relatively simple mechanisms for guid­ ing inference. Typical strategies consider the set of existing clauses (the "clause space") and the recency of derivation of each clause. Useful general strategies can be formulated with this information. Unfortunately, these weak strategies have proven inadequate in many instances.

In order for a strategy to be able to respond to features of individual problems and domains it must have access to a large body or knowledge. In addition, it must take into account more types of information than just the clause space and the recency of the clauses. This paper describes how strategy information can be automatically learned from examples by explanation-based learning, and presents a metalanguage that permits the use of more sophisti­ cated strategies and facilitates the analysis of explanations.

Explanation-based learning is a widely-used tech­ nique in AI [10] [12] [13] [15]. It has been used to gen­ eralize methods within a top-down problem-solver, to generalize control information, to facilitate interaction with users and to refine knowledge bases. Logically formulatin~ explanation-based learning provides us with two strengths that logic typically contributes to the problem-solving process:

• A precise notation for describing explanation­ based learning;
• The precise semantics of logic, which provides a semantics for precondition-based reasoning [16].

Also, formulating explanation-based reasoning within a logical framework permits its application to areas or mathematics for which standard axiomatizations exist, such ·as group theory. This opens the possibility of using explanation-based learning to acquire general strategies to guide theorem-proving systems in such domains. This paper presents one facet of our research on metatheoretical formulation or strategies [1] [3] [2].

2. Formalising Explanation·

In order to be able to use explanation-based learn­ ing in a wide variety . of domains and to more fully understand its strengths and weaknesses, it is desirable to formalize the use of explanations. We present a sys- · tem which formalizes the organization, acquisition and generalization or control rules.

Many production s11stem [14] architectures distin­ guish between two types of information. The first type consists or the rules ror manipulatinK the objects in the task environment, often called the object-level" rules. We will consider the system to be initially provided with a fixed set of object-level rules. We can think of these rules as corresponding to the statements in apr<>­ gramming language. The second type of information contains the knowledge about how to fire the object­ level rules in order to successfully achieve a goal. This information is sometimes referred to as "meta-level" information [6]. We can think of this information as descriptions ot programs written in the language or object-level rules. We use a production system as the object-level language in order to illustrate the useful­ ness of this approach to an existing AI programming system, and to take advantage or the conflict set, a data structure that contains the set or fully instan­ tiated rules. Production systems compute the conflict set, but theorem-proving programs typically do not.

The object-level rules contain all the initial domain-specific procedural knowledge in the system, and therefore constitute a model or problem-solving in the domain. An object-level rule can be viewed as a transformation, and an example execution trace is then a sequence of transformations leading from the initial state to the goal state. Thus, an example execution trace is a proof that the goal state is reachable from the initial state via the object-level rule set, or alternatively, that the initial state is a sufficient precondition to guarantee the truth or the goal condi­ tion after executing a specific sequence of instructions. This observation permits us to construct a system that examines object-level proofs.

Such proofs are valid only to the extent that the object-level rule set is correct. IT the object-level rules contain errors or omissions, then a proposed proof may be incorrect, or the system may not be able to find a proof that exists. For example, if the domain is mani­ pulations of a robot arm, then the object-level rules are all possible movements of the arm. In this case, it is possible to formulate a complete and correct set of object-level rules. On the other hand, if the domain is medical diagnosis, then this is not possible. In the fol­ lowing sections, we describe a language for describing the state or the object-level production system that facilitates reasoning about problem-solving methods.

I. The Space of Rule Instantiations

A ground instance of a rule is called a rule instan­ tiation. When a system draws inferences from its knowledge of its possible actions, we say that it is rea­ soning in instantiation space. In order to reason in this space, it is necessary for a system to have a language that provides access to its rule instantiations.

At each point in the execution of a task, the state or a system can be represented in terms or its full and partial instantiations. This representation captures existing and possible relationships among working memory elements. In addition, given a sequence of such state descriptions, i.e. a trajectory in instantiation space, we can derive relationships among instantia­ tions. In particular, explanation-based reasoning is based upon the precondition relationship, in which an instantiation helps another instantiation to become matched by either placing an element needed by that instantiation in working memory or removing an ele­ ment that matches a negated condition in that instan­ tiation. Precondition analysis has been used in the deri"!atiot;t of programs [7] and in the formulation and modtft.catlon of plans [16]. The representation described in the next section combines Waldinger's approach to planning with Davis' approach to reason­ ing about rules and controlling rules [5] [6].

4. The Representation

This section provides a very brief description of the representation. Detail is omitted for brevity and clarity. The production system used is OPS5 [8]. The OPS5 system does not have the capability of accessing its matching network as data for the productions. This precludes writing OPS5 meta-rules. Thus, we have designed the meta system to sit above the OPS5 sys­ tem, and access its internals. Each object-level rule is represented at the meta-level as a term of the form: rule(variables) - action1 & .action1 ... where "rule" denotes the the left-hand side of a rule, and each actioni denotes an action that can be executed. For example, the following OPS5 rule is from the monkey­ and-bananas problem (a well-known AI task in which a monkey must retrieve a bunch of bananas from the ceiling using a ladder.)

(p walk (object "name <o> "at <p>) {(moDieJ "on 8oor "at f<c> <> <p>) "holda nil) <monke:r>} ->(write (crlf) WALKING TO <p> (crlf)) (modif:r <monke:r> "at <p>) J

which moves the monkey to an object's location, is represented as: walk(O,P,C) - modify(monkey,at,P~. The parameters of the "walk" function are the vart­ ables in the rule definition. Instantiations of the "walk" object-level rule are represented as meta-level terms, which permits the meta-system to reason about the rules that are ft.reable.

Representing rules in this way permits rules to be characterised both according to their variable bindings, and according to the actions that they perform. This opens up the possibility or implementing strategies that use these types or information to control inference. Two of the meta-level predicates are:

• match{/ 1 ,/ 1 ) which returns the most general sub­ stitution that can be applied to the formula / 1 to yield the formula / 2;
• instantiate(rhs,match} which returns the result of applying the substitution match to the rule right­ hand side rhs.

These two formulas permit the meta-level to rea­ son about the object-level instantiations and are neces­ sary in order for the meta-level to be able to handle the object-level properly. Object-level variables must be meta-level constants to avoid spurious matches between meta-level variables and object-level variables. The structure of this system strongly resembles that of the PRESS system [4].

&. Reuonlns with Meta-Information

The usefulness of reasoning in instantiation space is that it facilitates reasoning about the object-level. In the following sections we describe how preconditions can be extracted, generalised and applied within a sya­ tem that utilises this representation. First we show how meta-information can be represented in terms of the preconditions that are necessary to enable rules to fire.

An example is given by the following OPS5 rules for the monkey-and-bananas task, their instantiations ni and condition elements cii.· together with the corresponding connection graph tO]:

(p ~rab-from-ceilin&

ob~ect "name <w> "at <p> "on ceilin&)

·

obJect "name ladder "at <p>)

(monkeJ "on ladder "holda nil) <monke:r>l

->(write (crlf) GRABBING <w> FROM CEtt.ING (crlt) )

(modif:r <monke:r> "holda <w>) )

(p carr:r

(object "name <o> "at <p>)

{(monke:r "on 8oor "at {<c> <> <p>} "holda <w> <>nil)

<monkeT>} {{object "name <w> "at <c>) <camed-object>}

->(write (crlf) CARRYING <w> TO <p> (crlf) )

(modif:r <monke:r> "at <p>)

(modif:r <carried-object> "at <p>))

(p climb

(object "name <o> "at <p> "on <n>J

{(monkeJ "at <p> "holda nil "on <n> <monke:r>}

.->(write (crlf) CLIMBING ONTO <o> crlf) ) (modif:r <monke:r> "on <o>))

Fipre 2. " 1: carr;r: o .. bananu p·2-2 c-e-5 w-ladder "·: climb: o·ladder p·2-2 n·Soor "a: &rab-from-ceilin&: w·banahaa p-2-2 Inatantiation "· dependa on 8rin1 "'' and "t dependa upon 8rin& both "\and "·· ("1 and "· alao depend on prnioua flrinp or init1aliaationa.) Some conditione are om1tted for clarit:r and apace. 2-2 and e-5 refer to x-:r coordinatea.

Given a connection graph Cor an example proof, the precondition chunks in the connection graph can be extracted. A precondition chunk is a rule whose right-hand side is an instantiation ni in the graph, and whose lert-hand side is the sequence or instantiations n; 11 ... ,n;. that directly caused ni to completely instan­ tiate, either by inserting tokens in working memory that satisfied condition elements of ni, or removing tokens that matched negated condition elements or ni. A precondition chunk describes sufficient conditions to enable ni to fire. For the above example, the precondi­ tion chunk Cor n 3 is:

carry(bananae,2-2,9-5,ladder) &: climb(ladder~2-2,floor) - srab-rrom-ceiling(bananae,2-2}

Precondition chunks can be used as problem­ reduction methods to construct plans in a top-down Cashion. A key feature or precondition chunks is that they are not specified in terms or a separate goal voca­ bulary. Problem-reduction methods are often specified in terms or a goal vocabulary in which the goals' types and attributes are not all part or the original specification or the task - the objects and rules. Precondition chunks specify how to satisfy the goal of firing a rule in terms of trying to fire other rules. The only information contained in precondition chunks is information about instantiations and their variable bindings. This domain-independent vocabulary provides a useful means of relating goals to each other.

8. Generalizing Precondition Chunks

Since we are viewing the object-level execution trace as a proof or the goal's attainability, the most general conditions under which a sequence of rules can be used to satisfll certain instantiation conditions arc given b11 the most general unification of those rules and conditions. This observation shows the usefulness of using instantiation information as the underlying representation - state and goal information are uni­ formly represented, and can be unified.

In general, there can be more than one way to resolve a set of rules. In order to decide which resolvent to use the example proof is used to guide the unification process. This is done before the unification process by renaming variables according to ~?recondi­ tion relationships. For example, the "climb , "grab­ from-ceiling" and "carry" rules are resolved to produce a general precondition chunk for "grab-from-ceiling" with the variables "o" and "p" in "climb" renamed to "w" and "c", respectively, since they correspond to the same actual object in "carry" (the ladder). Also, in the example the "w" in "r;rab-from ceiling" corresponds to the "o" in "carry" so 'w" is renamed to "o". The result­ ing generalized precondition chunk for "grab-from­ ceiling" is:

carry(o,p,c,ladder) &: climb(ladder,c,floor) - grab-(rom-ceiling(o,p)

This chunk describes the most general conditions under which execution of the "carry" and "climb" instructions will enable the "grab-from-ceiling" instruction to be executed. Generalized chunks function as meta-level lemmas. They are deducible from the object-level rules and provide solutions to subproblems. Chunks contain strategy information, as they select resolvents and guide the object level.

7. Using Generalised Precondition Chunks

Mter precondition information has been extracted from examples and generalized, the generalized chunks are added to the meta-level system and used as problem-reduction operators. The goal instantiation (the rule instantiation whose firing is desired) is inserted into the meta-system as a goal clause:

goal-instantiation -

Conflict set elements are represented as assertions:

- instantiation

Precondition chunks are reoresented as assertions: preconditions - instantiation

Resolution is used to chain back from the goal instan­ tiation to find a reduction to ground instances - a plan to achieve ·the goal. Object-level rule instantia­ tions are represented as meta-level ground clauses, and change as the task environment changes, i.e. as actions are taken by the system, or external forces affect the environment. The firing of object-level rules is a side effect of matching a goal instantiation to a ground instantiation.

To use these chunks it is necessary to provide a meta-level control component. There are many different possible types· of control that can be specified. The method of selecting which clauses to match is independent of the representation presented here. We use the ITP reasoning system [11] as the meta-level. The strategy for selecting problem reductions is the set-of-support strategy, which is ITP's default strategy. A more sophisticated means of selecting problem reduc­ tions is desirable. In order to take advantage of domain-specific information in the chunks we intend to investigate heuristic control rules such as preferring problem reductions that have been most successful in the past.

8. An Example

This system was tested on a number of tasks. A short example is the monkey-and-bananas task. The following set of production rules, together with those already presented, defines all the possible actions of the monkey. These rules contain no control information at all - they only specify legal actions.

(p pick-up ~object "name <w> "at <p> "on Boor)

-> write lcrlr) PICKING UP <w> (crlf) J

{ monkeJ "d <p:> "holds nil) <monke~>}

modify <monkey> "holds <w>))

(p jump-down (monkey "on <x>) <monkey>}

(object "name <x> "on <n>)

-> (write {crlr) JUMPING DOWN ONTO <n> (crlf) )

! modity <monk!> "on <n>)) { monker "holds <x> <> nil}}. <monkey>} -> write lcrlf) DR PPING <x> (crir) ) modify <monkey> "holds nil) )

(p drop

The system is provided with these rules together with an "initialize" rule that sets up the situation. When the system is given a specific task situation (the monkey is on a couch, and the bananas are on the ceiling):

! monkey "at 5-7 "on couch) object "name couch "at 5-7 "weisht heary "on floor) object "name ladder "on floor "at 9-5 "weight light) object "name banana· "on ceilin& "at 2-2)

and a problem (grab the bananas from the ceiling), the default strategy of OPS5, which is to prefer rules that use more recently generated facts, causes the system to make the monkey repeatedly jump from the couch to the floor and then climb back onto the couch.

Using a modified OPS5 in which a trainer can guide the actions or the system by performing the conflict resolution, the following execution trace is provided to the learning system:

initialise () -+ ~ 2 3 4 5) jump-down (2 3 -+ (7) walk (4 7) -+ (9 pick-ur (4 9) - (11) carry 5 11 4) -+ (13 15) drop ( 3) -+ (17) climb (15 17)-+ (19) grab-from-ceiling (5 15 19) -+ (21)

In this trace, the lists or numbers are the timetags or the elements used by and created by each instantia­ tion, e.g. "walk" used elements 4 and 7, and created element 9, which in turn was used by "pick-up".

The precondition relationships among the instan­ tiations are analyzed to produce the following precon­ dition chunks:

initialiae(couch,floor) -+ jump-down(couch,11oor) initialiae(ladder,9-5,5-7) At jump-down(couch,11oor)

-+ wallt(ladder,ll-5,5-7) initialise{ladder) At wallt(ladcler,9-5,5-7) -+ fick-up(ladder,9-5) initialiae(bananaa,2-2) At pick-up(ladder,9-5 -+ carry(bananaa,2-2,9-5,ladder) carry(bananaa,2-2,9-5,ladder)-+ drop(ladder) jump-down(couch,11oor) At carry(bananaa,2-2,9-5,ladder) -+ climb(ladder,2-2,floor) carry(bananas,2-2,9-5,ladder) & climb(ladder,2-2,floor) -+ grab-from-ceiling(bananas,2-2)

These chunks are generalized by resolving their general Corms and renaming variables according to precondi­ tion relationships, as described above, yielding the Col­ lowing set or generalized precondition chunks:

initialiae!x,n) -+ jump-down(x,n)

initialiae o,f,c) At jump-down(x,n)-+ wallt(o,p,c)

initialiae w & wallt(o,p,c)-+ piclt-up(w,p)

initialiae o,p} At pick-uJI(w,c)-+ carry(o,p,c,w)

carry(o,p,c,w) -+ drop(x)

jump-down(x,n) At carry{o,p,c,w) -+ climb(w,c,n)

carry(o,p,c,ladcler) At climb(ladc!er,c,11oor)-+ grab-from-ceiling(o,p)

When these chunks are used as problem-reductions, the system then solves new situations that it would not solve before, such as when the monkey is on a box that is on a box and the ladder is on a box.

9. Summary

We have described a system that acquires strategy information from examples. An execution trace is viewed as a proof that the goal is reachable from the initial state. Explanation-based generalization is then used to find the most general unification or a given goal rule and the rules that are preconditions Cor firing that goal rule. A representation is presented that facili­ tates reasoning about rules. The representation is based upon the instantiation space, and in particular upon preconditional relationships in that space. The notion or precondition chunks is presented.

Future work on this system will concentrate on expanding the range of relationships about which it can reason, to include such relationships as inverse, where one · action undoes another, and generalization/ specialization, where one rule is a gen­ eralization or specialization of another.

Acknowledgements

I would like to thank Richard Caruana, Brian Coffey, K.P. Lee, Damian Lyons, Richard Pelavin, Pa'!l Rutter and Dick Wexelblat Cor reading drafts of th1s paper. Their comments and suggestions were very helpful.