State Space Models of Remote Manipulation Tasks

Introduction and Problem Statement

Remote manipulation involves a human opera­ tor and a machine together performing a task which could be performed more easily and effi­ ciently by the man alone, were the task or its en­ vironment not too large, small, distant, ponder­ ous, delicate, obscure, dangerous or some combin­ ation of these. Manipulators are used in quite complex hot lab experiments,l7 for underwater re­ trieval, for complete operation and maintenance of large radioactive research installations for extended periods of time,S and in robot research,ll to name a few examples.

To overcome the handicaps of time, scale or distance barriers, two lines of research have de­ veloped which involve combining a manipulator and a computer. One is the Human Supervised Remote Computer~anipulator,l4 depicted in Figure 1. Here, a human operator is aided by the computers in planning and executing the task. The other approach is the autonomous robot, which is intended to maneuver and ma~ipulate unaided in a dis­ tant environment.ll,l Major problems in the design of human super­ vised or autonomous computer-manipulators are

*Work supported by NASA Grant NsG 107-61

1. Model and real world of hands, objects and obstacles.
2. Define the notion of manipulation task.
3. Develop methods which generate plans of manipulative action which are relevant to the task environment (as modelled in 1)) and which are capable of achieving the stated goal (as expressed in 2)).

To solve these problems, we shall consider the manipulator's hand and the task site as a sys­ tem to be controlled by-;n operator or other in­ telligence. This approach differs from previous worklO,lS in which only the hand is included in the system model. A state vector is defined, containing not only variables which describe the manipulative device, but also vital parameters of task site, possible including locations of rele­ vant objects and obstacles. This vector, suitably quantized, spans a discrete state space whichcon­ tains many different static configurations of the manipulator and the objects to be manipulated. A manipulation task is then defined as a new state which the "operator" (human or computer) wishes the manipulator-objects-obstacles system to occupy. State transitions are accomplished by commands: quantized basic motions of the manipulator's jaws plus grasp, release, push, twist, and so on.

One may interpret the resulting problem in Modern Control theory terms as follows: given that each state transition costs a known amount, find the cheapest (shortest) path from the pre­ sent state to the desired state. This path re­ presents the optimal control policy for accom­ plishing the given task.

Alternatively, one may view the state space in terms of problem solving or theorem proving: each state transition represents an instance of a predicate or an axiom such as "If the jaws move one inch to the right, then the new state is re­ lated to the old state by. · · , " or "If the jaws are grasping object A and the jaws move one inch to the right, then object A moves the same dis­ tance and the new state is related to the old state by ··· " Each instance is specified by ar­ guments including the current state, the name of a relevant object, and so on. Since the problem is purely geometric, the result of applying any axiom or predicate is unambiguously related to the goal. The resulting path may then be thought of as the solution to the problem (or the proof of the theorem) "Can the specified task be accom-

Tasks and Commands

At the outset we should distinguish two types of tasks, those which can be planned ahead and those which cannot. An excellent example of the latter is the task "Find the pencil." Execution cannot be planned open loop, along the lines of: Move jaws to location X, pick up pencil. Rather, execution consists of continual interaction be­ tween the manipulator-computer and its environ­ ment. The type of plan needed closes a loop through the manipulator's sensors, and has many of the features of a numerical algorithm rich in "If" statements. Such problems have been studied by Ernst4 and Barberl. Larson and Keckler21 have used Dynamic Programming to find search and motion strategies for a robot in an unexplored environ­ ment.

Aside from searches and other tasks whose history and outcome are almost unknown ~ priori, most manipulation tasks can be planned out in ad­ vance. The likelihood of the plan's success de­ pends greatly on the accuracy of ~ priori infor­ mation concerning location of named places and objects, and also on plain luck. Less than cer­ tain success is not, however, any reason for not planning. It is the ability to formulate and at­ tempt execution of plans that makes an automatic or semi-automatic manipulator different from and superior to a manually controlled manipulator. Furthermore, lack of certainty in the ~ priori information can be compensated for by execution routines which combine obedience to the plan with minor-range searches. Greater sophistication in the execution routines will allow more uncertain­ ty in the ~ priori information without degrading the certainty of overall task completion.

