Rule Creation and Rule Learning Through Environmental Exploration

1 Introduction

While solving problems in a new environment, as when we learn how to swim, a learning system must explore the environment to correlate its actions with its senses, to induce the laws of the environment, and to create feasible problem representations for problem solving. We refer to this task as learning from environment, and give its specification in Table 1.

*This research was sponsored by the Defense Advanced Research Projects Agency (DOD), ARPA Order No. 4976, Amendment 20, monitored by the: ·

Avionics Laboratory

Air Force Wright Aeronautical Laboratories

Aeronautical Systems Division (AFSC)

United States Air Force

Wright-Patterson AFB, OHIO 45433-6543

under Contract F33615-87-C-1499.

The views and conclusions contained in this document are those of the authors and should not be interpreted as rep­ resenting the official policies, either expressed or implied, of the Defense Advanced Research Projects Agency or the US Government.

Herbert A. Simon

School of Computer Science Carnegie Mellon University Pittsburgh, PA. 15213, U.S.A.

email: has@cs.cmu.edu

Given:

• Actions: Effectors executable in the environ­ ment ;
• Percepts: Objects' features or relations observ­ able from the environment;
• Constructors: A set of primitive predicates (e.g. = , >), functions (e.g. +, *) and logical connectives (e.g. /\,-., and 3);
• Environment: A process that provides the ob­ servable information and determines the effects of the actions;
• Goal: A state description of the environment;

Learn:

• The laws of the environment that predict ac­ tions' effects and reach the given goal.

Table 1: The Definition of Learning form Environment

For example, consider the Tower of Hanoi as an en­ vironment. Suppose that the learner has actions: (pick diskx pegx) and (put diskx pegx), percepts: (on diskx pegx), (in-hand diskx), and (size> diskx disky), and con­ structors: /\, -., and 3 . To solve problems, the learner must learn consequences of its actions and the laws of the Tower of Hanoi. The environment enforces its laws by refusing to carry out illegal actions. The specified learning task has a wide range of complexity. It becomes harder as the learner's actions and percepts become more environment independent and the environment contains larger laws and hidden features. For example, the Tower of Hanoi problem becomes much harder if (pick diskx pegx) is replaced by more primitive actions like pick(), turn-hand(O) and slide-hand(d), and (on diskx pegx) is replaced by objects' shape, size, and their locations.

This paper will focus on the rule creation and rule learning approach used by a learning system called LIVE that can solve the specified task with primitive per­ cepts (objects' features) and primitive actions (moving a hand) . The learned rules are similar to STRIPS's opera­ tors, but they are used for both prediction and problem solving, and their prediction does not change the world as STRIPS's add and delete lists. With this approach, LIVE creates new rules by noticing the changes caused by actions, and later refines them by discriminating the failures and successes of their prediction. When the dis­ crimination process fails , hidden features will be defined by searching back in the history. After briefly describing some related work and a survey of the LIVE system (de­ tails of LIVE's other components, such as exploring, plan­ ning with incomplete rules, integrating plan execution with learning, and constructing qualitative predicates from numerical percepts, will be discussed in another paper [Shen, 1989b]), we will discuss the three parts of the rule creation and rule learning method and demon­ strate them with examples.

2 Related Work

There are many approaches to the problem of rule cre­ ation and rule learning. The candidate elimination al­ gorithm [Mitchell et a/., 1983] is well known for learning conjunctive rules with a given concept hierarchy. Quin­ lan's ID3 [1987] is probably the best example of a system for learning disjunctive rules from many examples when learning and problem solving are separated. For discrim­ ination learning, Vere [1980] uses it as counterfactuals, and Langley [1987] utilizes it in his SAGE system and develops a theory. More recently, Falkenhainer [1988] uses discrimination as disanalogy, and Newell and Flynn [Newell, 1987] use it to modify incorrect productions in SOAR. Carbonell and Gil [1987] also use a similar method in learning by experimentation.

With respect to automatic creation of a problem space, Hayes and Simon [1974] have built a system capable of constructing problem spaces from written English, which is extended by Yost and Newell [Newell, 1987] in the SOAR system. However, few attempts have been made to create problem spaces from interactions with an envi­ ronment, although Drescher [1987] did some interesting work on implementing early Piagetian learning. As for discovering hidden features , the BACON system [Langley et a/., 1983] creates new terms to infer laws from given data. [Mitchell et a/., 1983] and [Utgoff, 1986] present methods for detecting the insufficiency of a concept de­ scription language in problem solving and define new terms. [Dietterich and Michalski, 1983] gives a survey on some of the existing constructive induction systems for discovering hidden features in time-independent en­ vironments (see Section 6), and present their solutions.

