Abstract:
An intelligent 3D fixture design method, which can solve interference problems between each workpiece, tool and fixture module to design optimal types, specifications and layouts of the fixture system. The design method of the present invention is based on a parametric solid model of 3D CAD software, which uses a space vector to determine if interference exists, and the interference position of such, between the solid models of workpieces, tools and fixture modules, and further utilizes a genetic algorithm to search type and its design shape and position parameters of each fixture modules, to design an optimal fixture system and related specification and layout.

Description:
BACKGROUND OF THE INVENTION 
       [0001]    1. Field of the Invention 
         [0002]    The present invention relates to an Intelligent 3D Fixture Design method, which can be applied in industries that have fixture design optimization requirements, such as in: fixture system design industries, various mechanical process industries, various mechanical assembly industries, etc. The above-mentioned requirements include avoiding interference between fixture modules, avoiding movement interference between workpieces and fixture modules, and/or avoiding interference between tools and fixture modules during operation while satisfying fixing position and/or fixing force requirements, thereby obtaining an optimal (inexpensive) fixture system and related specification and layout. The intelligent 3D fixture design of the present invention solves these above-mentioned problems. 
         [0003]    2. Description of the Related Art 
         [0004]    With improvements in computer-related technologies, more and more industries rely on automated and intelligent computer technologies. Currently, fixture system designs utilize computer-aided design (CAD) software, which has parametric standard parts and/or fixture modules drawing files, however, this CAD software suffers from the following problems:
       It is not easy to determine during the design stage whether there will be interference between fixture modules, interference in the movement between a workpiece and a fixture module, or interference between a tool and a fixture module.   The designing process may involve too many parameters related to select the type of fixture module and design its specification and layout, which are difficult to optimize.       
 
         [0007]    Many studies are related to fixture system designs. Darvish and Gill built a knowledge representation database, which includes machine tool data, workpiece data and standard fixture data into the database to develop a fixture design system for machine tools. Miller and Hannam built a knowledge database for specific fixture designs and developed an interactive CAD/CAM, wherein an inexperienced user could use the data stored in the knowledge database to design a suitable fixture. Grippo et al. use CAD/CAM as a tool to automatically design and assemble a modularized fixture, and then adds a robot arm to achieve complete automation of the fixture system. Boerma and Kals developed a fixture design with automated workpiece positioning to incorporate the entire process planning system of workpieces into the fixture design process. Nee points out that fixture designs can be variant fixture designs and generative fixture designs; in variant fixture designs, since the workpieces are similar, the designer can utilize similar existing fixture formats to design a new fixture; generative fixture designs are used when there are no similar fixture designs. Nee and Kumer utilize a rule-base to develop fixture design expert systems that include workpiece data, process data, machine tool data, cutting tool data and fixture component data as input modules, and provides as an output result a fixture stacked with fixture components. Dong et al. utilize a feature-base to describe the workpiece during manufacturing process to select a best positioning point. Liu utilizes conjugate forms to design a search method of stackable components, and then obtains a new module by disassembly and assembly. 
         [0008]    However, the above-mentioned studies focus on fixture designs for machine tools, which are inadequate for dealing with complicated shapes workpieces, fixtures and tools, or simultaneously providing decisions for types, specifications and layouts of fixtures. These involve in resolving a large numbers of parameters and include the inability to determine whether, and at what position, interference exists, extreme difficulty in obtaining optimal designs, long design times, and poor universality. 
         [0009]    Therefore, it is desirable to provide an intelligent 3D fixture design method that mitigates and/or obviates the aforementioned problems. 
       SUMMARY OF THE INVENTION 
       [0010]    A primary objective of the present invention is to provide an intelligent 3D fixture design method, which can solve interference problems between each workpiece, tool and fixture module, and which optimizes types, specifications and layouts of fixture modules over large numbers of design parameters. As shown in  FIG. 9 , the present invention can check interference between fixture modules, movement interference between workpieces and fixture modules, and/or interference between tools and fixture modules during operation, while satisfying fixing position and/or fixing force requirements of the fixture module, thereby obtaining an optimal (and inexpensive) type and related specification and layout of fixture system. 
         [0011]    The design method of the present invention is based on a parametric solid model of 3D CAD software, which uses a space vector to determine if interference exists, and the interference position of such, between each solid model of the workpiece, tool and fixture module, and further utilizes a genetic algorithm system to search type of each fixture module and its design shape and position parameters, to design an optimal fixture system and related specification and layout. 
         [0012]    The method of the present invention combines the benefits of 3D CAD software, genetic algorithms and special interference algorithm to achieve an optimal design for 3D fixture system. Furthermore, the method consistently obtains stable results, particularly with certain types of complicated workpieces; for example, with medium to large sized complicated car body panel fixture system, the method of the present invention provides a superior performance over conventional fixture design methods. The algorithm used in the method of the present invention includes a special interference algorithm, and a genetic algorithm with integer and symbolic codes. Operators within the genetic algorithm include a selection operation, a crossover operation, and a mutation operation. The method of the present invention provides enormously improved design efficiencies and quality. 
         [0013]    Other objectives, advantages, and novel features of the invention will become more apparent from the following detailed description when taken in conjunction with the accompanying drawings. 
     
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0014]      FIG. 1  is a flowchart of an intelligent 3D fixture design method according to the present invention. 
           [0015]      FIG. 2  is cross-sectional view of fixing directions (S directions) for a fixture module. 
           [0016]      FIG. 3  shows a cross-section of the workpiece being divided into P points. 
           [0017]      FIG. 4  shows fixing points p 2 , pdn 2  for the fixture module on the cross-section direction. 
           [0018]      FIG. 5  shows the workpiece can be removed during the fixture module widely opened. 
           [0019]      FIG. 6  shows no interference between the movement track of the fixture module and the workpiece. 
           [0020]      FIG. 7  shows no interference between the fixture module and the other fixture module. 
           [0021]      FIG. 8  shows no interference between a fixture module and an operating tool (a welding gun). 
           [0022]      FIG. 9  shows an optimal fixture system and related specification and layout. 
           [0023]      FIG. 10  shows an individual possessing 4×N genes with N groups consisted of 4 different gene types in a chromosome. 
           [0024]      FIG. 11  shows costs associated with different types and specifications of fixture modules. 
           [0025]      FIG. 12  shows fitness values of C(N). 
           [0026]      FIG. 13  shows the initial population generated by Genetic Algorithm. 
           [0027]      FIG. 14  shows the diagram of the selection probability for each individual. 
           [0028]      FIG. 15  shows using a crossover operation to generate various offspring. 
           [0029]      FIG. 16  shows a mutation operation and new generators. 
           [0030]      FIG. 17  shows the lowest fitness value, which is also the lowest fixture systems cost. 
           [0031]      FIG. 18  shows an optimal fixture system layout, with parameters sent back to a CAD system to automatically generate a 3D solid model. 
           [0032]      FIG. 19  shows an example of 3D fixture. 
           [0033]      FIG. 20  shows types of fixture module. 
       
    
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT 
       [0034]    The intelligent 3D fixture design method of the present invention has a flow chart as shown in  FIG. 1 , which shows that, after a genetic coding operation, the first group is randomly generated; after a selection operation, a crossover operation, and a mutation operation, a new offspring is generated; after decoding the code and reading the associated fixture design conditions, a cylinder stroke of the fixture module is determined, as are a fixing force of the fixture module, movement tracking and workpiece interference amounts of the fixture module, interference amounts between the fixture module and its neighbor fixture module, and interference amounts between the fixture module and tools. The type, cylinder diameter, cylinder stroke, fixing force, and position of rotation points (Rn, Rm) of the fixture module are thereby obtained. Fitness values of the fixture system are determined; the fitness value order of the parent and the new offspring operated by the mutation operation is calculated, and individuals with better fitness values are selected to form a subsequent new group. 
         [0035]    In these steps, the generation number is checked to determinate whether the predetermined generations have all been executed; if they have, an individual with the best fitness value is displayed, and the program terminated. 
         [0036]    If the predetermined generation number is not finished, the program returns back to the selection operation, crossing operation, and mutation operation, to generate new offspring. The fitness value order of the parent and the new offspring operated by the mutation operation is calculated, and individuals with better fitness values are selected to form a subsequent new group until the predetermined generation number have finished. 
       Special Interference Algorithm 
       [0037]    The special interference algorithm makes use of two vectors {right arrow over (T)} 1  and {right arrow over (T)} 2  that are not located on the same side of a plane as a sufficient and necessary condition, as follows: sign({right arrow over (n)}·{right arrow over (T)} 1 −C)≠sign({right arrow over (n)}·{right arrow over (T)} 2 −C) 
         [0038]    Where, {right arrow over (n)} is the plane normal vector; and 
         [0039]    c is a constant for the plane. 
         [0040]    It is assumed that the fixture module, fixture movement path, or tools are located in a space surrounded by six planes; wherein the six normal vector of the six planes are {right arrow over (n)} 1 , {right arrow over (n)} 2  . . . {right arrow over (n)} 6 , with six corresponding calculation constants c 1 , c 2 , . . . , c 6 ; each calculation constant is the sum of one vector {right arrow over (T)} 1  on the plane and its normal vector {right arrow over (n)} (C={right arrow over (n)}·{right arrow over (T)}); {right arrow over (T)} 1  is a vector surrounded by the six planes, {right arrow over (T)} 2  is an interference calculating point vector; and a determination method is provided as follows:
   1. When ∀i∈[1,2, . . . ,6], sign({right arrow over (n)} i ·{right arrow over (T)} 1 −C i )=sign({right arrow over (n)} i ·{right arrow over (T)} 2 −C i ), {right arrow over (T)} 2  is in the space surrounded by six planes, then there is interference.   2. When ∃j∈[1,2, . . . ,6], sign({right arrow over (n)} i ·{right arrow over (T)} 2 −C i )=0 and ∀i∈[1,2, . . . ,6], i≠j, sign({right arrow over (n)} i ·{right arrow over (T)} 1 −C i )=sign({right arrow over (n)} i ·{right arrow over (T)} 2 −C i ), {right arrow over (T)} 2   is on the edge of the space and on the plane of the normal vector {right arrow over (n)} j , then there is no interference.   3. When ∃j,k∈[1,2, . . . ,6], j≠k, ({right arrow over (n)} j ·{right arrow over (T)} 2 −C j )=({right arrow over (n)} k ·{right arrow over (T)} 2 −C k )=0 and ∀i∈[1,2, . . . ,6], i≠k, i≠k, sign({right arrow over (n)} i ·{right arrow over (T)} 1 −C i )=sign({right arrow over (n)} i ·{right arrow over (T)} 2 −C i ), {right arrow over (T)} 2  is on the edge of the space and on a crossing line of two panels represented by the normal vectors {right arrow over (n)} j  and {right arrow over (n)} k , then there is no interference.   4. When ∃j,k,l∈[1,2, . . . 6], j≠k, k≠l, l≠j, ({right arrow over (n)} j ·{right arrow over (T)} 2 −C j )=({right arrow over (n)} k ·{right arrow over (T)} 2 −C k )=({right arrow over (n)} 1 ·{right arrow over (T)} 2 −C 1 )=0 and ∀i∈[1,2, . . . ,6], i≠j, i≠k, i≠l, sign({right arrow over (n)} i ·{right arrow over (T)} 1 −C i )=sign({right arrow over (n)} i ·{right arrow over (T)} 2 −C i ), {right arrow over (T)} 2  is on the edge of the space and on a crossing point of three planes represented by normal vectors {right arrow over (n)} j , {right arrow over (n)} k  and {right arrow over (n)} l , then there is no interference.   5. When the conditions are beyond the abovementioned four conditions, {right arrow over (T)} 2  is located out of the space surrounded by six planes, and there is no interference.   
 
       Genetic Algorithm 
       [0046]    The genetic algorithm considers every individual of a gene as a parameter and determines the individual of a gene via coding. Assuming the fixture system includes N fixture modules, and the fixture module has T types, the workpiece with its fixing points can be cut into S cross-sections according to fixing directions for the fixture module, and P points are set from the fixing point to the edge of workpiece on every cross-section as positions for fixture module design parameters p 2 , pdn 2 . According to the above-mentioned problem, the fixture system in total has N fixture modules; every fixture module needs to select a type for the fixture module (T types), a fixing direction (S cross-sections ) and individual position for the parameter p 2  and pdn 2  (P points). Therefore, each fixture module has four parameters, and the entire fixture system has 4×N parameters. In the other words, this individual includes 4×N genes, and its genes are shown in  FIG. 10 .
   (1) a 1 , b 1 , . . . , n 1  present fixture module types, which are shown by 0˜T integers in  FIG. 20 .   (2) a 2 , b 2 , . . . , n 2  present fixing directions, which are shown by 0˜S integers in  FIG. 2 .   (3) a 3 , b 3 , . . . , n 3  present positions of the fixture module design parameter p 2 , which are shown by 1˜P integers in  FIG. 3  and  FIG. 4 .   (4) a 4 , b 4 , . . . , n 4  present positions of the fixture module design parameter pdn 2 , which are shown by 1˜P integers in  FIG. 3  and  FIG. 4 .   
 
         [0051]    The limitation condition may be provided as ψ=(ψ 1 , ψ 2 , ψ 3 , ψ 4 , ψ 5 ), which is explained as follows:
   (1) ψ 1  represents the stroke of the fixture module for removing the workpiece, as shown in  FIG. 5 .   (2) ψ 2  represents a necessary condition of the fixing force of the fixture module, such as a fixing force ≧30 kg.   (3) ψ 3  represents no interference between fixture modules, as shown in  FIG. 7 .   (4) ψ 4  represents no interference between the fixture module and an operating tool, as shown in  FIG. 8 .   (5) ψ 5  represents no interference between movement of the fixture module with respect to the workpiece, as shown in  FIG. 6 .   
 
       Fitness Value 
       [0000]    
       
         1. The types of the fixture modules are T 1 , T 2 , T 3 , T 4 , T 5 , . . . , T 12  from simple types to complicate types. 
         2. The cylinder strokes of the fixture module are 50, 75, 100, 125, and 150. 
         3. The cylinder diameters of the fixture module are 40, 50, and 63. 
       
     
         [0060]    The evaluation index C(N) for fitness values takes the lowest total cost of all fixture modules as an optimal value according to the cost of the fixture module type and its cylinder stroke and cylinder diameter, as shown in  FIG. 11 , and an fitness value can be obtained as shown in  FIG. 12 . 
       Generation and Coding of Initial Groups 
       [0061]    The present invention utilizes integer and symbolic coding to indicate every gene value, and then generates chromosome and initial individual groups. The following steps show how to generate M initial individual groups, wherein one set of the vectors (x 1 , x 2 , . . . x i , . . . , x N ) presents a set of N parameters that need to be determined. 
       Algorithm Steps: 
       [0062]    Step 1: randomly generating a random number β, wherein β belongs to [0, 1]. 
         [0063]    Step 2: make x i =l i +β(u i −l i ), x i  is rounded to be integer, wherein l i  and u i  is in the range of x i . 
         [0064]    Step 3: repeating the above steps N times to generate one set of vectors (x 1 , x 2 , . . . , x i , . . . , x N ). 
         [0065]    Step 4: repeating the above steps 1 to 3 M times to generate M initial groups; as shown in  FIG. 13 . 
       Selection Method 
       [0066]    Better parents are selected for a subsequent crossover operation, and a roulette wheel is utilized for the selection. The selection operation selects individuals with higher probabilities in the entire group. 
         [0000]    For example: for individual k, its fitness value is f k , its probability in the entire group is p k , and 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       p 
                       k 
                     
                     = 
                     
                       
                         f 
                         k 
                       
                       / 
                       
                         
                           ∑ 
                           
                             i 
                             = 
                             1 
                           
                           M 
                         
                          
                         
                             
                         
                          
                         
                           f 
                           i 
                         
                       
                     
                   
                   , 
                   
                     
 
                   
                    
                   
                     k 
                     = 
                     1 
                   
                   , 
                   2 
                   , 
                   … 
                    
                   
                       
                   
                   , 
                   
                     M 
                     . 
                   
                 
               
               
                 
                   ( 
                   1.1 
                   ) 
                 
               
             
           
         
       
     
         [0067]    Therefore, an accumulated probability q k  of each set of chromosome in the entire group is: 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       q 
                       k 
                     
                     = 
                     
                       
                         ∑ 
                         
                           i 
                           = 
                           1 
                         
                         k 
                       
                        
                       
                           
                       
                        
                       
                         p 
                         i 
                       
                     
                   
                   , 
                   
                     
 
                   
                    
                   
                     k 
                     = 
                     1 
                   
                   , 
                   2 
                   , 
                   … 
                    
                   
                       
                   
                   , 
                   M 
                 
               
               
                 
                   ( 
                   1.2 
                   ) 
                 
               
             
           
         
       
     
         [0068]    where, M is the number of individuals in the group. 
         [0069]    During the selection operation, the roulette wheel is turned M×P e  times, where P e  is a selection rate, and a member from the parent is selected to become a new member of the group according to each obtained probability. The following steps show how to generate M×P e  new group members. 
       Generation Step: 
       [0000]    
       
         Step 1: randomly generating a random number r from [0, 1]. 
         Step 2: if r≦q 1 , a first individual is selected, if q k−1 &lt;r≦q k , the kth (2≦k≦M) individual is selected. 
         Step 3: repeating the above steps M×P e  times to select M×P e  new group members, as shown in  FIG. 14 . 
       
     
       Generating Various Daughters Via the Crossover Method 
       [0073]    The crossover operation combines single point crossover and linear interpolation with convex set theory to randomly select four crossover points, exchanges the upper and lower two parents on the crossover point, uses linear interpolation to simultaneously calculate two gene values on the crossover points, and then generates two new offspring. For example, two different parents are x=(x 1 , x 2 , . . . , x N ) and y=(y 1 , y 2 , . . . , y N ); assuming point k is a randomly selected crossover point, the crossover method and the new daughters x′ and y′ are shown in  FIG. 15 . 
         [0000]        x ′=( x   1   , x   2   , . . . , x′   k   , y   k+2   , . . . , y   N ), 
         [0000]        y ′=( y   1   , y   2   , . . . , y′   k   , x   k+2   , . . . , x   N ),   (1.3) 
         [0000]    where, x′ k =x k +β(y k −x k ), y′ k =l k +β(u k −l k ), l k  and u k  is the range of y k , and β is a random number belonging to [0, 1]. Furthermore, x′ and y′ are rounded to be integers. This mixing crossover method and the new x k ′ and y k ′ generation method can generate various offspring and avoid premature. 
       Mutation Method 
       [0074]    The mutation operation uses linear interpolation with convex set theory as a basic concept, which randomly selects two points from the same group in one chromosome and performs linear interpolation to complete the mutation. This mutation method may also be viewed as performing a fine tuning in the space. 
         [0075]    For example: the parent is x=(x 1 , x 2 , . . . , x i , x j , x k , . . . , x N ); x i  and x k  are randomly selected for mutation; wherein, x i  and x k  need to be in the same range, or otherwise need to be normalized. The mutation method and new daughter x′ are explained in the following: 
         [0000]        x =( x   1   , x   2   , . . . , x   k   ′, x   j   , x   i   ′, . . . , x   N )   (1.4) 
         [0076]    where, x′ 1 =(1−β)x 1 +βx k , x′ k =βx i +(1−β)x k , and β is a random number belonging to [0,1], and x i ′, x k ′ are rounded to be integers, as shown in  FIG. 16 . 
         [0077]    Please refer to  FIG. 1 .  FIG. 1  is a flowchart of an intelligent 3D fixture design method according to the present invention. 
         [0078]    In step  101 , after the genetic algorithm coding, the first generation group is randomly generated, as follows: the selection operation in step  102 , the crossover algorithm in step  103 , the mutation operation in step  104 , generation of new offspring in step  105 , connecting point A in steps  106  to step  200  to decode the integer code, reading fixture system design conditions in step  201 , calculating cylinder stroke of the fixture module in step  202 , calculating fixing force of the fixture module in step  203 , calculating the interference between the movement track of the fixture module and the workpiece in step  204 , calculating the amount of interference between the fixture module and its neighboring fixture module in step  205 , calculating the amount of interference between the fixture module and the tools in step  206 ; obtaining the type, the cylinder diameter, the cylinder stroke and the fixing force of the fixture module in step  207 ; calculating fitness value of the fixture system in step  208 ; connecting point B in step  107  to step  108  for calculating and sequencing the fitness values of the parents and the offspring after the mutation algorithm, and selecting the individuals with better fitness values as the next new generation group in step  109 . 
         [0079]    In step  110 , all predetermined sets are checked to determine if they have been executed; if all have been executed, step  111  is performed to display the individual with an optimal fitness value, and then step  112  is performed to end the process. 
         [0080]    If not all of the predetermined generations have been executed, the process goes back to the selection operation in step  102 , the crossover operation in step  103 , the mutation operation in step  104 , the generation of new offspring in step  105 , step  106 , . . . , step  109  until all of the predetermined generations have been executed. 
         [0081]    The following description shows how an embodiment of the present invention may be utilized for car door panel welding fixture system optimized design. 
         [0082]    The car door panel fixture system has 12 fixture modules. Each fixture module has its fixing point which had 7 cross-section directions; each cross-section is divided into 30 points from the clamping point to the edge of the car door panel, to be the position points of the fixture module design parameter p 2  and pdn 2 . Therefore, the car doorpanel welding fixture system has 12 fixture modules, with each fixture module having 4 parameters, so that the entire fixture module has 48 parameters. There are 12 types of fixture modules, 7 fixing cross-section directions and 30 position points for the fixture module design parameters p 2  and pdn 2 ; therefore, the range of the entire fixture module selection space is about (12×7×30×30) 12 . 
         [0083]    The intelligent 3D fixture design method may be used to find an optimal 3D fixture module and related specification and layout as follows: 
         [0084]    GA Algorithm Settings 
         [0085]    Parents: 100, offspring: 80 generations: 400 selection rate: 0.8 mutation rate: 0.2 
         [0086]    Genetic Code: 
         [0000]    
       
         
               
               
             
           
               
                   
                   
               
             
             
               
                   
                 0 3 11 24 0 0 26 9 0 3 18 15 0 3 4 16 0 5 10 
               
               
                   
                 5 0 2 20 11 0 3 27 7 0 3 8 10 0 3 15 10 4 3 
               
               
                   
                 23 16 0 3 4 10 1 3 14 13 
               
               
                   
                   
               
             
          
         
       
     
         [0087]    Total fitness value: 238400 
         [0088]    The total fitness value is the lowest fixture system cost, which is 238400, as shown in  FIG. 17 . 
         [0089]    The type of the fixture module and its specifications and position parameters (as shown in  FIG. 18 ) are sent back to the CAD program to automatically generate a 3D solid model (as shown in  FIG. 9 ). 
         [0090]    Result Comparisons: 
         [0000]    
       
         
               
               
               
             
               
               
               
               
             
           
               
                   
                   
               
               
                   
                 prior design 
                 current design 
               
               
                   
                   
               
             
             
               
                   
               
             
          
           
               
                   
                 design hours (Hrs) 
                 112 
                 64 
               
               
                   
                 manufacturing cost (dollars) 
                 275100 
                 238400 
               
               
                   
                   
               
             
          
         
       
     
         [0091]    Although the present invention has been explained in relation to its preferred embodiment, it is to be understood that many other possible modifications and variations can be made without departing from the spirit and scope of the invention as hereinafter claimed.