LAMA: A Language for Automatic Mechanical Assembly

1. HE NATURE OF THE PROBLEM

This section tries to highlight the difficulties of pr gramming assembly operations by examining a parliculi!r astembly task in some detail.

· Fig. 1 shows the piston subassembly from a model aircr all en ine. We will use it to emphasize the number and complexity of I the decisions to be made in planning an assembly. The. a4embly has been carried out using the Silver robol manipulator at the MIT Artificial Intelligence Laboratory [Silver). This manipulator is not a fully general position and orient a lion ge'nerator because it has only five degrees of freedom, noi six. They are divided in the following manner: (l) an X'J table, (2) a wri~t which can displace and rotate along the z axis and (3) a vise which rotates about the x axis (see Fig. 2). The manipulator is equipped with a force sensing wrist capable of resolving the X'JZ components Of the forces and torques acting On the wrist. This allows the manipulator to generate and detect forces. The use of force feedback enables the Sliver Robot System to perform precise assembly tasks whose critical clearances are below its positional accuracy [lnoueJ

The hard part of this engine subassembly is inserting the piston-pin through the piston pin -hole and through the piston-rod. The obvious way to do this (for liiUman) is to line up the holes in the piston-rod and the piston and then push the pis,on-pin through both holes. This operation is impossible using th~ manipulator configuration we have described. Recall we only h've two sets of parallel fingers available; one set is the hand, tl;le other the vise. This restriction forces us to break the problem up into three parts.

First the pin is inserted partway into the piston. Then the piston-rod's pin-end can be placed onto the pin Inside the piston. And finally, I he pin pushed through the rod and the piston-hole.

This de.scrtptton of the piston assembly s.imply speCifies three snapshots of the system slate. Each stale is specified in terms of the spatial relations between the parts involved. The verbs used in the description (insert, place and push) give· some information as to the nature of the operation necessary to achieve each stale. Note thai no mention was made of the manipulator. The constraint thai only one hand and a vise is available dictates the nature of the solulior.~, but the manipulator motions necessary to carry out the solution are not specified, nor are they obvious.

The assembly can be carried out by first placing the pin in the vise such thai its main axis is horizontai"(Fig. 3a). Then the piston can be placed on the pin so that the cavity is facing upward. The rod can then be placed on the portion of pil'l that is projecting into the piston's cavity (Fig. 3b). The manipulator can then grasp the piston, remove the piston from the vise, and after closing the vise, push the part of the pin protruding from the piston against the vise (Figs. 3c&d). We call this the assembly plan.

For each operation in the assembly plan, the manipulator program must specify the position and orientation of the fingers such that they can securely grasp some pari of the object to be moved. The program must also specify a trajectory for the manipulator that is not likely to damage the manipulator or disturb any of the other parts.

The assembly description and the assembly plan mention only the spatial relationships that must hold between the parts in the goal state. These relationships involve mucl:l greater positional accuracy than is directly achievable by the manipulator to be used. These relationships can be achieved by employing force feedback techniques such as those described in [Inoue].

Inoue has developed. a program which, driven by force feedback, does peg-in-hole insertion. Unfortunately, his program cannot be used directly in the task at hand. Inoue's program assumes that the motions of the hand correspond directly ·to motions of the hole. The assembly plan described above specifies that the piston-rod be held at the opposite end from the point of insertion. This is because the insertion is happening inside the piston. Inoue's program must be changed to account for this.

Like most programs, Inoue's has parameters. The length .of certain motions and the magnitude of some forces are not specified. These parameters must be specified for the task at hand.

Inoue's program also lacks error dell!'ction capabilities. When the manipulator is told to move in a given direction until a force above some threshold is felt, no position bounds are specified. This can give rise to severe errors.

These considerations point to one, very Important, conclusion: Inoue's program is not so much a general utility program as a specification of an assembly strategy to be adapted to many different geometric environments. This is true of most manipulator programs because of their dependence on as.sumptions about the geometry of the task.

