IEEE TRANSACTIONS ON ROBOTICS AND AUTOMATION, VOL. 12, NO. 1, FEBRUARY 1996 31 A Complete Algorithm for Designing Planar Modular Using Fixtures Components Randy C. Brost, Member, IEEE, and Abstruct- Commercially 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 admis- sible 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. I. INTRODUCTION OST automated manufacturing, assembly, and inspec- M tion 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 [ll, PI. This is partly due to the uncountable set of alternative fixture designs that must be considered in the general case. One way Manuscript received January 15, 1994; revised December 9,1994. The work of R. C. Brost was supported by the U.S. DOE under Contract DE-ACO4- 94AL85000. The work of K. Y. Goldberg was supported by the NSF under Award DDM-9215362 and Award IRI-9123747, the NYI under Award IRI- 9457523, and by equipment grants from Adept Technology, Inc., and Qu-CO, Inc. R. C. Brost is with Sandia National Laboratories, Albuquerque, NM 87185 USA. K. Y. Goldberg was with the University of Southem California, Los Angeles, CA 90089 USA. He is now with the Department of Industrial Engineering and Operations Research, University of California, Berkeley, CA 94720 USA. Publisher Item Identifier S 1042-296X(96)01060-3. Kenneth Y. Goldberg, Member, IEEE 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 VI. The concept of modular fixturing using a family of inter- changeable components was originally developed in England during World War 11, and has resulted in a variety of commer- cially available modular fixturing systems [4]. These systems typically include a square lattice of tapped and doweled holes with spacing toleranced to zt0.0002 in 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 temfiel (fixture element) to refer to either a locator or a clamp and the temfiture to refer to a geometric arrangement of three locators and one clamp on the lattice. An acceptable fixture design must satisfy several require- ments. 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 [5]. 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 fixe1 makes point contact with only one 1042-296W96$05.00 0 1996 IEEE32 LEEE TRANS linear edge of the part. Given a part as input, the algorithm efficiently enumerates all admissible fixtures and ranks them according