Of all tasks which can be planned out in ad­ vance, we shall consider what for ordinary mani­ pulation constitute the great bulk, namely those in which the positions or orientations of objects and effectors (jaws, tools, etc.) are changed. Thus we specifically exclude such activities as bouncing a ball or balancing a stick on end. By ignoring velocities and accelerations, we may con­ centrate on the geometric constraints fundamental to manipulation: obstacle avoidance, rendezvous of a jaw-borne object and its destination for pushing, releasing, pouring, inserting, and so on. (Granted a jaw-borne object has a velocity: nev­ ertheless what is important about carrying is that jaws and object maintain a fixed geometric relation to each other throughout.) Then one may state the planning problem as that of finding a sequence of intermediate configurations for the task site to occupy on the way, so to speak, from the initial configuration to 1the desired one.

To enable the computer to solve such prob­ lems, we must equip it with a model of manipula­ tion tasks so that it can determine what config­ urations may follow from a given configuration, or equivalently what changes can be made to a given configuration. This requires a way of ex­ pressing geometric constraints or equivalently manipulative predicates and how they are altered by changes in the task site. More generally, we must recognize that some configurations are "near neighbors" while others are not, but rather are separated by one or more intervening configura­ tions, some of which are near neighbors. Near neighborliness of two-configurations may be de­ fined as a (usually bilateral) attribute imply­ ing that one single simple motion of the mani­ pulator jaws, probably of limited extent, will carry the task site from one configuration to the other. Working with a small, well chosen set of such submotions, we can plan a wide variety of tasks. To be precise, call the submotions atomic commands. For example:

Close jaws

In what follows we shall describe a method by which a task site may be modelled, the "operator" may request a task, and the computer can devise a sequence of atomic commands which, to the de­ gree of precision of the task model, can accom­ plish the task.

The State Space Model

The problem we have posed is to find a se­ quence of finite elements which has a particular property. We may dispense with enumeration of the possibilities, since there are far too many, and far too few of them are worth considering.

Let x be a vector containing the position of the manipulator jaws, the positions of rele­ vant objects and any other variables of interest, such as object orientations. Then the manipula­ tor-task system is governed by the equation

lvhere u(k) is a vector of admissible controls such as equation (1), and A is a state dependent matrix which expresses the geometric task con­ straints mentioned in the previous section. These constraints are more easily visualized on a finite graph3 in which each node represents a state x and each branch leading out to another state In­ dicates an allowed command at state x. States connected by a single branch are thus near neigh­ bors. The totality of nodes, some connected by branches, constitutes the state space. Its nodes represent all the configurations which the task site can assume as a result of the execution of arbitrary strings of atomic commands. Alterna­ tively, the state space represents the limited set of instances of the manipulative predicates being considered, the instances differing in the arguments associated with each, and the set bounded by the limits on each state variable. We may then say that paths through the space repre­ sent strings of atomic commands (controls or proof steps) which make coherent (though not necessarily purposeful or efficient) changes in the task site. For example, consider the task site in Figure 2. The jaws may move from point to point along the line, open and close, but may not move the block. (This last capability is added below.) Given the atomic command set (1), the state space corres­ ponding to Figure 2 is shown in Figure 3. The coordinates on the axes are xf, jaw position, and H, jaw status. xy and H are the state variables. The configuration of Figure 2 (jaws in location 4, closed) is represented by the flag at state [4,1] in Figure 3. The vertical lines indicate that the jaws may open or close at any x, while the horizontal lines indicate allowed jaw move­ ment. Movement directly into [2,1] from [3,1] or [1,1] is forbidden since this would involve col­ lision between jaws and object. Thus [3,1] and [2, 1] are~ neighbors in the sense defined above.