Let us summarize the problems to be faced in specifying an assembly operation.

• I Describe the objects to be assembled.
• I Specify a plan .for the assembly. The details of the plan will depend on the manipulaiOI' configuration available and on the capabilities of the assembly system. ·
• I Determine the grasping position and orientation for the objects involved in each operation.
• I _Determine a collision free path between the origin and destination of all motions.
• Tailor the assembly strategies to fit the particular geometric
• environme~l. This involves providing parameters 1o the strategies. ·
• I Examine the strategies for likely errors and determine the actions to be taken in case of failure.

2. THE NATURE OF THE APPROACH

The current implementation of LAMA has focused on a subset of the problems outlined in the previous section. The most important are grasping, tailoring assembly strategies and error prediction. This section briefly outlines our approach to these problems.

Computing a grasp point on an object from a description of the object and its surrounding environment is a very diff icult computational problem. The basic mechanism needed to solve the problem is the abifity to detect thai attempting to grasp some pari of the object will cause a collision. This involves computing the geometric intersection of the solids making up the manipulator description with the object to be grasped and with any nearby object. A non-null intersection indicates a collision. A simple approach to solving this problem would be to guess a grasp point and then lest whether it is safe. Typically there is an infinite number of possibilities and the challenge is to choose a grasp point with some confidence that it is a good choice. Trial and error methods are unsatisfactory in this context because not only do they have very poor worst-case behavior bu.t once a result is found, it is very difficult to evaluate it without knowing the alternatives. Our approach to grasping, briefly described in section 3, relies on describing the range of possible grasp points as a few sets of parameterized grasp positions which can be evaluated and compared as units.

In section 1, we pointed out the dependence of ma.nipulator programs on the particular geometry they were designed for. A useful mechanical assembly system must have some means of representing assembly strategies that does not make too many assumptions about the environment where they · are to be used. Our approach to making the strategies as general as possible is to have each of the steps in the strategy be essentially a goal statement. Each operation is decribed in terms of the geometric relafions it is meant to achie_ve in a coordinate system specified by the strategy. The assembly strategies can then be adapted to a particular situation by computing the parameters needed to achieve the goal of the individual steps of the strategy.

Once we have available a description of the goal of each step, then some "errors can be predicted by simulating the operations, laking into account some of the uncertainty in the positions of objects. These error predictions can be used to solicit corrective ac-tions from the user.

Section 3 will describe in more detail how the assembly strategies are used. ·

5. AN OVERVIEW OF THE LAMA SYSTEM

This section describes how we believe the piston assembly will be processed 'by LAMA when it is completely implemented. Prototype programs currl!nlly exist to do parts description, the Pick and Place phase and a simple Feedback Strategy phase . . No program exists to do the Assembly Planning.

The parts to be assembled must firsl "be described to the system. The user uses the system interactively to define modl!ls of the parts. Complex objects are described as unions of a few kinds of primitive object types. The primitive objects currently available in implemented parts of LAMA are a cuboid and a cylinder (both as solids and holes).

Fig. 4 s~ows a schematic description of the models for l~e parts in the piston assembly. Note thai the parts are arranged hierarchically. This allows a convenient treatment of subparts of objects. Any desired subparts can be represented as nodes in the part model trees. Each node has information regarding the size, type and relative position of the subpart. All the subparts, including the holes, are approximated as rectangular or octagonal right prisms. This provides a uniform internal represent at ion for all the object types. This representa1ion simplifies the definitions of the spatial modelling operations. By gene"ralizing to polyhedra the desired volumes can be approximated to any required accuracy.

The next step is that of describing the assembly. Ideally, we would like to specify the assembly process by simply describing the completed assembly. A more realistic goal is that of accepting assembly instructions similar to those given to people, as discussed in the introduction.

