Gradient Descent Optimization Approach for Optimal Synthesis of Path Generator Linkage

Gradient Descent Optimization Approach for Optimal Synthesis of Path Generator Linkage

Sandeep Deshmukp, Dr. M. K. Sonpimple2, Arvind Wadgure3, Pratik lande4

Department of Mechanical Engineering,Smt.Radhikataipandav College of Engineering, Nagpur, India,Department of Mechanical Engineering, Priyadarshini College of Engineering, Nagpur, India, Department of Mechanical Engineering, DMIETR,Wardha, India,

Department of Mechanical Engineering, YashwantraoChavan College of Engineering Nagpur, India.

Abstract

A very important task in a design process is how to make a mechanism which will satisfy desired characteristics of motion of a member, i.e. a mechanism in which one part will surely perform desired motion. There are three common requirements in kinematic synthesis of mechanisms: path generation, function generation and motion generation..The gradient descent (also known as steepest descent) optimisation algorithm has been used in the optimisation process. A computer programme based on this algorithm is implemented in MATLAB to obtainthe optimum dimension of four-bar linkage.All this is illustrated on an example of Path synthesis problem having 10 points and 19 variables.

Keyword-optimal synthesis, four bar linkage, objective function,steepest descent optimization algorithm.

1. Introduction

   There are various tools are available for the kinematic synthesis of a mechanism like Graphical approach, Matrix method approach, Complex number modelling but these approaches are valid for three to four precision points. So, it is essential to select as many as points on the given trajectory (path) to get the generated coupler curve very close to the desired coupler curve. Steepest descent approaches are applicable for many precision points so that we will get the exact desired coupler curve. Therefore this Approach is selected for path generation problem. Many techniques for the synthesis of linkages are invented in recent years. Most of these approaches are involved techniques and are mathematically complicated. Only few of them allow a closed from solution. Of these, optimization procedures attempting to minimize an objective function play an important role. A set of inequality constraints that limit the range of variation of parameters may be included in the calculation. The new values of linkage parameters are generated with each iteration step according to particular optimization scheme used. The closest achievable fit between the calculated points and

   desired points is sought. Even the desired points willnot exactly match but this is considered as acceptable result for most engineering tasks. Each optimization approach has as own advantages and disadvantages in term of convergence accuracy, reliability, complexity and speed. Some methods converge even to a minimum value of objective they may not be the best solution. Based on this points there is a lot of scope for application of new methods of optimization for four-bar synthesis problem

   Thispaper explains the basis path synthesis problem in terms of objective function to be minimized and constraints to be satisfied, describes the history and algorithm of steepest descent optimization method adopted in present work which gives the methodology implemented in MATLAB for handling constraints and minimizing the objective function

2. Coupler Point Coordinates

   In the problem of four-bar linkage synthesis there is some number of precision points to be traced by the coupler point P. To trace the coupler point, the dimension of the links (a, b, c, d, Lx, Ly) is to be determined along with the input crank angle 2, so that the average error between these specified precision points (Pxdi, Pydi), (where i=1, 2,N with N as number of precision points given) and the actual points to be traced by the coupler point P gets minimized. The objective or error function can be calculated when the actual traced points (Px, Py) is evaluated which is traced by the coupler point P with respect to the main coordinate from X,Y as shown in Fig.2.1.

   link lengths chosen are not capable of connection for the chosen value of the input angle 2. This can occur either when the link lengths are completely incapable of connection in any position. Except this there are always two values of 3 corresponding to any one value of 2. These are called, (i) crossed configuration (plus solution) and (ii) Open configuration of the linkage (minus solution) and also known as the two circuits of the linkage. The other methods such as Newton-Raphson solution technique can also be used to get approximate solution for 3. The positionof coupler P, with respect to world coordinate system XOY is finally defined by:

   Fig.4.1 Four-bar linkage with ABP as coupler link

   Px= x + Px cos

   – Py sin

   (2.12)

   The position vector of the coupler point P reference frame X-Y can be expressed as a vector equation:

   (2.1)

   whichcan be represented in its components according to:

   Pxr= a cos2 +Lx cos3 +Ly (-sin3) (2.2)

   Pyr= a sin2 +Lx sin3 +Ly cos3 (2.3)

   Here, for calculation the coupler point coordinates (Px, Py), we have to first compute the coupler link angle 3 using the following vector loop equation for

   0 r 0 r 0

   Py= y0+ Pxr sin0 + Pyr cos0 (2.13)

