Reasoning About the Spatial Relationships Derived From a RAPT Program for Describing Assembly by a Robot

Al\STRACT

The network reduction systen of RAP7, an offline object level language for progra~ming robot assen­ bly tasks is described in this paper. The task description is converted into a relational network with the positions of bodies as nodes, and rela­ tionships between positions as links. Rewrite rules based on the intersection and conposition of relations are used to si!":lpl ify the network.

l Introduction.

As versatile industrial robots cone into greater use, particularly for snall batch assembly, the ability to program the1~ offline hecones r~ore desirable. The RAPT language has been developed at the University of Erlinburgh for such progran­ ning of assenhly tasks.

ThP language allows the user to rlcscribe the task in a natural \my, in ten1s of surface features being in contact, and of notions of objects relative to each other. The grippinr, parts of na nipulators can he include rl simply as objects used in the task.

The transformation of this relational informa­ tion into the positional infon~ation necessary to drive a nanipulator is not a trivial task, and this paper is a description of the current system for doing it. This involves the reduction of a relational network, and was described in (Popple­ stone, Anhler & Bellas 1980b). An earlier system u s ed algebraic nanipulation, (Popplestone, Anhler & !lellos 1930a), and conparison will be nade with it.

Our system as implenent ed at present is con­ ple tely determinate - all positions are specified at compile time. Another paper at this conference (Yin 1933) describes how sensory information, in particular vision verification, can he incor­ porated.

This section can only give a brief outline of the input language; for a conple t e description sec (Popplestone, rulbler & gellos 1978).

-This paper describes work done in the Department of Artificial Intelligence at the University of Edinburgh supported by contract N2ll IR1019 fron the Science and Engi neering Research Council.

REASONING AJl<JlJT TilE SPATIAL RF.LATIOtJS/liPS DERIVED FRotl A RAPT l'ROG){Atl FOR OESCRIBUC ASS!~r!BLY ll':' ROBOT

Corncr,LJ.F., Anhlcr,A.P. and l'opplestone,R. J . llepartment of Artificial Intelligence, University of Edinburgh

In RAP!, each object is described in ten11s of a nm1her of surface features, e . g . planar faces, shafts (cylindrical faces) and holes.

At any stage of the asserlbly process, we have a situation ia which we can describe spatial rel a­ tions between objects, e . g .

AGAit!ST I FACE! OF llODYl, FACE2 OF llODY2 FITS I SIIAl'T OF BODY 1, HOLE OF llOUY2

An action statement describes the moveuent

between one situation and the next, e . g .

l!OV:: I BO iJYl

IIOVE I llODYl, PARLF.L , SIIAl'T Ol' llOUYl I!OVE I llOUYl, PARLEL , SHAFT OF tlOllYl, 100

Actions r~ay constrain the position of the body, e.g ., the second and third actions constrain the body position to be alonr, the axis of the shaft fron its previous position, the third action corl­ pletely deten~ines the final position relative to the start position. The first action inposes no constraints on the final position; it nust be de ten.li ned fron any subsequent spatia l relations.

The specification of a RAP! progran consists of a nunher of relationships between features of objects in different situations, and a nunher of actions. 1./e must solve for the position of each body in each situation . He call this set of posi­ tions a set of body instances, and we have a rel a­ tional network linking them. llithin any situa­ tion, body instances are linked by spatial rela­ tions; between situations the links are either action relations, or identity relations for sta­ tionary objects. The form of each link is identi­ cal, whichever type of constraint, and therefore situation and action relations can be mixed in any way to fonn the network. The task of the infer­ ence system is to reduce the network, and to determine the positions of each object.

A.

We represent the position of each hody instance as a 4x4 natrix which holds the origin and the orientation of the X, Y, and Z axes of each body. Body positions are defined relative to a world

frame of reference.

We use the post-multiplication convention of transfonnations to define positions transformed from the body position. Each feature of a body

can be represented by a transfonnation fron the body position, and therefore relative to the \Jorld fra111e transformation, can he expresseu of refe renee hy a