3 Overview of LIVE

The LIVE system is an extension of the GPS problem solving framework with a learning component that cre­ ates and learns rules through environmental exploration. Each rule consists of three parts: condition, action and prediction, all constructed in terms of the given per­ cepts, actions and constructors. When applied forward , a rule whose condition matches the current environmen­ tal state can predict the consequence of the action per­ formed; when applied backward, a rule that predicts the current goal can be used to propose new subgoals as if it were a problem reduction rule or inference rule. LIVE is capable of learning disjunctive rules when con­ structors include logical connectives /\ , · , and 3. In this case, the form of the conditions and predictions is: P1 1\ P2 1\ ... I\ ·3(P3/\ P41\ . . . ) 1\ . .. I\ ·3(P5 1\ P6 1\ .. . ), where the P; are predicates.

• 1 Solution Planning: find the differences between the goals and the current state; for each differ­ ence find a rule, order the differences by their rules;
• 2 If the first difference has no rule, propose an exploration plan;
• 3 If an exploration plan exists, then select an ac­ tion from it, else select the first difference with its rule from the solution plan;
• 4 If the rule is not executable, then identify new differences, order them by their rules, and m­ sert them in the solution plan, go to 3; .
• 5 Make prediction and execute the action;
• 6 If the outcome is expected, then go to 3; If the outcome is surprising, then explain the surprise and revise the rule set;
• If the current action is from the solution plan, then go to 1; else go to 3.

Table 2: The Outline of LIVE's Algorithm

As we can see in the algorithm outline in Table 2, when LIVE is solving problems in a new environment , it will alternate its attention between environment exploration and problem solving because no knowledge is given at the outset. The decision for alternation mainly depends on surprises, situations where an action's consequences violate its prediction. When no rule can be found for solving the problem, LIVE will generate and execute an exploration plan, or a sequence of actions, seeking for surprises to extend the rule set. When new rules are learned, problem solving is resumed and a solution plan may be constructed through means-ends analysis. Since the correctness of a solution plan cannot be guaranteed, learning is inevitable at execution time. When a rule's prediction fails during execution, LIVE will revise the rule set and then plan another solution for the problem.

To illustrate the rule representation and the algorithm, let us consider again the Tower of Hanoi environment , and suppose the initial state is (on diskl peg1) (on disk2 pegl) (on disk3 pegl). Since LIVE starts with no rules at all, it does not know how to reach the given goal state: (on disk1 peg3) (on disk2 peg3) (on disk3 peg3). So it generates an exploration plan, say, pick up a disk from peg1 and then put it down on peg2. RuleO and Rule1 are created in the exploration. Rulel is defined as follows :

Condition: (in-hand diskx)

Action:

(put diskx pegx)

[Rule1]

Prediction: (on diskx pegx) 1\ ·( in-hand diskx)

After the exploration, LIVE plans to put disks on peg3 one by one, believing that the order is unimportant. As a result, disk1 is successfully put on peg3, but not disk2. After (put disk2 peg3), LIVE is surprised that disk2 is still in the hand. An explanation for the surprise is then found (details will be discussed later), and LIVE splits the above rule into two with the help of the explanation (the 3 quantifier is necessary because the match process examines the action and the positive condition before any negative condition, and disky is a free variable here):

Co~dition: (in-hai_J-d diskx) 1\ -,::J(on disky pegx)

Actl~n:. (put d~skx pegx)

[Rule1]

Prediction: (on dzskx pegx) 1\ -,(in-hand diskx)

Condition: (in-hand diskx)/\(on disky pegx)

Acti~n:. (~ut diskx pegx)

Pred1ctwn: (m-hand diskx)

[Rule2]

After these rules are learned, LIVE begins to plan an­ other solution but finds that the current rules cause un­ resolvable goal interactions: no matter which goal is achieved first, it will be destroyed in order to achieve other goals. At this point, LIVE switches itself from problem solving to exploration, in the hope that new surprises will arise for learning better rules.

4 Creating New Rules through Exploration

L.IVE lec:rns.from a new environment by correlating its ac­ tions w1th 1ts percepts. At the very beginning, it simply executes its actions and compares the states before and aft~r . When noticing that facts disappear and emerge as act10ns are taken, the system will build a new rule us­ ing the disappeared facts as conditions, and the eme~ged facts plus the negation of disappeared facts as predic­ tions. For example, t<;> fig~re out what (pick diskx pegx) does, LIVE may try (p1ck d1skl peg1), and then find disk1 moved from peg1 to its hand. RuleO is then built (Rule1 is built in the same way):

