Strategies for Learning Search Control Rules: An Explanation-based Approach

1. Introduction

Recent research has demonstrated that explanation-based learning (EBL) is a viable method for acquiring search control knowledge [22, 6, 18, 27, 29). Almost all EBL problem solvers learn by analyzing why a solution succeeds in solving a problem. The result is a knowledge structure (such as a macro-operator or achema) that describes how to solve similar problems should they arise in the future.

However, explanation-based learning can also be used to learn why a problem-solving method failed. By explaining why a method failed to solve a problem or sub-problem, a system can learn when to avoid that method in the future [16, 11, 24). In fact, EBL is a very general technique, and in principle an EBI., system can learn from any phenomenon that it can explain. To do so, however, a system must know what phenomena - or tllrget concepts - to explain and be able to formulate appropriate explanations [12). Furthermore, the system must be able to modify its behavior appropriately on the basis of the learned information.

This paper describes how the PRODIGY system learns from multiple target concepts In order to Increase the utility of the learning process. Specifically, unlike previous EBL problem-solvers, PRODIGY learns from a variety of phenomena, Including success, failure, and goal-interactions. E!!Ch of these meta-level target concepts corresponds to a strategy for optimizing PRODIGY's effectiveness as a problem solver. Explanations are formulated using an explicit theory describing the domain and the PRODIGY problem solver. Both the set of target concepts and the theory are declarative

1Thls reoearch wao aponiiOfed In pert by the DefenM Adv111ced Raarch Projecb · Agency (DOD), ARPA Order No. 4976, monitored by the Air Force A vlonlCI Laboratory under contract F33615-84-K-1520, In pert by the Office ol Nav81 R.....:h under Contract N00014-84-K-0345, and In pwt by a gift from the Hup Corpantloo. In addition, the flnt author wu tupported by a Bell t..boralorleo Ph.d Sdi<Jiao.hlp. The views and conch..tot\1 contained In thia document an thole of the authon 111d lhould not be Interpreted u repreMnllng the offtd81 pollda, either ex~ or Implied. of DARPA, the Air Force Office of Scientific Reoearch or the US government.

2coaJ concept Is an equivalent term, but Is eully confuMd with the go8l ol the problem-solver.

~e use of incomplete, approximate, and default theorleo are topiCI of current reoearch, but not considered here.

Strategies for Learning Search Control Rules: An Explanation-based Approach

Steven Minton and Jaime C. Carbonell

Computer Science Department Carnegie-Mellon University Pittsburgh, PA 15213

and extensible, therefore additional optimization strategies can be incorporated into the system when necessary. This paper also introduces an new EBL algorithm, Explanation-based Specialization (EBS), which constructs explanations by specializing proof schemas using information gained from a training example. EBS is particularly appropriate for problem solvers that learn from their own problem solving performance.

2. The Terminology of Explanation-based Learning

Several recent papers [22, 6, 27) have contributed greatly to the emergence of a relatively standard terminology for describing explanation-based learning. ·(We use the generic term "explanation­ based learning" to refer to deductive learning from single examples, u exemplified by [17, 22, 23, 9, 8).)

