# Efficient Planning and Solving Algorithm ofS-Shape Acceleration and Deceleration

Authors: Zhijie Li; Ligang Cai; Zhifeng Liu
Journal: Wireless Communications and Mobile Computing
 (2020)

---

## Abstract

S-shape acceleration and deceleration are the most widely used flexible acceleration and deceleration method in the current CNC system, but its velocity solution equation contains irrational terms, which create a more complicated solution process. When analyzing the solution process of the S-shape acceleration and deceleration directly, using a traditional numerical solution method, the phenomenon of “solving the interval jump” arises, which is the main reason for low efficiency and poor stability of the solution. According to the S-curve profile and solution, the concept of separating the curve profile recognition from the velocity solution was proposed, and a method of quickly identifying the interval of the solution location was introduced. Through the method mentioned above, the complete acceleration and deceleration curve parameters can be obtained through a one-time plan and a one-time solution, and the solution efficiency and stability are guaranteed; solving the Newton problem depends too much on the initial value of Newton velocity, which not only retains the speed advantage of the Newton method but also uses the downhill factor to ensure its convergence. Through the simulation comparison and analysis, the efficiency, stability, and universality of the method are verified.


---

## Body

## 1. Introduction

The ability of acceleration and deceleration is an important index in evaluating the performance of CNC systems, which directly affects the processing efficiency and quality of CNC equipment. High-speed and high-quality machining demands higher requirements for the acceleration and deceleration control abilities of CNC systems. The CNC equipment must be able to move from the current position point to the next position point quickly and accurately, while also ensuring the smooth operation of the equipment and avoiding impact, out of step, over the range, or oscillation.The commonly used acceleration and deceleration algorithms in medium and low-speed equipment include trapezoids [1, 2] and exponential acceleration and deceleration algorithms [3, 4]. The two algorithms are simple in programming, good in real-time performance, and high in processing efficiency, but they all have the problems of abrupt change and discontinuity of the acceleration curve, which makes them not suitable for high-speed and high-accuracy machining [5].In high-speed equipment, flexible acceleration and deceleration algorithms are often used, and their acceleration and acceleration function expressions are continuous, to reduce the impact on mechanical components [6]. S-shape acceleration and deceleration algorithm is the most widely used in flexible acc/dec algorithms at present. This method is based on the jerk constraint. The curves of displacement, velocity, and acceleration are composed of cubic, quadratic, and linear functions, respectively, and all of them are continuous without deviation [7, 8].The mathematical programming and solution of theS-shape acc/dec method have attracted considerable attention. The complete S-shaped acc/dec curve is composed of 7 segments, with many parameters. In most cases, the velocity solution equation is nonlinear, which makes its solution complex. Altintas [9] presented a detailed seven segment model of S-shape acc/dec, without elaborating its efficient solution. Barre [10] studied the influence of the acc/dec control in a high-speed machining process and analyzed the control algorithm of the seven-segment S-shape acc/dec. Shi [11] summarized eight possible cases of S-shape acc/dec in the planning, according to the characteristics of the curve segment. Nam [12] used the binary iteration to find the numerical solution, but the calculation amount was uncertain, and the solution efficiency was not ideal. Yang [13] adopted the Newton iteration, but the preconditions and convergence of Newton iteration were not clarified.Many scholars simplified theS-shaped acc/dec curve in order to reduce the complexity of the solution. Wang and others [14, 15] introduced a look-ahead control algorithm based on the S-shaped acc/dec curve with assuming that the velocity curve is symmetrical. In reference [16], the uniform acceleration and deceleration segments were removed, and the model was simplified to 5 segments. Although the above method reduced the complexity of the solution, it limited the dynamic performance of the machine tool. Xia [17] used the S-shape acc/dec based on the reference table to plan the velocity, which reduced the calculation time while limiting the flexibility of S-shape acc/dec.Presently, the planning of NURBS curve interpolation velocity based onS-shape acc/dec has become a hot research topic, and the solution mainly adopts the matching displacement by changing the velocity step by step [18, 19].The main idea of this method is to use the assumed key velocity value to calculate the corresponding displacement, match it with the actual displacement, and then determine the curve profile according to the matching situation. For small line segments, the calculation needs to be repeated more than three times, which reduces the efficiency of the solution.In order to reduce the complexity inS-shaped acc/dec curve planning and solutions, some scholars introduced the artificial intelligence algorithms such as genetic algorithms [20] and particle swarm optimization algorithms [21]. Although the above artificial intelligence algorithm has strong robustness, it needs to calculate the fitness of each iteration. Compared with the traditional dichotomy and Newton iteration, it has a large amount of calculation and low competitiveness in real-time.ForS-shaped acc/dec curves, the more ideal solution method should have smaller calculation complexity and higher solution accuracy. However, there is no general perfect solution at present.In this paper, the characteristics of theS-shaped acc/dec curve were analyzed. Focusing on the disadvantages of low efficiency and poor stability of traditional algorithms, a more concise, efficient, and stable general solution was proposed. In this method, the curve profile planning and velocity solution were completely separated. On the basis of proving the continuity of displacement’s segmented function about velocity, the interval boundary points were used to analyze the interval of velocity, so as to complete the profile planning quickly. After obtaining the interval of the velocity solution, the modified Newton method was introduced, which can make full use of the Newton method to accelerate up to the convergence speed, and at the same time, the downhill factor guarantees the convergence of the iteration.