Condition: (on diskx pegx) Action: (pick diskx pegx) Prediction:(in-hand diskx) 1\ [RuleO] -,(on diskx pegx)

The main objective for rule creation is to keep the new rule. a~ general as possible. In the example above, the rule IS mdeed most general because the action hap­ pens to make one and only one change. But what ifthere is no change at all, or there are many changes? In the case ?fn? c.ha?ge, as when a robot hand does put() when nothmg IS m 1ts hand, the system will build a new rule with equal conditions and predictions made by the facts related to the action. For example, a new rule about the put() will use the position of the hand both as the condition and as the prediction because the hand is the actor. In the exc:mple above, if (pick disk1 peg1) did not cha~ge. anythmg, then (on diskx pegx) will also be t?e predictwn because diskx and pegx appear in the ac­ tlOn. In the case of many changes, the system will select necessa.ry relational changes just adequate for specifying the act10n. For example, suppose that a robot hand is above a stack of disks (disk1 , disk2 , ... , disk;), when it turns away all the ~elations (direction= hand disk;) will become false. In th1s case, LIVE will not include all these relations in the rule but choose one, any one, of them.

Perhaps a more important question to ask here is what if there are no given relation predicates, and all that can be percei~ed are objects' features such as shape, size, and locatwn. The answer is to construct new relation predicates by noticing t.he features that changed [Shen, 1989b]. However, we w1ll not discuss this topic further in this paper.

5 Splitting Rules by Explaining Surprises

The newly constructed rules, as we saw in the last sec­ tion, are clearly over-general and incomplete, but they serve as a springboard for further exploration. Because of their generality, LIVE will have chances to make mis­ takes, to be surprised, and hence to increase its knowl­ edge about the environment.

Incomplete rules can be easily identified in LIVE, be­ cause all rules predict and LIVE compares their predic­ tions with the actual outcomes in the environment when­ ever a rule's action is executed. A surprise occurs when the actual outcomes falsify the predictions, and the rule that made the predictions is the faulty rule.

LIVE uses discrimination to revise its rules. It remem­ bers each rule's latest application, which contains the rule index, a state, and the rule's variable bindings. Once a rule causes a surprise, LIVE will search for the rule's last application, find the difference (using Langley's method [1987]) between the state now and the state then and use the differences found to split the rule into two.'

For example, suppose the current state is (on disk1 p~g3) (o~ disk3. pegl) (in-hand disk2) (size> disk3 disk1) (siZe> disk2 d1skl) (size> disk3 disk2), and LIVE tries to put disk2 on peg1 with the prediction (in-hand disk2) made by Rule2 w~th varia?le bindings: ((disky . disk3) (~egx . peg1) (dzskx . d1sk2)). After executing (put disk2 peg1), LIVE is surprised because disk2 is now on pegl. To explain the surprise, the system fetches the rule's last application which contains a state: (on disk1 p~g3) (o~ disk3.pegl) (!n-han~ disk2) (size> disk3 diskl) (siz:> disk~ d1sk1) (s1ze> disk3 disk2), and bindings: ((dz.sky . d1skl) (pegx . peg3) (diskx . disk2)). Com­ parmg these two applications, LIVE finds the difference to be ( ~ize> diskx disky) 1\ (on disky pegx) (the details are omitted here because readers can find similar exam­ ples in [Langley, 1987]) . Based on the difference Rule2 is th~n split into two new rules (shown below): ' one is a varian~ of the old rule with the condition augmented by the difference; the other is a new rule, whose condi­ ti_on combines the old condition with the negation of the difference, and whose prediction is the surprising conse­ quences (constructed by the same method used in rule c~eation). N.ot~ that LIVE keeps both rules after split­ tmg, and thts IS one of the main distinctions between LIVE's discrimination process and the one employed by ~angley [1987]; f<:>r ifRule2 were thrown away when split­ tmg Rulel , as hts method does, the good Rule3 might never be found.

Con~ition:( ~n-hand diskx )A( on disky pegx) /\(size> dzskx diskz )/\(on diskz pegx) Action: (put diskx pegx) [Rule2] Prediction: (in-hand diskx) Conditio?:(in-h.and diskx)/\(on disky pegx) 1\-:'::l((stze> dzskx diskz)/\(on diskz pegx)) Acti~n :. (put diskx pegx) [Rule3] Pred1ct10n: (on diskx pegx) 1\ ...,(in-hand diskx)