The tllrget concep_t Is a high-level description of a concept (i.e., a class of instances).2 A training emmple Is an Instance o( the target concept. Using the domain theory, a set of axioms describing the domain, one can explain why the training example Is an instance of the target concept. The explanation constitutes a proof that the training example satisfies the target conceptl. By finding the weakest conditions under which the explanation holds, EBL will produce a lttlrned description that is both a generalization of the training example, and a specialization of the target concept. Typically, the purpose of the learning process Is to produce a description that can serve as an efficient recognizer for the target concept.

As an example (adapted from [22)) consider the target concept (SAFE-TO-STACK x y), that is, object x is can be safely placed on object y without object y collapsing. A training example could be a demonstration that a particular book, ''Principles of AI", can be safely placed upon a particular table, Coffee-Table-t. Let us suppose that our domain theory, shown below, contains assertions enabling us to prove that "Principles of AI" Is safe to stack on Coffee-Table-1 because all books are lighter than tables. From this proof we can conclude that that any book can be safely stacked on any table. Thus the learned description Is (AND (15-BOOK x) (15-TABLE y)).

DOMAIN THEORYt

(IS..BOOK PRINCIPLES-OF-AI) (SAFE!-TO-ST ACK lC y) If (OR (LIGHTER "y) (NOT -FRAGILE y)) (LESS-THAN 111 5-LBS) If (AND (IS..BOOK ~t) (WEIGHT" w))

3. The PRODIGY System

PRODIGY Is a learning apprentice [20) that acquires problem solving expertise by interacting with an expert, by carrying out experiments, and, as described In this paper, by analyzing problem solving traces. PRODIGY can be divided Into four subsystems:

· An advanced Strips-like [9) problem solver that provides a uniform control structure for searching with both Inference rules and operators. The problem solver Includes a simple reason-maintenance system, allows operators with conditional effects to be specified, and is capable of Interleaving goals. The problem solver's search can be guided by domain-independent or domain-specific control rules.

• An explanation-based learning facility [19, 15) that can propose explanations about why a control decision was appropriate, and transform them into search control rules.
• A learning-by-experimentation module [4) for refining incompletely or incorrecdy specified domain knowledge. Experimentation Is triggered when plan execution monitoring detects a divergence between Internal expectations and external expectations.
• A user-Interface that can participate in an apprentice-like dialogue, enabling the user to evaluate and modify the system's behavior.

Except for the experimentation module (which is currently under development), PRODIGY has been fully implemented, and tested on several task domains Including a machine shop scheduling domain and a 3-D robotics construction domain. For brevity of exposition the examples described in this paper will be taken from an extremely simple task domain, the familiar ''blocks world", whose standard specification [25) is shown in Figure 3-1. While the blocks world may seem contrived, solving apparently simple problems may involve searching hundreds of nodes. In other words, the domain is simple but as we will see, the formalization (i.e., axioniization) of the domain is far from ideal. By acquiring search control knowledge, PRODIGY effectively modifies its behavior so that its performance reflects the inherent simplicity of the domain, rather than the deficiencies of the formalization. Learning search control knowledge thus has the same effect as reformalization - important knowledge Is brought to bear early, so that correct decisions can be made efficiendy.

PICKUP II

Precondition: (AND (CLEAR b) (ONT ABLE lo) (ARMEMPTY>l Add: (HOLDING lo) Delete: (ONTABLE b) (CLEAR b) (ARMEMPTY)

PUTDOWNb

Precondition: (HOLDING b)

Add: (ONTABLE lo) (CLEAR lo) (ARMEMPTY>

Delete: (HOLDING b)

STACK111112

Precondition: (AND (HOLDING Ill) (CLEAR lo2)) Add: (ON Ill 112) (CLEAR Ill) (ARMEMPTY) Delete: (HOLDING Ill) (CLEAR 112)

UNSTACK!Il 112

Precondition: (AND (ON Ill lo2) (CLEAR Ill) (ARMEMPTY)) Add: (HOLDING loll (CLEAR 112) Delete: (ON Ill 112) (CLEAR lot) (ARMEMPTY)

Figure 3-1: Blocks World Specification

3.1. An Example Problem

A problem consists of a description of a start-state, and a set of goal states, as shown in Figure 3-2. PRODIGY's description language, called POL, is a logic-based language that includes conjunction, disjunction, negation, existential quantification, and universal quantification over sets. (Variables are shown in lower case.) POL is also used for describing the preconditions of operators and search control rules.

By default, PRODIGY searches depth-first, attacking goals from left to right, unless search control rules Indicates a more appropriate ordering. To solve a goal, the system selects an operator with a postcondition (a formula in the add or delete list) that matches the goal. U the preconditions of the operator are satisfied, then the operator can be applied, otherwise the system subgoals on any unsatislied preconditions. (For simplicity, this paper describes only the basic capabilities of the system necessary to Illustrate the examples. More sophisticated features, such as conditional effects, inference rules, functions, and non-linear planning are discussed in [15). Readers unfamiliar with the basic operation of a STRIPS-style system should see [25).)

To solve the example problem, PRODIGY considers applying either PICKUP or UNSTACK to achieve (HOLDING B), as illustrated In Figure 3-3. PICKUP is inappropriate, but this is only discovered during the course of solving the problem. In attempting to PICKUP B, PRODIGY Is forced to subgoal on (CLEAR B) and (ONTABLE B), the unsatisfied preconditions of PICKUP. These are added to the goal-stack, and then PRODIGY attempts to solve (CLEAR B). Unstacldng A from B achieves (CLEAR B), but then a goal-stack cycle occurs In attempting to achieve (ONT ABLE B). PRODIGY then attempts other ways to (CLEAR B) at Node2, but these also result In failure. (The problem solver has no way of knowing that unstacking A from B did not cause the failure of Node3. But as we will see, when learning is interleaved with problem-solving, PRODIGY backtracks more intelligently.) Eventually backtracking to Nodel, PRODIGY attempts unstacking B from C, which leads to a solution.

PRODIGY's performance in a given domain can be improved by the addition of search control rules. Control rules constrain the search by mediating the four decisions PRODIGY makes during each problem solving cycle. First, the system must choose a node in the search tree to expand next - the default is depth-first expansion. · Each node consists of a goal-stack, a set of subgoals and a state describing the world. Once a node has been chosen, one of the subgoals must be selected, and then an operator relevant to reducing this subgoal. Finally, a set of bindings for the variables in that operator must be decided upon.

Each of these four decisions can be affected by control rules, which indicate when to SELEcr, REJEcr, or PREFER a particular candidate (node, goal, operator or bindings). Given a default set of candidates, PRODIGY first applies the applicable selection rules to select a subset of the candidates. If no selection rules are applicable, all the candidates are selected. Then rejection rules are executed to filter this set, and finally rreference rules are used to find the heuristically best alternative . (If backtracking is necessary, the next most preferred is attempted, and so on.)

Consider the first control rule shown in Figure 3-4. This rule is a operator selection rule; it is used in deciding which candidate operator to choose. Notice that the description language POL allows the use of meta-level predicates such as KNOWN. The formula (KNOWN node exp) is true if the expression exp matches the state at node. Therefore the rule asserts that if the current goal matches (HOLDING x) and x is not on the table, then UNST ACK is the appropriate operator. Normally, since both PICKUP and UNSTACK can achieve (HOLDING x), both would be candidate operators. If this rule had been learned prior to our example problem (Figure 3-3), PRODIGY would have solved the problem without having to waste time exploring Node2 and its descendents.

(SELECT OPERATOR (UNSTACJt x y)) i~ (and (CURRZN'l-NODB node) (CURRZN'l-GOAL node (HOLDING X) ) (CANDIDATJ:-OPERATOR node (UNSTACJt X y) ) (ltNOWN node (NOT (ON'rABLE X) ) ) ) (PRZrER GOAL (ON X y) OVER (ON W X) ) if (and (CURREN'l'-NODE node) (CANDIDATE-GOAL node (ON X y)) (CANDIDATE-GOAL node (ON w X)))

The second control rule in Figure 3-4, a goal preference rule, is used to decide which of the candidate goals at a node to attempt first. The rule states that if (ON w x) and (ON x yl are candidate goals, then it is preferred that (ON x yl should be attempted before (ON w x). This piece of control knowledge directs the problem solver to build stacks of blocks from the bottom up. Since PRODIGY finds the most preferred goal from a set of candidates, this rule correctly handles stacks regardless of height (i.e., the number of goals in the ON chain).

4. Learning Control Rules: The Explanation-based Specialization Method

PRODIGY's explanation-based learning module can either be invoked after the problem solver has finished, or learning can be interleaved with problem solving. In either case, the learning process begins by examining the a trace of the explored search tree (in a pre-order traversal) in order to pick out examples of PRODIGY's target concepts. Search control rules are learned by explaining why a training example satisfies a target concept. There are currently four types of target concepts implemented in PRODIGY:

1. SUCCEEDS: A control choice succeeds if it results in a solution. Learning about successes results in preference rules.
2. FAILS: A choice fails if there is no solution consistent with that choice. Learning about failures results in rejection rules.
3. SOLE-ALTERNATIVE: A choice is a sole-alternative if all other candidates fail. Learning about sole alternatives results in selection rules.
4. GOAL-INTERACTION: A choice causes in a goal-interaction if it results in a situation where a goal must be re-achieved. Learning about goal-interactions results in preference rules.

Each type of target concept has four variants, one for each of the four control decisions (picking a node, goal, operator, and bindings). For example, the target concept (0PERA10R-FAILS op g n) is true if operator op fails to solve goal gat node n. As with all .,,,ncepts in the system, target concepts are represented by atomic formulas. Each target concept is declaratively specified to the system, as illustrated by Figure 4-1. A target concept specification includes a template for building search control rules, and 'may include other infm mation such as heuristics for selecting training examples, as described in [15].

4 Preferences are transitive. If there Is a cycle In the preference graph, then those preferences In the cycle are disregarded. A candidate is best, or "most preferred", if there Is no candidate that is preferred over it.

Tarv·t Conc·pt: (OPERATOR-rAILS op goal node) Rul· Templat·: (RZJZCT OPERATOR op) i~ (AND (CURRZN'l-NODB node) (CURRZN'l-GOAL node goal) (CANDmATE-OPBRATOR op node) (OPERATOR-rAILS op goal node))

An explanation describes why an example is a valid instance of a target concept, and corresponds to a proof. To construct such proofs, we require a theory describing the problem-solver, as well as a theory that describes the task domain (such as the blocks world). Therefore, PRODIGY contains a set of architecture-level axioms which serve as its theory of the problem solver. The domain theory is given by a set of domain-level axioms extracted from the domain operators by a pre-processor. Together, these sets of axioms are referred to as proof-schemas. Each proof-schema is a conditional which describes when a concept is true. Appendix I.1 illustrates the architecture­ level proof schemas releyant to the concept OPERA 10R­ SUCCEEDS. These schemas state that an operator succeeds in solving a goal at a node if:

• the operator is applicable and directly solves the goal, or
• subgoaling occurs, creating a child node where the operator succeeds, or
• another operator is applied to achieve a subgoal, creating a child node where the operator succeeds.

Domain-level schemas (Appendix 1.2) indicate the available operators, and their effects and preconditions.

To prove that a target concept is satisfied by an example, PRODIGY specializes the target concept in accordance with the example. This process is equivalent to creating a proof tree by .starting at the root (i.e., the target concept) and incrementally expanding the leaves of the tree. To specialize a concept PRODIGY retrieves a proof schema that implies the concept and recursively specializes all the subconcepts in the schema, as described in Figure 4-2. The process terminates when primitive concepts are encountered. The result of the specialization process is a description of the weakest premises of the explanation.

If a concept is described by more than one proof schema, as is OPERA10R-SUCCEEDS, then it is disjunctive. When specializing disjunctive concepts, PRODIGY uses the examfle to determine which schema gives the appropriate specialization . Specifically, we allow each concept to be aSS9Ciated with a discriminator function which examines the problem solving trace and selects a schema consistent with the training example. In this way, discriminator functions provide a mapping between the example and the explanation.

After the EBS process terminates, the resulting description is a specialization of the target concept. A search control rule is formed by retrieving the rule construction template (found in the target concept specification) and substituting the specialized description A concept is represented by an atomic formula.

Sorhere can be multiple training examples for a subconcept if the subconcept Is within the scope of a universal quantifier. Universally quantified statements take the form FORALL x SUCH-THAT (P x), (Q x). The formula(!' x) acts as a generator for values of x. (Q x) can be any expression. The implementation treats universally quantified statements as if they were written In the logically equivalent normal form: FORALL x (OR (NOT (!' x))(Q x))). Because (!' x) Is negated, It Is not spedalized. (However, If P generates a fixed set of values, It can typically be simplified out of the learned description using simplification axioms[15] .) EBS specializes Q separately for each example of x, and returns the disjunction of these descriptions as the specialization of Q.

To specialize a concept:

• If the concept is primitive- there is no schema that implies the concept - then return the concept unchanged, otherwise,
• Call the discriminator function associated with the concept to retrieve a schema consistent with the training example. Each non-negated atomic formula in the schema is a subconcept. While there exists a subconcept in the schema that has not been specialized, do the following:
• Specialize the subconcept,
• Uniquely rename variables in the specialized desaiption to avoid name conflicts,
• Substitute the specialized description for the subconcept in the schema and simplify.

Return the schema (now a fully specialized description of the concept).

Figure 4-2: The EBS Algorithm

for the target concept in the template. During subsequent problem­ solving episodes, PRODIGY will maintain a utility estimate for the new rule, where utility is defined by the cumulative time cost of matching the rule versus the cumulative savings in search time provided by the rule. Only rules that prove useful are retained in the set of active control rules.

Let us return to our example problem (Figure 3-3) to illustrate how the EBS algorithm works. As stated previously, the selection of UNSTACI< at Nodel provides a training example for the target concept OPERA TOR-SUCCEEDS.

Tar;-t conc-s>t : (OPJ:RATOR-SUCCU:OS op goal node) , l:zulple : (CIPJ:RATOR-SUCCU:OS (tnt8T1Clt B) (HOLDING B) Nadel)

Because OPERATOR-SUCCEEDS is a recursive definition, the success of UNSTACK depends on its success at nodes 9 and 10 and eventual application at Nodell. We shall illustrate the specialization process by ''unrolling" the recursion from the bottom up, starting with the success of UNSTACI< at Nodell.

lubooao-s>t: (CIPII:R.I.TCa-StiCC:DDS op goal node) , l:zulple: (OPDATOR-StiCC:DDS (tntSUClt B) (HOLDING B) Bodell)

Because UNSTACK. directly solves (HOLDING B) at Nodell, OPERA TOR-SUCCEEDS is specialized by Schema-51 in Appendix 1.1 - the schema consistent with ·the example. The system then recursively specializes the subconcepts as shown below:

SpeoJ.albe (OPJ:RA'l'OR-IOOCI:I!DS op goal node) udng Sohema-81 :

(llaD (1DDZD-BY-QPJ:RA'l'OR goal op) (UPLIC:UU op node) SpeciaU.ae (1DDJ:D-BY-OPJ:RATOR goal op) ueing Sch--Dl: (llaD (llaD (IA'l'CBZS op (tntST1Clt x, y) (IA'l'CBZS goal (HOLDiaG x) ) (UPLICULJ: op node) Specialbe (1PPLICULJ: op node) udng sch--D4: (llaD (llaD (IA'l'CBZS op (tntST1Clt x y) (IA'l'CBZS goal (HOLDiaG x) ) (llaD (IA'l'CBZS op (ONST1Clt u v) )

(JafOIOI node (1ND (CLEAR u) (ON u v) (ARMEMPTY)))

After some trivial simplifications, our result can be re-expressed as follows:

(OPJ:RA.TOR-SOCCEEDS op goal node) if (AND (lATCHES op (ONSTAClt x , y)) (lATCHES goal (HOLDING x)) (JafOWN node (and (CLEAR x) (OH x y) (ARMEMPTY)))

This simply states that an operator succeeds in solving a goal at a node if the operator is UNSTACI<, the goal is to be holding an object, and the preconditions of UNST ACK are known to be true at the node. Though this result is not particularly useful by itself, it serves as a lemma in explaining why the application PUTOOWN at nodelO enabled the application of UNSTACK:

Sub-Concept : (OPJ:RA.'l'OR-SOCCDDS op goal node) , ll!xample: (OPJ:RATOR-SOCCEEDS (ONST1Clt B) (HOLDING B) HodelO)

This time, OPERA TOR-SUCCEEDS is specialized by schema-52, the recursive definition of OPERATOR-SUCCEEDS, because PUTOOWN was applied as a precursor to UNSTACK, rather than directly solving the problem. Then APPLICABLE is specialized as before, and the recursive specialization of OPERATOR-SUCCEEDS is accomplished using the result from Nodell. Finally, the concept (CHILD-NODE-AFI'ER-APPLYING-OP child-node pre-up node) is specialized and then simplified; doing so effectively regresses the constraints on child-node across the definition of PUTOOWN. (The relevant proof-schemas used for regression are shown in Appendix 1.3). The result states that UNSTACK will succeed whenever the goal is to hold an object, and the preconditions of the sequence PUTOOWN w, UNSTACK x yare satisfied:

(OPJ:RATOR-SUCCU:OS op goal node) if (AND (IATCIIJ:S op (ONST1Clt x y) ) (IATCIIJ:S goal (HOLDIHG x) ) (JafOIOI node (AND (CLJ:llR x) (OR x y) (HOLDiaG w)) )

The specialization process continues in this manner, until finally the successful selection of UNSTACK at Nodel is explained. The resulting expression indicates that UNST ACK is appropriate if the goal is to hold an object and the preconditions of the sequence UNSTACK w x, PUTOOWN w, UNSTACK x yare satisfied. 6 That is, UNST ACI< is appropriate when the goal is to hold a block, there is a single block on top of the desired block, and the robot's arm is empty:

(OPJ:RATOR-SUCCU:OS op goal node) if (AND (IATCIIJ:S op (ONST1Clt X y) ) (IATCIIJ:S goal (HOLDING x) ) (JafOWN node (AND (OH X y) (OH w X) (CLEAR w) (ARMEMPTY)))))

At this point, a control rule can be built from the rule construction template for OPERA TOR-SUCCEEDS. However, the reader may have noticed that the learned description seems very specific. Although we will not discuss here the process by which PRODIGY evaluates the utility of the rules it learns, it should be clear that the learned rule will be a relatively weak control rule. In the next section, we will see that a much better explanation of why UNSTACI< was appropriate can be found by by analyzing why the alternative choice, PUTOOWN, failed 7 .

This example was chosen for several reasons. First, it is similar to the USEFUL-OP example in LEX2, as described in [22), and thus can be directly compared to previous work. Furthermore, the example illustrates that learning from successful operator applications is not guaranteed to produce strong control rules. As we will see, the utility of explanation-based learning in a given task domain depends greatly on the choice of target concept and explanation.

'Notice that the arguments of the first UNSfACI< must be w and x in order to achieve the preconditions of the remainder of the sequence. Otherwise unique variables would take the place of wand x.

7 A third possibility, not discussed In this paper, Is to formulate an inductive proof explaining that UNSTACK succeeds no matter how many blocks are on top [16, 5, 26].

S. Learning from Failure

To learn from the failure of PICKUP at Nodel in our example (Figure 3-3), PRODIGY uses the target concept OPERATOR-FAILS. Proof-schemas for specializing OPERATOR-FAILS are shown in Appendix 1.4. These schemas state that an operator fails to achieve a goal at a node if:

• the operator is rejected by a control rule, or
• the operator is not relevant to the goal, or
• the operator is not applicable and subgoaling fails, or
• the operator is applicable, and all operator applications result in failure.

Th~ rea~~ is cautioned that for expository clarity these schemas are a s1mphf1ed subset of those used in the actual implementation.

To explain why the selection of PICKUP at Nodel failed PRODIGY ~ust explain why the subtree rooted at Node2 failed. A~ in the previOus section, the analysis is recursive and corresponds to a pre-order traversal of the tree. We will describe the results of the EBS process in a bottom-up manner. First, attempting to PUTDOWN B at Node3 failed ~'_lse the goal (HOLDING B) was already on the goal-stack, resulting m a goal-stack cycle. Therefore, specialization of OPERATOR-FAILS at Node3 proceeds as follows:

'1'~ concept: (OPIIIRA'l'OR-r.ULS op goal node)

&zallple: (Ol'UA'l'OR-FAILS (POTDONN B) (Orl'ABLIC B) lloda3)

8peo1a111:· (OPIIIRA'l'OR-rAILS op goal node) by Soh--r3:

(AND (ADDJ:D-BY-OPIIIRA'l'OR goal op) (IS-PUCONDI'l'ION p op) (DIOWII node (NOT p) ) (StJBGOALING-rAILS p node) ) 8peo1alil:e (ADDJ:D-BY-OPERA'l'OR goal op) by Sohema-02, 8peo1alil:e (IS-PRICCONDI'l'ION p op) by Soh--03, 8pec1alil:e (StJBGOALING-FAILS p node)) by 8ohema-F5: (AND (AND ()Q'l'CIIU op (POTDONN .r) ) (lll.'l'CIII:S goal (Orl'ABr.& .r))) (AND (IIA'l'CIIU op (POTDONN y) ) (lll.'l'CIII:S p (BOLDING y) ) ) (DIOWII node (NOT p) ) (ON-QCW.-S'l'ACK node p) ) )

PRODIGY simplifies this result to the following expression, which states that PUTDOWN fails if (ONTABLE x) is the goal, and (HOLDING x) is not true, but is on the goal-stack.

(OPIIIRA'l'OR-FAILS op goal node) if (AND (lll.'l'CIIU op (Pll'l'DOWN .r)) ()Q'l'CIIU goal ( ON'l'ABLIC .r) ) (DIOWII node (NOT (BOLDING .r) ) ) (ON-QCW.-I'l'AClt node (BOLDING .r) )

This expression describes why the operator PUTDOWN failed at Node3. Because PUTDOWN was the only operator relevant to (ONT ABLE B) the goal at Node3, the node failed. Therefore the concept (NODE-FAILS node) specializes to the following, given (NODE-FAILS Node3) as the training instance, and using the result shown above as a lemma:

(1100&-F.ULS node) (and (II-QCW. node (OII'l'ABr.& .r) ) (DIOtlll node (NOT (BOLDINO .r) ) ) (ON-QCW.-I'l'AClt node (BOLDING .r) )

Moving up the tree, we find that the description above also explains why Node2 failed. In fact, had the user asked PRODIGY to interleave learning with problem-solving, the inevitable failure of Node2 would have been recognized without the necessity of exploring the rest of the subtree below Node2. In effect, because PRODIGY reasons about its failures in the process of learning, dependency-directed btlcktracking [7) results when learning and problem solving are interleaved.

At this point, PRODIGY can explain why the selection of PICKUP failed at Nodel. Because the precondition (ON-TABLE B) was not true, it became a goal at Node2 and (HOLDING B) was pushed down on the goal-stack, resulting in the failure described above. Thus, after the appropriate specializations, EBS yields the following learned-description for OPERATOR-FAILS:

(OPIIIRA'l'OR-r.ULS op goal node) if (AND (lll.'l'CBES op (PICJttJP .r)) (lll.'l'CBES goal (HOLDING .r) (!mOWN node (NOT (ON'l'ABLE .r) ) )

This description can then be converted into a control rule asserting that if the current goal is (HOLDING x) and x is not on the table, then PICKUP should be rejected. However, in addition, an even higher-level rule can be learned by specializing the target concept OP-I5-SOLE-ALTERNATIVE (whose definition is shown in Appendix 1.4), which says that an operator should be selected if all other operators will fail. The description shown above, stating why PICK-UP failed, is used as a lemma while specializing OP-I5-SOLE­ ALTERNATIVE. Thus, PRODIGY learns the first control rule shown in Figure 3-4, stating that (UNST ACK x y) should be selected if the goal is to be holding x, and x is not on the table. (Selecting UNSTACK is slightly more efficient than rejecting PICKUP, because, as described in section 3, PRODIGY first selects the appropriate · alternatives, and then uses rejection rules to filter this set. If a single alternative is selected, it is not necessary to check the rejection rules.) Notice that this rule provides a much more general and more efficient description of why UNSTACK was appropriate than the rule learned in the previous section.

As this example illustrated, learning why an alternative choice failed can be more useful than learning why a candidate succeeded [13]. This is especially true in the blocks world, where one can succinctly state the reason why a choice was "stupid". Learning from success and from failure are complementary optimization techniques whose relative utility varies from domain to domain.

6. Learning From Goal Interactions

An example of a goal interaction [30] occurs when PRODIGY attempts to solve (AND (ON A B)(ON B C)) by first stacking A on B before stacking Bon C (see Figure 6-1). Of course, stacking A on B deletes (CLEAR B), a prerequisite for stacking 13 on C. Consequently, there is no way to achieve (ON B C) without unstacking A from B.

In the general case, we say that a plan exhibits a goal interaction if there is a goal in the plan that has been negated by a previous step in the plan. There are two complementary forms in which a goal interaction may manifest itself. A protection violation occurs when an action undoes a previously achieved goal, requiring the goal to be re-achieved. A prerequisite violation occurs when an action negates a goal that arises later in the planning process. In our example, a prerequisite violation occurs when stacking A on B deletes (CLEAR B). (Furthermore, a protection violation will follow when picking up B deletes the goal (ON A B). The two phenomenon can also occur independently.)

Goal interactions typically result in sub-<>ptimal plans. Some previous planning systems have included built-in mechanisms for avoiding goal interactions [28, 3, 32]; PRODIGY improves on this by reasoning about interactions in order to learn control rules (in a manner reminiscent of Sussman's HACKER [30].) Since goal interactions can be unavoidable in some problems (and may even occasionally result in better plans) PRODIGY learns rules that express preferences, thereby enabling solutions to be found even when interactions are unavoidable. Learning to avoid goal intera~tions is an optimization technique specifically designed for planrung domains; In other types of domains (e.g., theorem-proving) this technique may be irrelevant.

To explain why a decision caused a goal-interaction, PRODIGY must show that all paths in the search tree subsequent to that decision resulted in a protection violation, a prerequisite violation or a failure. Shown below is an informal definition of the target concept GOAL-CAUSE5-INTERACTION which describes how selecting a goal before another goal at a node 8 can result in goal interaction:

(GOAL-CAUSES.. INTERACTION goall goa12 node) if

forall paths in which goall is selected before goal2, either:

• -the path terminates in a failure, or
• while achieving goal2, goall is negated (a protection violation), or
• -while achieving goal2 a subgoal arises that was negated in the process of achieving goall (a prerequisite violation).

Figure 6-1 illustrates the relevant section .,of the search tree from our example. Nodel and Node6 represent the two goal orderings that PRODIGY attempts. As can be seen, it is not necessary to expand the entire tree to prove that a goal interaction occurs if (ON A B) is attacked before (ON B C). Next to nodes 2 through 5 are shown the intermediate descriptions produced by EBS in explaining why the goal interaction occurred. The target concept and training example are:

Target concept:

(GOAL-CAUSICS-INTZRACTION goal1 goal2 node)

J:xample:

(GOAL-CAUSICS-INTICRACTION (ON A B) (ON B C) Hodel)

'"The proof sc:hemas for goal·lnteractions are similar to the proof schemas for failures. A goal interaction can be regarded as a "soft" failure. As with failure, the wrong choice of a node, goal, operator, or bindings can result In a goal interaction.

The final result of the learning process is the goal preference rule shown in Figure 3-4 indicating that (ON x y) should be attacked before (ON w x) when both are candidate goals. After learning this rule, PRODIGY will always work from the bottom up whenever the goal is to produce an ON chain.

The key point in the learning process occurs at Node4, where EBS reveals that attacking (ON v1 v2) before (ON v3 v4) results in an interaction only if v2 equals v3. This equivalence is a necessary part of the proof because achieving (ON v1 v2) must delete (CLEAR v3) for the prerequisite violation to occur. The fact that v2 and v3 were incidently bound to the same constant in the example is not the reason for the equivalence.

7. Discussion

7.1. Explanation-Based Specialization

The most obvious difference between PRODIGY's EBS method and previous explanation-based learning algorithms, such as CBG [17], EBG [22), EGGS [23) and the STRIPS MACROPS algorithm [9), is that EBS is a specialization-based method rather than a generalization-based method. Although this is primarily an algorithmic distinction, it demonstrates how the appropriateness of an EBL algorithm depends on the environment in which learning takes place. As an example, consider the EBG method described by Mitchell, Keller, and Kedar-Cabelli. The first step of the EBG method is to create a fully instantiated explanation (in the form of a proof tree). In the second step, EBG takes the explanation and computes a general set of sufficient conditions under which the explanation structure holds. Similarly, the CBG, EGGS and STRIPS methods are given an instantiated explanation (often a sequence of operators produced by a problem solver) and they compute sufficient conditions under which the explanation structure holds. Thus these generalization-based methods all take a ground-level explanation and compute a generalization that is based on the structure of the explanation. There are two basic approaches to generating the explanation. Either it is constructed by a black box as in EBG (perhaps using a theorem prover as demonstrated by Mostow and Bhatnagar [24)), or more typically, an observed solution sequence serves as the explanation, as in STRIPS. In the latter case the problem solving operators are the domain theory 9

EBS, on the other hand, never bothers to create a ground-level explanation. Instead, a generalized proof tree is expanded from the top down 10 · There are two factors that make this method appropriate. First, there is no ground-level explanation that is immediately observable, as in SfRIPS. Although the problem solving trace is available, it does not constitute a useful explanation; to explain failures, goal-interactions, etc., an explanation must be constructed from the appropriate architecture-level and domain­ level axioms. Secondly, mapping between from the problem solving trace to the explanation can be efficiently accomplished in a top down manner. The discrimination functions that augment the theory control the explanation process; by specifying the appropriate schema (i.e., inference rules) with which to specialize each concept

'n.eee two schemes have been Implemented In a variety of ways. Foe example, Dejong and Mooney [6] dlscusa a hybrid echeme In which the observed operator oequence b optional. If there b no observed operator oequence, it Is constructed from the domain theory. In either case, a fully Instantiated explanation Is eventually produced. In the SOAR system [27], an observed sequence of production flrin&" Is the basis for learning. SOAR learns whenever a sequence of productions produces a result for a goal. (Because learning Is Implemented on the production level and a result Is obtained independent of the goal's failure or success, SOAR is able to learn from certain forms of failure as well as success.)

10 Also, note that In EBS, unlike EBG, the learned description represents the ~sl suffident conditions under which the proof holds [15].

'they provide all the information necessary to directly find the preconditions of the generalized proof. Therefore PRODIGY simply specializes the target concept top-down to produce the learned description, instead of first constructing the instantiated proof and then regressing the general conditions through the proof structure. In fact, the learned description produced by EBS is more general than the training example only because EBS terminates before producing the ground-level explanation. The bias in EBS (i.e., the factor determining the generality of the resulting desCription [21, 31, 10)) comes from the proof schemas, and in particular, is determined by the disjunctive and primitive concepts used.

7.2. The Utility Of Multiple Optimization Strategies

In this paper, we have described how Explanation-based learning can serve as a general method for implementing optimization strategies to improve problem solving performance. In particular, we have illustrated four strategies for dynamically improving the performance of the PRODIGY system; each strategy corresponds to a target concept that can be explained, and therefore, be learned. In the future, more target concepts can be added to PRODIGY by augmenting the theory as necessary.

The four optimization strategies illustrated in this paper are . completely general, as they are applicable in any domain specified to PRODIGY. A better question concerns the utility of the techniques. Obviously, PRODIGY can always learn from observing solutions, as do other EBL systems. However, using additional target concepts gives the system· a range of options that can result in better performance, as illustrated by our examples. In general, the utility of a particular target concept depends greatly on the task domain and its formalization. In a sense, any optimization techl)ique can be regarded as a strategy for recovering from suboptimal formalizations - those that are epistemologically adequate but procedurally inadequate [14]. The need for multiple strategies is suggested by both theoretical and practical work on program optimization [2, 1].

8. Acknowledgements

We gratefully acknowledge the assistance of Craig Knoblock, Dan Kuokka and Henrik Nordin in designing and implementing the PRODIGY system. Ideas and suggestions by Jerry DeJong, Oren Etzionl, Yolanda Gil, Smadar Kedar-Cabelli, Rich Keller, Sridhar Mahadevan, Tom Mitchell, Ray Mooney, Jack Mostow, and Prasad Tadepalli greatly influenced our work.

I. Proof Schemas

The following proof schemas represent a very simplified subset of the actual schemas used in the PRODIGY implementation. We have assumed, for instance, that the preconditions of operators are simple existentially quantified conjunctions, that there can be not negated goals, and that an operator can have at most one formula in its add­ list relevant to a goal. A more complete description of the actual schemas used in PRODIGY can be found in [15].

1.1. Architecture-Level Schemas for OPERATOR­ SUCCEEDS

Schema-Sl: An operator succeeds if it directly solves the problem.

(OPDATOR-8tJCCDD8 op goal node) if (AND (ADDED-BY-OPDATOR goal op) (APii'LICABLJ: op node) )

Schema-S2: For an operator to succeed, another operator may first be required. (<ll'DATCa-8ucc:aD8 op pd node) u (AJID (APii'LICABLJ: pre.qp node) ) ) (<ll'DATCa-8ucc:aD8 op pd child-node) (CRILD-JIOD&-U"l'':R-APii'LYIHG-<ll' child-node pre.qp node) ) ) Schema-53: For an operator to succeed, subgoaling may be necessary. (Sub goaling creates the node where pre-op applies. See Schema-S2.) (Ol'DATCa-8ucc:aD8 op pd node) U (AND (CRILD-·ODII-U"l'':R-SUBCOALIIIIG child-node pre.qp node) ) )

(OPDA'fOR-80CCUD8 op pd child-node)

1.2. Some Domain-level Schemas for the Blocks World

Schema-01: A postronditlon of (UNSTACK b1 b2) is {JiOLDING bl) (ADD&D-BY-ol'DA'fOR pd op) if (AND ()Q.'l'CRU op (OH8'1'ACit bl b2)) (DTCRU pd (BOLDIHCJ bl)))

Schema-02: A postrondition of (PUTDOWN b) is (ONTABLE b)

(ADD&D-BY-ol'DA'l'Oil pd op) if (AND (DTCRU op (li'l7TDO'Iftl b) ) (MHCIIU pd (Oil'l'ULII b) ) )

Schema-03: A precondition of (PUTDOWN b) is (HOLDING b) (%8-li'UCOIIDI'l'IO. adlpll op) it (AND (DTCRU op (l'l7TDO'IIR b) ) (DTCRU subpd (BOLDIIIIG b) ) )

Schema-04: UNST ACK is applicable if its preconditions are established. (APii'LICDLII op node) if (ANil ()Q.'l'CRU op (OH8'1'ACit bl b2) ) ' (DIOIIII node (AND (CLUR bl) (011 bl b2) (AlUCEKii''l'Y))))

1.3. Architecture-level Axioms for Computing Regressions

Schema-R1: Computes the constraints on node when child-node results from applying op. Note that child-node and op must be bound when this schema is used, otherwise the result may be incorrect. (CRILD-IIOD&-U"l'':R-API'LYIHG-<ll' child-node op node) U (I'ORALL " 8tJCB-'l'IIA'l' (1010101 " child-node)

(RIIGitii88-ACII088-oi'-APii'LICA'fiO. node child-node :r op) ) )

Schema-R2: The following two schemas represent frame axioms. All literals that hold at the child node were either added by the operator, or hold at the parent node (and don't match any member of the operator's delete list). (RIIGIRU8-ACR088-oi'-API'LICA'l'IOH p<Jrent-node child-node lit op) U

(ANil (DIOIIII child-node lit) (I--ADD-L%8'1' add op) (DTCRU add lit) )

Schema-R3:

(RIIGitii88-ACR088-oi'-APii'LICA'l'IOH p<Jrent-node child-node lit op) U (AND (DIOIIII :r p<Jrent-node) ) (I'CIRALL del 80CR-'l'BAT (IH-D&LIC'l'J:-LIS'l' del op) (JIO'l' (DTCRU del lil) ) )

Schema-R4: These 3 schemas regress facts when subgoaling. Called

by Schema-F6.

(RIIGitii88-ACR088-8tJBOOAL-AC'l'IOH node subgoal formula) if (1010101 node formulA)

Schema-RS:

(RIIGitii88-ACR088-8tiBOOAL-AC'l'IOR node subgoal formula) if (ANil ()Q.'l'CRU formulA (011-GOAL-STACit child-node goal) (IS-GOAL node goal) ) )

Schema-R6:

(UGIIIE88-ACR088-8UBOOAL-AC'l'IOII node subgoal formulA) U (lm'l'CBII8 formula (IS-GOAL child-node subgoal))

1. Architecture-level Axioms relevant to OPERATOR­ FAILS

Schema-Fl: An operator fails if it is rejected by a control rule. (C.DU<a-niiA up gotd node) u (BJZC'BD-IIY-COII'l'liOL-RtiLE up gotd node))

Schema-F2: An operator fails if It Is not relevant to the current goal. (c»DU<a-r.uu up go«1 node) ) it (1'01\ALL tuld IIOCII-'r&'l' (I·-ADD-LIII'l' tuld up) (110'1' (IIUCBU tuld gotd) ) )

Schema-F3: An operator fails If it's not applicable, and subgoaling fails. (c»DU<a-r.uu up go«1 node) ) it (UD (ADDJCD-BY-C.DU<a gotU up) (I8-l'RZCOm)I'l'ICla swbgotd up) (DOn node (JIO'l' subgotd) ) (8tiJIGCW.IJIQ-niL8 subgotzl node))

Schema-F4: An operator fails If aU possible applications result In failure.

(c»DU<a-r.uu up gotd node) u

(UD (ADDJCD-IIY-C.DU<a gotd up)

(UPLICABLZ up)

{aOD&-niLS child-node)

(CBILD-·00&-U'l'&R-UPLYI~ ciWd-node up node) )

• Schema-FS: Subgoaling fails If a goalstaclt cycle occurs. (IIUIIQQaLiao-r.uLS sllbgotd node) if (Cla-GOU.-II'l'.la node subgotd) )

Schema-F6: Subgoaling fails If aU child nodes fail after subgoaling. (8UIIGOU.Im-r.uLS sllbgotd node) ) it

(UD {aOD&-niLS child-node) (I'CIIW.L foi'PIIUla SUCR-'r&'l' (DOn fol'riiUla child-node) (UQB88-ACR088-IIOIIGOU.-AC'l'ICla node subgotzl Jol'riiUla))

• Schema-F7: A node fails If solving one of the goals at that node 11 unsolvable.

(IIOD&-r.ULS child-node) if

(UD (IS-GOaL child-node gotd) (I'CIIW.L up SUCR-'l'BM' (IS-oHRI.'fOR up) (c»DU<a-r.uLS up go«1 child-node) ) )

Schema-F8: A node falls If there Is a state cycle. (IIOD&-r.ULS child-node) it

(PRZVIOUSLY-VISI'l'JCD-8'1'1'1'& child-node))

Schema-F9: An operator is the only possible choice If all other operaton fail.

(C:.-IS-801'.&-AL'l'I:IUIP.'l'IV& unique.qp gotd node) it (roRALL up SUCR-'r&'l' (I8-0S'J:RA'l'OR up) (<a (&QtJAL up unique.qp) (C.DU<a-r.ULS up gotd node) ) )