## 2. Profile Characteristics ofS-Shape Acceleration and Deceleration

The name of theS-acceleration and deceleration curves are derived from the fact that the acceleration curve is approximately S-shaped. This type of S-acceleration and deceleration processes includes the S-acceleration process, deceleration process, and the uniform connection between acceleration and deceleration. Acceleration processes includes the accelerated acceleration segment, uniform acceleration segment, and decelerated acceleration; the deceleration process includes the accelerated deceleration segment, uniform deceleration segment, and decelerated deceleration segment. There are 7 sections in total, as shown in Figure 1. The corresponding mathematical expression is as follows:Figure 1
Profile ofS-shape acceleration and deceleration.In the follow formula,tii=1,2,⋯,7 is the running time of each segment. Command T1=t1, T2=t1+t2, and so on, T7=t1+t2+t3+t4+t5+t6+t7,.A is the maximum acceleration, J is the maximum jerk, Vs is the initial velocity, Ve is the final velocity, and Vmax is the maximum velocity. According to the characteristics of the S-acceleration and deceleration curve, t1=t3, t5=t7.
(1)Jt=J1=J0≤t<T1J2=0T1≤t<T2J3=−JT2≤t<T3J4=0T3≤t<T4J5=−JT4≤t<T5J6=0T5≤t<T6J7=JT6≤t<T7,at=a1=Jt0≤t<T1a2=AT1≤t<T2a3=A−Jt−T2T2≤t<T3a4=0T3≤t<T4a5=−Jt−T4T4≤t<T5a6=−AT5≤t<T6a7=−A+Jt−T6T6≤t<T7,vt=v1=Vs+12Jt2v2=V1+Jt1t−T1V1=Vs+12JT12v3=V2+Jt1t−T2−12Jt−T22V2=V1+Jt1t2v4=V3V3=V2+12Jt12v5=V4−12Jt−T42V4=V3v6=V5−Jt5t−T5V5=V4−12Jt52v7=V6−Jt5t−T6+12Jt−T62V6=V5−Jt5t6.Displacement of the acceleration section:(2)Sacc=S1+S2+S3=v+Vs2t1+t2/2.Displacement of the deceleration section:(3)Sdec=S5+S6+S7=v+Ve2t5+t6/2.Total displacement:(4)ST=Sacc+Sdec=v+vs2t1+t2/2+v+vs2t5+t6/2.If the actual displacement isS>ST, then there is a uniform velocity segment and running time:
(5)t4=S−STv.Whether there is a uniform acceleration section or a uniform deceleration section in the process of acceleration and deceleration is decided byVs, Ve, v, A, and J.
(6)v−Vs=t1+t2A,v−Ve=t5+t6A,(7)t1=t3=AJ,t2=v−VsA−AJv>Vs+A2J,(8)t1=t3=v−VsJ,t2=0v≤Vs+A2J,(9)t5=t7=AJ,t6=v−VeA−AJv>Ve+A2J,(10)t5=t7=v−VeJ,t6=0v≤Ve+A2J.Substituting the above time expression into the displacement formula:(1)
Whilev>Vs+A2/J&v>Ve+A2/J, then ST=1/Av2+A/Jv−Vs2+Ve2/2A+Vs+Ve/2JA(2)
Whilev>Vs+A2/J&v≤Ve+A2/J, then ST=v+Vs/2A/J+v−Vs/A+v+Vev−Ve/J(3)
Whilev≤Vs+A2/J&v>Ve+A2/J,then ST=v+Ve/2A/J+v−Ve/A+v+Vsv−Vs/J(4)
Whilev≤Vs+A2/J&v≤Vs+A2/J, then ST=v+Vsv−Vs/J+v+Vev−Ve/JThe expression (13) is a quadratic equation of one variable, and the exact solution can be obtained by using the root formula, while the expressions (14)-(16) contain the irrational part, so it is difficult to obtain the analytical solution.


## 3. Direct Numerical Solution

### 3.1. Dichotomy