where ** denotes matrix multiplication, f is a feature transformation, and p a body position.

A relationship links features of two bodies. Corresponding to each relation type is a transfor­ nation function with a nunber of variable parame­ ters, representing the degrees of freedon implicit in the relation. 7he relationship states that the world position of one feature, transfontecl by this function, 11ith unknown values for the variable parameters, e<Juals the world position of the other feature.

is an exanple of a relationship linking features f 1, f2 of bodies in posit ions pl, p2 respectively, l<here v is a vector of n variables unique to this instance, and Rel is one of a set of relation functions. An example of such a relation is AGPP(x,y,theta)

representing the against relationship between two plane faces, with t;;o spatial and one rotational degree of frecdou.

Actions are represented by similar equations. If an action operates on a body to move it frrn~ posi­ tion pl to position p2, and the action is relative to a feature f, it can he represented by the equa-

tion

This is an e<Juation of the sane form as the equa­ tion derived fron a relationship, and the RAPT inference system docs not distinguish between

ther.t.

It is implicit in the description of actions that sane bodies in the system do not move during the action. This is encoded by making the posi­ tions of the body before and after the action equal.

The fundamental reduction step takes a pair of equations relating the same two positions

and combines ther:l to form a ne\i equation

Each expression is the pro~ct of one or more relation functions and feature transfonnations, and the vectors represent the variables. Expres­ sion) is derived from expression! and expression2, and v3 has at most the number of eler:~ents of the smaller of vl and v2, where v3 represents the remaining degrees of freedon..

The equation solving method solved the set of equations fran first principles, but it 1.1as real­ ised that since for most pairs of the relation functions Rel(~), there are standard solutions, this 1·as inefficient. The present method uses these standard solutions, and does not form the equations; these are implied by the fom of the relation. Thus, when a suitable pair of relations is found, the standard solution is applied, e.g., subject to certain constraints, fron the relations ACPI' between FAGr:ll of BOO'!l ,FACE21 of BOiJY2 AGPP bet11een FACI::l2 of BODYl,FACE22 of BODY2 the standard solution gives LPl bet1~een FEAT13 of BOUYl ,FEAT23 of BOOY2 LIN is a relation with only one degree of spatial freed on, and fEAT13, FEAT2l are genera ted as part of the standard solution.

tlot all pairs of relations have a solution. In sone cases there are two results, in others the relation ls not expressible as one of our set of relations.

D. FIX Relations.

A FIX relation is a special case, because the linking function is the identity function, with no variables, i.e. the equation becomes:

He have determined the position p2 relative to pl, so that whenever we have an equation in pl, 11c could transfom it to one in p2, or vice-versa.

\Je use a FIX relation to do a merge operation. \le choose one of the positions, say p2, and renove it fron our set of unresolved positions. \~e also transfonn any equation involving p2 into one involving pl. 1-nten, at a later time, we have solved for the position pl, we can transform it and so produce the position p2.

\.Je can only use our standard solutions 11hen we have two relations between the same pair of body instances. The nethod of chaining relations allows a solution in nore general cases.

Given a relation involving body instances A and B, and another involving body instances B and C, the two nay be chained together to form a new

relation between A and C.

The equation solver placed no lir:litation on chaining, since it could conbine

f21 ** p2 = Rell(vl) ** fll ** pl

to fona the equation

In a number of case~~- this can be simplified to the form

where Rel3 is one of the set of relation func­ tions.

When this simplification is possible, we can apply a standard chaining solution to the pair of

relations to form the new one.

!lot all pairs of relations can he chainecl; for sane, the result is not expressible as one of the set of relations, for others, there is no relation the input relations are too weak and the two bodies are unconstrained.

We could consider our operations, solution, chaining and mer"ing as a set of re1vrite rules. The so!ution operation is obviously a terminating operation. since it recluces the nunher of rela­ tions (equations) in the system. !lerginr, is also tenlinatin!:, since the nur.1her of unresolved posi­ t.ions is reduced.

