A real-time predictor-modification-evaluation–corrector-modification-evaluation parametric interpolator for numerical control transition curves

Abstract

A real-time parametric interpolator based on a predictor-modification-evaluation–corrector-modification-evaluation algorithm is proposed in this article, which is utilized to efficiently calculate the reference points of transition curves. Meanwhile, the stable calculation is guaranteed by analyzing the convergence condition of the predictor-modification-evaluation–corrector-modification-evaluation algorithm. Under the convergence condition, the proposed parametric interpolator and traditional line interpolators are simultaneously implemented to interpolate a two-dimensional butterfly path, which consists of quintic Bézier transition curves and line segments. Simulation and experiments are carried out, and the results demonstrate that the proposed real-time predictor-modification-evaluation–corrector-modification-evaluation parametric interpolator achieves the highest accuracy and the light stripe on the tool path is further reduced and hardly observed. Compared with other parametric interpolators, the proposed real-time predictor-modification-evaluation–corrector-modification-evaluation parametric interpolator is capable of achieving a good balance between interpolation accuracy and interpolation efficiency.

Keywords

Predictor-modification-evaluation–corrector-modification-evaluation parametric interpolator convergence analysis transition curve real-time interpolation system interpolation implementation

Introduction

In numerical control (NC) machining, line segments are widely applied to describe the complex machining graphics in light of their flexibility.¹ However, due to the discontinuities of tangency and curvature at segment junctions, the feedrate of cutting tool has to be slowed down frequently to avoid the feedrate fluctuation. To overcome the frequent acceleration and deceleration, a transition method by using a curve to transit line segments is commonly utilized.² With this method, a smooth tool path with curvature continuity is achieved. Then, an acceleration/deceleration (ACC/DEC) scheduling³ and a look ahead scheme⁴ are implemented simultaneously to generate the corresponding feedrate profile in real time. Based on the tool path and feedrate profile, a series of reference points are generated by the interpolator,⁵ and the reference points guide the NC machining along with the path. Since the path is composed of line segments and curves, both line interpolator and parametric interpolator are involved. Generally, line interpolator is utilized to calculate the reference points on the line segment by using the analytic algorithm, so it does not cause the interpolation error. Parametric interpolator, which uses the numerical algorithm to approximate curve parameters, causes the interpolation error inevitably because there is no analytical relationship between curve length and curve parameter. Thus, the performance of the abovementioned interpolators, especially the parametric interpolator, directly affects the machining quality and efficiency.

The parametric interpolator can be divided into two categories,⁶ that is, feedback method and straightforward method. By taking the feedrate command error reduction as the calculation criterion, the feedback method employs the iteration algorithm⁷ to determine curve parameters, while large computation is required due to undetermined iteration number. Although some methods^8,9 have been improved to reduce the number of iterations, the execution time still fluctuates greatly, which affects the machining efficiency. To deal with the problem, a fast interpolation method was proposed to achieve a high efficiency and a minimum feedrate fluctuation by accurately deducing the relation between the curve parameter and arc length.¹⁰ However, the method was only available for cubic B-spline. The straightforward method, as indicated by its name, directly calculates the curve parameters. The typical straightforward method is Taylor’s expansion (TE) method,¹¹ which has the advantages of simplicity, stable execution time, and fast convergence. The first-order Taylor’s expansion (FOTE) can realize an o(T²) truncation error with a feedrate fluctuation ratio of 5.81%.¹² When the second-order Taylor’s expansion (SOTE)¹³ is implemented, an o(T³) truncation error can be achieved, and the feedrate fluctuation ratio can be decreased to 0.4%.¹⁴ However, when the curve curvature is large, the feedrate fluctuation increases because only the o(T³) truncation error is achieved.¹⁵ To deal with this issue, a parameter-compensated algorithm was proposed,¹⁶ which adopts a compensatory polynomial to correct the generated curve parameters. In this way, the fluctuation ratio is decreased to 0.01%. Nevertheless, the polynomial coefficients are determined by the matrix calculation, which blocks the real-time interpolation. Recently, an augmented TE method based on Heun’s algorithm was put forward to obtain a better approximation value of the curve parameter.¹⁷ Since the convergence analysis was not analyzed, each generated parameter has to be calibrated via off-line computed knot-length pairs.

In order to decrease the feedrate fluctuation, the third-order Taylor’s expansion (TOTE) algorithm is deduced to achieve an o(T⁴) truncation error. The expression of the TOTE algorithm is not complicated, and the computational burden is acceptable for real-time interpolation. Meanwhile, both the effects of acceleration and jerk can be considered in the TOTE algorithm. To further achieve an o(T⁵) truncation error for real-time interpolation, the fourth-order Runge–Kutta (FORK) algorithm,¹⁸ rather than the fourth-order TE algorithm, is much more appropriate for simple construction, since the FORK algorithm only needs to calculate the first derivative of the curve four times in each interpolation cycle. To reduce the computation, Jahanpour and Alizadeh¹⁹ proposed an interpolator based on the Adams–Bashforth (AB) algorithm, which needs to calculate the first derivative of the curve only once in each interpolation cycle. Actually, by combining the AB algorithm with the Adams–Moulton algorithm (ABM), the accuracy can be further improved.²⁰ Based on this idea, a real-time predictor-modification-evaluation–corrector-modification-evaluation (PMECME) parametric interpolator is proposed in this article, which can achieve an o(T⁵) truncation error with certain convergence condition. Meanwhile, a quintic Bézier transition curve is introduced according to the condition, which can easily realize the stable interpolation with small calculation.

From the abovementioned analysis, it is concluded that parametric interpolator for transition curves is a key part of NC machining, but its performance is decreased due to the complexity of feedback method or the instability of straightforward method. Therefore, how to improve the stability of straightforward method is discussed here. The remainder of this article is organized as follows. In section “Principles of a quintic Bézier transition curve and a parametric interpolator,” a quintic Bézier transition curve is adopted to smooth line segments. Meanwhile, the principle of parametric interpolator is introduced briefly. In section “Parametric interpolator based on TE,” the commonly used parametric interpolator based on TE is described, and its disadvantages are discussed. In section “PMECME parametric interpolator and convergence analysis,” a parametric interpolator based on the PMECME algorithm is proposed, and the convergence condition is analyzed. The interpolation performances of different algorithms are compared in section “Simulation.” In section “Real-time interpolation experiments,” a real-time interpolation system is constructed. Meanwhile, an interpolation example is implemented to verify the effectiveness of the PMECME algorithm. The conclusions are given in section “Conclusion.”