Dichotomy is the most common method in solving nonlinear equations. Its main process in solvingS-shape acceleration and deceleration is shown in Figure 2.Step 1.
input the initial velocityVs, the final velocity Ve, maximum acceleration A, maximum jump A, required moving displacement S, and maximum limiting velocity Vmax.Step 2.
compare the value ofV=Vmax, Vs′=Vs+A2/J, and Ve′=Ve+A2/J.Step 3.
call formulas (7)-(10) to calculate the time of each segment ti and put them into formulas (13)-(16) to calculate the displacement ST.Step 4.
ifST≤S, call formula (5) and obtain the running time of each segment and the overall curve profile. The calculation is finished.Figure 2
Solving theS-shape acceleration flow chart with dichotomy.If in step4ST>S, the binary algorithm will be executed in step 5 to step 8:Step 5.
take the initial intervalVa,Vb, where Va=maxVs,Ve andVb=Vmax and set the velocity accuracy Vε.Step 6.
determination of termination conditions: ifVb−Va≤Vε, the calculation will be stopped.Step 7.
for iterative calculation, takeV′=Vb+Va/2, compare V′, Vs′=Vs+A2/J, and Ve′=Ve+A2/J, call formulas (7)-(10) to calculate the time of each segment, and substitute them into formulas (13)-(16) for calculation ST. If ST≤S, then set Va=V′; otherwise, set Vb=V′.Step 8.
turn to step6.


### 3.2. Newton Iteration

#### 3.2.1. Principle

For nonlinear equationfv=ST−S=0, V0 is assumed to be an approximate solution of V∗; fv is expanded in the Taylor form at V0, and the following formula is obtained:
(11)fv≈fV0+f′V0v−V0=0.V1=V0−fV0/f′V0f′V0≠0 is obtained as the first approximation of V∗; Vk is assumed as the current point, andfv can be expanded in the Taylor form at Vk:
(12)fv≈fVk+f′Vkv−Vk=0.Then,(13)Vk+1=Vk−fVk/f′Vkf′Vk≠0,k=0,1⋯


#### 3.2.2. Iteration Process

The first four steps are the same as the first four steps of dichotomy, so it will not be described here. Start with step5:Step 5.
V0 is taken as the initial value, N is the maximum number of iterations, and Vε is taken as the accuracy requirements.Step 6.
calculateVk+1=Vk−fVk/f′Vk.Step 7.
ifVk+1‐Vk<Vε, the calculation will be stopped.Step 8.
ifk=N, stop; otherwise, k=N+1 and turn to step 6.


## 3.1. Dichotomy

Dichotomy is the most common method in solving nonlinear equations. Its main process in solvingS-shape acceleration and deceleration is shown in Figure 2.Step 1.
input the initial velocityVs, the final velocity Ve, maximum acceleration A, maximum jump A, required moving displacement S, and maximum limiting velocity Vmax.Step 2.
compare the value ofV=Vmax, Vs′=Vs+A2/J, and Ve′=Ve+A2/J.Step 3.
call formulas (7)-(10) to calculate the time of each segment ti and put them into formulas (13)-(16) to calculate the displacement ST.Step 4.
ifST≤S, call formula (5) and obtain the running time of each segment and the overall curve profile. The calculation is finished.Figure 2
Solving theS-shape acceleration flow chart with dichotomy.If in step4ST>S, the binary algorithm will be executed in step 5 to step 8:Step 5.
take the initial intervalVa,Vb, where Va=maxVs,Ve andVb=Vmax and set the velocity accuracy Vε.Step 6.
determination of termination conditions: ifVb−Va≤Vε, the calculation will be stopped.Step 7.
for iterative calculation, takeV′=Vb+Va/2, compare V′, Vs′=Vs+A2/J, and Ve′=Ve+A2/J, call formulas (7)-(10) to calculate the time of each segment, and substitute them into formulas (13)-(16) for calculation ST. If ST≤S, then set Va=V′; otherwise, set Vb=V′.Step 8.
turn to step6.


## 3.2. Newton Iteration

### 3.2.1. Principle

For nonlinear equationfv=ST−S=0, V0 is assumed to be an approximate solution of V∗; fv is expanded in the Taylor form at V0, and the following formula is obtained:
(11)fv≈fV0+f′V0v−V0=0.V1=V0−fV0/f′V0f′V0≠0 is obtained as the first approximation of V∗; Vk is assumed as the current point, andfv can be expanded in the Taylor form at Vk:
(12)fv≈fVk+f′Vkv−Vk=0.Then,(13)Vk+1=Vk−fVk/f′Vkf′Vk≠0,k=0,1⋯


### 3.2.2. Iteration Process

The first four steps are the same as the first four steps of dichotomy, so it will not be described here. Start with step5:Step 5.
V0 is taken as the initial value, N is the maximum number of iterations, and Vε is taken as the accuracy requirements.Step 6.
calculateVk+1=Vk−fVk/f′Vk.Step 7.
ifVk+1‐Vk<Vε, the calculation will be stopped.Step 8.
ifk=N, stop; otherwise, k=N+1 and turn to step 6.