If we wish the jaws to move to location x·l, jaws closed, we ask the computer to find a satis­ factory path from state [4,1] to state [1,1].* (Naturally we want the computer to derive by it­ self the fact that the jaws must straddle the ob­ ject on the way.) Such a path, if it exists, can be translated immediately into a string of atomic commands suitable for accomplishing the task, since the path tells the sequence of neighboring intermediate configurations through which the task site should pass on the way to the desired con­ figuration. There are countless possible paths, most of which go nowhere purposive. But a short­ est path cannot go nowhere and in particular can­ not loop. So let us find shortest paths.

Many algorithms are available for finding shortest paths in net1vorks, among them Dynamic Programming,2 Ford's algor~thm,6 and the Hart­ Nilsson-Raphael algoritl~. ** Of more interest to us is the general interpretation we can give to "shortest": A path may be short in time, fuel, risk, lack of information, or some (normalized) combination of these, for example. A state space may well be costly in fuel all over, but costly in risk only in certain areas. Sometimes a given command, like carrying, is costly everywhere, while at other times the cost of a command may depend on the state at which it is being executed (for example, carrying through a crowded region of phy­ sical space). By specifying the dimension, mag­ nitude and distribution of the''l.engths" of lines between points in the state space, the operator

*Suitable computer routines can generate the value of the desired state from a less formal­ ized input command, such as "Go to the left of the object."

**For tasks at the complexity level considered here, this analytic approach seems superior, in terms of computer time and likelihood of success, to similar work employing Heuristic Programming to elicit strategies.l6

can to some degree affect the nature or "style" of the resulting solution. The arrangement of lengths shown in Figure 4 results in the path in­ dicated by the arrows. (This schedule of lengths suppresses unnecessary motions of the open jaws.) The corresponding work plan is:

Move left one inch Open Move left one inch Move left one inch

Close

A path which allows the jaws to grasp the object is shown in Figure 5. The corresponding path for the case where the object is in loca­ tion x·l is shown in a new state space in Figure 6. By making the object's location a new state variable, y 0 , we may represent carrying and push­ ing in a larger state space, Figure 7. This figure is made by combining Figures 5, 6, and others like them, each corresponding to a parti­ cular value of y 0 · Note that pushing is not ex­ pressed as a transition analogous to that from [3,1] to [2,1] in Figures 3, 4, and 5, for ex­ ample. This type of state transition is still forbidden since it tells nothing about what hap­ pens to the pushed object. Pushing is properly expressed in Figure 7 as a variation of carrying.

Physical Demonstration

The ideas of the previous section were im­ plemented on a three degree of freedom manipu­ lator converted from a plotting table. Square objects could be grasped and moved about in a re­ gion 15 inches on a side. The manipulator jaws were equipped with grip sensors inside and con­ tact sensors outside. No jaw rotations were pos­ sible. A Digital Equipment Corp. PDP-8 computer contained a 2000 word program and a 500 word state space.* The state vector consisted of (XJ, YJ· H), while objects and obstacles were kept track of in a separate list. The 2000 word program con­ tained all I/O, a path finding algorithm, touch sensor evaluation routines, stepping motor control, plus interpretation of commands such as

operator designates object at (x,y) with name. pick up object with name. take it to location (x,y) go to location (x,y)

If a new object was discovered by the touch sen­ sors while a path was being executed, the system estimated its location, asked the operator for a name and then computed a new path to the original goal, incorporating knowledge of the new object. This object could be referred to later by name, picked up, carried, and so on. A more complete description appears in 18

*Twelve bits per word.

A More Complex Example

Suppose we wish to move a long thin spar through a crowded two-dimensional environment. (Picture carrying a sofa from the living room to the porch.) Here the interactions between the en­ vironment and the spar's position and orientation are of the most interest. To map motions of the spar once it is grasped by a rotating pair of jaws, we choose state variables

x · x coordinate of spar, y · y coordinate of spar, a · orientation of spar .~o if spar is parallel 1 !S._X 1 ~y to x ~ 5 ~ 3 axis