The assembly description for the piston assembly is shown in Fig. 5. The assembly description s.pecifies only that operations, such as insertion, are to be performed on the .parts. The individual operations are often under-specified. Parameters are missing or only weakly constrained, e.g., inserl ihe pin partway into the piston. No mention is made of the manipulator or of the strategies to be used to carry out the operations. Merely saying insert is not enough to specify an assembly operation. The actual motions carried out are sensitive to the shape and relative sizes of the parts.

The first step in the transformation from user input to manipulator program is to completely specify the assembly description. This is the task of the Assembly Planner. It must .first introduce into the description those operations that will achieve the prerequisites of the operations in the initial description. This requires specification of some high level manipulator commands such as GRASP, l,JNGRASP and PLACE. Then the operations. must be completely specified and strategy choices made for them. The end result of this process is an assembly plan. In this plan each operation is fully specified and the positions and orientations of the parts involved are well constrained. An important point to note is that the plan sti" does not determine the manipulator motions necessary to carry out the assembly. The assembly plan corresponding to the assembly description in Fig. 5 is shown in Fig. 6.

The current implementation assumes that the Assembly Plan is directly available as an Input to the system. We can then focus on the process. of transforming an assembly plan into a manipulator program.

Once the assembly plan has been fully specified, a detailed pick and place computat ion can be carried out. This will determine precisely where the objects are to be grasped and what paths they must follow to avoid collisions. Unfortunately, the Pick and Place computation is not independent of .the nature of the assembly strategies. Where the object is grasped and where it is placed prior to an operation depends on the details of the operation. The solution is to do the grasp computation at the initial position of the object to be moved, before the operation i.s instantiated. This determines the range of possible grasp points. After this, the assembly step is expanded. The instantiation process places additional constraints on both the initial position of the part and its grasp point. · Then, an exact grasp. point is chosen and the path computed after the operation has been ex·panded.

The pick and place computation exercises most of the spatial expertise of the system. The basic operation in both grasping and collision avoidance is detecting the possibility of a collision by intersecting volumes. In finding a collision-free trajectory we are interested in whether the volume swept out, by the manipulator and the object it carries, cOllides with other objects In the workspace. Simtlarly, In grasping we are interested in the locations on the object where the hand can be placed su<;h that no collisions will result. Since there are a whole range of grasping positions for a given object, this amounts to intersecting the volume of the hand, swept out over the possible grasping positions, with the workspace.

We have characterized the. types of grasping positions for the primitive objects as a series of K"asp sets. Grasp set$ are parameterized ranges of hand positions over a surf.ace of the object. Fig. 7 shows a graphical representation of lhe grasp sets for cuboids and cylinders. Complex objects are analyzed by considering how to grasp each of their component objects while taking into account the interactions with olher parts of the object as well as with the rest of the environment.

• Fig. 8 shows the system's representation for the /ltg-tn-ltolt tnsertton strategy. II is very similar to the program presented in (Inoue} The Feedback Strategy phase simulates this sh.tltton program, predicts contacts and estimates the direttion and magnitude of the forces that will be produce<;l.

Note !hat each step in the skeleton program is 11nnotated by the geometric relations it generates between the manipulated parts. This information can be used in two ways:

• I To generate numerical values. for parameters in the programs. For example, the size of the shift in the y direction in the DROP-INTO operation can be determined by examining the geometrical relations it is meant to achieve.
• I To generate tests for likely failure situations given the particular execution environment. A good example of this .is the operation of moving the piston-rod near the piston-pin for the insertion of the rod's pin-end onto the pin inside the piston. By examining the clearance between the tip of the pin and the piston wall given the errors in grasping and positioning, we can predict that sometimes the rod will contact either the pin or the piston. A test for this srtualion can be generated and .instr.uctions as to corrective action could be solicited fr.om the user . .

4. THE FEEDBACK STRATEGY PHASE