. Three ad?itional details are worth mentioning here. First, what 1f the discrimination process returns a wrong reason and the rule later becomes too specific? Such rules will be wasted and new rules will be re-learned. To prevent learning wasted rules again, LIVE will reject an explanation if the result of splitting is equivalent to some existing rule. Second, it seems that even though the order of surprises may cause rules' conditions to be built differently, the rules learned are always useful and effective for LIVE to reach the given goal , as we have found in many running examples. Third, if the outcomes include more changes than predicted, no surprise arises, but LIVE will remember those extra changes. In further plan execution, if these changes violate the conditions of the later rules in the plan, LIVE will then insert the changes into the rule's predictions.

6 Discovering and Assimilating Hidden Features

Previous research in discrimination learning has devel­ oped many methods for finding the critical difference between two states, but what if the two states have no difference at all, as when two pairs of green peas look ex­ actly the same but produce different offspring? In this case, we say that the environment has hidden features, something unobservable that yet can discriminate two states that appear identical.

LIVE has two ways to discover hidden features, de­ pending on whether an environment is time dependent or not . In a time-independent environment, where states do not depend on the previous actions, LIVE discovers hidden features by applying its constructor functions to the existing features and testing whether the result dis­ criminates the ambiguous states. For example, when predicting whether a balance-beam [Siegler, 1983] will tip or balance, LIVE discovers the invisible "torque" con­ cept by multiplying distance and weight. (This kind of hidden features is normally categorized by the term con­ structive induction.) In time-dependent environments, where states do depend on the previous actions, LIVE discovers hidden features by searching back in its his­ tory to find differences in the states preceding the two indistinguishable states. We will give a detailed descrip­ tion of the discovery of genes in a later section.

Discovering hidden features is only the first half of the whole story; they have to be assimilated into the sys­ tem to be useful in the future . In a time-independent environment, since hidden features are defined in terms of observables, the system can simply use the newly de­ fined features as if they are visible because they are com­ putable from the observables. For example, when the concept of torque is discovered by a system that per­ ceives only objects' distances and weights, the concept will simply be added as another object feature. Any rule that needs torque to discriminate its condition can use it by computing the value weighhdistance. In a time­ dependent environment, since hidden features determine the observables, two additional things must be done be­ fore these features can be used: determine how the hid­ den features define the observables; and determine how the hidden features are inherited through actions. One strategy is used for both tasks: testing all the construetor functions to find one that is consistent with all the examples collected . We will have more to say about this later when LIVE attempts to discover genes.

Although LIVE's discovering method has been tested in both time-independent and time-dependent environ­ ments and the hidden features to be discovered can be quite complex in principle (previous discovered features can be used to discover new features), it depends heavily on the constructors that are given. For example, if * is not given, no features like torque can be discovered. In the future, we hope LIVE will start with a parsimonious, domain independent set of primitives from which neces­ sary constructors like * can be constructed during the interaction with environment. Some early results along this direction have been reported in [Shen, i989a] .

7 Solving the Low-Level Tower of Hanoi

In this section, we complete the description of how LIVE learns a set of correct and useful rules in the Tower of Hanoi environment. We call it low-level, because LIVE's innate percepts and actions do not include high-level concepts and actions that previous studies have used. In this environment, no matter what the initial state is , LIVE always creates a set of good rules (different rules may be learned in different runs) and reaches the given goal state. In the run we have been talking about so far, it takes LIVE 35 steps, including both actions and proposing subgoals, to solve the problem. We have ex­ plained how RuleO through Rule3 are created. In the later stage, LIVE meets three more surprises, the first surprise comes when it tries to pick up a disk when an­ other disk is in the hand, which splits RuleO into RuleO and Rule4; the second surprise comes when it tries to put a bigger disk on a smaller one, which splits Rule3 into Rule3 and Rule5; the third surprise comes when it tries to pick up a bigger disk underneath a smaller disk, which spilts RuleO into RuleO and Rule6. The following is a list of all seven rules learned by LIVE:

Condition: (on diskx pegx) 1\ -.3(in-hand disky)

1\ -.3((size> diskx diskz) 1\ (on diskz pegx))

Action:

(pick diskx pegx)

[RuleO)

Prediction: (in-hand diskx) 1\ ·(on diskx pegx)

Condition: (in-hand diskx) 1\ -.:J(on disky pegx)