a ~1 if spar is parallel to y axis

The allowed commands are

Move ± x direction one unit Move ± y direction one unit

Rotate 90°

Thus both position and orientation of the spar are quantized.

The physical space is shown in Figure R. Walls are shown as open rectangles, while the two possible orientations of the spar are shown by cross lines at each possible position. The chal­ lenge is provided by the doorways, which allow the spar to pass axially but not athwart. This con­ straint and the presence of walls are shown in the state space by deleting the lines corresponding

to the forbidden transitions.

The state space appears in Figure 9. We as­ sume for illustration that each "move" is of length 2, each "rotate" of length 3. Let the spar be initially at location (2,2) in the physical space, oriented parallel to the y axis, and say we want it moved to (3,3), ending up oriented parallel to the x axis. Then the initial state is [2,2,1] and the final state is [3,3,0]. These are marked Start and End, respectively, on Figure

9.

There are two equal length solution paths, shown in Figure 10 and visualized on a sketch of the task site in Figure 11. These paths do not "look like" the most direct route. Closer exam­ ination, however, reveals that these paths, by initially moving the object away from the final state, are able to save two rotations by spending a little more distance. Again, if we read a solu­ tion path, we get a list of the required moves and rotates in the correct order. A more general solution to this problem which includes grasping and releasing the spar in arbitrary (quantized) positions and orientations, may be found in Chap­

ter V of Reference 18.

Discussion of the State Space Model and its Implications

The main feature of the State Space Models above is their quantization. This is a direct consequence of the kind of atomic commands we al­ low and of our interest in the main motion fea­ tures of tasks for planning purposes. The atomic commands may be thought of as task differentials, but ultrafine quantization is neither practical nor necessary, especially if good sensors .· are available. In fact, since more complex tasks re­ quire, in principle, state spaces of higher di­ mension, quantization poses staggering computer storage problems. (6 state variables, 10 points per axis · 10 6 points.) Three factors mitigate such difficulties:

1. Only a handful of these points need be in live (core memory) storage at any one time. In fact, the problem of finding shortest path-s is, by default, one of State Increment Dynamic Pro­ gramming,9 which latter may be greatly speeded by algorithms such as that of Hart, Nilsson and Raphael, which pursue only the currently most promising path.
2. The state space need not be built and held whole and intact in storage, but rather only those sections needed as a particular path is pursued. The state space is just a logical con­ sequence of a list of object and jaw locations, sizes and orientations, plus -extremely local "know­ ledge" of what circumstances prohibit a given com­ mand. The needed portions of the state space may be built to order, using the information in the list. Then, merely by concentrating on one state and its immediate neighbors at a time, the com­ puter can plan tasks which involve hundreds (or any number) of states. In most algorithms, more­ over, progress is monotone so that a state, once considered, is never considered again. These no­ tions suggest that the state space is a list and that list-processing computer languages may be useful in dealing with it.
3. A state space describing a complex task is of high dimension only because the space stores the relations for all tasks which could be per­ formed by manipulating the objects and jaws in question. No command, however, asks for all tasks, and because rearrangement tasks consist of re­ peated sequences such as "Move empty jaws to lo­ cation X, grasp, carry object to location Y, re­ lease," it should be clear that only the state variables actually involved in one such sequence need be considered variable at one time. This is obviously equivalent to considering only a limited and much lower dimension cross section of the ori­ ginal space. Great savings in computer time and storage may be effected by treating sequences of such cross sections, indeed considering them as atomic actions on a much higher level than the atomic commands which underlie them. We are thus afforded two levels of planning, an upper level in which gross motion goals are selected, and a lower level in which detailed strategies for such motions are evolved and their costs evaluated. Thus we can consider more complex tasks without recourse to -unmanageable state spaces. In this way, competing gross plans may be judged for cost­ effectiveness and the best one (for the given cost structure) selected. It is worth speculating that

