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.)

Abstract:

(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)