Action:

(put diskx pegx)

[Rulel)

Prediction: (on diskx pegx) 1\ ·(in-hand diskx)

Condition: (size> diskx diskz) 1\ (on diskz pegx)

1\ (in-hand diskx) 1\ (on disky pegx)

Action:

(put diskx pegx)

[Rule2)

Prediction: (in-hand diskx)

Condition: (in-hand diskx) 1\ (on disky pegx)

1\ -.:J((size> diskx diskz) 1\ (on diskz pegx))

1\ ·(size> diskx disky)

Action: (put diskx pegx)

[Rule3)

Prediction: (on diskx pegx) 1\ ·(in-hand diskx)

Condition: (on diskx pegx) 1\ (in-hand disky)

Action: (pick diskx pegx)

[Rule4)

Prediction: (on diskx pegx)

Condition: (in-hand diskx) 1\ (on disky pegx)

1\ ·::!((size> diskx disky) 1\ (on diskz pegx))

1\ (size> diskx disky)

Action:

(put diskx pegx)

[RuleS]

Prediction: (in-hand diskx)

Condition: (on diskx pegx) 1\ ·::!(in-hand disky)

1\ (size> diskx diskz) 1\ (on diskz pegx)

Action:

(pick diskx pegx)

[Rule6]

Prediction: (on diskx pegx)

Note that because of the order of exploration, dis­ cussed in Section 5, some rules, such as Rule3 , are not as perfect as others, such as RuleO. The conditions (on disky pegx) and ·(size> diskx disky) in Rule3 are not necessary. Nevertheless, the rules taken together com­ pose a good set for LIVE to solve any problems in the low-level Tower of Hanoi environment.

8 Discovering Genes

To demonstrate how LIVE discovers hidden features, we give it the task of discovering genes by hybridizing gar­ den peas as Mendel [1865] did. For simplicity, a pea is initially denoted as pi( color), where i stands for its gen­ erat ion and j stands for its identification, and we assume that a pea's color, green as 1 and yellow as 0, is its only observable feature. The system is given one action: arti­ ficial f ertilization , or AF(peax, peay ) , which we assume produces exactly four children peas and distributes the parent's genes evenly into the children. Two predicates: = , >, and three functions: U (bit-or), n (bit-and), and an even distributed pairing function e-distr((a b) (c d)) = ((a c) (a d) (b c) (b d)), are given as constructors. If there were a large set of constructors, LIVE might of course have to make a lengthier search, but the present set will illustrate the process. From the system's point of view, the task is no more than predicting the effect of its action.