methods of Heuristic ProgrammingS would be useful at the higher level, but some comparisons 19 show that for actually finding detailed paths, even the relatively inefficient Ford algorithm is greatly faster than Travis·l6 heuristic path finding

methods.

Extending the Power of the State Space Method

Now we have reduced some basic manipulation tasks to shortest path problems. In this section we show how to make use of the basic pick-up-and­ carry capability demonstrated in Figure 7 to pro­ gram more complex tasks without recourse to enor­ mous state spaces, preserving the "operator's" ability to shape the general features of the re­ sult without having to specify details.

We think of commands as functions whose ar­ guments (specified by the operator) may be place or object names, and whose values are paths in one or more related state spaces. The basic func­ tion "Take" is evaluated by a state space such as Figure 7. Formally:

Take (A,X,Y) · carry object A to location X, leaving the jaws in location Y (3)

To exchange objects A and B, we may use "Take" to define "Switch", using an appropriate interpretive computer language:

in which "+" means "followed by", X is a loca­ tion between A and B (chosen by the "operator"), Y is a location near X, A' is A's old location and B' is B's old location. Switch may be "opti­ mized" if we allow the operator to define fuzzy areas X andY in which points X andY, respectively, are to-be sought by the computer so as to achieve minimum total task length:

in which /xi1 and lYj J~enote_the sets of locations comprising regions! and! respectively.

The evaluation of (5) requires the establish­ ment of a tree representing the result of choos­ ing each xi and Yj· the fre~ subgoals. S~e Figure 12, in which we let ! · x1 ,x2 and! · Y1· y 2 · The cost of an arc on the tree is deduced by cons.tructing a state space similar to Figure 7 (simpler alternatives using even lower dimension spaces may also be used20) and finding the length of the shortest path which does the required job. This space, consistent with remarks in the previous section, may be thought of as a cross section through a much larger space, which we never bother to construct. In this way, only those subtasks which the "operator", in his greater wisdom, thinks are worth considering will actually be evaluated · . When all the possibilities in X andY have been priced, the cheapest xi and Yj may be chosen, completing the evaluation of (5).

The advantage of (5) over (4) is that the "operato.E_" nee~ not have precise knowledge con-_ cerning X and Y in order to request a switch. X and y correspo~d to the statement "over there some­ where", a convenient sort of statement to be able to make. In a working system, one could make this statement by py~nting one's finger, a light pen, a Lincoln Wand or similar I/O device at the task site or a representation of it on a TV or CBT screen.

Function definition is an obvious way of in­ creasing the manipulative capabilities of a com­ puter-manipulator. We may build layer on layer, using the existing functions to define new ones. We have a way of telling the computer "how" to do new tasks, such as assembling involved structures or making complex selection and ordering of sub­ goals. As an example of the latter, consider the task site in Figure 13. Two objects block a nar­ row doorway. We wish to move object A to location X. Both blockers must be moved from the doorway before A can be carried through. It is possible to define a recursive function which enables the computer to decide, on the basis of minimum total length, which blockers to move, the order in which to move them, and where to, in order to get A to X. The operator, when defining the function, says in effect, "These are the blockers, here is a region where they m!ght be put; move A to X." If the cost of a unit move empty is one, the cost of a unit carry is two, and no diagonal moves are al­ lowed, then the tree corresponding to the evalua­ tion of this function is shown in Figure 14. The cost shown on each arc of the tree is deduced from a two dimensional state space based on the appro­ priate version of Figure 13. 53 such evaluations are required, employing vastly less computation and storage than the general 8 dimensional space which could be defined. The two equal length so­ lution paths differ only in that B1 and B2 exchange roles. This problem is discussed more fully in Chapter V of 18.

Conclusions

The state space method has been shown to be capable of describing a wide variety of the logi­ cal and physical constraints which comprise mani­ pulation. Using it, we can plan some non-trivial tasks and gain insight into the nature of tasks and commands. Combined with a flexible input language and carefully composed execution routines, it can provide a basis for Supervisory Controlled

or Autonomous manipulation.