2 A multi-agent approach to fixture design.pdf

Journal of Intelligent Manufacturing 12, 3142, 2001 # 2001 Kluwer Academic Publishers. Manufactured in The Netherlands. A multi-agent approach to fi xture design V. SUBRAMANIAM,* A. SENTHIL KUMAR and K.C. SEOW Department of Mechanical and Production Engineering, National University of Singapore, 10 Kent Ridge Cresent, Singapore 119260, Republic of Singapore Received August 1999 and accepted March 2000 The design of fi xtures is a highly complex process that requires the human designer to draw from his rich experience. In addition, for a given workpiece, multiple solutions may exist. By exploiting the recent advances in CAD/CAM and Artifi cial Intelligence techniques, one may constrain the multiple solutions such that only good designs (measured through performance measures) are considered. In this paper, a multi-agent fi xture design system is proposed that harnesses the advantages of genetic algorithms and neural networks. This system attempts to capture the relevant domain knowledge and uses it to produce acceptable solutions effi ciently. The system is applied to a case problem and the suggested fi xturing solution is compared to one offered by a human designer. The agreement between the two solutions is very close. Keywords: Fixture design, neural networks, back propagation, genetic algorithms, multiple agents 1. Introduction Fixtures are workholding devices that are used in manufacturingoperationssuchasmachining, assembly, inspection, etc. (David and Reid, 1991; Nee et al., 1995). For a given workpiece, the fi xture design is not unique since numerous designs are possible. Traditionally, the design of a fi xture relies heavily on the designers expertise and experience. Performance evaluation of a fi xture design solution is also very diffi cult due to the highly non-linear relationship of the design parameters. Consequently, for a given workpiece, it is not immediately apparent if a fi xture design solution is optimal or near optimal. This paper attempts to replace the human expert designer with artifi cial intelligence agents (Dini, 1997; Nelson and Illington, 1991; Senthil Kumar et al., 1998) such as neural networks (NN) and genetic algorithms (GA). A hybrid combination (Goonatilake and Khebbal, 1995; Kandel and Langholz, 1992) of GA and NN is proposed to form the basic structure of a multi-agent fi xture design System (MAFDS). GA has been reported to be an effective search mechanism for locating optimal or near optimal solutions in large and complex solution spaces (Arena et al., 1993; Montana, 1995; Goldberg, 1989) similar to the fi xture design problem. The proposed MAFDS consists of two main components, namely, the fi xture designer and the fi xture evaluator (Fig. 1). For a given fi xture design problem, the workpiece and process information can be easily determined. The fi xture designer and fi xture evaluator will use this problem-dependent informa- tion in the design process. The proposed MAFDS will be illustrated with prismatic workpieces consisting of simple features such as holes and steps (Fig. 2). For such workpieces, the workpiece and process information required for the fi xture design process can be categorized as follows: *Workpiece information 1. Workpiece weight 2. Part size 3. Premachined features. *Process information 1. Batch size *Corresponding author. 2. Spindle speed 3. Operation type 4. Base support surface 5. Primary locating surface 6. Secondary locating surface. In addition, the basic skeletal confi guration of a fi xturefortheseprismaticworkpiecescanbe described by the following seven components: 1. Base locators 2. Side locators 3. End locators 4. Clamping directions 5. Type of clamp 6. Type of clamp actuation 7. Fixture body. The combinations of the variants of these seven components constitute the design space of fi xtures (Table 1). The fi xture designer uses GA to search through this space for an optimal or near optimal fi xture design. Each fi xturing design is represented as a chromosome (concatenated string) of the seven components listed above and each individual compo- nent is referred to as a gene. The fi xture designer selects chromosomes for reproduction based on their respective fi tness values. New fi xture designs of better fi tness values are evolved through genetic operators such as crossover and mutation. This cycle of operations are repeated for several generations until a fi xture of good fi tness is obtained. The fi xture evaluator uses a neural network to evaluate the fi tness values of individual chromo- somes. Each chromosome (fi xturedesign) is evaluated using the workpiece and process information, the fi xture confi guration and the following performance criteria: *Ease of loading and unloading *Cost *Rate of production. The evaluated fi tness value is used by the fi xture designer for the selection and reproduction of the chromosomes. Fig. 1. Basic framework for the MAFDS. Fig. 2. A prismatic workpiece (locating fi nger). 32Subramaniam, Kumar and Seow Table 1. Performance matrix No.Input typeVariantsCodeEase of loading and unloading Production rateCost EffectScoreEffectScoreEffectScore 1Base locatorsFlat with slot2Easy90Fast80High80 Flat1Easy90Fast80Medium60 3 points0Medium60Medium40Low30 2Side locatorsFlat2Easy60Fast80High50 2 points1Medium30Medium40Low10 1 point Dirk et al., 1993; Munro, 1993). There have been recent attempts to replace the back-propagation training algorithm with a GA training algorithm (Arena et al., 1993; Montana, 1995; Dirk et al., 1993). This training algorithm has the potential of locating regions of very high performance, but due to the stochastic behavior of GA, one can only expect quasi-optimum (frequently good) training (Alba et al., 1993). Ithas also been reportedin the literature that by Table 2. Sample fi tness calculation Sample input combination for locating fi nger (Fig. 2) is as follows: f2 1 1 2 2 1 2 1 1 0 0 1 1 1 1 1g Scores assigned to selected input variants are tabulated as follows: Information typeInput typeSelected input variantScores assigned TypeCodeEase of loading and unloading Production ratei Costi Fixturing componentsBase locatorsFlat with slot2908080 Side locators2 points1304010 End locators fl at1608040 Clamping direction2 sides27090NA Type of clampToggle2708040 Type of clamp actuationManual140?3010 Fixture bodyWelded2NANA10 Process informationBatch sizeMedium1NANA50 Spindle speedFast1NA9080 Operation typeMilling0401070 Workpiece informationWorkpiece weightLight06060NA Part sizeMedium160NA50 Premachined featuresHole15050NA Support surfacePlane1808030 Primary locating surfacePlane1708020 Secondary locating surfacePlane1608010 Total780850500 Fitness?780?850?500 ?1130 NA: Choice of variant of the corresponding component was not considered in evaluating the performance criteria. A multi-agent approach to fi xture design35 employing local optimization, one can substantially improve the performance of genetic algorithms (Ulder et al., 1990). Therefore, a hybrid training approach based on Genetic Algorithms that uses back-propagation as a form of local optimization is proposed. The local optimization was used for a small number of epochs, as experience has shown that the marginal improve- ment in increasing the number of epochs is relatively insignifi cant.Thepseudocodeforthistraining algorithm is as follows: Randomly generate a population of neural net- works (chromosomes in GA) Locally optimize the population Evaluate fi tness of chromosomes Repeat until termination criteria Mutate all chromosomes Selection Crossover Local optimization of offspring chromosomes Evaluate fi tness of offspring chromosomes Reinsertion Local optimization of new generation Evaluate fi tness of new generation This hybrid training approach is advantageous as it exploits the strengths of the GA training algorithm and addresses its weakness with the strengths of the backpropagation training algorithm and vice versa. The details of the implementation of the hybrid approach are summarized in Table 3. The neural network to be trained is coded as a chromosome and each gene represents either a bias or a weight in the neural network. The coding is designed such that the bias and weights belonging to the same node in the neural network are grouped together. This coding systemintegratesthealreadyavailabledomain knowledge into the training approach. It also allows Table 3. Summary of the GA-BP hybrid NN training algorithm Selection method? Standard roulette wheel selection. Ranking and scaling of fi tness values are adjusted according to the rate of convergence. ReproductionCrossover? Nodal crossover operatorWeights and bias belonging to each node are grouped into nodal groups in the chromosome string. This modifi ed version of the binary masking approach ensures that crossover is done without destroying the integrity of each nodal group. ? Proportional crossover This operator caters to the continuous nature of the weights and bias. It allows interpolation of genetic material from the initial pool of chromosomes, hence improving the convergence rate. Mutation? Fitness-based mutation rate for individual chromosome This individualistic assignment of mutation rate allows more mutation on weaker chromosome and vise versa. With this approach, it would be less likely to lose good genetic material via mutation. Fitness evaluation? Back propagation Offspring created are locally optimized with BP. The application of BP to the offspring serves two purposes: 1. To local optimized the offspring. This improves their fi tness reasonably, hence prevent offspring of good potential from being discarded. 2. To provide the fi tness value of the offspring. Reinsertion method? Elitist reinsertion After the offspring are evaluation for fi tness, they are combined with chromosomes from their parent generation to form a chromosome pool. Members from this chromosome pool are selected (fi tness-based) to forms the next generation. This approach is adopted to overcome excessive fl uctuation at the later stage of the optimization process. Local minimization? Back propagation This increases the rate of convergence. 36Subramaniam, Kumar and Seow for a more effective nodal crossover operation in the reproduction process. In addition, a proportional crossover was created to cater to the continuous nature of the weights and biases. Numerous neural networks were trained using the two training algorithms, viz, *Back-propagation. *Genetic algorithms with back-propagation for local optimization. Populationswith160chromosomes each,were randomly generated. Each chromosome is a neural network and its effectiveness is measured through the SSE (sum of squared errors). Each population is then trained with the 2500 training examples using the two training algorithms for approximately the same amount of CPU time. These trained population of neural networks are then used on the testing (1000 examples) and verifi cation (500 examples) sets. Based on the average performance, we identifi ed the best and worst population for each training algorithm. The chromosomes of these best and worst populations are then ranked and sorted in ascending order (i.e. chromosomes #1 and #160 are the best and worst chromosomes of a population respectively). Our results for the testing set (Fig. 4) and the verifi cation set (Fig. 5) both indicate that the hybrid training approach is much more effective than the standard back-propagation training algorithm alone. 3. Fixture designer The fi xture designer is at the heart of the proposed MAFDS and is responsible for the formulation of good fi xturing solutions to any prismatic workpiece. The fi xture designer uses genetic algorithms to search the fi xture design space for an appropriate fi xture. The algorithm (pseudocode) used in the fi xture designer is as follows: (Note, that this pseudocode presupposes that the fi xture evaluator has already been trained and is capable of generalizing the fi xturing domain knowledge extracted from the training examples). Fig. 4. Performance of the training algorithms using the testing set. A multi-agent approach to fi xture design37 Fig. 5. Performance of the training algorithms using the verifi cation set. Table 4. Summary of the fi xture designer Selection method? Standard roulette wheel selection. Ranking and scaling of fi tness values are fi xed for the entire search. Reproduction operator Crossover? Multiple-points crossover Standard multiple-points crossover available is used. Mutation? Fitness-based mutation rate for individual chromosome This individualistic assignment of mutation rate allows more mutation on weaker chromosome and vise versa. With this approach, it would be less likely to lose good genetic material via mutation. Fitness evaluation? Fixture evaluator (NN) NN is used to cater to the highly non-linear nature of the relationships between the inputs. Reinsertion method? Elitist reinsertion After the offspring are evaluation for fi tness, they are combined with chromosomes from their parent generation to form a chromosome pool. Members from this chromosome pool are selected (fi tness-based) to forms the next generation. This approach is adopted to overcome excessive fl uctuation at the later stage of the optimization process. 38Subramaniam, Kumar and Seow Randomly generate a population of fi xture design solutions (chromosomes in GA) Evaluate fi tness of chromosomes using fi xture evaluator Repeat until termination criteria Selection Crossover Mutation Evaluate fi tness of offspring chromosomes using Fixture Evaluator Reinsertion The details of the fi xture designer are presented in Table 4. Some of the characteristics of the MAFDS are: * Design knowledge is captured into the fi xture evaluator, and this enables faster evaluation of the fi xture design. The fi xture evaluator is easily trained to adapt to additional examples, as the training and design phases of the MAFDS are independent of one another. *The system has the ability to give not just one optimal solution, but also a group of sub-optimal solutions. This will help the designer to explore alternate design schemes if needed. This facility is not available in conventional optimization techniques such as linear programming. To test the effectiveness of the MAFDS, 330 sample problems were created. Each sample problem repre- sents the inputs to the MAFDS, and consists of the three workpiece and six process information. The outputsofthe system aretheseven fi xturing information. To ensure that the sample problems are well distributed in the problem space, the problem selection procedures were constrained such that between two sample problems, there are at least two inputs that are different. For each sample problem, ten different initial populations were randomly generated and opti- mized using the MAFDS. The results of these test problems are summarized in Table 5. The results show that the average number of generations required for the system to locate the global minimum is 14.3 generations and 99.9% of all the sample problems had their global minima located within 50 generations. Only four out of 3300 sample trials (*0.1%) did not result in the location of the global minima. Thus, based on these results, the fi xture designer is very effective in locating the best fi xturing solution for different sample problems. 4. Case study To demonstrate the feasibility of the MAFDS, a vibrator arm as shown in Fig. 6, is used as a case study. The fi xture confi gurations suggested by the MAFDS and a human fi xture designer are compared and analyzed. The input information, for machining hole #1 (Fig. 6), to the proposed MAFDS is presented in Table 6. For the purposes of a fair comparison, the human designer is constrained to design the fi xture Table 5. Rate of convergence to global minimum No. ofNo. of test groups converging to global minimum of search space generations Experiment no.Averagerequired 12345678910 (%) Less than 1010487799283797486878786 (26.0) Less than 20259255239250265254248267249248253 (76.8) Less than 30320321319320319315318318313319318 (96.5) Less than 40326325319320326326326326326325325 (98.4) Less than 50330329 *330330330329 *329 *330329 *330330 (99.9) Average13.61414.714.214.214.714.713.914.314.314.3 *In these experiments, 1 out of the 330 test groups did not locate the global minimum defi ned by the fi xture evaluator after 50 generations of reproduction. A multi-agent approach to fi xture design39 confi guration using the variants of the seven fi xture components described in Table 1. Using the information in Table 6, the suggested fi xture confi gurations obtained using the MAFDS and the human fi xture designer are summarized in Table 7. The two solutions are exact for fi ve out of the seven fi xture components. The differ only with respect to the choice of base locator and fi xture body types. On careful inspection of the vibrator arm (Fig. 6 and Table 6), we observe that a drilling operation is required and that the base of the workpiece has a step premachined feature. For drilling operations, a suitable fi xture confi guration may use either a 3- pin or a fl at with slot base locator. The human designer rightfully chose the 3-pin confi guration because the premachined step at the base is not negligible and the fl at with slot base locator type would have been less suitable for this workpiece. The MAFDS is incapable of determining if suffi cient locating area is available for fl at locators. In the absence of such information, the systems choice of fl at with slot base locator is a reasonable one. If the batch size for producing a workpiece is small, Table 6. Workpiece and process information for vibrator arm Input typeInput variantCode Batch sizeMedium1 Spindle speedFast1 Operation typeDrilling1 Part weightLight0 Part sizeMedium1 Premachined featureStep0 Base support surfacePl