3. Position Errors as objective Function

   The objective function is usually used to determine the optimal link lengths and the coupler link geometry. In path synthesis problems, this part is the sum squares which computes the position error of the distance between each calculated precision point (Px, Py) and the desired points (Pxd,Pyd) which are the target points indicated by the designer. This is written as:

   f X = Pxd Px 2 + Pyd Py 2 (2.14)

   the four-bar linkage:

   (2.4)

   i=1

   where X is set of variables to be obtained by

   This equation also can be expressed in its components with respect to relative coordinates:

   a cos2+ b cos3 -c cos4 -d (2.5) a sin2+ b sin3 -c sin4 =0

   We can compute the angle 3 for known values of 2 and eliminating 4 so, the result will be

   K1cos 3 +K4 cos2 +K5 = cos (2-3) (2.7)

   where

   minimizing this function. Some authors have also considered additional objective functions such as the deviation of minimum and maximum transmission angles min and max from 90o, for all the set of initial solutions considered.

4. The constraints of the linkages

   The synthesis of the four-bar mechanism greatly depends upon the choice of the objective function

   K1=d/a, K4=d/b and K5

   =c2 d2 a2 b2

   2ab

   (2.8)

   and the equality or the inequality constraints which is imposed on the solution to get the

   32

   For this equation following two solutions are

   obtained:31 =

   2tan1 E+ E24DF (2.9)

   2D

   optimal dimensions. Generally the objective function is minimized under certain conditions so that the solution is satisfied by a set of the given constraints. The bounds for variables considered in the analysis are treated as 20 one set of

   = 2tan1 E E2 4DF (2.10)

   2D

   where,

   D=cos2 -K1+K4cos2+K5, E= -2 sin2

   andF=K1+(K4-1)cos2+K5 (2.11)

   These solutions may be (i) real and equal (ii) real and unequal and (iii) complex conjugates. If the discriminates E2-4DF is negative, then solution is complex conjugate, which simply means that the

   constraints, while the other constraints include: Grashof condition, input link order constraint and the transmission angle constraint.

   1. Grahof criterion

      For Grashof criterion, it is required that one of the links of mechanism, should revolve fully by 360o angle. There are three possible Grashof linkages for a four-bar crank chain: (a) Two crank-rocker mechanisms (adjacent link to shortest is fixed) (b) One double crank mechanism (shortest link is fixed) and (c) One double rocker mechanism (opposite to shortest link is fixed). Of all these, in

      the present task, only crank-rocker mechanism configuration is considered. Here, the input link of the four-bar mechanism to be crank. Grashof criterion states that the sum (Ls+Ll) of the shortest and the longest links must be lesser than the sum (La+Lb) of the rest two links. That is:

      (Ls+Ll La+Lb) (or) 2(Ls+Ll) a+b+c+d

      (or) 1 = 2(Ls + Ll) / (a + b + c + d) 1 0 (2.15) In the present work violation is defined as follows:

      Grashofs = 1 if 1> 0

      Or =0 if 1 0

   2. Input link angle order Constraint

      Usually a large combination of the mechanisms exists that generates the coupler curves passing through the desired points, but those solutions may not satisfy the desired order. To ensure that the final solution honors the desired order, testing for any order violation is imposed. This is achieved by requiring that the direction of rotation of the crank as defined by the sign of its angular increments

      2 2 2

      i=( i- i-1), between the two positions i and i-1,

      where i=3,4,5.,N, have same direction as that between the 1st and the 2nd positions ( 2- 1). That

      The condition to be satisfied max(2.19) The constraint given by equations (2.15), (2.16) and (2.19) are handled by penalty method. That is

      the non-dimensional constraint deviation is

      directly added to the objective function for minimization. For example, constraint eq.(2.19) if not satisfied, the penalty term is given as follows:

      = 1 min)( min 2

      =0

      + 1 max)( max 2

      Where,

      Transmin = sign (b2+c2-(d-a)2-2bc cosmin) Transmax =sign (2bc cosmax -b2+c2(a+d)2)

      Thus the solution seeks to obtain a feasible set of optimum values.

      3) Variable Bounds

      All variables considered in the design vector should be defined within pre specified minimum and maximum values. Often, this depends on the type of problem. For example, if we have 19 variables in a 10 point optimization problem, all the variables may have different values of minimum and

      checks the following:

      2 2 maximum values. Generally, in non-conventional

      optimization techniques starting with set of initial vectors, this constraint is handled at the beginning

      Is sign ( i) = sign ( 1- 1) for all i=3 to N? (2.16)

      itself, while defining the random variable values.

      2 2 2

      where, sign(Z)=1 if Z 0

      = -1 if Z<0 (2.16a)If this condition is not satisfied the solution is rejected.

   3. Transmission Angle Constraint

   For a crank-rocker mechanism generally the best results the designers recognize when the transmission angle is close to 90 degree as much as possible during entire rotation of the crank. Alternatively, the transmission angle during entire rotation of crank should lie between the minimum and maximum values. This can be written as one of the constraints as follows. First of all, the expressions for maximum and minimum transmission angles for crank-rocker linkage are defined.

   That is we use the following simple generation rule: X=Xmin +rand (Xmax-Xmin)

   Where, rand is a random number generator between 0 and 1.