The result of the operation of the Feedback Strategy phase is a manipulator program. This section considers the operation of the Feedback Strategy phase during the expansion of the PEG- IN-HOLE operation in which the piston-rod is to be inserted onto the piston-pin, while the pin is inside the piston. A preliminary implementation currently exists of the program that does the simple code generation shown here.

The assembly plan (Fig. 6) has the following entrie~ for the operation of inserting the piston-rod on the piston-pin:

(GRASP OBJ : [PISTON-ROD]

.

SUCH-THAT : (FACING+ ([ROD-BAR] TOP) UP))

(INSERT OBJl [PISTON-PIN]

OBJZ : [PISTON-ROD PIN-END-HOLE])

(UNGRASP OBJ : .["PISTON-ROD])

We must first find a grasp point on the piston-rod. There are two possible grasp positions on the rod; one along the sides of the piston-rod's pin-end, the other on the flat ends. The choice will depend on several factors: (1) flat surfaces are preferred to curved surfaces and (2) possible collisions. Collisions are predicted by simulating the assembly operations while assuming the hand can be at both of the legal grasp positions. The Feedback Strategy phase can then consider the effects on each of the grasp ranges simultaneously.

The first task in expanding an assembly strategy is to setup the local reference system. The REFERENCE statement in PEG- IN-HOLE indicates that the reference frame's x axis is ALIGNED&CENTE.RED with the HOLE's front face. This leaves one rotational degree of freedom unspecified. The current system always tries to line up unspecified degrees of freedom in the reference with global axes. In this case, the referenc:e's z is aligned to the global r.

The INITIAL statement specifies !he constraints on the initial position of the parts. In PEG- IN-HOLE it specifies that the HOLE and the PEG be ALIGNED&CENTERED and IN-FRONT-Of each other. Fig. 9a shows a top view of the interaction volume

·-- .. -of the piston-rod's pin end and indicates the intersection of that volume with that of the piston. The intersection divides .the range of legal positions into two ranges on either side of the piston wall. The current system chooses to use the range where the objects are closer to each other as the range of legal positions of the piston-rod.

The first step in the DROP- INTO strategy calls for the object in the hand to be rotated 0.1 radians. The Feedback Strateg.y phase must establish that this rotation will not have any bad effects. This is done by simulating the motion. In this case, contacts with the pin and/or the piston are possible. These accidental contacts determine that the force parameter be "detect-contact" and that an error should be generated if the termination condition indicates a contact. The code that does this is shown here:

since it implies going through the piston. The collisi.on avoidance routine generates a path that goes above lhe piston and moves down to the desired position.

5. RELATION TO OTHER WORK

The problem of construction planning has been very important in the study of problem solving. During the last three or four years several programs have been developed to do construction planning in the Blocks World domain. Fahlman's BUILD [Fahlman) is expert in planning Blocks World assemblies. The programs of Sussman and Sacerdoti have explored general issues of planning and debugging in the context of assembly problems. [Sussman] treated assemblies of blocks exclusively while [Sacerdoti] has also considered the assembly (and disassembly) of a water pump.

(CHANGE R BY 0 .1 WHILE ( RFORCE < "dcttct-contact"))

(COND ((CONTACT? R 0.0 0.1) (ERROR)))

At this point the user is asked about the likelihood and seriousness of the predicted error. The user can choose to mechanical assembly. But even BUILD, being limited to block ignore the error condition.

The next step involves a shift in the 'Y position of the ·rod so as to place the hole to the left of the pin. The motion is constrained as follows:

(I) Hole's center LEFT-OF Peg's center: This restrict ion is placed manipulator. The work on LAMA has focused ·on the problems on the displacement operation itself. Fig. 9b shows (in dashed lines) the volume taken up by the piston-rod over the range of manipulator. positions consistent .with this relation.

Of these programs, only BUILD considered the issues of stability, contact, etc., which are vital to the process of structures could ignore most of the problems of spatial interactions. BUILD also ignored the manipulation aspect of .the construction. Sacerdoti's use of NOAH in SRI's Consultant project avoids all these problems because it assumes a human as the introduced by more realistic objects and the errors of a real .

The approach taken in LAMA to assembly strategies was (2) Hole CONTACT Peg: This restriction is . imposed by the next influenced principally by the work of Sussman [Sussman] and operation in which the rod is moved along X until contact is Goldstein [Goldstein) in debugging programs. They both stressed achieved. Thus the rod's position for the shift in 'Y is al~o the usefulness of having a statement of purpose for each constrained so as to allow the contact to happen. This is .operation in a program. The elegant method of [Ambler & equivalent to constraining the position of the rod's pin~end-hoie Popplestone) for computing the position and orientation of to OVERLAP in 'Y that of the piston-pin's front face. Fig. 9b objects given relations such as AGAINST and FITS-IN provided shows (in solid lines) the volume of the rod over the range of some of the key ideas on how to describe the goals. of strategy positions consistent with this relation. . steps.

A position consistent with both of these relations is There are, at least, five other projects that have direct obtained by computing the range of values of the position · relevance to the task of building an automatic mechanical system. parameters that satisfy each one and then intersecting the These projects are being conducted by the IBM Thomas J. range·s. Fig. 9b shows a graphical representation of the ranges Watson Research Center, the Stanford AI Laboratory, the and their intersection. Stanford Research Institute, the University of Edinburgh, and the c. s. Draper Laboratory.

The IBM system design, AUTOPASS [Lieberman & Wesley], is closest to LAMA. 11 is to be imbedded in PL/1 and will provide the user with a selection of high level assembly operations, the most general being a PLACE command in which the destination is specified as geometric relations between objects.

The Stanford system, AL [Finkel et. al.], is . a complex Algol-like language with many new data-struciure and control primitives. The design includes a Very High Level Language capability. Both AL and AUTOPASS, as well as LAMA, rely to a large extent on modeling the effect on the world of the assembly operations.

(CHANGE Y BY "y" WHILE (YFORCE < "dettct-contact"))

A simulation of the motions shows that the rod can come in contact with the pin and with the inside of the piston (Fig. 9c). These contacts cannot always be avoided by adjusting the starling position of the piston-rod and so they must be expected to happen. This dictates that the force threshold be "detect-contact". The distance parameter of the motion is chosen as the midpoint of the range of legal displacements (indicated by ·,-). This choice is quite arbitrary. The conditional statement after the motion merely tests whether the contact occurred. The user is again given the option to ignore the contact if it happens. In this case that is the best course. The code generated is:

(COND ((CONTACT? Y 0.0 Yl (ERROR)))

After the shift operation, the landing step is simulated. A contact Russell Taylor in his dissertation [Taylor] develops can always be achieved, but there is a region of uncertainly mechanisms to predict errors in location values from the AL where ~ontact with the inside of the piston is possible before planning model and uses this information to generate AL code contact with the pin. The contact is ambiguous, so the error automatically. He also introduces skeleton programs or strategies cannot be detected by using the location of the contact. The which describe and summarize the coding decisions that have .to code generated simply makes sure that the contact is.·in fact be made. The semantics for the strategies are fixed at . system· detected. The displacement used in the motion is the creation time. displacement necessary to go past the last possible contact with the piston-pin and collide unambiguously with the piston wall.

(CHANGE X BY "x" WHILE (XFORCE < "detect-contact"))

( COND ((CONTACT? X 0. 0 "x")) ( T (ERROR))) This completes the DROP- INTO operation. The· complete program assembly strategies to be manipulated by the system. The key can be seen in Fig. 10.

The next step is to compute a path from the position where the piston-rod is first grasped to that where the INSERT is to happen. A straight line path to this position is not possible

r ----- The goal of all these systems is to expand a task-level description into an program for a specific· manipulator. LAMA shares many of the ideas and the a11proaches of both AL and AUTOPASS. LAMA differs mainly in that it allows user-defined idea is to allow the specification of strategies to be independent from the operations performed by the system.

The Edinburgh group [Ambler et. al.] has focused on the problem of assembling an object whose parts must be visually

----------·-·

located and pulled out of a heap. An early speculative paper from their group [Popplestone) anticipated many of the ideas and approaches adopted in this research, even to the choice of a model aircraft engine as the example.

The Or a per Lab [Nevins el. at.) group has focused on direct applicability of a mechanical assembly system in the short range. This has led to emphasis on the type of capabilities that can be made available on a minicomputer. They have also carried out extensive theoretical analysis of the requirements of assemblies in terms of manipulator design and control as well <IS assembly strategies.

Work being pursued at the Stanford Research Inst itute on .Advanced Automation [Rosen et at) has taken a direction similar to that taken by the Draper Lab. SRI has focused on mechanical assembly techniques with industrial potential in the short r.ange. They also have significant commftments to the ind·ustrial applications of computer vision techniques.

BIBLIOGRAPHY

[Ambler & Popplestone)

A. P. Ambler and R. J. Popplestone, Inferring the Positions of Bodies from Specified Spatial Relationships, AISB Summer Conference, University of Sussex, July 1974.

[Ambler el. at.]

A. P. Ambler, et. at., "A Versatile System for Computer Controlled Assembly", Artificial Intelligence, Volume 6, Number 2. 1975.

[Fahlman]

S. E. Fahlman, A Planning S'jstem for Robot Construction Tasks, MIT Artificial Intelligence Laboratory Technical Report 283, May 1973.

[Finkel, et. at.]

R. Finkel, R. Taylor, R. Bolles, R. Paul and J. Feldman, AL, A Programming System for Automation, Stanford Artificial Intelligence Laboratory Memo AIM-177, November 1974.

[Goldstein]

I.P. Goldstein, Understanding Simple Picture Programs, MIT Artificial Intelligence Laboratory Technical Report 294 .· September 1974.

[Inoue)

H. Inoue, Foret Feedback in Precise Assembly Tasks, MIT Artificial Intelligence Laboratory Memo 308, August 1974.

[Lieberman & Wesley)

L. I. Lieberman and M.A. Wesley, AUTOPASS , A Very Htgh Lel!el Programming Language for Mechanical Assembler S'jstem, IBM Research Report RC-5599,. August 1975.

[Lozano-Perez)

T. Lozano-Perez, The Design of a Mechanical Assembly S7stem, MIT Artificial Intelligence Laboratory Technical Report 397, December 1976.

[Nevins el. at.)

J. L. Nevins, el. at., Explorator'J Research in Industrial Modular Assembl'J, Charles Stark Draper Laboratory, NSF Report covering December 1974 to August 1975.

[Poppies tone)

R. J. Popplestone, How Could FREDDY Put Things Together, Dept. of Machine Intelligence and Perception, University of Edinburgh, Memo MIP-R-88, May 1971.

[Rosen, el. at.]

C. Rosen, el. at., Explorator1 Research in Advanced Automation, Stanford Research Institute, NSF Report, January 1976.

[Sacerdot i)

E. 0. Sacerdoti, A Structure for Plan and Behavior, Stanford Research Institute Artificial Intelligence Center Technical Note 109, August 1975.

[Silver)

D. Silver, The Little Robot S'Jstem, MIT Artificial Intelligence Laboratory Memo 273, January 1973.

[Sussman]

G. J. Sussman, A Computer Model of Skill Acquisition, MIT Artificial Intelligence Laboratory Technical Report 297, August 1973.

[Taylor)

R. H. Taylor, A Synthesis of Manipulator Control Programs From Task-Level Specifications, Stanford Art i ficial Intelligence Laboratory Memo AIM-282, July 1976.

r

- .