The experiment starts with a set of purebred peas, P\(0) , ?i(O), Pj(1), PJ(1) , PJ(O) , PJ(1), P}(1) , and P8 ( 0) , as the first generation. All their ancestors are known to have the same color. To make the sec­ ond generation, the system fertilizes yellow with yel­ low, green with green, yellow with green, and green with yellow. When applying AF(?l(O), Pi(O)) (with no prediction), the system observes that all the off­ spring, P[(O) , Pi(O) , Pj(O) and P1(0) , are yellow, and constructs a new rule:

This rule predicts correctly that the hybrids of green ~~(1) with green PJ(1) will be all green: P{(1), PJ(1), P7 (1) , P?(l), but fails to predict that the hybrids of yellow P5 (0) with green PJ(1) will be all green too: PJ(1 ) , Pf0(1 ) , Pf1 (1), P[ 2 (1). The incorrect prediction is made because c; is bound to yellow. This surprise causes the system to compare this application with the last one (green with green) , finding a difference that c; = Cj was t rue previously but is not true now, and splits Rule1 in two:

Condition: Pt(c;) 1\Pja(cj) 1\·(c;=cj)

Action: AF(P;(c;), Pj(cj))

[Rule2]

Rule2 is then applied to predict that all hybrids of green P}(1) with yellow PJ(O) will be yellow (because Cj is bound to yellow) , but the result is again a surprise: all Pf3(1), P[4(1) , Pf5(1) , Pf 6 (1) are green. After compar­ ing the two cases, the system concludes that the reason for the surprise is c; > Cj (> is a given relational pred­ icate) , and splits Rule2 in two to reflect the fact that green dominates yellow, and that ends the second gen­ eration:

Condition: Pt( c;) 1\ P/( Cj) 1\ ·( c; = Cj) 1\ ·( c; > Cj)

Action: AF(P;(ci), Pj(cj))

[Rule2]

Condition: Pt(c;) 1\Pl(cj) 1\ ·(c;= cj ) 1\ (c;>cj)

Action: AF(P;(c;), Pj(cj))

[Rule3]

The third generation of the experiment is made by self-fertilizing the second generation. We assume the pairs to be hybridized are: (Pl(O)?i(O)) , (?i(l)Pi(1)), (PJ(1)P[0 (1)) , and (P[3(1)P14(1)) . Rulel successfully predicts the results of the first two pairs, which produce (P1 3 (0)Pf(O)Pff(O)P~(O)) and (Pf(1)P~(l)P.f(1)Pl(l)) respectively. However, the hybridization of the third pair surprises the system because the children have dif­ ferent colors: (Pi(l)P 1 3 0 (1)Pl 1 (1)P 1 3 2 (0)) . In explain­ ing the surprise, the last application (the second pair) is brought in to compare with the current application, but the system fails to find any relational difference be­ cause both pairs are green. This is a point where hidden features must be discovered. Since the experiment is time-dependent, LIVE traces back in history for previous difference states. Fortunately, a difference is found when comparing the parents of the second and the third pair: c; = Cj was true for (Pi(1)PJ(1)) 's parents [Pj(1)PJ(1)] but not for (PJ(1)Pf0(1))'s parents [PJ(O)PJ(1)] . This difference indicates the existence of two hidden features from the grandparents, denoted as m and fin the follow­ ing, that are invisible in the parental generation but are necessary to determine the grandchildren's color. The representation of the pea is then extended to include three features : (color, m , f) .

As we noted before, two things must be done at this point in order to use the hidden features . One is to figure out how m and fare related to the color feature , and the other is to figure out how m and f are inherited through the action. For the first task, since we know color is determined by m and f, and we know many examples (because the first generation peas are purebred): Pf(O 0 0) , Pj(l 1 1) , Pi(11 0) , P[ 3 (1 0 1) , etc. , it is straight­ forward to search through the constructor functions and see that color= mUf , i.e. 0=0UO, 1=1U1, 1=1UO, and 1=0Ul. In Mendel's words , the dominant determines the color . For the second task, since we know that parents'

m and fare inherited into all four children's m and f, and we have the examples of how the third generation is produced from the second generation (where surprises arise):

Searching through the constructor functions, we find that e-distr fits the data. Based on the answers to these two questions, Rule1 is now split into the following two new rules:

Condition: Pt(c; m; /;) 1\Pja(cj mj /j) 1\ (c;=cj)/\(m;=/;)1\(mj=fj) Action: AF(Pt(c; m; J;), pja(cj mj /j)) [Rule1] Predict: p:+ 1 (m;Umj m; mj) 1\ Pt+ 1 (m;U/j m; /j) 1\ p::,+ 1 (J;Umj f; mj) 1\ p::,+l (f; u /j f; /j) Condition: Pt(c; m; /;)1\Pj(cj mj fi) 1\ (c;=cj)l\ ·(m;=f;)l\·(mj=fj) Action: AF(Pt(c; m; /;) , pja(cj mj fi)) [Rule4] Predict: p:+ 1 (m;Umj m; mj) 1\ Pt+ 1 (m;U/j m; fi) 1\ pa+l(f·Um· f · m ·) m ' J ' J 1\ p::,+l (f; Ufj f; fi)

When Pl 3 (1 1 0) is hybridized with P[ 4 (1 1 0), Rule4 predicts correctly that among four children, three will be green and one will be yellow. After three generations of hybridization, as in the experiments Mendel reported in his paper, LIVE has discovered the hidden features, genes.

9 Conclusion

In this paper, the problem of learning and problem solv­ ing in new environments is specified as a problem of cor­ relating a learner's percepts and actions and inferring the rules from the given environment . A discrimination­ based learning method is invest igated that creates gen­ eral rules by noticing the changes in the environment, and then specifies the rules by explaining their failures in prediction. The method has two distinct characteristics. First , when an over-general rule is split , the method will keep both new rules for further development . Second, when the discrimination process is unable to find any difference between a success and a failure , the method will define hidden features in terms of existing or histor­ ical features. We have been investigating the method in several very different domains and further studies are fo­ cusing on applying it to more complex exploration tasks and learning problem solving strategies.

Acknowledgement

We thank Jaime Carbonell, Tom Mitchell , Chuck Thorp and Jeff Schlimmer for their valuable comments, and Klaus Gross for the suggestion of using Mendel's discov­ ery as a testing domain. We also appreciate the support from the World Modelers project upon which LIVE is originally developed.