5. OVERALL OPTIMIZATION PROBLEM The objective function is the sum of the error function and the penalties assessed to violation the

   constraints as follows:

   F (k) = f(X) + W1 × Grashof + W2 × Tran , whereas

   W1 is the weighting factor of the Grashofs criteria anW2

   is the weighting factor of the Transmission

   max

   = 2cos1 b2 (d+a)2+c2

   2bc

   angle constraints .these additional terms acts as scaling factors to fix the order of magnitude of the

   min

   =2cos1 b2 (da)2+c2 (2.17)

   2bc

   different variables present in the problem or the objective function.

   2

   The actual value of transmission angle at any crank angle is given by:

   max 1 2

   b2 a2 d2 +c2 + 2ad cos

   = 2cos (2.18)

   2bc

6. STEEPEST DESCENT METHOD

The method of steepest descent is the simplest of the gradient methods. Imagine that theres a function F(x), which can be defined and differentiable within a given boundary, so the direction it decreases the fastest would be the negative gradient of F(x). To find the local minimum of F(x), The Method of The Steepest Descent is employed, where it uses a zigzag like path from an arbitrary point X0and gradually slide down the gradient, until it converges to the actual point ofminimum.

FIG. 4.1 The Method of Steepest Descent finds the local minimum through iterations, as the figure shows, it starts with an arbitrary point x0 and taking small steps toward the direction of Gradient since it is the direction of fastest changesand stops at the minimum.

It is not hard to see why the method of steepest descent is so popular among many mathematicians: it is very simple, easy to use, and each repetition is fast. But the biggest advantage of this method lies in the fact that it is guaranteed to find the minimum through numerous times of iterations as long as it exists. However, this method also has some big flaws: If it is used on a badly scaled system, it will end up going through an infinite number of iterations before locating the minimum, and since each of steps taken during iterations are extremely small, thus the convergence speed is pretty slow, and this process can literally take forever. Although a larger step size will increase the convergence speed, but it could also result in an estimate with large error.

