Diffy-S: Learning Robot Operators from Examples of Operator Effects

Carl M. Kadie

Microsoft Research
Redmond 98052-6399, WA

Author Email: carlk@microsoft.com

In physicist Richard Feynman's Lectures on Physics (1963), he says:

What do we mean by "understanding" something? We can imagine that this complicated array of moving things which constitutes "the world" is something like a great chess game being played by the gods, and we are observers of the game. We do not know what the rules of the game are; all we are allowed to do is to watch the playing. Of course, if we watch long enough, we may eventually catch on to a few of the rules. The rules of the game are what we mean by fundamental physics...If we know the rules we consider that we "understand" the world.

The Diffy-S program tries to learn chess rules from watching play. (CCSC, a later algorithm, does try to learn a bit about the physical world from observation.)


(Master's. Thesis, U. of Illinois. David C. Wilkins, Advisor)

The research presented here focuses on inductively acquiring new knowledge for robots. The thesis introduces, Diffy-S, a system that learns the behavior of robot operators from examples of their observed or desired effects. The outputs of Diffy-S are hypothesis operators that model these effects. This model can be used to predict the results of a sequence of robot actions, and thus, is useful to a robot that wishes to plan its actions intelligently. The complexity of the knowledge that can be inductive acquired-in the form of nested functional expressions-exceeds that of extant systems for operator learning.

In the first part of the thesis, the operator-effect learning problem is presented and a useful representation for operator-effect learning problems is introduced. Next, the algorithms of Diffy-S are detailed. These algorithms solve operator-effect learning problems by combining top-down explanation-based methods with inductive methods. The latter part of the thesis describes a series of thirteen empirical tests in the domains of block movement and (Chinese and standard) chess-piece movement. The tests show that Diffy-S is an effective learner. Finally, the performance of Diffy-S as a function of learning-problem complexity is analyzed and directions for further research are identified.

Technical Report UIUCDCS-R-89-1550, Department of Computer Science, University of Illinois, Urbana, IL, October 1989. (postscript)