## 3.2.1. Principle

For nonlinear equationfv=ST−S=0, V0 is assumed to be an approximate solution of V∗; fv is expanded in the Taylor form at V0, and the following formula is obtained:
(11)fv≈fV0+f′V0v−V0=0.V1=V0−fV0/f′V0f′V0≠0 is obtained as the first approximation of V∗; Vk is assumed as the current point, andfv can be expanded in the Taylor form at Vk:
(12)fv≈fVk+f′Vkv−Vk=0.Then,(13)Vk+1=Vk−fVk/f′Vkf′Vk≠0,k=0,1⋯


## 3.2.2. Iteration Process

The first four steps are the same as the first four steps of dichotomy, so it will not be described here. Start with step5:Step 5.
V0 is taken as the initial value, N is the maximum number of iterations, and Vε is taken as the accuracy requirements.Step 6.
calculateVk+1=Vk−fVk/f′Vk.Step 7.
ifVk+1‐Vk<Vε, the calculation will be stopped.Step 8.
ifk=N, stop; otherwise, k=N+1 and turn to step 6.


## 4. Phenomenon of Solving Interval Jump

For the numerical solution, whether dichotomy or the Newton method, the solution interval is selected according to the initial value of the velocity in the first step, and then the displacement expression of this interval will be calculated. The solution obtained is not the final velocity solution, and the solution interval will be selected again according to the velocity value, and the iterative calculation will be carried out repeatedly until the termination condition is met. The process will cause the velocity value to jump at different intervals, and the displacement expression needs to be selected repeatedly, which will affect the solution efficiency, as shown in the following figure:Figure3 shows the case of Vs<Ve<Vs+A2/J<Ve+A2/J<Vmax. The blue dotted line represents the segment point of the interval. From formula (13) to formula (16), it can be seen that the expression of displacement velocity is different in different segments. Taking dichotomy as an example, assuming that the required solution V∗ is slightly less than Ve+A2/J, the solution obtained after the first iteration is V′=Va+Vb/2=Ve+Vmax/2A2/JA2/J. Red indicates the corresponding position of the iterative solution. At this time, formula ((3)–(14)) is applicable, and the next iteration is carried out V′′=Va+Vb/2=V′+Vmax/2A2/Jmax. At this time, formula (16) is applicable, and the third iteration is carried out V′′′=V′+V′′/2∈Vs+A2/J,Ve+A2/J. In this case, (14) applies again.Figure 3
Schematic diagram of interval jump in the solving process.This kind of iterative solution jumps between intervals, which causes different displacement expressions to be called back and forth, which leads to the instability of the solution process and affects the solution efficiency. In order to solve this kind of jump problem, the analytic programming method is introduced; that is, the interval of the expected solution is estimated first, and then the solution is calculated.


## 5. Solution by Matching with Velocity Step by Step

The main idea of this method is to use the assumed key velocity value to calculate the corresponding displacement, match it with the actual displacement, and then determine the curve profile according to the corresponding situation.Take acceleration segment as example:Step 1.
assuming that the velocity can reach the required maximum velocity, the maximum velocity is substituted into the displacement formula, and the calculated displacement is compared with the actual displacement. If the calculated displacement is smaller than the actual displacement, then there is a uniform velocity segment:Step 2.
if the calculated displacement is larger than the actual displacement, assume that there is just a uniform acceleration segment and substitute the assumed velocity value into the displacement formula and compare the calculated displacement with the actual displacement. If the calculated displacement is smaller than the actual displacement, it means that there is a uniform acceleration segment, then use the displacement formula including the uniform acceleration segment to solve the actual velocity value.Step 3.
if the calculated displacement is larger than the actual displacement, it means that there is no uniform acceleration section. At this time, the displacement formula without uniform acceleration section is used to solve for the actual velocity value.The specific flow of the algorithm is shown in Figure4.Figure 4
Flow chart of solution by matching with velocity step by step.The advantage of this method is that you can use the assumed velocity to plan first; then, you can solve for the actual velocity and avoid the jump in value ranges, increasing the stability of the solution, but there are also obvious disadvantages: the displacement is calculated and matched step by step with the assumed velocity. For the small line segment, the calculation needs to be repeated more than three times, which reduces the efficiency of the solution.


## 6. Interval Identification