1. Algorithm

   The algorithm is initialized with a guess x1, a maximum iteration count Nmax, a gradient norm tolerance g that is used to determine whether the algorithm has arrived at a critical point, and a step tolerance x to determine whether significant progress is being made. It proceeds as follows.

   1 For, k = 1, 2. . . Nmax: 2xk+1 xk kf(xk)

   1. If ||f (x k+1) || < g then return "Converged on

      critical point"123

   2. If ||xk x k+1|| < x then return "Converged on

      an x value"

   3. If f (x k+1) > f (xk) then return "Diverging"

   4. Return "Maximum number of iterations reached"

      The variable k is known as the step size, and should be chosen to maintain a balance between convergence speed and avoiding divergence. Note that kmay depend on the step k. Note that the steepest decent direction at each iteration is orthogonal to previous one. Therefore the method zigzags in the design space and is rather inefficient. The algorithm is guaranteed to converge, but it may take an infinite number of iterations. The rate of converge is linear. Usually, a substantial decrease is observed in the few iteration, but the method is very slow. Where,

      xk, xk+1 = Values of variable in k and k+1 iteration f(x) = Objective function to be minimized

      f(x) = Gradient of objective function k = The size of the step in direction of travel

2. FLOW CHART OF STEEPEST DESCENT METHOD:

FIG 5.3 Flow chart of steepest descent method.

1. RESULT AND DISCUSSION

   7.1) Path synthesis problem having 10 points and 19 variables

   Ten Points Path Generation and 19 design variables: Design variables are:

   X=[a,b,c,d,ly,lx,, 3 , 4, 5, 6, 7, 8, 9, 10 , 0,

   1. Actual points which is traced by the coupler link and the precision points

      yo, lxo]

      2 2 2 2

      2 2 2 2

      Target Points: =

      [(20,10),(17.66,15.142),(11.736,17.878,(5,16.928),

      (0.60307,12.736),(0.60307,7.2638),

      (5, 3.0718),(11.736,2.1215),(17.66,4.8577),(20,10)]

      Limits of the variable:

      a, b, c, d, [5,60];

      lyo,lxo, ly, lx, [-60,60];

      2 2 2 2 2 2 2

      1, 2 , 3, 4, 5, 6 , 10 , 0 [0, 2];

      Table 7.2 Actual points which is traced by the coupler link and the precision points

   2. Multiple solution of coupler curve

      The synthesized geometric parameters and the corresponding values of the precision points (Pxd, Pyd) and the traced points by the coupler point (Px,Py) and the difference between them are shown in table (7.1) and table (7.2) respectively Although the constraint of the sequence of the input angles during the evolution is ignored in this case. The accuracy of the solution in case has been remarkably improved using the present method.fig (7.1) shows the convergence of steepest descent algorithm. Fig 7.2 shows ten target points and the coupler curve obtained using the steepest descent search method.

      7.2) Optimized values for the ten target points problem

      a	b	c	d	lx	ly
      65. 492 1	78. 616 1	65. 699 9	10. 174 8	36. 996 1	46. 80 83	4.3 04 9	4.7 14 5	1. 05 63	1. 70 4

      							lx0	ly0
      2.2 251	2.6 147	3.0 282	3.4 990	3.9 342	4.3 049	1.2 727	9.8 114	7.9 970

      Table 7.1 Optimized values for the ten target points problem

      Fig (7.1)multiple solution of coupler curve

   3. Ten target points and the coupler curve obtained

      Columns 1 through 16

      65.9145 79.0994 64.9069 10.4386 36.2136

      47.1237 4.9782 5.2825 0.9006 1.9093

      2.6710 3.1331 3.5318 4.0167 4.5492 4.9782

      Columns 17 through 19

      4.5593 9.2188 7.9941 f =3.3802e+003

      msg

      ——————————- X =

      Columns 1 through 16

      65.6375 78.7892 65.3948 10.2563 36.7092

      46.9506 4.1708 4.5727 0.9279 1.5803

      2.1124 2.5205 2.9677 3.4441 3.8369 4.1708

      Columns 17 through 19

      0.4439 9.6930 7.9628

      f =

      Fig 7.2 (Ten target points and the coupler curve obtained).

   4. The Matlab program shows the final output as final minimize error for 10 points and 21 variables

   X =

   Columns 1 through 16

   69.7541	83.4937	57.7889	12.8368	29.0996
   49.9909	11.0996	10.4460	-0.5152	3.7542
   6.7239	7.8453	8.1098	8.7228	10.1396
   11.0996

   Columns 17 through 19

   34.4372 3.8311 7.9678

   f =4.0008e+003

   msg

   ——————————— X =

   794.5327

   msg =

   ——————————— X =

   Columns 1 through 16

   65.6375 78.7892 65.3948 10.2563 36.7092

   46.9506 4.1708 4.5727 0.9279 1.5803

   2.1124 2.5205 2.9677 3.4441 3.8369 4.1708

   Columns 17 through 19

   0.4439 9.6930 7.9628

   f =794.5327

   msg

   ———————————

   Solver stopped prematurely.

   fminunc stopped because it exceeded the function evaluation limit,

   options.MaxFunEvals = 1900 (the default value).

   x =

   1.2727 9.8114 7.9970

   fval =13.1193 mymsg =

   My final minimised error final error = 13.1193

