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.

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 *complete*
in the sense that it is guaranteed to find all admissible
fixture designs for an arbitrary polygonal part silhouette and to
identify the optimal fixture relative to an arbitrary quality metric.
The algorithm does not consider out-of-plane forces or motions;
however, we view this planar result as an essential component of a
larger algorithm that solves the 3-d fixture design problem by treating
the planar and out-of-plane constraint problems separately. This
approach is analogous to the widely used 3-2-1 fixture design heuristic,
and appears to be applicable to a broad class of man-made parts.

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 *modular* fixturing systems also have the
advantage of allowing rapid set-up and changeover for new parts,
precision locating on a tightly-toleranced lattice, and a reduced
fixture inventory comprised of re-usable components
[Mason 1992].

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
*locators*, each centered on a lattice point, and one translating
*clamp* that must be attached to the lattice via a pair of unit-spaced
holes, thus allowing contact at a variable distance along the principle
axes of the lattice. We use the term *fixel* (fixture element) to
refer to either a locator or a clamp and the term *fixture* to refer to
a geometric arrangement of three locators and one clamp on the lattice.

An acceptable fixture design must satisfy several requirements. First,
it must fully constrain the part to prevent its motion. We require
fixtures to provide *form closure,* which is a kinematic constraint
condition that prevents all motion [Reuleaux 1876]. In addition to
constraining the part, the fixture must not interfere with certain
geometric regions of the part, perhaps due to cosmetic surfaces or the
need to retain clearance for grasping, machining, assembly, or other
operations. Thus we define *geometric access constraints,* which
define regions of points that must remain free of fixture components.
With these requirements in mind, we say that a fixture is *admissible*
if it provides form closure and obeys the geometric access
constraints. In this paper, we further restrict our attention to
fixtures where each fixel makes point contact with only one linear edge
of the part. Given a part as input, the algorithm efficiently
enumerates all admissible fixtures and ranks them according to a
user-definable scalar quality measure.

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 *locator setup* as
the combination of three locator positions and a part configuration such
that the part contacts all three locators. The algorithm enumerates all
locator setups; for each, it identifies the set of all points along the
perimeter of the object where an additional contact would provide form
closure constraint. This in turn allows us to identify all of the possible
form-closure clamp locations for each locator setup; each clamp location
defines a unique fixture design. After pruning this set of fixtures by
checking for geometric violations such as the clamp body intersecting
the part or other fixels, we rank the surviving admissible fixtures
based on some scalar metric such as ability to resist an applied force
without exerting large contact reaction forces. The resulting fixtures
are then returned to the user.

We believe this is the first modular fixture design algorithm that is
*complete* in the sense that it is guaranteed to find an admissible
fixture if one exists. It is essential to acknowledge that such a fixture
does not always exist; for example, parts that are much smaller than the
lattice spacing will have no available fixture design. Other parts
for which no fixture exists are considered in [Zhuang 1994].

This algorithm is guaranteed to find the *optimal* fixture.
Since the algorithm constructs the set of all fixture designs possible for
a given modular fixturing kit, the algorithm can score the constructed
designs according to a user-supplied quality metric, sort the results,
and return the fixture with the highest score. The contact-force analysis
included in our implementation is one example of such a metric.

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.

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..

Reauleaux showed that at least four wrenches are necessary for form
closure in the plane [Reuleaux 1876]. Recently, Markenscoff *et al.*
showed that four wrenches are sufficient for any piecewise-smooth
compact connected planar body, excluding surfaces of revolution
[Markenscoff 1990]. For objects in 3-d space, it is known that seven
wrenches are necessary for form closure [Somoff 1900, Lakshminarayana 1978];
Markenscoff *et al.* showed that seven wrenches are sufficient for
polyhedra [Markenscoff 1990].

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, *et al.* showed that for the
modular fixture kit employed in this paper, there exist polygons of
arbitrary size for which no fixture design exists [Zhuang 1994].

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.

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 *et al.* developed a procedure that designs
fixtures for prismatic parts using screw algebra, geometric heuristics to
place locators at positions that allow easy loading of the part, and a
rotation center analysis to place clamps [Chou 1989].As with Mani, they
did not consider the constraints imposed by a modular fixture kit. Kim
developed a procedure that designs fixtures using top clamps
[Kim 1993]. The procedure focuses primarily on placing the top clamps and
estimating the required clamping force; lateral locators are only allowed on
user-specified orthogonal datum surfaces,
which are assumed to be aligned with
the hole grid. Our work complements Kim's result, since we generate all
possible locator placements for an arbitrary part shape but do not address top
clamping. Kim also developed a procedure for designing fixture setups using a
vise. In related work, Hayes and Wright developed an expert system for
planning machining operations ,[Hayes 1989, Hayes 1990]. This system analyzed
the interaction between machined features and constructed a sequence of setup
plans that would allow a part to be machined from raw stock while avoiding
feature interaction problems (such as drilling into a slanted surface). This
system employed
a simplified feature-based geometric analysis to design
fixtures; it may be possible to extend the scope of this high-level planning
system by including the more detailed geometric analysis presented in this
paper. Finally, Englert and Sakurai also reported fixture design methods
based on geometric heuristics
[Englert 1987, Sakurai 1990]; these methods do not have the generality of the
algorithm presented here.

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 *(x,y)* position may
not be known until the location of the fourth fixel is chosen, at which time
the part pose may be determined. Consequently their algorithm includes another
nested loop instead of the direct force-sphere construction we employ.
Further, their algorithm does not require a check for interference between the
part and the clamp body. The net result of these differences is that their
algorithm entails one less factor of * n* and one more factor of
* d * in its asymptotic complexity (see Section Complexity), while
providing the additional capability of designing fixtures with two translating
fixels instead of just one.

- 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.

**Input:**

- 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.

- 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.

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.

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 _{1} , e_{5} , e_{2})* and

Given a combination of three edges,* (e _{a} , e_{b} , e_{c})*, we can assume without
loss of generality that

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 _{a}* and the second locator contacts

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 *[O _{min} , O_{max}]*
interval of reachable part angles. Then we transform this interval by
adding the

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.

To generate the set of form-closure clamp positions for a locator setup, we
perform a constraint analysis on the *force sphere,* a unit sphere
centered at the origin of the *(F _{x} , F_{y} , T/P )* space of planar
forces.

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 *P* to
correspond to the the part center of mass and radius of gyration; however,
in our purely static analysis these may be chosen arbitrarily.

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.

The 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 *p'* within a force-sphere region, the maximum
contact reaction force may be constructed directly. First the negation
of the point* -p'* is constructed. Since the four force-sphere points
corresponding to fixel contact normals positively span the force sphere,
the point *-p'* must lie in a triangle formed by three of the normals,
along an edge formed by two normals, or exactly coincide with one
normal. In each of these cases,* -p'* may be expressed as a positive
linear combination of the corresponding normals, and the associated
scaling factors may be computed directly. These scaling factors
determine the magnitude of each contact reaction force in the force
space; projecting the resulting scaled vector onto the *[F _{x} ,F_{y}]* plane
produces the contact reaction force in the real space. The maximum
contact reaction force then corresponds to the force with the largest
magnitude

An asymptotic upper bound on the running time of the algorithm can be derived
as follows. For the given polygonal part, let* n* be its number of edges and
* d* the length of its maximum diameter (in units of lattice spacing). The
enumeration considers *O(n ^{3})* triplets of edges. For each triplet of edges,
there are

For questions or comments, please send e-mail to:

Dr. Ranndy Brost or

Prof. Ken Goldberg