To solve the problem of low efficiency of solution by matching with velocity, a new velocity planning method is proposed here.From formula (5) to formula (10), it can be seen that when the initial velocity, final velocity, and maximum acceleration are given, the value of V directly affects the size and existence of each segment time ti, and the actual s determines whether the actual velocity can reach the maximum allowable value.WhenVs<Ve, Ve≤Vs+A2/J, and Ve+A2/J<Vmax, because of maxVs,Ve≤V≤Vmax, interval 0 in Figure 5 is meaningless, and V may exist in the intervals 1-3.Figure 5
Case 1 with initial velocity less than the final velocity.The velocity value interval is divided into six sections and interval 0-5 by five key numerical points. The time expression (8) and formula (10) are suitable in interval 1, and the corresponding displacement expression is formula (16); the time expressions (7) and (10) are suitable in interval 2, and the corresponding displacement expression is formula (14); the time expressions (7) and (9) are suitable in interval 3, and the corresponding displacement expression is formula (15). Then, the piecewise function is obtained:
(14)STiv=ST1=v+Vsv−VsJ+v+Vev−VeJST2=v+Vs2AJ+v−VsA+v+Vev−VeJST3=1Av2+AJv−Vs2+Ve22A+Vs+Ve2Jv≤Vs+A2J≤Ve+A2J≤VmaxVs+A2J≤v≤Ve+A2J≤VmaxVs+A2J≤Ve+A2J≤v≤Vmax.According to the definition of the function continuity, lety=sv exist in a certain field of point v0; when v→v0, if the limit of the function sv exists and is equal to its function value at point v0,that is limv→v0sv=sv0, then function y=sv is continuous at point v0. If Vs′=Vs+A2/J and Ve′=Ve+A2/J, it can be proved that the function is continuous at the points Vs′and Ve′.It can be seen from Figure6 that the curve increases monotonously in the range of Vs,Vmax. Letfiv=STiv−S, (i=1,2,3), S is the actual displacement, and there is a unique solution to fiv=STiv−S=0 (i=1,2,3), and with the difference of the displacement s value, the interval of solution of the piecewise function equation will change.Figure 6
STvFunction curve.In the initial conditions, the initial velocity, the final velocity, the maximum acceleration, and the maximum jerk are given. The end values of three intervals are substituted intofiv=STiv−S, respectively. Fis and Fie are function values of the endpoints of the i-th interval.
(15)F1s=f1vv=Ve=ST1vv=Ve−sF1e=f1vv=Vs+AJ=ST1vv=Vs+AJ−sF2s=f2vv=Vs+AJ=ST2vv=Vs+AJ−sF2e=f2vv=Ve+AJ=ST2vv=Ve+AJ−sF3s=f3vv=Ve+AJ=ST3vv=Ve+AJ−sF3e=f3vv=VmaxT2v=Vmax∣.From the properties of the continuity function,F1e=F2s, F2e=F3s.In the next step, the function values offiv=STiv−S at the end points of each group of intervals are multiplied by each other to determine whether the product result is less than zero. There are two situations for the result:
(1)
IfFis∗Fie>0, the ST and S curves do not intersect in this interval, and there is no solution in this interval. If there is no solution in the three intervals, the velocity is taken as Vmax, which indicates that the system has a uniform segment, the time is t4, and the curve is composed of seven segments. The ti can be obtained by substituting the velocity value into the solutions of formulas (4) and (5)(2)
IfFis∗Fie≤0, it means that the ST curve and S line intersect in this interval, and the equation has a solution, which is the actual value of velocity V that the system can achieve. At this time, substituting V into equation (7)—(10) can calculate the running time of each segmentTable1 is the summary of the curve profile planning of case 1. The first three lines show the three cases of Fis∗Fie≤0 when i equals 1,2,3, respectively. The fourth line shows that i=1,2,3 cannot meet the situation of Fis∗Fie≤0.Table 1
The summary of the curve profile planning of case 1.
Serial numberFis∗Fie≤0, fis∗fie≤0 true or falseExpression for calculatetiComposition of curve profileF1s∗F1eF2s∗F2eF3s∗F3e1TFF10/124 segments:t1/t3/t5/t72FTF9/125 segments:t1/t2/t3/t5/t73FFT9/116 segments:t1/t2/t3/t5/t6/t74FFF9/11/77 segments:t1/t2/t3/t4/t5/t6/t7Formulas (14)-(16) can be solved by the dichotomy and Newton method listed above to get the velocity value. Then, the value is brought into the corresponding time calculation formula to get the running time of each segments.As shown in Table2,there are 12 possibilities in the comparison of five key values of the initial velocity Vs, the final velocity Vs, Vs+A2/J, Ve+A2/J, and Vmax.Table 2
Possibility of key point value comparison.
Case no.Description of value1Vs<Ve<Vs+A2J<Ve+A2J<Vmax2Vs<Ve<Vs+A2J<VA2Jmax3Vs<Ve<VA2JA2Jmax4Vs<Vs+A2J<Ve<Ve+A2J<Vmax5Vs<Vs+A2J<Ve<VA2Jmax6Vs=Ve<Vs+A2J<Vmax7Vs=Ve<VA2Jmax8Ve<Vs<Ve+A2J<Vs+A2J<Vmax9Ve<Vs<Ve+A2J<VA2Jmax10Ve<Vs<VA2JA2Jmax11Ve<Ve+A2J<Vs<Vs+A2J<Vmax12Ve<Ve+A2J<Vs<VA2JmaxNext, case2 and case 3 in Table 2 will be discussed, and the interval distribution is shown in Figure 7.Case 2.
Interval 1 and interval 2 make sense.Figure 7
Interval partition graph of cases 1-3.The time expression (8) and equation (10) in interval 1 are suitable, and the displacement expression is the same as equation (17).The time expression (7) and equation (10) in interval 2 are suitable, and the displacement expression is the same as equation (18).Case 3.
Only interval 1 makes sense. The time expression (8) and equation (10) in interval 1 are suitable, and the displacement expression is the same as equation (17).Case4 and case 5 express the situation when Ve>Vs+A2/J, as shown in Figure 8.Case 4.
interval 1s and 2 make sense.Figure 8
Interval partition graph of cases4 and 5.The time expression (7) formula (10) in interval 1 is applicable, and the displacement expression is the same as formula (14).Time expression (7) and equation (9) in interval 2 are applicable, and displacement expression is the same as equation (13).Case 5.
Interval 1 makes sense.The time expression (7) and formula (10) in interval 1 are suitable, and the displacement expression is the same as formula (15).
(1)
WhenVs=Ve, there are only two cases, case 6 and 7, as shown in Figure 9Case 6.
Interval 1 and 2 make sense.Figure 9
Interval partition graph of case6 and 7.The time expression (8) and equation (10) in interval 1 are suitable, and the displacement expression is the same as equation (17).The time expression (7) and equation (9) in interval 2 are suitable, and the displacement expression is the same as equation (24).
(2)
WhenVs>Ve, the possible value range of velocity is from case 8 to case 12. The actual solution process is the same as that of Vs<Ve, and only 1 and 2 need to be interchanged. In consideration of space, it will not be expanded here(3)
There are four other possibilities, which are not listed in the bid, as shown in Table3Case 7.
Only interval 1 makes sense. The time expression (8) and equation (10) in interval 1 are suitable, and the displacement expression is the same as equation (17).Table 3
Only acceleration section or deceleration section.
Case no.Description of value13Vs<Vs+A2J<Vmax14Vs<VA2Jmax15Vs<Ve+A2J<Vmax16Ve<VA2JmaxThe so-calledS-shape means that the shape of acceleration is similar to the S-shape, case 13—case listed in Table 3. There is only acceleration section or deceleration section, and acceleration is similar to half circle. According to the definition of the S-shaped acceleration and deceleration curve, these four cases do not meet the definition, but these four cases do exist in small displacement, especially in the speed sensitive area, so they are listed here. The calculation method is the same as above and will not be described here.


