Using Modular Components

Randy C. Brost, Sandia National Laboratories

Ken Goldberg, UC Berkeley

This is an html version of the paper published in IEEE International
Conference on Robotics and Automation,

May, 1994.

## Contents
## AbstractCommercially-available modular fixturing systems typically include a lattice of holes with precise spacing and an assortment of precision locating and clamping modules that can be rigidly attached to the lattice. Currently, machinists manually design a suitable arrangement of these modules to hold a given part. This requires expertise and can delay production. Futhermore, a machinist may in many cases settle upon an arrangement that is not optimal for a given machining operation.In this paper we present an implemented algorithm that accepts a polygonal description of the part silhouette, and efficiently constructs the set of all feasible fixture designs that kinematically constrain the part in the plane. Each fixture is comprised of three locators rigidly attached to the lattice and one sliding clamp, and constrains the part without relying on friction.
The algorithm is based on an efficient enumeration of admissible designs
that exploits part geometry and a graphical force analysis. The
algorithm run time is linear in the number of designs found, which is
bounded by a polynomial in the number of part edges and the part's
maximal diameter in lattice units. Our review of the literature
suggests that this is the first fixturing algorithm that is
## IntroductionMost automated manufacturing, assembly, and inspection operations require fixtures to locate and hold parts. Given part shape and desired position and orientation, fixtures are usually custom designed by manufacturing engineers and machinists. Although there are a few general guidelines and a number of studies, systematic algorithms for automatically designing fixtures based on CAD part models are still lacking [Chang 1992; Shirinzadeh 1993].
This is partly due to the uncountable set of alternative fixture
designs that must be considered in the general case. One way to
reduce the number of alternatives is to limit consideration to a
small set of components that must be located on a regular lattice
structure. Such The concept of modular fixturing using a family of interchangeable components was originally developed in England during World War II, and has resulted in a variety of commercially-available modular fixturing systems [Hoffman 1987]. These systems typically include a square lattice of tapped and doweled holes with spacing toleranced to more or less 0.0002 inch and an assortment of precision locating and clamping elements that can be rigidly attached to the lattice using dowel pins or expanding mandrels. Although the lattice and set of modules greatly reduce the number of alternatives, designing a suitable fixture currently requires human intuition and trial-and-error. Designing a new fixture can be time consuming. Furthermore, if the set of alternatives is not systematically explored, the designer may settle upon a suboptimal design or fail to find any acceptable design.
In this paper we present an algorithm for automatically designing a
class of modular fixtures. These fixtures constrain all motion of a part
in the support plane. Constraint is provided by four point contacts and
does not rely on friction. Each fixture in this class uses three round
An acceptable fixture design must satisfy several requirements. First,
it must fully constrain the part to prevent its motion. We require
fixtures to provide
The algorithm begins with a geometric transformation that expands the part
edges by the radius of the locators; this allows us to treat the locators
as points on the transformed edges. These edges are then trimmed to
respect geometric access constraints. We define a
We believe this is the first modular fixture design algorithm that is
This algorithm is guaranteed to find the There are a number of issues that are not considered by the algorithm. For example, out-of-plane motions and part deformations are both important considerations in some fixturing problems, and these are not addressed by our planar fixture design algorithm. However, the strong analysis and enumerative aspects of our algorithm make it well-suited for use as part of a larger procedure that synthesizes 3-d fixture designs for prismatic parts, which occur in a variety of man-made products. Limitations and possible extensions of this algorithm are discussed further.
## ExampleFigure 1 shows an example. The part is shown on the left of (a). This plastic housing is one-half of the case of a commercially-available hot glue gun. We would like to design a fixture to hold this housing (the part) while assembling the gun. In (b) the part boundary is represented as polygon, as are geometric access constraints that delineate regions that must remain clear of fixture components --- in this case to allow the gun tip, trigger, and cord to be assembled with the part. The part has 28 edges, and the access constraints have a total of 20 edges.A commercial modular fixturing kit is illustrated in (c), comprised of a precisely machined plate with alternating dowel/threaded holes, a set of three round locators, and a manually-actuated clamp. In (d) this kit is represented by a model of the plate, the locators, and the clamp. The clamp is modeled by a polygon delineating the space occupied by the clamp during normal operation; this includes the region swept as the handle is moved from the open to closed position. The clamp model also includes a polygon describing the shape of the clamp plunger, and the plunger travel limits. For this example, the algorithm returned 97 fixture designs in just over two minutes on a desktop workstation, sorting them according to a quality metric which examines the maximum contact force required to resist an arbitrary unit applied force. Figure 2 shows three of the returned fixture designs. Note that all three fixture designs provide form closure and obey the geometric access constraints. If we consider a clockwise unit torque applied to the part, we see that the fixture in (a) is superior to the one in (c), where contacts A and B must exert very large contact reaction forces to resist the torque. Our implementation includes these considerations in the metric it uses to rank fixtures; see Quality Metric..
## Previous WorkThere is a substantial literature on fixturing and the related topic of grasping. These results may be roughly grouped into three categories: Fundamental analysis of the existence of fixtures or grasps, analysis of a given fixture or grasp, and automatic synthesis of fixtures or grasp configurations.
## The Existence of Fixtures and GraspsThe century-old definition ofform closure captures the intuitive
function of a fixture [Reuleaux 1876]. A set of contacts provides
form closure if infinitesimal part motion is completely constrained;
equivalently, the set of frictionless contacts is able to resist
arbitrary forces and torques on the part. This condition may be
analyzed using the concept of a wrench, which is a generalized
force that includes moment contributions [Ohwovoriole87]. In the
plane, a set of wrenches provides form closure if they positively span
R^{3}.
Reauleaux showed that at least four wrenches are necessary for form
closure in the plane [Reuleaux 1876]. Recently, Markenscoff
The above proofs demonstrate the existence of form-closure fixtures
where contacts may occur at arbitrary positions in space. In the case
of modular fixtures, the locations of contacts are constrained by the
modular fixturing kit. Mishra studied the problem under these
constraints, and showed that a fixture can always be found for a
rectilinear part as long as all edges have length of four or more
lattice units [Mishra 1991]. Zhuang,
## Fixture/Grasp AnalysisGiven a fixture or grasp configuration, a variety of considerations may be applied to evaluate the suitability of the fixture or grasp for a given task. In this section, we review past work on evaluating fixtures and grasps; some of these evaluation criteria are already embodied in our algorithm (such as the determination of whether or not the fixture provides form closure), while others would be appropriate to include in future extensions to the algorithm's quality metric.Asada and By showed how to determine whether a given fixture design provides total constraint of a rigid body, as well as loading accessibility before clamping [Asada 1985b]. Our glue gun example is inspired by their example of a power-drill housing, and highlights the similarities and differences between the results. Our paper extends Asada and By's analysis methods by providing an automatic design procedure that considers geometric access constraints and modular assembly constraints in addition to kinematic closure. However, our algorithm considers only three degrees of freedom. Several grasp quality measures have been proposed based on the smallest contact force necessary to resist applied forces [Cutkosky 1985,li88]. Such a metric can be defined as the solution to an optimization problem [Markenscoff 1989,Trinkle 1992] or geometrically as the radius of the largest sphere that can be embedded inside the wrench convex [Ferrari 1992, Kirkpatrick 1992]. One subtlety is that the wrench space is not homogeneous, and one must take care when comparing forces with torques. In a similar vein, Bausch and Youcef-Toumi developed a method of evaluating the degree of motion constraint imposed by seven fixels contacting a three-dimensional rigid body [Bausch 1990]. The quality metric we describe in Section Quality Metric is similar to Bausch and Youcef-Toumi's metric, except that our metric analyzes planar problems and explicitly considers expected task forces. Unlike some previous geometric quality metrics, our quality metric is not sensitive to the selection of a force/torque scaling factor, which can be a somewhat arbitrary parameter. Other authors addressed task-specific requirements that must be satisfied by a fixture. Englert reported methods for assessing a fixture design's susceptibility to part deformation, locator wear, and dynamic chatter during machining operations [Englert 1987]. Sakurai later explored the relationship between fixture design, part tolerances, and part deformation in greater detail [Sakurai 1990]. Sakurai also studied the relationship between cutting forces and clamping forces in fixtures that rely on friction for part restraint --- particularly when top-clamps are employed. Lee and Cutkosky extended Sakurai's results by clarifying the relationship between a fixture with top clamps and the friction limit surfaces that were previously developed to study the motion of sliding planar bodies [Lee 1991]. Kim further extended these results by considering whether or not expected force magnitudes would exceed clamp stress limits [Kim 1993]. Other authors reviewed additional practical requirements of fixture designs [Gandhi 1986, Cohen 1991, Chang 1992]. The algorithm we report in this paper is complementary to these results; while we do not present an analysis of part deformation, tolerances, or maximum allowable clamp forces, it is reasonable to expect that these and other considerations could be folded into the quality metric that rates fixture designs. Ultimately, we envision that the synthesis methods of this paper could be combined with enhanced quality metrics to produce a larger system that will select the fixture that best satisfies this myriad of considerations. Schimmels and Peshkin examined the problem of loading a given fixture using generalized damper compliant motions, and showed that in the absence of friction, a robust loading strategy exists for all deterministic fixture designs [Schimmels 1992]. (The fixture designs returned by our algorithm are always deterministic in their sense.) Later work characterized the conditions where a fixture may be robustly loaded if friction is present [Schimmels 1994]. Schimmels and Peshkin considered only infinitesimal motions, and did not analyze the effect of finite motions such as large rotations. Whether or not a fixture may be reliably loaded is an important aspect of fixture design that we do not treat in this paper; this consideration may be used either to discard fixtures that cannot be loaded robustly, or as a metric to compare fixtures based on their ease of loading.
## Fixture/Grasp SynthesisFor a review of current practice in manual fixture design, see [Boyes 1989]. In addition to these methods, a number of techniques have been developed for automatically synthesizing grasp and fixture configurations.Mishra, Schwartz, and Sharir described an algorithm for synthesizing form-closure grasps on an arbitrary 2-d or 3-d object; the grasps returned by the algorithm may require up to six contacts for 2-d objects [Mishra 1987]. Nguyen gave an algorithm for finding a set of four (seven) independent regions on the boundary of a polygon (polyhedron) such that a frictionless contact applied to each region is guaranteed to provide form closure [Nguyen 1988]. Such regions are useful because they allow for uncertainty in the part's pose. For three frictional contacts in the plane, Ponce and Faverjon showed that comparable regions on a polygon could be found using linear optimization [Ponce 1993]. These results both allow contacts at arbitrary points in space, and do not consider the constraints imposed by a modular fixture kit. In the context of planning grasping strategies for lifting an object off a supporting surface, Trinkle and Paul identified jamming regions on an object's boundary, given three point contacts [Trinkle 1990]. These jamming regions are analogous to the form-closure clamping regions produced by our force-sphere analysis, in that they identify portions of the object boundary where an additional contact would lead to a force-closure condition. The form-closure analysis presented in this paper differs from Trinkle and Paul's construction in that it applies to all possible arrangements of contact normals, while Trinkle and Paul's construction addresses the special case where two of the contact normals are parallel.
In the specific context of fixturing, Mani developed a method for designing
planar fixtures based on Reuleaux's rotation center analysis techniques
[Mani 1988]. Given a polygonal part shape, Mani's procedure identifies all
topologically equivalent fixture designs. However, his procedure does not
accurately consider the fixel shape or the mapping of the fixture design onto
a modular fixture plate. Chou
Recently, Wallack and Canny reported an algorithm for designing a class of
modular fixtures with four round locators on a split lattice that can be
closed like a vise [Wallack 1994]. Their algorithm, like ours, takes the
part shape as input and enumerates all combinations of fixture elements that
achieve form closure. Also, like ours, their algorithm sweeps edges to
compute contact conditions and runs in polynomial time. However, the
algorithms differ in the construction of the fourth fixel location. In the
case of Wallack and Canny's split vise, the third fixel's
## The Algorithm## Problem StatementAssumptions:
- Parts and locators are rigid solids. A part can be represented with a simple polygon and locators can be represented as circles with identical radii less than half the grid spacing l$(SQRT\; 2)l/2$ on an alternating grid). Thus we do not have to check collisions between locators.
- All contacts are ideal unilateral point constraints. Our analysis treats these contacts as frictionless: the fixtures do not depend on any minimum level of friction.
- Polygonal part boundary, provided as a list of vertices.
- A set of geometric access constraints, provided as a list of polygons defined in the part coordinate frame.
- Height and width of the fixture plate lattice.
- Locator radius.
- Description of the clamp. This includes a polygon describing the shape of the clamp body, locations of the clamp mounting holes, a polygon describing the shape of the clamp plunger, and its min/max travel limits. The tip of the plunger is assumed to be a circle of the same radius as the locators.
- A quality metric. This is a function that accepts a fixture design and returns a scalar quality measure.
Output:
A list of all admissible fixtures for the part, sorted in order of quality.
## Overview of the AlgorithmGiven the input described above, the algorithm produces its output by performing the following steps:
- The input is transformed by growing the part such that the fixels can be treated as ideal points, and the fixture plate lattice is assumed to be infinite.
- All possible candidate fixture designs are constructed. This is accomplished by enumerating the set of possible locator setups, and then passing the result to a form-closure analysis routine that constructs all of the possible abstract clamp locations for each setup. Each locator setup and clamp location specifies a unique fixture.
- The set of candidate fixtures are then filtered to remove those that do not obey clamp travel limits, cause collisions with the clamp body or plunger, or do not fit on the finite fixture plate.
- The resulting fixtures are scored according to the user-specified quality metric, and then sorted in order of decreasing score. The algorithm returns the sorted list of fixtures.
## Transforming the InputThe first step of the algorithm is a transformation that allows us to treat round locators as ideal points. This is accomplished by forming the Minkowski sum of the polygonal part boundary and the circular fixel shape; fixturing the resulting expanded boundary with ideal points is then equivalent to fixturing the original part boundary with finite-radius locators. Thus it is sufficient to consider points on the edges of this expanded boundary as candidate positions for locators.Although the expanded boundary has rounded edges corresponding to contacts between a locator and an object vertex, we consider only the linear components of the expanded boundary. We similarly grow the constraint regions by the fixel radius, and then restrict our attention to the subset of the expanded part edges which do not intersect the grown constraints. This will assure that the fixels of all generated fixtures will avoid the access constraint regions. This results in a list of rigidly attached but possibly unconnected linear edges. See Figure 4. We are now free to translate and rotate this group of edges to bring edges into contact with lattice centers.
## Generating Candidate FixturesWe proceed to enumerate all possible fixtures. First, we enumerate triplets of locators, identifying the part configurations consistent with each. Each combination of a locator triplet and an(x,y,t)
configuration specifies a locator setup. After enumerating all possible
locator setups, we identify the set of all clamp positions that
provide form closure.
## Enumerating Locator Triplets
To enumerate all locator triplets, the following steps are
repeated for all combinations of three edges, where either all three
edges differ, or two of the three edges are identical. For example,
(e are both valid edge combinations.
Order is not significant, so there are {n!/[(3!)(n-3)!]}+n(n-1)
such combinations for_{4} , e_{7} , e_{4}) n edge segments.
The second combinatorial is multiplied by two because there are two
valid triples for every choice of two distinct edges. Note that we need
not consider combinations with three identical edges, since a part with
three locators on one edge cannot be held in form closure.
Given a combination of three edges, e makes contact with a locator at the origin of
the lattice. By translating and rotating _{a} e about the origin,_{a} e sweeps
out an annulus centered on the origin, with inner diameter equal to the
minimum distance between_{b} e and _{a} e and outer diameter equal to the
maximum distance between_{b} e and _{a} e. That is, for any orientation of
_{b} e, as we translate along the extent of _{a} e, _{a} e sweeps out a
parallelogram. The union of these parallelograms as we rotate _{b} e forms an
annulus. To eliminate equivalent fixtures, we only need to consider the first
quadrant of this annulus. See Figure 5._{a}
We now consider each of these second locator positions in turn, and
identify all possible positions for the third locator. If the first
locator contacts e, then a
third locator in contact with_{b} e must be pairwise consistent with
both _{c} e and _{a} e. The exact region swept out by _{b} e as we
maintain contact with the first two locators is difficult to
characterize. However, we can easily find an envelope that contains
this region by independently considering each pair. That is, the
possible locations for_{c} e with respect to _{c} e form an annulus
around the origin, and the possible locations for _{a} e with respect to
_{c} e form an annulus around the second locator. Intersecting these
annuli provides a conservative bound on the set of grid locations that
simultaneously satisfy both constraints. _{b}
We can further refine this bound by considering the angular limits for
each annulus. This is accomplished by first identifying the angular
limits of the part configurations that simultaneously contact the first
and second locators, producing a [B interval that delineates
the minimum and maximum angle attainable by a ray connecting _{min} , B_{max}] e and
_{a} e. The resulting_{c}[(O interval describes the set of all possible
angles between points on edge _{min}+B_{min}) , (O_{max}+B_{max})] e and _{a} e , while _{c} e and _{a} e
maintain contact with locators 1 and 2. This interval defines a sector
of the _{b} e _{a} e annulus; points outside this sector are unreachable by
_{c} e. A similar construction produces a sector of the _{c} e _{b} e annulus
based on the _{c}B-interval corresponding to edges e and _{b} e
.
Intersecting these annular sectors provides a set of candidate locations
for the third locator. See Figure 6._{c}
## Identifying Consistent Part ConfigurationsFor each triplet of locators and associated contact edges, we must identify the set of consistent part configurations. This is accomplished by a configuration-space analysis that constructs the intersection points of edge/vertex--edge/vertex (ev-ev) contact equations. This calculation identifies intersection points between the ev-ev edges on the configuration-space obstacle corresponding to two-point contact situations. For example, if e,_{a} e, and_{b} e
are the edges of the part in contact with fixels_{c} v,_{1} v,and _{2} v
respectively, then the combinations
_{3} e-_{a} v_{1} e,
_{b} v_{2} e-_{a} v_{1} e,and
_{c} v_{3} e-_{b} v_{2} e,
all correspond to two-contact situations that have an associated
one-dimensional locus of points in the _{c} v_{3}(x , y , O) configuration
space. Three-point contact is only possible at the intersections of
these loci, so the set of part configurations where all three fixels are
in contact may be found by solving for the roots of the parametric
equations describing these intersections.
There may be up to two solutions to these equations, corresponding to different poses of the part that permit simultaneous contact with the three chosen locators (see Figure 7). In these cases, we generate two candidate locator setups, one for each pose. In certain geometric situations there are an infinite number of solutions (such as when all three edges are parallel); these cases are discarded because they do not constrain the part to a unique location.
## Enumerating Clamp ConfigurationsSo far we have enumerated all possible three-edge combinations, all possible locator triplets for each edge combination, and all possible part configurations for each locator triplet. This has produced a list of all possible locator setups for the part. Next, we visit each setup and generate all of the possible clamp positions that provide form-closure. Thus for each setup, we may generate several candidate fixtures, each with a different clamp position.
To generate the set of form-closure clamp positions for a locator setup, we
perform a constraint analysis on the
This representation was previously described in Brost 1990;
see Brost 1991 for implementation details. This space represents
both the direction and moment components of a line of force exerted in
the plane. For example, Figure 8 shows an example
planar force and its corresponding point on the force sphere. Note that if we were
performing dynamic analysis, we would choose the part origin and We treat each fixel/edge contact as an ideal unilateral point constraint. Thus each fixel may resist motion by exerting a reaction force in the direction of the inward-pointing contact normal. Figure 9 shows the set of points on the force sphere corresponding to the three contact normals of a typical locator setup. The convex-combination of these points is also shown; this triangle on the force sphere delineates the set of all total contact reaction forces that may be produced by combining forces from all three contacts. A fixture design provides form closure exactly when the corresponding set of contact normals positively spans the entire force sphere. When this condition is satisfied, combinations of contact reaction forces may produce an arbitrary total reaction force, thus opposing an arbitrary motion. Put another way, if the set of contact normals for a given fixture design span the force sphere, then all possible motions will violate at least one kinematic constraint. Given a set of three contact normals corresponding to a locator setup, we can directly construct the set of forces that would produce form closure if provided as a fourth contact normal. This is accomplished by forming the convex-combination of the three contact normals on the force sphere, and then centrally projecting this triangle onto the opposite side of the sphere. The resulting negated triangle delineates the set of all forces that will produce form closure. If we can find a clamp position with a contact normal that corresponds to a point strictly in the negated triangle, then this clamp position and the three locators will define a form-closure fixture. We can directly construct the set of clamp positions that satisfy this condition. We accomplish this by characterizing the set of all contact reaction forces that can be applied by a contact along the perimeter of the grown part. This set of forces is illustrated in Figure 10. Note that the set of all possible contact forces corresponds to a ``zig-zag'' locus of points that encircle the force sphere. Fixel contacts along the edges of the polygon correspond to the vertical edges of the locus; note that as a force moves along an edge, only the torque component of its wrench will vary. Fixel contacts with the vertices of the polygon correspond to the diagonal locus edges. By intersecting the vertical locus edges with the set of possible form-closure forces constructed previously, we can identify the set of all available edge-contact normals that produce form closure for a given locator setup. We then map this set of contact normals back onto the grown part perimeter to identify the regions where a fourth contact point will produce form closure. Finally, we identify the set of possible clamp positions by intersecting the identified regions with the horizontal and vertical edges of the fixture lattice. This construction is illustrated in Figure 11.
## Filtering the CandidatesAt this point the algorithm has enumerated all form-closure fixtures where the round fixels obey the geometric access constraints. The next step is to filter the candidates through several geometric tests. First, we determine the clamp location and check clamp travel limits. Next, we discard those fixtures where the clamp body or plunger intersects the part, the locators, or the access constraints. Finally, we attempt to fit the remaining fixtures on the finite fixture plate; fixtures that cannot be placed either horizontally or vertically are also discarded.## Ranking the SurvivorsThe final step of the algorithm is to rank the surviving fixtures according to the user-supplied quality metric. A user may then view the top fixtures and apply additional criteria to select a winner. Our implementation includes a default quality metric that favors fixtures that can resist expected applied forces without generating excessive contact reaction forces. Large contact forces are undesirable because they may deform the part. The effect of fixture geometry on contact reaction force is illustrated in Figure 12. In this figure, a part is held in two different fixtures, both of which provide form closure. Which fixture is better? The answer depends on the forces that will be exerted on the part. For example, if downward forces will be applied to the part, then fixture A is better than fixture B, since fixture B will develop large ``wedging'' forces between the fixels. On the other hand, if clockwise torques will be applied, then fixture B is superior, since fixture A must develop large contact reaction forces to oppose rotation of the part. As an example, we implemented a quality metric that allows the user to specify a list of expected forces on the part. These forces are represented by a list of force-sphere regions with associated magnitudes that could arise from operations such as machining, assembly, or pallet transfer operations. The quality metric scores each fixture by estimating the maximum contact reaction force required to resist the list of expected applied forces. The estimated maximum contact reaction force for a given fixture is calculated by visiting each force-sphere region in the applied force list, generating a discrete sampling of points in the region, computing the maximum contact reaction force required to resist each point, scaling the result by the associated magnitude, and taking the maximum of all the resulting contact reaction forces.
Given a particular point sqrt(F.^{2}_{x}+F^{2}_{y})
## Algorithm Complexity
An asymptotic upper bound on the running time of the algorithm can be derived
as follows. For the given polygonal part, let O(d locations for the second locator since we consider a sector
of an annulus of diameter no greater than the part, and similarly for each
pair of locators, there are ^{2})O(d locations for the third locator. Once
the part pose is determined by three locators, the number of possible clamp
locations is bounded by its perimeter: ^{2})O(nd). Thus the maximum number of
possible fixtures is O(n. Checking for unwanted collisions can be
accomplished in ^{4}d^{5})O(n) time for each fixture, since the number of clamp edges
is constant. If the quality metric can also be evaluated in O(n) time or less
for each fixture, then the total running time for the algorithm is
O(n.
^{5}d^{5}) |

Back to *FixtureNet* Complete Story

For questions or comments, please send e-mail to: Prof. Ken Goldberg