Chaining by itself does not appear to be a ter­ minating operation, since it adcls a new relation to the set of relations. (It does not acid any new infon.wtion, since the inf ormation in it ·is con­ tained in the relations it was derived from). Because of this, we only use chainin!l to create temporary relations.

\/hen 1vc have a cycle of relationships: Relation between R1 ancl 82 Relation between R2 and 133

Relation between Bn-1 ancl Bn

Relation between Bn and 31

we can chain the first two to forn a relation between !H and llJ, use this to forn one between 81 and fl4, and so on until we have chained all except the last together to form a relation between B1 and Bn. We can uow apply our solution method to this and the final relation; if it gives a new relation, we can replace the relation between Bn and B1 with this new relation.

Since the result of our solution nethod has the same number or fewer degrees of freedon than either input relation, and we only accept the solution from the couhination of a relation formed by chaining with another if we have reduced the number of degrees of freedom, the net effect of the operation is to reduce the number of der:rees of freedon in the relations left in the problem.

With a crn1plex network of relations there can be a large number of cycles, many of which will be large, ancl for each cycle we can choose any of the body instances as a start point, and work in either direction. There is therefore a large search space. In practise, we restrict the size of the cycles to which we apply this method to a maxir.mn of four. This has been found to be ade­ quate. In addition, we defer cycle finding until there are no more solution or merge operations possible. If the processing of cycles has resulted in any FIX relations, merge operations can be per­ funned, with the consequent possibility tahe more pairs of relations appear.

In general, application of and the cycle our process consists of alternate the solution and merge operations, finding operations, until all the positions have been resolved, or until no further progress is possible.

G.

The cycle-finding system is very 11UCh nore effi­ cient than the equation solving systera (speeds have increased 100-fold) but it is less powerful. The restricted set of relations to which the stan­ dard solutions can be applied means that sone sim­ plifications cannot he raade that the equation solvin!l syster~ would manage. The pairwise conhi­ nati.on of relationships and the restriction to unique solutions sonetimes means that a solution within the theoretical capability of the syster.l is missed: three constraints taken a pair at a time might always produce two solutions; the third con­ straint would elininate one of them. There are sane specifications which should produce multiple solutions (eg 3 revolute joints): at the monent the cycle finder does not solve thera. There are sone constraints which cannot he easily represented in the si!!!ple· relational form. These involve variables: for example the jaws of a gripper may he constrained to move in equal and opj)OSite directions by the sar~e ar1ount.

Given these inherent limitations in the system, we feel that the cycle finder shoulr! be used as front end to some more pOI<erful inference system - the cycle finder will be used to solve quickly and efficiently those proble1as it is capable of, and pass the residue on the the next system. In our experience most of th<:! probler.1s we cone across can be conpletely solved by the cycle finder.

Sone linkages form standard, but large cycles. (Duffy 1980) has provided solutions for th.en . ~le anticipate including such solutions in the final inference systen.

REF~Rf.NCES

• [ 1] Duffy,J., Analysis of mechanisns and Robot
• _!!~I!_i_~~l-~1:_<:~~ London~ Edwa-;,1,\;~old: 1980
• [ 2] Popplestone, I .H., "RAPT: blies" in pp.131-137 R.J., Anhler, A.l>., and Be !los, A Language for describing Assem­ Indu~t ri_~~ Robot Sept. 1978,
• Popplestone, R.J., Arabler, A.P., and Bellas, I. H., "RAPT: An interpreter for a language describing asse1ablies" in Arti~icia~ .!_I!_t_elli-: ile~~ 14(1980) pp.79-107
• Popplestone, R.J., Aiahler, A.P., and Bellas, I. H., "An Efficient and Portable Impleraenta­ tion of RAPT" in Proc. 1st ICAA. Bedford, UK: Il'S( Publications)-:-~i;rchl9_3Q,""_ pp 411-422
• Yin, B., "A Framework for Handling Vision Data in an Object Level Robot Language" in this conference proceedings.