## 7. Comparison of Solution Methods

### 7.1. Match with Velocity VS Interval Identification

The first step when using the velocity method is to assume that the curve has seven complete segments, and that the time and velocity values are substituted into the formula to calculate the displacement. If the calculated displacement is less than the actual displacement, the one with the larger value inVs+A2/J and Ve+A2/J will be substituted into the equation again to calculate the displacement, and the calculated displacement and the actual displacement will be compared again. If the calculated displacement is greater than or equal to the actual displacement, then the actual velocity and running time can be obtained by solving the equation.If the calculated displacement is smaller than the actual displacement, it is necessary to replace the smaller value ofVs+A2/J and Ve+A2/J into the displacement equation again, calculate and compare the displacement for the third time, and then plan out the profile of the curve. Finally, the actual velocity can be obtained by solving the equation.The specific steps of the interval identification method are as follows: ① input the initial value, compare 5 key speed values, and find the corresponding case No.; ② in the corresponding case No., substitute the value to judgeFis∗Fie≤0; ③ solve the equation in the interval of Fis∗Fie≤0 and get the velocity; and ④ replace the speed V with the time calculation formula and get the whole curve profile.Figure10 shows the comparison of the processes of the two methods. In summation, if the curve has 7 or 6 segments, the calculation steps and calculation amounts of the two methods are basically the same. If the curve has 4 or 5 segments, the calculation steps and calculation amounts of the interval identification method are less and therefore, the efficiency is higher.Figure 10
Comparison of matching with velocity and interval identification.
(a)
Matching with velocity(b)
Interval identification


### 7.2. Direct Numerical Solution vs Interval Identification

