FIGURE: Four Bar Mechanism and the Coupler Curve
Synthesis of Four-Bar Linkage Mechanisms
using Pattern-Matching Approach
and Genetic Algorithms
Project Report
ME451 Computer Aided Engineering Design
Instructor: Dr Amitabha Mukherjee
Submitted By:
Vipul Kumar Gupta AE (94309)
Shorya Awtar ME(94279)
We have repeated this much often , in our proposal, in the presentation and here we state this fact again that the design of linkage mechanisms is one of the most challenging problems that is faced by a design engineer. Nonetheless, the subject is too interesting and exciting that it instigated us to pick up this area for the current Computer Aided Engineeering Design project.
What we understand of CAED, based on the earlier lectures by Professor Amitabha Mukherjee, is that ,creative and genuine designers are rare and these people invariably have to undertake lots of computational and iteravative procedures while designing, which is a sheer wastage of their valuable time. And furthermore the scope of the problem to be solved might be such that a common engineer (not the creative designer) becomes too unnerved to address it. Here comes the underlying philosophy of CAED, to help the designer, to assist the designer, to cut away the huge time that goes into heavy computational works that buttress every design, to ensure that a person of a lower intellectual status can approach the given problem with CAED as a strong tool in his hands.
Now interpolataing this philosophy to the pertinent topic, we underscore the following.
The four-bar mechanism is a very versatile linkage , the design of which has been used extensively, and can be seen in a huge number of contemporary machines say the Ackerman steering in all automobiles, the sewing machines, earth movers, the bicycle ,packaging machines . . . . the list continues .
Furthermore, points on the coupler ( the link that is floating ) follows fascinating paths of order six (6 degree curves). This property is exploited to materialize designs pertaining to path generation. The example that we cited in the classroom presentation was that, if the crank pin moves in a certain weird path rather than the traditional circle in a reciprocating pump, the thermodynamic efficiency of the process increases. At this stage if we could design a four-bar mechanism ,such that a certain point on its coupler generates this required weird path, then the problem is solved.
Easier said than done!! There is simply no other way to do this than to refer to the standard Hrones Nelson Atlas of four bar mechanisms which catalogues a host of paths and the corresponding mechanisms. The database is finite and even after a particular mechanism has been selected a much finer tuing of the dimensions is a must to match the precise requirements. This truly is a painfully long procedure and involves a lot of iterations.
Now CAED!! Say we present a software which asks the user the curve/path that he wants and after sometime returns the corresponding mechanism. Sounds promising to the fatigued engineer, doesn't it ?
This remains to be the purpose, goal and motivation behind our work on the subject.
There has been considerable amout of serious work going on in the academic circles regarding the generation of fourbar mechanisms which produce desirable coupler curves. We shall present here the review of an article which deals with the subject and offers a tentative approach.
@Article{Hoeltzel/Chieng:1989,
author = { Hoeltzel, D A and Chieng, W-H },
year = { 1989},
keywords = { COMPUTER-AIDED-DESIGN KNOWLEDGE-BASED-METHODS
MECHANISM-DESIGN GRAPH-THEORY HEURISTICS ## },
institution = { Intelligent Design Laboratory,
Columbia University, NY },
title = { Knowledege-based approaches for the creative
synthesis of mechanisms },
journal = { CAD },
volume = { 22 },
number = { 1 },
pages = { 57-67 },
annote = {
This paper presents an approach for mechanism synthesis. It
uses It uses the principles from graph theory and heuristics
for this purpose. A mechanism is represented in the form of a
graph which in turn can be stored as a compact matrix. The
problem of searching through a large data base is an NP complete
problem. Since the CPU time involved in handling an NP complete
problem increases exponentially with the size of the problem, the
potential to solve these NP-complete problems depends on the
availability of certain heuristics. In this paper two alternative
solution strategies are given, "forward design reasoning"
and "backward design reasoning". In back design reasoning
the pattern matching is done by adopting a machine learning approach
based on neural network computing. The paper also gives an example on
the evaluation of the kinematic effects of joint clearances and link
length tolerances on kinematic performance.
- Shorya Awtar/Vipul Kumar Gupta, 10/9/97 },
}
Instead of using heuristics, as suggested by the paper, for search purpose we employ Genetic Algorithms. The details of the process are elaborated upon in the subsequent sections.
Whereas strong analytical tools are coming up to solve five point accuracy or six point accuracy paths but the generation of a closed curve which requires a much higher number of accuracy points, say 50, is simply not possible using any analytical or graphical means. Invariably all the research that is being done in this regard involves matching of the required curve with a database. This search process can be heuristics in some case like in the abovementioned paper or can be GA, the method which we have employed.
To present the problem in an objective fashion we present a formal statement of the problem. A certain amount of information on four bar linkages would be useful in this regard.
A four-bar mechanism is defined in the following way ( see figure ). The fixed link , the crank, the coupler,and the follower are specified in the figure. Each joint between any two consecutive links is a simple hinge (also called an R joint standing for a revolute joint)
FIGURE: Four Bar Mechanism and the Coupler Curve
We are dealing with a special case of four-bar mechanisms. Only those cases which give coupler curves are of our interest. Like in the above case, for a certain dimension for each of the links, the point P on the coupler follows a closed path for a complete rotation of the crank.Such mechanisms are called the Grashoff Mechanisms .The following is true for these
* l(min)+l(max) < l' + l"
l(min) and l(max) are the lengths of the shortest and the longest links respectively, l' and l" are the lengths of the remaining two links. This is formally known as The Grashoff's Criterion.
* the crank is the l(min) for a crank rocker the fixed link is the l(min)for the double crank case
These are the only two cases in which we get closed loop coupler curves.
Of these, for the sake of keeping the computational load on GA low, we are dealing only with crank rocker cases, which are the ones that are actually used in practical applications.
Now, the user inputs the required curve in terms of a sufficiently large no of points via some input mode. The program then searchs one such mechanism that can produce a fairly close coupler curve.
As an output you get a mechanism in terms of five parameters
- L2 -> crank dimension
- L3 -> coupler dimension
- L4 -> follower dimension
- (r, phi) -> defines the location of the germane coupler point wrt the coupler.
FIGURE: Four-Bar Linkage Parameters:
The lengths of the links
are measured as ratios with the fixed base.
The coupler point is given
in polar coordinates.
The methodology followed is simple and straightforward. Two concepts, viz, pattern matching and genetic algorithms are invoked to handle the problem.
First of all we summarize the whole process with the help of a flowchart and subsequently we shall come to the niceties.
FIGURE: Flowchart of the Coupler Curve Matching Process
The salient steps involved in the procedure are,
Now, we proceed to the details
PATTERN MATCHING
Any closed curve or closed loop is uniquely represented by it curvature signature, which is a record of the variation of the local curvature with the arc length. This is a very useful piece of information which we have exploited for the purpose of pattern matching.
We therefore adopt the following procedure .
Start from the left most point on the curve and move along the arc length , recording the local slope theta all the while. The variation of theta with arclength s , at a given point on the curve , is the useful piece of data for us. This can be plotted on a graph with s as the abssica and d(theta)/ds as the ordinate. We note the following properties about the plot between the quantity d(theta)/ds and s :-
All these properties make this particular signature plot an ideal means for pattern matching. If the signature plots corresponding to two curves match, this straightaway implies that the two physical curves match.
It is noteworthy here that in the variation of theta with s , we get discontinuities at 2*n*pi (multiples of 360 degrees) . But the second derivative eliminates this problem since it is independent of the initial values of theta i.e. slope.
This is done for both the curves.
Two similar curves with different dimensions
Curves that are translated in space
Curves that are relatively rotated in the space
Any combination of the above configurations should give a successful match
Thus, we have a very robust and a failproof procedure in which we can match two curves in space. We shall use this algorithm to match coupler curves and then search for a suitable mechanism.
What is a genetic algorithm?
The underlying philosophy of genetic algorithms has been borrowed from the biological concept of genes . We deal with terminologies like mutations ,cross overs and population generation. Every time a set of population of genes is compared with the perfect case. Those genes which perform better in this test are picked up and these are now treated as parent genes. From these a next set of popultion is generated by the mutations and crossover of the parent genes to produce new offsprings. Once again the new population undergoes the same set of processes. This keeps on recurring until the program finds a reasonably satisfactory gene.
Now its application to our case.
As mentioned earlier a fourbar mechanism with a coupler point can be represented by a set of five parameters ( L2, L3,L4,r, phi) . (Please see the figure)
One such set of parameters that uniquely describe a mechanism is called a PHENO_TYPE
Corresponiding to each PHENO_TYPE there exists a GENE or GENO_TYPE which contains all the information of the pheno_type in a coded form. It is nothing but a string of binary bits.
The program randomly generates an initial population (100 in our case) of Genes. Each of these is decoded to the Phenotype .For each Phenotype it generates the coupler curve . Now, this coupler curve is matched with the input required curve(using the pattern matching algorithm explained above) and is accordingly alloted a fitness value.Based on these fitness values , a random group of 50 genes is selected from the population. This is called the tournament selection. Of these 50 , the best fit genes are made the parents, they are mutated and crossed in a controlled fashion, thereby generating the new population. The process repeats on and on.
After each generation the best genes are copied and stored . Finally when all the generations are over , the best of the stored genes is returned and decoded to give the Phenotype which is the final SOLUTION.
A GENE looks like
1110001010101010101010101010101000011110100111110101111011110
comprising of 65 bits
Now , in CROSSOVER
two parent genes are hybridized i. e. crossed . Thus the offspring retains the characteristics of its parents . A high crossover rate leads the process to a local best fit as the parent characteristics become prominent. A low crossover rate implies a higher computation time as many newer genes are tested each time.
In MUTATION ,
drastically different genes are produced by flipping of a certain no. of bits of one Gene.A higher mutation implies that a very wide range of possibilities are being encompassed and also larger time is involved.
This random process of genetic algorithms despite being time consuming does produce very useful results. This became evident after we conducted a number of test runs.
We present a couple of test cases
CASE I
Required Input curve is the bigger (green) curve.
The solution curve that we obtain is the smaller(red) curve which has a fitness value of 97.44 out of 100. The signature plots are presented alongwith.
The corresponding solution mechanism is given by
L2=0.21261 ; L3=8.196209 ; L4=8.391394 ; r= .832998 ; phi= 0.876202;
 |
|
 |
The signature plots as we see are not very close. Since we limited the number of generations to 50 ,this is the best possible match that we could obtain. For a much finer match we would have to run the code for at least 1000 generations. The curvature plots actually reflect the nature of the curves e.g. signature of input curve shows only one prominent peak, this is because the left extreme turn of the input curve has a much higher radius of curvature which implies comparitively a low value of dtheta/ds.
CASE II
This is a double looped input . The solution curve that we obtain here is once again not close enough to the required curve.The number of generations taken here are only 40. Unfortunately we can't work with a higher number of generations. Fitness value of the solution curve is 89.79 and the solution mechanism is
L2=0.40088; L3=6.451035; L4=6.496356; r=6.110822; phi=0.265219
The near proximity between the two signatures is well evident.
 |
 |
One fact is clear from all the test runs that we conducted - No solution with a fitness value of less than 99 out of 100 is an acceptable solution. To achieve such a high degree of closeness to the required curve, the program must make at least 1000 population generations.
In fact an example cited in the book Genetic Algorithms and Engineering Design by Mitsuo Gen ,says that in a certain appln of GA , the best fit was obtained in the 419th generation of the thousand generations that were conducted. Whereas we are working with numbers as low as 40- 50. This is a limitaion, there is some bug in the program that causes a Bus Error as soon as we conduct generations higher than 50.The code runs perfectly well for the first 50 generations. Unfortuantely we have not been able to catch hold of the bug and therefore we have to make a compromise with relatively lower fitness solutions.