Minimal Fixturing of Frictionless Assemblies: Complexity and Algorithms

In many assembly tasks it is necessary to ensure the stability of a subcollection of contacting objects. To achieve stability, it is often necessary to introduce fixture elements (also called ``fingers' in some work) to help hold objects in place. In this paper the complexity of stabilizing multiple contacting bodies with the fewest number of fixture elements possible is considered. Standard fixture elements of the type explored in previous single-object grasping work are considered, along with a generalized variant of fixture elements. Both form-closure (complete immobility of the assembly), and first-order stability (stability of an assembly in the neighborhood of a specific external force and torque on each body) are considered. The major result is that for three of the four combinations of fixture element varieties and stability considered, achieving an optimal solution (that is, finding a smallest set of fixture elements yielding stability) is NP-hard. However, for many fixturing problems it seems likely that suboptimal, yet acceptably small solutions can be found in polynomial time, and some candidate algorithms are presented. Received May 24, 1994; revised January 6, 1995, and February 3, 1995.     

A CAD-Based hierarchical approach to interference detection among fixture modules in a reconfigurable fixturing system

A reconfigurable fixturing system has been developed for a computer-integrated assembly environment. The fixturing system employs a number of fixture modules which are set-up, adjusted and changed automatically by the assembly robot. A dedicated software program has been developed for the design, analysis, and verification of the fixture layout. The software program has been integrated with a commercially available computer-aided design (CAD) package to provide a user-friendly platform for modeling and display purposes. The robot program for setting up, adjusting, and dismantling the designed fixture is generated automatically. Interference between fixture modules during the fixture construction may arise due to incorrect selection of the fixture contact points at the design stage. The objective of the work described here is to develop a hierarchical approach for calculation of interference between fixture modules in a reconfigurable fixturing system. The formulation for the interference detection employs geometrical constraints as the basis. The approach does not require detailed simulation of the fixture construction for interference detection.     

Development of an automated flexible fixture for planar objects

A three fingered automated flexible fixturing system has been developed to fixture planar objects in a machining process. The fixturing system consists of two computer numerically controlled (CNC) modules, an auxiliary mechanism and a fixturing algorithm. This fixture is designed on the idea of the minimum number of fingers needed to immobilise an object. The fixturing algorithm is developed on the concept of the maximal inscribed circle in a polygon. It offers the flexibility to reconfigure the fingers of the system to accommodate workpieces of different shapes and sizes. A prototype of the system has been successfully built and tested, showing satisfactory performance in mechanical design and automatic control over the configurations of the fingers. Examples are given of the application of the system with objects of different shapes. The system is shown to be flexible, reconfigurable and automatic, capable of fixturing planar objects of different shapes and sizes in the machining process.     

Finite element analysis and optimization in fixture design

Fixturing locating point synthesis considers the workpiece and the fixturing elements to be rigid, but however they are elastic and deformable. To ensure sustained quality of manufacture to meet the design tolerances, fixture design must be predictably repeatable. This paper is concerned with minimizing deformation of the workpiece due to machining loads about fixturing support positions, especially in thin castings. Finite element analysis is used in simulating the deformation of the workpiece at selected points. An optimization algorithm is developed to minimize deflections at these selected nodal points by considering the support and tool localtions as design variables. The resulting support locations and tool point designs ensure part support, kinematic closure and minimal workpiece deflections during machining.     

Computer-aided analysis of reconfigurable fixtures and sheet metal parts for robotic drilling

This paper presents an automated manufacturing system for drilling sheet metal parts. All stand-alone systems such as the robot, a set of reconfigurable fixtures and the CAD/CAM workstation have been integrated into a flexible manufacturing system. This system analyzes and evaluates a given fixturing layout and assembles the reconfigurable fixtures automatically using a robot manipulator. An optimum fixturing layout and assembly are achieved by examining the workpart from a stress-strain point of view. In addition, issues such as geometric constraints, yielding and buckling, database design, collision detection, fixturing sequential control and the automatic assembly of fixture elements are considered. The computational and analytical concepts for the reconfigurable fixturing and drilling system are also presented in this paper.     

A genetic algorithm based approach to optimal fixture configuration

In this paper the application of genetic algorithms (GAs) to the fixture configuration optimisation problem is presented. A general purpose fixturing verification system has been developed to check the validity of individual fixture configurations by analysing various contact types in the workpiece-fixture system. Based on the information provided by the verification system, a genetic algorithm based approach carries out the evaluation process to determine the most statically stable fixture configuration among a large number of candidates. The preliminary implementation is introduced to demonstrate the ability of GAs and two different coding schemes are tested to explain their influence on the performance of GAs.     

Design and implementation of robot-operated adaptable and modular fixtures

This paper presents the design issues and hardware implementation for robot-operated automatic modular and adaptable fixtures. Modular fixtures are workholding devices made from stackable self-contained modular elements. Adaptable fixtures provide surface contact with the workpiece and therefore can adapt to the workpiece geometry. These fixtures are shown to have several advantages over conventional fixtures. Issues in modularity and adaptability for workpiece fixturing are discussed for the purpose of evaluating automatic modular fixtures in flexible manufacturing systems. The basic design requirements for robot-operated modular and adaptable fixturing systems are developed and classified into mechanical and operational. Automatic assembly issues such as the use of special mating surfaces, compact actuators for active modules, as well as the importance of communications between the robot manipulator and the modular fixture are discussed.

Hardware design and implementation of a shape memory alloy actuated locking module and a discrete conformable surface module are presented. Performance characteristics such as free-play, stiffness and time response were evaluated experimentally for the locking module. Several workpiece geometries are tested on the comformable surface module.     

Expansion of Linear Steiner Trees

A Steiner tree T on a given set of points A is called linear if all Steiner points, including those collapsing into their adjacent given points, lie on one path referred to as its trunk. Suppose A is a simple polygonal line. Roughly speaking, T is similar to A if its trunk turns right or left when A does. In this paper we prove that A can be expanded to another polygonal line, and T can be constructed in linear time using this expansion method. Received January 15, 1995; revised November 19, 1995, and February 3, 1996.     

Towards the design and development of a knowledge-based universal modular jigs and fixtures system

Jigs and fixtures are one of the important aspects of manufacturing. Parts may have different sets of fixturing requirements and call for different design strategies. Although there are numerous possibilities for fixture designs, a few basic configurations are clearly identifiable. Computer aided design (CAD) has done a little in assisting designers to design jigs and fixtures, making decisions of the best design selection, and providing designers with suggestions. The goal of this paper is to develop and document the design parameters and specifications utilized in jigs and fixtures design using universal modular jigs and fixtures design system (UMJFS). This is the first step to develop a knowledge-based Jigs and Fixture design and selection system. This application has the advantages of making the fixture design information completely modular and transparent, providing better match to the working conditions, reducing lead-time, and generally providing a significant enhancement of fixture productivity and economy. UMJFS has different standard and modular elements. This makes jigs and fixtures elements interchangeable and reusable. Designing a UMJFS then becomes a task of selecting and assembling the proper elements together.     

Constructing minimum deflection fixture arrangements using frame invariant norms

This paper describes a fixture planning method that minimizes object deflection under external loads. The method takes into account the natural compliance of the contacting bodies and applies to two-dimensional and three-dimensional quasirigid bodies. The fixturing method is based on a quality measure that characterizes the deflection of a fixtured object in response to unit magnitude wrenches. The object deflection measure is defined in terms of frame-invariant rigid body velocity and wrench norms and is therefore frame invariant. The object deflection measure is applied to the planning of optimal fixture arrangements of polygonal objects. We describe minimum-deflection fixturing algorithms for these objects, and make qualitative observations on the optimal arrangements generated by the algorithms. Concrete examples illustrate the minimum deflection fixturing method. Note to Practitioners-During fixturing, a workpiece needs to not only be stable against external perturbations, but must also stay within a specified tolerance in response to machining or assembly forces. This paper describes a fixture planning approach that minimizes object deflection under applied work loads. The paper describes how to take local material deformation effects into account, using a generic quasirigid contact model. Practical algorithms that compute the optimal fixturing arrangements of polygonal workpieces are described and examples are then presented.     

Multi-objective optimal fixture layout design

This paper addresses a major issue in fixture layout design to determine and evaluate the acceptable fixture designs based on multiple quality criteria and to select an optimal fixture with appropriate trade-offs among multiple performance requirements. The performance objectives considered are related to the fundamental requirements of kinematic localization and total fixturing (form-closure). Three performance objectives are defined as the workpiece localization accuracy and the norm and dispersion of the locator contact forces. The paper focuses on multi-criteria optimal design with a hierarchical approach. An efficient interchange algorithm is extended and used for different practical cases, leading to proper trade-off strategies for performing fixture synthesis. Examples are given to illustrate empirical observations with respect to the proposed approach and its effectiveness.     

Qualitative analysis and quantitative evaluation of fixturing

Form-closure is considered as a purely geometric property of a set of unilateral contact constraints such as those applied on a workpiece by a mechanical fixture. This paper provided qualitative analysis of form-closure fixturing. The necessary and sufficient condition for form-closure fixturing is derived. Some fundamental problems related to form-closure are solved such as minimum number of frictionless contact points and the way to arrange them to achieve form-closure. On the basis of qualitative analysis, the quantitative evaluation of form-closure is investigated. To assess quantitatively the form-closure fixturing, two quantitative indices, one to minimize the sum of all normal contact forces and the other to minimize the maximum normal contact force, are presented. Finally, the given example verifies the analysis method and evaluating indices.     

An integrated fixture planning and analysis system for machining processes

Fixture planning is an important part of computer-aided process planning (CAPP), which is the link between design and manufacturing in a CIM environment. This paper presents a rational approach to computer-assisted fixture planning (CAFP), emphasizing integration of fixture planning with process planning, an issue that has not been adequately addressed until very recently. A systematic approach to fixture selection is outlined for planning of modular fixtures. A prototype CAPP-CAFP system has been developed at UCLA and linked to a commercial CAD system, namely, CADAM. Part design information can be extracted from the CAD model and multiple-view engineering drawings of a part stored in the CADAM system. Modular fixture elements can be selected automatically by the CAPP-CAFP system and the generated fixture layout can be displayed on the screen. Included also in the system is a fixture analysis module for verification and rationalization of a fixturing scheme. The force analysis module has a built-in local optimization routine that can determine the clamping forces of more reasonable magnitudes. The friction forces between the fixture and the workpiece can also be considered for simple cases.     

Multi-Objective Approach to Automated Fixture Synthesis Incorporating Deep Neural Network for Deformation Evaluation

In machining, the synthesis of a fixturing schema significantly impacts the accuracy of the final product. Moreover, A robust and automatic configuration of fixture elements can reduce production costs and eliminate the need for expert labor to perform the task. Given the multi-modal problem of fixture synthesis, this article presents a multi-objective approach to fixture synthesis in the discrete domain. The performance criteria are localization accuracy, detachment of locators, workpiece deformation, severity and dispersion of reaction loads, and the spacing between contact points. Optimization is performed via an improved Declining Neighborhood Simulated Annealing algorithm (DNSA). To achieve consistent performance over different inputs, the number of iterations follows a Shanon entropy index reflecting the recurrence of folds/corners. Except for deformation, all other objectives are derived from the kinematic analysis of the workpiece-fixtures system. In contrast, deformation is estimated via a Constitutive Deep Neural Network (CDNN). Both models incorporate the machining loads as quasi-static intervals. A new strategy is adopted for the trade-off based on the Z-score quantification of objectives through a pre-calibration run of DNSA. Numerical examples demonstrate the implementation flow of our generalized CAD-based tool developed for the purpose. The approach is verified and proved efficient in automating the robust selection of a fixture layout for a prismatic workpiece.     

Automated fixture configuration for rapid manufacturing planning

The wide adoption of agile manufacturing systems has necessitated the design and use of fixtures or work holding devices that have in-built flexibility to rapidly respond to part design changes. Despite the availability of reconfigurable fixtures, practical fixture configuration largely remains an experience driven manual activity to enable customization for varying workpiece geometry, and most automated solutions do not scale well to accommodate such variation. In this paper, we address the problem of rapidly synthesizing a realistic fixture that will guarantee stability and immobility of a specified polyhedral work-part. We propose that the problem of automated fixture layout may be approached in two distinct stages. First, we determine the spatial locations of clamping points on the work piece boundary using the principles of force and form closure, to ensure immobility of the fixtured part under external perturbation. In particular, we show that the candidate restraints mapped to the six dimensional vector space of wrenches (force–moment pairs) may be hashed in a straightforward manner to efficiently generate force closure configurations that restrain part movement against large external wrenches. When clamps are allowed to exert arbitrarily high reaction forces on the part, the spatial arrangement of the clamping locations ensures the part is in form closure. On generating force/form closure configurations, the chosen locations are matched against a user-specified library of reconfigurable clamps to synthesize a valid fixture layout comprising clamps that are accessible and collision free with each other and the part. Additionally, in the case of determining machining setups the clamps are chosen to avoid collisions with the moving cutting tool. We demonstrate fast algorithms to perform both location selection and fixture matching, and show several results that underscore the practical application of our solution in automated manufacturing process planning.     

Maintaining Regular Properties Dynamically in k-Terminal Graphs

The t -topology tree data structure is developed for maintaining t -ary trees dynamically. Each of a certain set of tree operations is shown to take O(log n) time, where n is the number of vertices in the trees. The t -topology trees are used to maintain any given regular property on members of the family of k -terminal graphs under a variety of dynamic graph operations. Received February 1994; revised February 1995.     

Intelligent Fixture Design through a Hybrid System of Artificial Neural Network and Genetic Algorithm

In designing fixtures for machining operations, clamping scheme is a complex and highly nonlinear problem that entails the frictional contact between the workpiece and the clamps. Such parameters as contact area, state of contact, clamping force, wear and damage in the contact area and deformation of the component are of special interest. A viable fixture plan must include the optimum values of clamping forces. Along research efforts carried out in this area, this comprehensive problem in fixture design needs further investigation. In this study, a hybrid learning system that uses nonlinear finite element analysis (FEA) with a supportive combination of artificial neural network (ANN) and genetic algorithm (GA) is discussed. A frictional model of workpart–fixture system under cutting and clamping forces is solved through FEA. Training and querying an ANN takes advantage of the results of FEA. The ANN is required to recognize a pattern between the clamping forces and state of contact in the workpiece–fixture system and the workpiece maximum elastic deformation. Using the identified pattern, a GA-based program determines the optimum values for clamping forces that do not cause excessive deformation/stress in the component. The advantage of this work against similar studies is manifestation of exact state of contact between clamp elements and workpart. The results contribute to automation of fixture design task and computer aided process planning (CAPP).     

Tree-Based Parallel Algorithm Design

In this paper a systematic method for the design of efficient parallel algorithms for the dynamic evaluation of computation trees and/or expressions is presented. This method involves the use of uniform closure properties of certain classes of unary functions. Using this method, optimal parallel algorithms are given for many computation tree problems which are important in parallel algebraic and numerical computation, and parallel code generation on exclusive read and exclusive write parallel random access machines. Our algorithmic result is complemented by a P-complete tree problem. Received February 13, 1995; revised March 25, 1996.     

Case based reasoning method for computer aided welding fixture design

This paper presents a case-based reasoning (CBR) method for welding fixture design, a critical issue in the manufacturing of large and complicated equipment. However, previous fixture design research has mainly focused on machining fixtures rather than welding fixtures. In this paper, an approach of data abstraction for fixture design information representation is proposed, first to systemize and manage myriads of fixture related resources, e.g., past fixture design solutions, fixture units depository. Based on this approach, a multi-level CBR method for welding fixture design is then presented. This method could help designers, by referencing previous design cases, to make a conceptual fixturing solution quickly and, finally, finish the detailed solution of fixture design.     

The integration of modular fixture database, fixturing knowledge base and 3-D fixture planning interface

The objective of this project is to present a computer aided fixturing system (CAFS), which integrates modular fixture database, fixture positions knowledge base and 3-D graphic display interface. The system will automatically select and layout the fixture elements to secure a workpiece through an interactive progress. This work can be sub-divided into three tasks. The first task is to build a modular fixture element database. The second task is to determine true positions of modular fixture elements given a set of fixture points, called fixture configuration. The third task is to provide a 3-D graphic interface to display and refine the fixture plan interactively. The system will be developed on the platform of a solid modeler, I-DEAS. Using this platform, the user can graphically rearrange fixture elements to refine the fixture plan.