In order to verify the efficiency of the solution, various methods and algorithms are programmed with matlab2018a, and the displacement is taken as a variable between 0.0001 m and 0.018 m, and the interval between the value points is 0 and 1 mm. Computer configuration: processor Intel (R) core (TM) i5-4200u memory 8 g. The solution time of each algorithm under different displacement conditions is calculated, and the solution efficiency of each method is compared. The number of Newton iteration and dichotomy iteration termination is 10000. The specific parameter settings are shown in Table4, and the solution efficiency is shown in Figure 11.Table 4
Parameters used in the simulation.
SymbolItemValueVsInitial velocity20 mm/sVeFinal velocity30 mm/sVmaxMaximum velocity100 mm/sAmaxMaximum acceleration600 mm/s2JmaxMaximum jerk3×104mm/s3VεIteration termination precision1×10−6mm/sTsInterpolation period1 msSDisplacement0.01-18 mmVoInitial velocity of iteration15 mm/sFigure 11
Solution efficiency comparison.It can be seen from Figure11 that the abscissa of either direct Newton iteration or interval identification+Newton iteration does not start from zero; that is, the red dotted area in the figure which indicates that Newton iteration does not return the velocity solution and directly jumps out of the iteration cycle after reaching the limit of iteration rounds. As mentioned in the previous paper, the convergence of the Newton iteration needs to be further verified. When the displacement value is about 1-3 mm, the number of Newton iterations is also significantly higher than the number after it is stable. When the displacement is more than 4 mm, all algorithms tend to be more stable as displacement increases.In order to see the solution efficiency of the four methods more clearly and intuitively, the abscissa in Figure11 is intercepted through 7-12 mm part, resulting in Figure 12.Figure 12
Local amplification of efficiency comparison graph after stabilization.Regarding solving efficiency, the efficiency of the interval identification method is obviously better than that of the direct iterative method when the solving process of various algorithms is stable. The efficiency of interval identification plus Newton iteration is the highest, and then the efficiency of direct Newton iteration is about one third of that of interval identification plus Newton iteration. The efficiency of dichotomy is obviously lower than that of Newton iteration. The efficiency of direct dichotomy is about one seventh of interval identification plus the Newton iteration. From the point of view of solving stability, the interval identification method is also better than the direct iteration method. As mentioned earlier in the paper, the interval identification avoids the phenomenon of iteration jumping back and forth in different value intervals, thus improving the stability.To sum up, the interval identification+Newton iteration method is the best both in solving efficiency and solving stability.Figure11 is the abscissa which is truncated at 0-5 mm and enlarged locally to get Figure 13. It can be seen that the efficiency of all solutions fluctuates within a certain boundary, and the Newton iteration is the obvious. In the figure, the red dot dash appears near two key points, which are ST1 and ST2 in formula (17), corresponding to the interval boundary points in the interval identification method. This shows that the expression change caused by the change of displacement length has an obvious effect on the iteration efficiency. The smaller the displacement, the more time-consuming the solution.Figure 13
Comparison of solution efficiency when small displacement.


## 7.1. Match with Velocity VS Interval Identification

The first step when using the velocity method is to assume that the curve has seven complete segments, and that the time and velocity values are substituted into the formula to calculate the displacement. If the calculated displacement is less than the actual displacement, the one with the larger value inVs+A2/J and Ve+A2/J will be substituted into the equation again to calculate the displacement, and the calculated displacement and the actual displacement will be compared again. If the calculated displacement is greater than or equal to the actual displacement, then the actual velocity and running time can be obtained by solving the equation.If the calculated displacement is smaller than the actual displacement, it is necessary to replace the smaller value ofVs+A2/J and Ve+A2/J into the displacement equation again, calculate and compare the displacement for the third time, and then plan out the profile of the curve. Finally, the actual velocity can be obtained by solving the equation.The specific steps of the interval identification method are as follows: ① input the initial value, compare 5 key speed values, and find the corresponding case No.; ② in the corresponding case No., substitute the value to judgeFis∗Fie≤0; ③ solve the equation in the interval of Fis∗Fie≤0 and get the velocity; and ④ replace the speed V with the time calculation formula and get the whole curve profile.Figure10 shows the comparison of the processes of the two methods. In summation, if the curve has 7 or 6 segments, the calculation steps and calculation amounts of the two methods are basically the same. If the curve has 4 or 5 segments, the calculation steps and calculation amounts of the interval identification method are less and therefore, the efficiency is higher.Figure 10
Comparison of matching with velocity and interval identification.
(a)
Matching with velocity(b)
Interval identification


## 7.2. Direct Numerical Solution vs Interval Identification

