Manipulation Extrapolation: A System for Controlling Trainable Robots

1. INTRODUCTION

When training another human, we frequently dem­ onstrate, by example, how the first few of a sequence of similar problems are solved. The trainee induces a program from such a demon­ stration. For example, a program to insert shims in an assembly might be as follows:

1. Test fit and exit if within tolerance.
2. Select largest shim not overcompensating.
3. Insert selected shim. Go to step (1). An industrial trainee would likely learn this by repeatedly
4. observing the initial state of an assembly.
5. observing a sequence of actions by a train­ er which modify this state. And perhaps,
6. hearing comments such as, "Always use the largest shim possible."

This paper proposes a model for such an inter­ face between a human trainer and a computer. The most general context, program synthesis, is employed. The input for the i-th problem is assumed to be as follows:

1. an initial state, si, of data in the memory of a computer.
2. an execution trace, ti' of a hypothetical program to be induced. This is the sequence of instructions executed by the program in transforming si to a final state, from which control commands are deleted. And perhaps,
3. identification by the trainer of those var­ iables of significance at decision points. This reduces combinatorial explosion and is not required by the example to follow.

A training sequence, as follows, is assumed: TN= ((sl,tl),(s2,t2), .. · ' (sN,tN)]

2. MANIPULATION EXTRAPOLATION

The process to be presented will employ two subsystems, both well-detined in the liter­ ature elsewhere. Grammatical inference, the problem of inducing a grammar from a sample of sentences, is solved by a variety of pub­ lished methods for regular languages [4]. One by the author has convergence character­ istics especially suited to this application [1]. The calculation of discriminant func­ tions for numerical vectors has also been extensively studied [2]. An algorithm for the linear functions sufficient for the fol­ lowing is found in [5]. More general poly­ nomial functions may use linear 2rogramming as demonstrated by the author [lj.

2.1 The Process

In the following, G is a formal grammar in­ duced to generate the set of execution traces. Alternative productions in this grammar (pro­ ductions with identical left parts) are selec­ ted by discriminant functions defined over the set of partially transformed states occurring at the associated point in the calculation.

The process is specified in detail by speci­ fying the inference procedures to be used for G and the discriminant functions. This is done in (1) where convergence is established.

A micro--processor controlled manipulator is envisioned, communicating interactively with a large computer where its program would be

induced as follows;

1. INITIALIZE: Set grammar, G, to generate the empty language, T 0 = nil and i = 0.
2. INCREASE SAMPLE: Set i = i+l and Ti a Ti-l U [(si,ti)]
3. TEST G: If ti is in the language gener­ ated by G, BP to step 4.
4. INFER GRAMMAR: Reform G to generate at least tj j·l,2, ... ,i and go to 5.
5. TEST STATE DISCRIMINATORS: If discriminant functions involved in processing si select the correct path to generate t ,go to 1.
6. COMPUTE DISCRIMINANT FUNCTIONSf Reform discriminant functions for each set of pro­ ductions altered in step 3 or found to be improperly selected in processing si. Go to 1.

3. ILLUSTRATIVE EXAMPLE

The computation of N-factorial will provide a simple illustration. Let the data state con­ sist of two elements, (xl,x2), with xl initial­ ized at i-1 for the i-th problem (the compu­ tation of (i-1)-factorial) and let x2 be ini­ tialized at 1. Associated with each such starting state will be the shortest sequence of instructions possible to transform x2 into the factorial of the initial value in xl. The training sequence for the first three problems is as follows:

Each t 1 will be treated as a 'sentence' over the 'alphabet' of commands shown in figure 1.

CHARACTER

INTERPRETATION

Figure 1: EIGHT 'CHARACTERS' IN ALPHABET OF G

A grammar generating this language, {nil, load-xl-store-x2}. is shown in figure 2. The language is more concisely represented using the numbers of the commands in figure 1, {nil,l4}, instead of the commands above.

<start> : := < 1 > <1> : := < end > <1> : := < 2 > <2> : := load-xl-store-x2 <end>

The fourth and fifth problems yield the training sequence:

Each of these new sentences is found to be absent from the language generated by the grammar induced from the precedi.ng training s e­ quence and a new grammar is induced. The re­ sulting grammar induced from T 5 is shown in figure 3. This grammar will .be seen equivalent to the flowchart in figur e 4 . It generates a solution for each of the infinite set of prob­ lems, N-factorial for N=O,l,2, ... . Branches in the flowchart correspond to alternative pro­ ductions in the grammar. These must now be associated with discriminant functions to transform this grammar into a program.

Figure 5 shows the data states associated with each of the branch points in the flowchart. Each of these sets of states is dichotomously partitioned into mutually exclusive subsets associated with a particular alternative pro­ duction in the grammar. A linear discriminant function, F(xl,x2) = A*xl+B*x2+C, is adequate tor both branches. For branch 1, (A,B,C)=(J,-2,-2) will cause F(xl,x2) to be negative for states associated with rule, <1>: := <end>, and posi­ tive for states associated with its alternativ~ <1>: := <2>. For branch point 3, ~,B,C)=(2,0,-5) will similarly select the correct 'sentence' for each problem. An algorithm exists, guar­ anteed to find such linear separators if they exist [5].

3.1 Interaction with Trainer

Trainees often ask questions. Some grammati­ cal inference methods use· interroRation to de­ termine sentences to be excluded from the language generated by the grammar. This is not appropriate to the application represented here and the grammar inference process used in [1] avoids a need for this by assuming that the training sequence contains all sentences shorter than the longest sentence present. The trainer would, however, likely have insights about which variables in the state vector are irrelevant at decision points. Interrogation of the trainer for this purpose, while not yet implemented, would greatly reduce the complex­ ity of the discriminant function calculations.

4. CONVERGENCE

While flowcharts are equivalent to regular grammars, execution traces, representing a subset of all possible paths through the flow­ chart, are often a proper subset, selected by predicates at decision points, and are not regular languages. The regular grammar induced from such execution traces will, in general, generate a language larger than the solutions to all problems under consideration. A con­ vergence criteria "approach from below," cap­ tures the notion appropriate here [1]. A ~en­ era! discussion of such convergence is in L3].

Convergence of the grammar inference process is necessary but not sufficient. Separability of states at decision points in the induced gram­ mar must be assured. The assumption that the training sequence could have been generated by a program with separable decision points is not sufficient since the induced grammar may be structurally dissimilar to the hypothetical generator.

A constructive grammar inference process de­ vised by the author has been shown to preserve polynomial separability under the assumption of the existence of such a hypothetical program (1). Polynomial separability is reasonably general but excludes some frequently used tests such as "branch if variable xis even."