Principles of a quintic Bézier transition curve and a parametric interpolator

Figure 1 shows a quintic Bézier transition method between two line segments. $\vec{Q_{0} Q_{1}}$ and $\vec{Q_{1} Q_{2}}$ denote two line segments. $\vec{T_{0}}$ and $\vec{T_{2}}$ represent tangent vectors of $\vec{Q_{0} Q_{1}}$ and $\vec{Q_{1} Q_{2}}$ , and $Q_{1}$ is the junction between them. Due to the discontinuity of tangency and curvature at the junction, the feedrate changes abruptly when the tool moves across the junction.

Figure 1.

A quintic Bézier curve $C (u)$ between line segments.

To solve this issue, a quintic Bézier curve $C (u)$ is adopted as a transition curve to smooth line segments (the red dotted line in Figure 1). The detailed deduction of $C (u)$ can be seen in the study by Wang et al.,²¹ and the expression of $C (u)$ is given as

C (u) = \sum_{i = 0}^{5} B_{i, 5} (u) P_{i}

(1)

where $u$ is the curve parameter with range of $u \in [0, 1]$ , and ${B_{i, 5}}$ is a set of Bernstein polynomials. ${P_{i}}$ denotes a set of control points, which can be obtained from

{\begin{matrix} R = \frac{2 ε}{\sqrt{2 - 2 {\vec{T}}_{0} \cdot {\vec{T}}_{2}}} (\frac{128 + 56 | {\vec{T}}_{0} + {\vec{T}}_{2} |}{128 - 19 | {\vec{T}}_{0} + {\vec{T}}_{2} |}) \\ α = \frac{30 R | {\vec{T}}_{0} + {\vec{T}}_{2} |}{7 | {\vec{T}}_{0} + {\vec{T}}_{2} | + 16} \\ P_{0} = C (0), P_{5} = C (1) \\ P_{1} = P_{0} + \frac{α {\vec{T}}_{0}}{5}, P_{2} = P_{0} + \frac{2 α {\vec{T}}_{0}}{5} \\ P_{3} = P_{5} - \frac{2 α {\vec{T}}_{2}}{5}, P_{4} = P_{5} - \frac{α {\vec{T}}_{2}}{5} \end{matrix}

(2)

where α is a constant value. When ε or R is given, a transition curve $C (u)$ can be determined by equation (2). As shown in Figure 1, the whole tool path is smoothed by using the curve, so the feedrate fluctuations are effectively avoided. In the real applications, the curve $C (u)$ needs to be discretized to guide the tool movement. Therefore, the parametric interpolator is utilized to discretize the curve $C (u)$ , and then the reference points are generated for a servo loop in each interpolation period. For instance, at the interpolation time $t_{k}$ , the tool locates at the reference point $C (u_{k})$ . When the next interpolation cycle $t_{k + 1}$ $(t_{k + 1} = t_{k} + T)$ arrives, the parametric interpolator will calculate the next reference point $C (u_{k + 1})$ , and guide the tool movement from $C (u_{k})$ to $C (u_{k + 1})$ . In this way, the interpolation procedure is implemented again until all the reference points are generated.

Generally, the parametric interpolator utilizes the numerical method to calculate the reference points, which affects interpolation accuracy and efficiency inevitably.¹¹ To deal with the problem, the parametric interpolator is then discussed in detail.

Parametric interpolator based on TE

In general, TEs are widely used to establish the parametric interpolators, for example, FOTE¹² and SOTE.¹³ Nevertheless, higher order TE is not commonly utilized as a parametric interpolator. The reason is as follows.

The equation of TE can be expressed as

u_{k + 1} = u_{k} + T u'_{k} + \frac{T^{2}}{2!} {u ″}_{k} + \cdot \cdot \cdot + \frac{T^{n}}{n!} u_{k}^{(n)} + HOT

(3)

where $u'_{k}$ , ${u ″}_{k}$ , and $u_{k}^{(n)}$ represent the first, second, and nth derivatives of $u_{k}$ , respectively. HOT indicates the higher order terms. When the value of n equals to 1, the FOTE algorithm with an $o (T^{2})$ truncation error is written as

u_{k + 1} = u_{k} + \frac{v_{k} T}{{‖ C' (u) ‖}_{u = u_{k}}}

(4)

where ‖·‖ represents Euclidean norm in the three-dimensional space. Substituting equation (4) into equation (1), the reference point $C (u_{k + 1})$ can be generated. Similarly, if the value of n is 2, the truncation error will be decreased to $o (T^{3})$ , and the SOTE algorithm is described as

\begin{matrix} u_{k + 1} = u_{k} + \frac{v_{k} T}{{‖ C' (u) ‖}_{u = u_{k}}} + \frac{a_{k} T^{2}}{2 {‖ C' (u) ‖}_{u = u_{k}}} \\ - \frac{v_{k}^{2} T^{2}}{2} \frac{{(C' (u) \cdot C ″ (u)) |}_{u = u_{k}}}{‖ C' (u) ‖_{u = u_{k}}^{4}} \end{matrix}

(5)

where $C' (u) \cdot C ″ (u)$ represents the dot product between $C' (u)$ and $C ″ (u)$ . Although the SOTE algorithm can achieve an $o (T^{3})$ truncation error, the interpolation accuracy may not satisfy high precision machining requirements especially when interpolating the large curvature curve. Under this circumstance, the value of n is going to be higher. Therefore, the TOTE algorithm with an $o (T^{4})$ truncation error is deduced as

\begin{matrix} u_{k + 1} = u_{k} + \frac{Δ s}{{‖ C' (u) ‖}_{u = u_{k}}} - \frac{{Δ s^{2} (C' (u) \cdot C ″ (u)) |}_{u = u_{k}}}{2 ‖ C' (u) ‖_{u = u_{k}}^{4}} \\ - \frac{{Δ s^{2} ({C ″}^{2} (u) + C' (u) \cdot C ″' (u)) |}_{u = u_{k}}}{6 ‖ C' (u) ‖_{u = u_{k}}^{5}} \\ + \frac{{2 Δ s^{3} {(C' (u) \cdot C ″ (u))}^{2} |}_{u = u_{k}}}{3 ‖ C' (u) ‖_{u = u_{k}}^{7}} + \frac{a_{k} T^{2}}{2 {‖ C' (u) ‖}_{u = u_{k}}} \\ + \frac{T^{3}}{6} (\frac{J_{k}}{{‖ C' (u) ‖}_{u = u_{k}}} - \frac{3 a_{k} v_{k} {(C' (u) \cdot C ″ (u)) |}_{u = u_{k}}}{‖ C' (u) ‖_{u = u_{k}}^{4}}) \end{matrix}

(6)

where $Δ s$ denotes the incremental arc length, which is equal to $v_{k}$ . Although a truncation error can be greatly reduced by further extending the value of n , the equation is much more complicated than equation (6), and its computation is rapidly increased. Therefore, it is not suitable for real-time interpolation. To tackle with this issue, a parametric interpolator based on the PMECME algorithm is put forward in the next section.

PMECME parametric interpolator and convergence analysis

PMECME algorithm

In this subsection, a new parametric interpolator based on the PMECME algorithm is proposed, which can achieve an $o (T^{5})$ truncation error without consuming much computational resources.

According to equation (4), a standard differential equation can be established as

{\begin{matrix} u' = \frac{du}{dt} = \frac{v (t)}{‖ C' (u) ‖} = f (t, u) \\ u (t_{0}) = u_{0} \end{matrix}

(7)

where $u (t_{0}) = u_{0}$ is the initial condition. If $1 / ‖ C' (u) ‖$ is differentiable everywhere and the absolute value of its derivation is bounded, $f (t, u)$ satisfies the Lipschitz condition.²² Then, the analytical solution $u (t)$ is existent and unique. Generally, $u (t)$ is too complicated to solve exactly by using the analytic method. Thus, a numerical method named as the PMECME algorithm²³ is introduced as follows, which utilizes the numerical solution $u_{k}$ to approximate $u (t)$

{\begin{matrix} Predictor : u_{k + 4}^{p} = u_{k + 3} + \frac{T}{24} \\ (- 9 f_{k} + 37 f_{k + 1} - 59 f_{k + 2} + 55 f_{k + 3}) \\ Modification : u_{k + 4}^{pm} = u_{k + 4}^{p} + \frac{251}{270} (u_{k + 3}^{c} - u_{k + 3}^{p}) \\ Corrector : u_{k + 4}^{c} = u_{k + 3} + \frac{T}{24} \\ (f_{k + 1} - 5 f_{k + 2} + 19 f_{k + 3} + 9 f (t_{k + 4}, u_{k + 4}^{pm})) \\ Modification : u_{k + 4} = u_{k + 4}^{c} - \frac{19}{270} (u_{k + 4}^{c} - u_{k + 4}^{p}) \end{matrix}

(8)

where the terms of “Predictor” and “Corrector” represent the AB four-step explicit algorithm and the Adams–Moulton (AM) three-step implicit algorithm, respectively. $u_{k + 4}^{pm}$ is a modified value with the “Predictor” term, and u_k+4 is a modified value with the “Corrector” term. f_k, f_k+1, f_k+2, and f_k+3 are abbreviations of f(t_k, uk_k), f(t_k+1, uk_k+1), f(t_k+2, uk_k+2), and f(t_k+3, uk_k+3), respectively. Since the initial values f₁, f₂, and f₃ do not exist at the first interpolation cycle, the FORK algorithm¹⁸ is adopted to determine these values by calculating their parameters u₁, u₂, and u₃. Meanwhile, $u_{3}^{c}$ does not exist at the first cycle, so $u_{4}^{p}$ is equal to $u_{4}^{pm}$ . In this way, the numerical solution u_k₊₄ at the time t_k₊₄ is obtained. Similarly, the numerical solutions at other interpolation cycles can also be generated by the PMECME algorithm.

PMECME algorithm can achieve o(T⁵) truncation error, and the proof is given as follows. As shown in equation (8), the PMECME algorithm is mainly composed of four terms, which are “Predictor,”“Modification,”“Corrector,” and “Modification,” respectively. In these terms, the truncation errors of “Predictor” term and “Corrector” term are given, respectively, as²⁴

{\begin{matrix} u (t_{k + 4}) - u_{k + 4}^{p} \approx \frac{251}{720} T^{5} u^{(5)} (t_{k}) = o (T^{5}) \\ u (t_{k + 4}) - u_{k + 4} \approx - \frac{19}{720} T^{5} u^{(5)} (t_{k}) = o (T^{5}) \end{matrix}

(9)

where u(t_k₊₄) is the analytical solution at the time t_k₊₄. According to equation (9), the difference between the errors of “Predictor” term and “Corrector” term is derived as

u_{k + 4}^{p} - u_{k + 4} \approx - \frac{270}{720} T_{i}^{5} u^{(5)} (t_{k}) = o (T^{5})

(10)

Then, substituting equation (10) into equation (9), the “modification” terms are obtained as

\begin{matrix} {\begin{matrix} u_{k + 4}^{pm} - u_{k + 4}^{p} \approx - \frac{251}{270} (u_{k + 4}^{p} - u_{k + 4}) = o (T^{5}) \\ {\bar{u}}_{k + 4} - u_{k + 4} \approx \frac{19}{270} (u_{k + 4}^{p} - u_{k + 4}) = o (T^{5}) \end{matrix} \\ \Rightarrow {\begin{matrix} u_{k + 4}^{pm} = u_{k + 4}^{p} + \frac{251}{270} (u_{k + 4} - u_{k + 4}^{p}) \\ {\bar{u}}_{k + 4} = u_{k + 4} - \frac{19}{270} (u_{k + 4} - u_{k + 4}^{p}) \end{matrix} \end{matrix}

(11)

From equation (11), it can be observed that the truncation errors of “modification” are also o(T⁵). Therefore, the PMECME algorithm can achieve o(T⁵) truncation error.

Convergence analysis

Based on the abovementioned description, the PMECME algorithm can be used as the interpolator to compute the curve parameter in each interpolation cycle. However, the round-off error cumulates gradually in each cycle and may exceed the numerical solution eventually. Therefore, it is necessary to analyze the convergence of the PMECME algorithm. As shown in equation (8), the algorithm convergence is related to the interpolation period T. In the numerical methods, the range of T is determined by solving the first-order linear test equation²² as follows

{\begin{matrix} y' = λ y \\ y (t_{0}) = y_{0} \end{matrix}

(12)

where λ is an imaginary number, and the analytical solution of equation (12) is $y (t) = y_{0} e^{λ (t - t_{0})}$ . Therefore, if $Re (λ) < 0$ , $y (t) \to 0$ when $t \to \infty$ . That is to say, the numerical solution of equation (12) is stable when the real part of λ is less than zero. Based on this condition, when the AB algorithm or the AM algorithm is utilized to solve equation (12), the following equation is obtained

\sum_{i = 0}^{n} α_{i} y_{k + i} = \bar{h} \sum_{i = 0}^{n} β_{i} y_{k + i}

(13)

where $\bar{h}$ is equal to T·λ. α and β are the constant coefficients. According to equation (13), the characteristic polynomials $π (ζ, \bar{h})$ of AB and AM algorithms can be constructed as

π (ζ, \bar{h}) = ζ^{4} - ζ^{3} - \frac{\bar{h}}{24} (- 9 + 37 ζ - 59 ζ^{2} + 55 ζ^{33})

(14)

π (ζ, \bar{h}) = ζ^{3} - ζ^{2} - \frac{\bar{h}}{24} (1 - 5 ζ + 19 ζ^{2} + 9 ζ^{3})

(15)

where ζ is the root of $π (ζ, \bar{h}) = 0$ . If a numerical method is stable, its stability region should be located in the half plane based on the Dahlquist theory.²⁵ That is to say, all the roots ζ_i should be laid inside the unit circle $| ζ | < 1$ . Accordingly, the interval of absolute stability (IAS) of AB and AM algorithms can be determined by solving equations (14) and (15). After calculation, the IASs of these two algorithms are obtained and shown in Table 1.

Table 1.

The IASs of these algorithms.

Algorithm	IAS
AB algorithm	–0.3 < $\bar{h}$ < 0
AM algorithm	–3 < $\bar{h}$ < 0
FORK algorithm	–2.78 < $\bar{h}$ < 0

IAS: interval of absolute stability; AB: Adams–Bashforth; AM: Adams–Moulton; FORK: fourth-order Runge–Kutta.

Since the initial parameters u₁, u₂, and u₃ are acquired by the FORK algorithm, its convergence condition is also required to be analyzed. When the FORK algorithm is applied to solve equation (12), the following equation is obtained

y_{n + 1} = [1 + \bar{h} + \frac{{\bar{h}}^{2}}{2!} + \frac{{\bar{h}}^{3}}{3!} + \frac{{\bar{h}}^{4}}{4!}] y_{n} = E (\bar{h}) y_{n}

(16)

Similarly, the FORK algorithm is stable as long as the absolute value of $E (\bar{h})$ is less than 1, that is $| E (\bar{h}) | < 1$ . After calculation, the IAS of the FORK algorithm is obtained, which is also shown in Table 1.

From Table 1, the IAS of PMECME is determined by computing the intersection of these IASs, and it is $- 0.3 < \bar{h} < 0$ . Thus, the range of T is obtained as

- \frac{0.3}{λ} > T > 0

(17)

However, equation (17) only guarantees that the PMECME algorithm is stable when calculating a linear system such as equation (12), and it is not suitable for a nonlinear equation such as equation (7). Fortunately, equation (7) can be converted into a linear system approximately at the neighborhood of $(\bar{t}, \bar{u})$ by the local linearization method. Thus, f(t, u) is expanded into Taylor’s series at the neighborhood of $(\bar{t}, \bar{u})$

\begin{matrix} \overset{\cdot}{u} = f (\bar{t}, \bar{u}) + {f'}_{t} (\bar{t}, \bar{u}) (t - \bar{t}) + {f'}_{u} (\bar{t}, \bar{u}) (u - \bar{u}) \\ = {f'}_{u} (\bar{t}, \bar{u}) + g_{1} t + g_{2} \end{matrix}

(18)

where g₁ and g₂ are the constant coefficients. Therefore, equation (18) can be locally linearized and transformed into a linear system as

\begin{matrix} φ' = λ φ \\ φ = u + (g_{1} / λ) t + (g_{1} / λ^{2}) + (g_{2} / λ) \\ λ = {f'}_{u} (\bar{t}, \bar{u}) \end{matrix}

(19)

With the abovementioned method, a linear equation is achieved. Therefore, the PMECME algorithm can be utilized to solve equation (7), and the range of T is approximated as

\begin{matrix} \frac{- 0.3}{λ} = \frac{0.3 {‖ C' (\bar{u}) ‖}^{3}}{v (\bar{t}) C' (\bar{u}) \cdot C ″ (\bar{u})} \geq \frac{0.3 {‖ C' (\bar{u}) ‖}^{3}}{v_{m} ‖ C' (\bar{u}) ‖ ‖ C ″ (\bar{u}) ‖ \cos β} \\ \geq \frac{0.3 {‖ C' (\bar{u}) ‖}^{2}}{v_{m} ‖ C ″ (\bar{u}) ‖} \geq \frac{0.3 ‖ C' (\bar{u}) ‖_{\min}^{2}}{v_{m} {‖ C ″ (\bar{u}) ‖}_{\max}} \\ \Rightarrow T \leq \frac{0.3 ‖ C' (\bar{u}) ‖_{\min}^{2}}{v_{m} {‖ C ″ (\bar{u}) ‖}_{\max}} \end{matrix}

(20)

where v_m indicates the maximum feedrate. Based on the abovementioned analysis, the PMECME algorithm is stable when T satisfies the convergence condition of equation (20).

Simulation

Determination of the interpolation period T

In this section, the PMECME algorithm is adopted to interpolate the quintic Bézier curve C(u). Since the property of curve²¹ demonstrates that $1 / ‖ C' (u) ‖$ is differentiable everywhere and the absolute value of its derivation is bounded, the PMECME algorithm can be used to interpolate C(u). Before interpolation, the range of T should be determined by equation (20). Considering that equation (20) consists of $‖ C' (u) ‖_{\min}$ and $‖ C ″ (u) ‖_{\max}$ , it is necessary to deduce $C' (u)$ and $C ″ (u)$ . The derivatives of C(u) are consequently deduced from equations (1) and (2) as

\begin{matrix} C' (u) = α {\vec{T}}_{0} + b {\vec{T}}_{2}, C ″ (u) = c {\vec{T}}_{0} + d {\vec{T}}_{2} \\ {\begin{matrix} a = 5 (6 R - 3 α) u^{4} + 4 (- 15 R + 8 α) u^{3} \\ + 3 (10 R - 6 α) u^{2} + α \\ b = 5 (6 R - 3 α) u^{4} + 4 (- 15 R + 7 α) u^{3} \\ + 3 (10 R - 4 α) u^{2} \\ c = 20 (6 R - 3 a) u^{3} + 12 (- 15 R + 8 a) u^{2} \\ + 6 (10 R - 6 a) u \\ d = 20 (6 R - 3 a) u^{3} + 12 (- 15 R + 7 a) u^{2} \\ + 6 (10 R - 4 a) u \end{matrix} \end{matrix}

(21)

Therefore, the coefficients of ${\vec{T}}_{0}$ and ${\vec{T}}_{2}$ are achieved, respectively. Meanwhile, because the angle between ${\vec{T}}_{0}$ and ${\vec{T}}_{2}$ belongs to [0, π], $‖ C' (u) ‖_{\min}$ and $‖ C ″ (u) ‖_{\max}$ are in the intervals as

{\begin{matrix} \min {{‖ - (a + b) ‖}_{\max}, {‖ - (a - b) ‖}_{\max}} \leq ‖ C' (u) ‖_{\min} \leq \max {{‖ - (a + b) ‖}_{\max}, {‖ - (a - b) ‖}_{\max}} \\ \min {{‖ c - d ‖}_{\max}, {‖ c + d ‖}_{\max}} \leq ‖ C ″ (u) ‖_{\max} \leq \max {{‖ c - d ‖}_{\max}, {‖ c + d ‖}_{\max}} \end{matrix}

(22)

In the same way, when u is equal to 0.5, the maximum value of $‖ c - d ‖$ is obtained, which is $α \sqrt{4.5 (1 + \cos θ)}$ . When u is {0.2113, 0.7887}, the value of $‖ c + d ‖_{\max}$ occurs, which is equal to $\sqrt{150 R (1 - c o s θ) (R - α) + (42 - 33 c o s θ) α^{2}}$ . Therefore, the value of $‖ C ″ (u) ‖_{\max}$ equals to $\max {‖ C ″ (0.2113) ‖, ‖ C ″ (0.5) ‖, ‖ C ″ (0.7887) ‖}$ . Based on the abovementioned deduction, the range of T is determined as

T \leq \frac{0.3 {‖ C' (\bar{u}) ‖}^{2}}{v_{m} ‖ C ″ (\bar{u}) ‖} = \min (\frac{0.3 α}{v_{m} \sqrt{4.5 (1 + \cos θ)}}, \frac{0.3 α^{2}}{v_{m} \sqrt{150 R (1 - \cos θ) (R - α) + (42 - 33 \cos θ) α^{2}}})

(23)

When T satisfies the condition of equation (23), the stable interpolation can be guaranteed. Next, the interpolation example is given as follows.

As shown in Figure 2(a), $\vec{Q_{0} Q_{1}}$ and $\vec{Q_{1} Q_{2}}$ are two line segments. The coordinates of Q₀, Q₁, and Q₂ are (0,0,0), (8,8,12), and (20,2,4), respectively. With the transition method discussed in section “Principles of a quintic Bézier transition curve and a parametric interpolator,” the curve C(u) is generated to transit the line segments with the approximation radius $R = ‖ Q_{1} Q_{2} ‖$ . By using the adaptive Simpson’s integration rule,²⁶ the length of C(u) is calculated, which equals to 23.93 mm. Then, the ACC/DEC scheduling is carried out,²⁷ whose parameters are listed in Table 2. After the scheduling, the corresponding feedrate profile is generated as shown in Figure 2(b). Next, the convergence analysis is implemented to determine the range of T. According to equation (2), α is equal to 23.98, which is also the minimum value of $‖ C' (u) ‖$ . In addition, when u is 0.5, the maximum value of $‖ C ″ (u) ‖$ is achieved, which equals to 55.4. After that, depending on equation (23), only when T is less than 0.156 s, the PMECME method is stable. From Figure 3(a), it can be observed that the PMECME algorithm is stable when T is chosen as 0.1 s, which is less than 0.156 s. However, when T is chosen as 0.18 s, the parameter error diverges, as shown in Figure 3(b). Therefore, the convergence analysis must be implemented to acquire the convergent interpolation results.

Figure 2.

Schematic diagram of the transition Bézier curve and the generated feedrate profile: (a) a quintic Bézier transition curve and (b) the corresponding feedrate profile.

Table 2.

Parameter setting of the ACC/DEC scheduling.

Name	Parameter	Value
Interpolation period (s)	T	0.1, 0.18
Initial feedrate (mm/ms)	$v_{s}$	0.1
Maximum feedrate (mm/ms)	$v_{m}$	0.2
Final feedrate (mm/ms)	$v_{e}$	0.05
Maximum acceleration (mm/ms²)	$a_{m}$	1.5 × 10⁻⁴
Maximum jerk (mm/ms³)	$j_{m}$	1.5 × 10⁻⁷

Figure 3.

Errors of the PMECME algorithm with different interpolation periods: (a) errors of the proposed algorithm with T_i = 0.1 s and (b) errors of the proposed algorithm with T_i = 0.18 s.

Comparison of different parametric interpolators

In this section, the PMECME algorithm is introduced in the NC field, which is used as a parametric interpolator to generate reference points on the transition curve C(u) in real time.

To evaluate the performance of the PMECME algorithm, other approaches including PCI,⁷ FOTE,¹² SOTE,¹³ TOTE, FORK,¹⁸ and ABM²⁰ algorithms are discussed here. All the algorithms are coded with Visual Studio C++ 2010 and executed in a PC configured with Intel^® Core i5-3470 3.2 GHz CPU and Kingston^® DDR3 1600 MHz 8G memory. The interpolation period T is chosen as 0.1 s, which is less than 0.156 s. After the interpolation, the parameter errors of these algorithms are shown in Figure 4(a) and (b), and their mean parameter errors are presented in Table 3. Meanwhile, two Win32 API functions,²⁸ named as “QueryPerformanceFrequency()” and “QueryPerformance Counter(),” are used to exactly record their execution time. Each algorithm is repeatedly measured 10 times, and the mean execution time is listed in Table 3.

Figure 4.

Comparison of the parameter errors generated by different algorithms: (a) errors generated by PCI, FOTE, and SOTE algorithm and (b) errors generated by TOTE, ABM, FORK, and PMECME. ABM: Adams-Bashforth-Moulton.

Table 3.

Statistical comparisons of the mean parameter error and the mean execution time.

Evaluation index	Algorithm
Evaluation index	PCI⁷	FOTE¹²	SOTE¹³	TOTE	FORK¹⁸	ABM²⁰	Proposed PMECME
Mean parametererror	1.1 × 10⁻²	1.3 × 10⁻²	1.1 × 10⁻³	2.1 × 10⁻⁴	3.81 × 10⁻⁶	9.1 × 10⁻⁵	4.3 × 10⁻⁵
Mean execution time (μs)	129	61	84	103	238	114	116

FOTE: first-order Taylor’s expansion; SOTE: second-order Taylor’s expansion; TOTE: third-order Taylor’s expansion; FORK: fourth-order Runge–Kutta; PMECME: predictor-modification-evaluation–corrector-modification-evaluation; PCI: predictor-corrector interpolator.

Real-time interpolation experiments

Real-time interpolation system construction

From Table 3, it can be observed that the current PCI iteration algorithm cannot satisfy the increasing real-time requirements of parameter error and execution time. The reason is explained as follows. As shown in Figure 5, C(u_k) is a reference point and the corresponding feedrate is v_k at the time t_k. When the next interpolation cycle t_k₊₁ arrives, the scheduled path is an arc $\bar{C (u_{k}) C ({\bar{u}}_{k} + 1)}$ and the arc length is s = v_k·T. However, the actual path is the line path $\bar{C (u_{k}) C ({\bar{u}}_{k + 1})}$ according to PCI iteration condition.⁷ When the PCI algorithm is used to interpolate the transition curve with small length and large curvature, it leads to large position error inevitably as shown in Figure 5. Compared with the PCI algorithm, SOTE and TOTE algorithms can improve the interpolation accuracy, and their computational amounts can both satisfy the real-time requirements. When the higher interpolation accuracy is required, the FORK algorithm needs to be adopted. Nonetheless, it needs to calculate f(t, u) four times in each interpolation cycle, which is not suitable for real-time interpolation. To overcome this problem, the ABM algorithm is adopted, which only needs to calculate f(t, u) two times in each cycle. However, the interpolation accuracy of this algorithm is decreased. To further improve the ABM algorithm, the PMECME algorithm is deduced. From Table 3, it can be seen that the PMECME algorithm provides a good balance between efficiency and accuracy. Therefore, the PMECME algorithm is more suitable for real-time interpolation.

Figure 5.

Explanation of the error generated by PCI iteration algorithm.

In this section, a real-time interpolation system is constructed, which includes a smoothing module, a look-ahead ACC/DEC scheduling module, an interpolation module, and a timer module. The relationships among them are depicted as follows. The smoothing module is responsible to smooth line segments based on the transition method as shown in section “Principles of a quintic Bézier transition curve and a parametric interpolator.” Thus, a smooth tool path including Bézier curves and line segments is generated. Then, the path is divided into several ACC/DEC schedule units (ASUs) at the midpoint of each Bézier curve. After that, the ACC/DEC scheduling²⁷ is implemented for each ASU to generate the corresponding feed rate profile. Since all the ASUs’ feedrate profiles could not be generated at one time due to the computational limitation of system, a look-ahead ACC/DEC scheduling module is utilized, which can generate feedrate profiles step by step (the detailed process is depicted in the next paragraph). Next, according to the generated feedrate profiles and the corresponding ASUs, reference points can be generated in real time with the cooperation of the interpolation module and the timer module. Here, the interpolation module consists of a parametric interpolator and a line interpolator.²¹ In addition, the timer period is set to 10 ms based on the Win 32 multimedia timer modular (with 1 ms resolution), which aims to repeatedly activate the interrupt service routine (ISR). Meanwhile, the interpolation period T is set to 1 ms. In this way, the NC system generates 10 reference points in each ISR.

The real-time interpolation strategy in the system is given as follows. As shown in Figure 6(a), a sliding window is introduced, which can cover the maximum number of k line segments. Note that the window-sliding position is set to an integer multiple of ASU.

In the first time period (expressed as I₀ in Figure 6(b)), NC system puts k line segments into the window (e.g. window 0 in Figure 6(a)). Then, the timer module activates ISR and enables other modules in ISR. First, the smoothing module smoothes these line segments and generates a smooth tool path (the solid blue lines connected with the dotted red lines in window 0). Second, the path is divided into ASUs. Then, the look-ahead ACC/DEC scheduling module obtains feedrate profiles. At last, based on ASUs and feedrate profiles, the interpolation module generates the specified number of reference points (10 points) and utilizes the points to guide the tool movement along the path.

In the next timer period, the NC system examines whether the tool has reached the window-sliding position (the position where the window 0 and windows 1 overlap). If not reached, only the interpolation module works in this ISR (the I₁ in Figure 6(b)). Accordingly, the new reference points, with the same number as before, are generated and make the tool continue to move. Otherwise, the window slides forward (the window 1 in Figure 6(a)). That is to say, the line segments in front of the window-sliding position are removed from the window, and the same number of new line segments is added into the window.

Figure 6.

Schematic diagram of the real-time interpolation strategy: (a) the machining tool path and (b) the program of real-time interpolation.

Interpolation experiments and efficiency analysis

As shown in Figure 7(a), a NC machine with the real-time interpolation system is adopted to evaluate the computational efficiency of PMECME algorithm by imbedding the algorithm into its system. Meanwhile, other comparative algorithms including PCI, SOTE, and TOTE algorithms are also imbedded into the system, respectively.

Figure 7.

Real-time interpolation experiment of the two-dimensional butterfly pattern: (a) the NC machine used in the experiment, (b) the smooth tool path ( $ε$ = 1 mm), (c) the corresponding feedrate profile, and (d) the real-time interpolation experiment.

A butterfly graphic, which consists of 500 line segments, is used here as the test pattern for implementing the real-time interpolation task. These line segments are depicted as solid blue lines in Figure 7(b). The interpolation parameters are presented below. The timer period is set to 10 ms, and the interpolation period T is set to 1 ms. The approximation error ε is 1 mm, and the number of line segments k in each window is 5. The maximum feedrate, the maximum acceleration, and the maximum jerk are 0.05, 0.001,² and 0.001 mm/ms,³ respectively. First, with the smoothing module, a smooth tool path, composed of the solid blue lines and the dotted red lines in Figure 7(b), is generated. Then, the look-ahead ACC/DEC scheduling is executed, and the generated feedrate profile of tool path is illustrated in Figure 7(c). From the figure, it can be seen that the whole interpolation task consumes 22,701 ms. After the completion of interpolation task, the tool path of each algorithm is generated and the enlarged partial view of the path is shown in Figure 8, respectively.

Figure 8.

Comparison of the enlarged partial view of tool paths generated by different systems with PCI (a), SOTE (b), TOTE (c), and PMECME (d) algorithms.

The position error and execution time of each ISR are recorded and illustrated in Figures 9 and 10. Figure 9(a) shows the position error achieved by the system that uses the PCI algorithm as the parametric interpolator. The reason that causes the error has been discussed in section “Simulation.” Since the error leads to deviation of the interpolation point, there is an obvious light stripe on the tool path, which can be seen in Figure 8(a). Meanwhile, Figure 10(a) indicates the execution time of the system with the PCI algorithm. The figure indicates that this system takes the longest amount of time. Since the PCI algorithm adopts the iteration operation to calculate reference points, it is inapplicable to interpolate the transition curve in real time.

Figure 9.

Comparison of the position errors generated by different systems with PCI (a), SOTE (b), TOTE (c), and PMECME (d) algorithms.

Figure 10.

Comparison of the execution time generated by different systems with PCI (a), SOTE (b), TOTE (c), and PMECME (d) algorithms.

Figures 9(b) and 10(b) show the positron error and execution time of the system with the SOTE algorithm, respectively. Since the SOTE algorithm has the merits of flexible control and simple implementation, it is less time-consuming and has higher convergence precision than the PCI algorithm, which has been widely utilized in the NC field. However, this algorithm only achieves o(T³) truncation error, and the error may not satisfy high precision machining requirements especially when interpolating the transition curve which has the large curvature.

As shown in Figure 8(b), there is also an obvious light stripe on the tool path. To obtain o(T⁴) truncation error, the TOTE algorithm is deduced. Figures 9(c) and 10(c) show the position error and execution time of the system with the TOTE algorithm. As shown in the figures, this system has smaller position error than the system with the SOTE algorithm. When this system is adopted to generate the tool path, the light stripe on the path, as shown in Figure 8(c), is reduced effectively. However, the TOTE algorithm is obtained from the high-order expansion of the SOTE algorithm, so it spends longer execution time than the SOTE algorithm. Accordingly, these two systems fail to achieve good interpolation performance as shown in Table 4. When the quintic Bézier curve is specified as the transition curve, the system with the proposed PMECME algorithm, as shown in Figures 9(d) and 10(d), achieves the highest accuracy because it has the o(T⁵) truncation error. Figure 8(d) gives the tool path generated by the system with the PMECME algorithm. In the figure, the light stripe on the tool path is further reduced and hardly observed. In addition, the convergence of the PMECME algorithm is deduced in equation (20), so the stability of the algorithm is guaranteed during the real-time interpolation. Although this system, as shown in Figure 10(d), consumes a little more time than that of the SOTE-based system, it achieves a good balance between efficiency and accuracy.

Table 4.

Comparison of experimental results obtained by the systems with different interpolation algorithms.

Interpolation system	Evaluation index
Interpolation system	Mean absolute position error (mm)	Mean execution time (ms)
System with PCI	3.24 × 10⁻³	0.3465
System with SOTE	3.15 × 10⁻³	0.1412
System with TOTE	3.02 × 10⁻⁴	0.1848
System with proposed PMECME	2.37 × 10⁻⁷	0.1465

SOTE: second-order Taylor’s expansion; TOTE: third-order Taylor’s expansion; PMECME: predictor-modification-evaluation–corrector-modification-evaluation.

Conclusion

The parametric interpolator based on the TE algorithm with different orders is discussed first in this article. With the increase in the order of Taylor series, computational burden is getting more and more complicated. To deal with the issue, a parametric interpolator based on the PMECME algorithm is proposed here to achieve an o(T⁵) truncation error, and the convergence condition is analyzed afterward. The determination of interpolation period is deduced, and different parametric interpolators are simulated to compare with each other. Simulation results show that with the PMECME algorithm, the mean execution time is decreased as well as the truncation error is further improved. Then, the proposed parametric interpolator and traditional line interpolator are simultaneously applied for real applications with a cutting tool path composing of transition curves and line segments. The performance of PMECME algorithm is evaluated through the two-dimensional butterfly interpolation experiment, and the results verify the accuracy and efficiency. The proposed PMECME algorithm achieves the highest accuracy and the light stripe on the tool path is further reduced and hardly observed.

Footnotes

Appendix 1 Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: This work was supported in part by National Natural Science Foundation of China (Grant No. 51805325), National Key Basic Research Program of China (Grant No. 2013CB035804), National Science and Technology Major Project (Grant No. 2015 ZX04005006), and State Key Lab of Digital Manufacturing Equipment & Technology (Grant No. DMETKF2016002).

ORCID iDs

Chao Liu

Hui Wang

References

Huang

Zhu

L-M.

A locally optimal transition method with analytical calculation of transition length for computer numerical control machining of short line segments. Proc IMechE, Part B: J Engineering Manufacture 2018; 232: 2409–2419.

W-J

Rastegar

A real-time and look-ahead interpolation algorithm with axial jerk-smooth transition scheme for computer numerical control machining of micro-line segments. Proc IMechE, Part B: J Engineering Manufacture. Epub ahead of print 3 November 2018. DOI: 10.1177/0954405418809768.

Huang

Parallel acceleration/deceleration feedrate scheduling for computer numerical control machine tools based on bi-directional scanning technique. Proc IMechE, Part B: J Engineering Manufacture 2019; 233: 937–947.

Zhang

Gao

Acceleration smoothing algorithm for global motion in high-speed machining. Proc IMechE, Part B: J Engineering Manufacture 2019; 233: 1844–1858.

Zhang

S-J

, et al. A segment feedrate profile fitting method for parametric interpolation. Proc IMechE, Part B: J Engineering Manufacture 2018; 232(2): 267–280.

J-G

Qiu

M-M

Zhang

T-H

, et al. A practical realtime non-uniform rational B-spline curve interpolator for computer numerical control machining. Proc IMechE, Part C: J Mechanical Engineering Science 2012; 226(4): 1068–1083.

Chen

C-W

Tsai

M-S

Maciejowski

Feedrate control for non-uniform rational B-spline motion command generation. Proc IMechE, Part B: J Engineering Manufacture 2006; 220(11): 1855–1861.

Karimi

Nategh

MJ.

Development of a novel adaptive nonuniform rational basis spline interpolator with limited kinematic error for hexapod machine tools. Proc IMechE, Part B: J Engineering Manufacture 2014; 228(3): 319–327.

Han

J-Z

Chen

W-H.

Velocity control algorithm in glass polishing based on the cubic NURBS curve. Proc IMechE, Part C: J Mechanical Engineering Science 2018; 232: 685–696.

10.

Zhang

, et al. Fast parametric curve interpolation with minimal feedrate fluctuation by cubic B-spline. Proc IMechE, Part B: J Engineering Manufacture 2018; 232(9): 1642–1652.

11.

Sun

Y-W

Zhao

Bao

Y-R

, et al. A novel adaptive feedrate interpolation method for NURBS tool path with drive constraints. Int J Mach Tool Manu 2014; 77: 74–81.

12.

Baek

D-K

T-J

Yang

S-H.

Fast and precision NURBS interpolator for CNC. Int J Precis Eng Man 2012; 13(6): 955–961.

13.

Cheng

C-W

Tsai

MC.

Real-time variable feed rate NURBS curve interpolator for CNC machining. Int J Adv Manuf Tech 2004; 23(11–12): 865–873.

14.

Wang

Yang

Gai

, et al. Design of trigonometric velocity scheduling algorithm based on pre-interpolation and look-ahead interpolation. Int J Mach Tool Manu 2015; 96: 94–105.

15.

Liu

Jia

, et al. Interpolation using non-uniform rational B-spline for the smooth milling of ruled-surface impeller blades. Proc IMechE, Part B: J Engineering Manufacture 2015; 229(7): 1118–1130.

16.

Zhou

Tang

, et al. A NURBS interpolation algorithm with continuous feedrate. Int J Adv Manuf Tech 2012; 59(5–8): 623–632.

17.

Chen

Zhao

W-S

X-C.

Augmented Taylor’s expansion method for B-spline curve interpolation for CNC machine tools. Int J Mach Tool Manu 2015; 94: 109–119.

18.

Jia

Z-Y

Song

D-N

J-W

, et al. A NURBS interpolator with constant speed at feedrate-sensitive regions under drive and contour-error constraints. Int J Mach Tool Manu 2017; 116: 1–17.

19.

Jahanpour

Alizadeh

MR.

A novel acc-jerk-limited NURBS interpolation enhanced with an optimized S-shaped quintic feedrate scheduling scheme. Int J Adv Manuf Tech 2015; 77(9–12): 1889–1905.

20.

Fathoni

Wuryandari

. Comparison between Euler, Heun, Runge-Kutta and Adams-Bashforth-Moulton integration methods in the particle dynamic simulation. In: Proceedings of the 4th international conference on interactive digital media (ICIDM), Bandung, Indonesia, 1–5 December 2015, pp.1–7. New York: IEEE.

21.

Wang

J-H

Liu

, et al. A real-time interpolation strategy for transition tool path with C2 and G2 continuity. Int J Adv Manuf Tech 2018; 98(1–4): 905–918.

22.

Garrappa

On some explicit Adams multistep methods for fractional differential equations. J Comput Appl Math 2009; 229(2): 392–399.

23.

Chiou

SD.

On the generation of higher order numerical integration methods using lower order Adams-Bashforth and Adams-Moulton methods. J Comput Appl Math 1999; 108(1–2): 19–29.

24.

Burden

Faires

JD.

Numerical analysis. 9th ed. Scarborough, ON: Nelson Education Ltd, 2010.

25.

Dahlquist

GG.

A special stability problem for linear multistep methods. Bit Numer Math 1963; 3(1): 27–43.

26.

Heng

Erkorkmaz

Design of a NURBS interpolator with minimal feed fluctuation and continuous feed modulation capability. Int J Mach Tool Manu 2010; 50: 281–293.

27.

Wang

Liu

J-H

, et al. A high-flexible ACC/DEC look-ahead strategy based on quintic Bézier feedrate curve. In: Proceedings of the 9th international conference on intelligent robotics and applications (ICIRA), Tokyo, Japan, 22–24 August 2016, pp.697–708. Cham: Springer.

28.

Kuperberg

Krogmann

Reussner

. TimerMeter: quantifying properties of software timers for system analysis. In: Proceedings of the 6th international conference on the quantitative evaluation of systems (QEST), Budapest, 13-16 September 2009, pp.85–94. New York: IEEE.