In order to verify the efficiency of the solution, various methods and algorithms are programmed with matlab2018a, and the displacement is taken as a variable between 0.0001 m and 0.018 m, and the interval between the value points is 0 and 1 mm. Computer configuration: processor Intel (R) core (TM) i5-4200u memory 8 g. The solution time of each algorithm under different displacement conditions is calculated, and the solution efficiency of each method is compared. The number of Newton iteration and dichotomy iteration termination is 10000. The specific parameter settings are shown in Table4, and the solution efficiency is shown in Figure 11.Table 4
Parameters used in the simulation.
SymbolItemValueVsInitial velocity20 mm/sVeFinal velocity30 mm/sVmaxMaximum velocity100 mm/sAmaxMaximum acceleration600 mm/s2JmaxMaximum jerk3×104mm/s3VεIteration termination precision1×10−6mm/sTsInterpolation period1 msSDisplacement0.01-18 mmVoInitial velocity of iteration15 mm/sFigure 11
Solution efficiency comparison.It can be seen from Figure11 that the abscissa of either direct Newton iteration or interval identification+Newton iteration does not start from zero; that is, the red dotted area in the figure which indicates that Newton iteration does not return the velocity solution and directly jumps out of the iteration cycle after reaching the limit of iteration rounds. As mentioned in the previous paper, the convergence of the Newton iteration needs to be further verified. When the displacement value is about 1-3 mm, the number of Newton iterations is also significantly higher than the number after it is stable. When the displacement is more than 4 mm, all algorithms tend to be more stable as displacement increases.In order to see the solution efficiency of the four methods more clearly and intuitively, the abscissa in Figure11 is intercepted through 7-12 mm part, resulting in Figure 12.Figure 12
Local amplification of efficiency comparison graph after stabilization.Regarding solving efficiency, the efficiency of the interval identification method is obviously better than that of the direct iterative method when the solving process of various algorithms is stable. The efficiency of interval identification plus Newton iteration is the highest, and then the efficiency of direct Newton iteration is about one third of that of interval identification plus Newton iteration. The efficiency of dichotomy is obviously lower than that of Newton iteration. The efficiency of direct dichotomy is about one seventh of interval identification plus the Newton iteration. From the point of view of solving stability, the interval identification method is also better than the direct iteration method. As mentioned earlier in the paper, the interval identification avoids the phenomenon of iteration jumping back and forth in different value intervals, thus improving the stability.To sum up, the interval identification+Newton iteration method is the best both in solving efficiency and solving stability.Figure11 is the abscissa which is truncated at 0-5 mm and enlarged locally to get Figure 13. It can be seen that the efficiency of all solutions fluctuates within a certain boundary, and the Newton iteration is the obvious. In the figure, the red dot dash appears near two key points, which are ST1 and ST2 in formula (17), corresponding to the interval boundary points in the interval identification method. This shows that the expression change caused by the change of displacement length has an obvious effect on the iteration efficiency. The smaller the displacement, the more time-consuming the solution.Figure 13
Comparison of solution efficiency when small displacement.


## 8. Interval Identification plus Modified Newton Iteration

In order to prevent the divergence of Newton iteration, a requirement is attached to the iteration process to keep its monotonicity.(16)fVk+1<fVk.In order to meet this requirement, Newton iteration is modified.(17)V̄k+1=Vk−fVkf′VkVk+1=λV̄k+1+1−λVk,Whereλ0<λ≤1 is the downhill factor, and formula (18) is obtained after the transformation of the above formula:
(18)Vk+1=Vk−λfVkf′Vkk=0,1,⋯In the iteration, it starts fromλ=1 and reduces by half until it meets the requirements (16).After the modified Newton iteration is introduced, the iteration parameters and initial conditions are set according to Table4. Under the same conditions, the efficiency curve Figure 14 is obtained.Figure 14
Comparison between Newton iteration and Newton downhill method.Only Newton iteration can be seen in Figure14, because the iteration diverges until the number of iterations jumps out of the cycle. The record time of 0.01 seconds in the figure is the time taken to jump out of the cycle. Figure 13 is partially enlarged to obtain Figure 15.Figure 15
Local enlarged map of comparison between Newton and Newton downhill.It can be seen from Figure15 that, when the displacement is large, the solution efficiency of interval identification plus modified Newton method is very close to that of interval identification plus Newton iteration, which retains the characteristics of fast convergence of Newton iteration; when the displacement is small, the downhill factor ensures the convergence of iteration.


## 9. Conclusion

(1)
When analyzing the process of solvingS-shape acceleration and deceleration directly by the traditional numerical solution method, the phenomenon of “solving interval jump” was concerned, which is a main reason for the low efficiency and poor stability of the solution(2)
According to theS-curve profile and solution, the concept of separating the curve profile recognition from the velocity solution was introduced, and a plan of quickly identifying the interval of the solution location was put forth. With this method, the complete acceleration and deceleration curve parameters can be obtained through one-time planning and one-time solutions, and the solution efficiency and stability are certain(3)
The modified Newton method was introduced to solve the problem that the Newton iteration depends too much on the initial value of velocity, which not only retains the speed advantage of the Newton method but also uses the downhill factor to ensure its convergence(4)
Finally, through the simulation comparison and analysis, the efficiency and stability of the interval identification and modified Newton method were verified



---

*Source: 8884678-2020-11-26.xml*