2. Conclusion

   In this paper we have consider a crank rocker mechanism of four-bar linkage. The objective function namely path error varies with respect to the number of precision points specified. The two different cases were considered. It is found that in each case the computational time for convergence of 10,000 cycles changes. In some examples even the constraint violation is maintained, the minimum value of the objective function is found to be close to the published results available in the literature by other methods. In each case the convergence of multiple iteration graph, coupler curves & tables of optimum dimensions and final coupler point coordinate were reported.

3. Scope of Future work

Even this work has concentrated on path synthesis part with some important constraints, some more constraints like mechanical advantage of the linkage, and flexibility effects can be also considered to get the accuracy. Also as in hybrid synthesis approach, the same linkage may be adopted both for path synthesis applications as well as motion synthesis applications. The objective function should be modified so as to get a different optimum link dimensions. Finally fabrication of the proto-type of this linkage may be done to know the difference between theoretically obtained coupler coordinates and actual values achieved.

These approaches are very useful for the kinematician those who are working in the field of mechanism synthesis, robotics, assembly line, automation material handling and conveyors.

Mechanical Engineering, Indian Institute of Technology, Kanpur

1. Robert L.Norton, Design of machinery,

   McGraw hill

2. A.Kunjur and S.Krishnamurty, GA in mechanical synthesis, Applied mechanisms and robotics, Vol.4, pp.18-24, 1997.

3. D.A. Hobson and L.E. Torfason, optimization of four-bar knee mechanisms A computerized approach, Journal of Biomechanics, Volume 7, Pages 371-376,1974.

4. Z.W.Geem&J.H.kim, new heurisrc optimization algorithm H , imulation, vol.76, pp.60-68, 2001.

5. M.Mahdavi, M.Fesanghary&E.Damangir, An improved HS algorithm for solving optimization problem, Applied Mathematical computation, Vol.188, pp-1567-1579, 2007.

6. T.S.Todorov, Synthesis of four-bar mechanismsby Freudenstein-Chebyshev theory, Mechanism and Machine Theory, Volume 37,Pages 1505-1512,2002.

7. A.K. Khare and R. K. Dave, Optimizing 4-bar crank-rocker mechanism, Mechanism and Machine Theory, Volume 14, Pages 319-325,1979.

8. J.A .Carbrea. A. Simon &M.Prado, Optimal synthesis of mechanism with GA, Mechanism & Machine Theory, Vol.37, pp 1165-1177, 2002.

9. E.C.Kinzel, J.P.Schniedeler&G.R.Pennock, Kinetic synthesis for finitely separated positive any geometric coordinate programming, J. Machine design, Trans.ASME, Vol.12, pp.1070- 1079, 2006