Sage Journals: Discover world-class research

Abstract

The acceleration/deceleration feedrate scheduling is one of the most important techniques in computer numerical control systems. Along with this technique, the bi-directional scanning technique is always employed. The bi-directional scanning technique consists of a backward scanning process followed by a forward scanning process. The two scanning processes in the conventional methods are executed in a serial manner by scanning through all the scheduling blocks one by one. Consequently, the feedrate scheduling will suffer from a heavy computational burden when there are massive blocks to be scanned, which deteriorates its real-time performance for computer numerical control machining. To alleviate the computational burden, a parallel acceleration/deceleration feedrate scheduling approach is proposed in this article. With this method, the scheduling blocks are splitted into several scheduling units and the feedrate for each of them is scheduled simultaneously. The feasibility of the proposed approach is validated through the feedrate scheduling for two widely used butterfly and helix paths. For a constructed example of feedrate scheduling, a significant acceleration ratio about 3.7 on a personal computer with a quad-core central processing unit is achieved.

Keywords

Computer numerical control system parallel feedrate scheduling bi-directional scanning technique feedrate-acceleration function long-block threshold

Introduction

In order to meet the high-speed and high-accuracy requirements in modern computer numerical control (CNC) equipment, various techniques have been proposed to schedule the feedrate for CNC machine tools. Due to its robustness and high computational efficiency, the acceleration/deceleration (AD) feedrate scheduling method is one of the most widely used scheduling methods in CNC systems.

The AD method was first applied to plan motions for single-axis systems and linear tool paths^1–4 and extended to deal with motions for parametric tool paths later.^5–12 As mentioned in previous studies,^13–17 the most widely used profiles in AD approach are polynomial (e.g. linear-velocity, trapezoidal-velocity and trapezoidal-acceleration) and trigonometric profiles. The formulas of the AD feedrate profile are well studied, and one can easily construct an AD feedrate profile following the ideas in previous studies.^{2,10,12,15,18,19} However, the feedrate profile for the whole tool path usually consists of a sequence of AD feedrate profiles splitted by the so-called critical/break points. For multiple profiles, the start and end feedrates of each AD feedrate profile must be thoroughly handled to avoid feedrate discontinuity at the junction of two adjacent profiles. The bi-directional scanning technique, which consists of a backward scanning process followed by a forward scanning process, is normally adopted to guarantee the smoothness of the whole feedrate profile. Contrary to the construction of AD feedrate profiles, analysis of the bi-directional scanning technique is scarcely addressed. Bobrow et al.²⁰ proposed a switching-curve algorithm to solve the time-optimal control problem for manipulators. The algorithm, which was later adopted to plan time-optimal feedrate for machine tools,^21–24 employed an idea similar to the bi-directional scanning technique and its feasibility was proved. However, the switching-curve algorithm differs from the bi-directional scanning technique in the following two aspects: (1) the backward scanning process was invoked several times in the switching-curve algorithm when multiple switching points are encountered, while it was employed only once in the bi-directional scanning technique; (2) the switching points were determined by solving differential equations in the switching-curve algorithm, while critical/break points were specified in advance for the bi-directional scanning technique. Luo et al.¹⁴ introduced a doubly linked list to generate the feedrate profiles and the bi-directional scanning technique was applied within the list. Lee et al.⁹ categorized the scheduling blocks into long and short block according to their length and applied a backward scanning process to the successive short blocks in priority. Zhao et al.^11,17 detailed the bi-directional scanning technique and applied it within a look-ahead window in real time. To make the entire feedrate profile continuous, Fan et al.¹⁰ proposed a backtracking algorithm which is similar to the bi-directional scanning technique.

To our knowledge, all of the conventional AD feedrate scheduling approaches applied the bi-directional scanning technique to scan through the entire scheduling blocks or the blocks in a look-ahead window (if a look-ahead window is involved) one by one. As mentioned in Suh et al.,¹ thousands of blocks are pre-interpreted by the look-ahead algorithm in the commercial CNC systems. If the traditional serial approach is utilized, the feedrate scheduling for numerous blocks will become computationally demanding. Consequently, the real-time performance of the CNC systems will be deteriorated. To alleviate the heavy computational burden, a parallel AD feedrate approach based on the bi-directional scanning technique is proposed in this article.

The remainder of this article is organized as follows. In section “Feedrate-acceleration function,” the mathematical model of the feedrate-acceleration function is first established and then the properties of the feedrate-acceleration function are discussed. In section “Long-block threshold,” the long-block threshold is defined and the blocks are categorized into long and short blocks by their long-block thresholds. In section “Parallel feedrate scheduling approach,” a parallel approach for AD feedrate scheduling is proposed. Simulations are conducted in section “Examples” and conclusions are drawn in section “Conclusion.”

Feedrate-acceleration function

As discussed in Luo et al.¹⁴ and Huang and Zhu,¹⁵ there are seven practicable AD feedrate profiles, as shown in Figure 1. Given the kinematic constraints, the start velocity and the end velocity, the type of a feedrate profile is determined by its length. If the length is long, an acceleration (ACC)+constant feedrate (CF)+ deceleration (DEC) profile is adopted. If the length is short, an ACC or DEC profile is adopted. Otherwise, an ACC+DEC profile is adopted. The CF, ACC+CF or CF+DEC profile is utilized only under some rare conditions.

Figure 1.

Seven practicable AD feedrate profiles.

For the ACC and DEC profiles, the boundary velocities will probably be decreased by the bi-directional scanning technique.¹⁵ Specifically, the end velocity of the ACC profile is decreased, and so is the start velocity of the DEC profile. Therefore, it is necessary to study the properties of the ACC and DEC profiles with decreased boundary velocities. Note that the DEC profile can be regarded as an ACC profile accelerating the velocity from the end velocity to the start velocity, as shown in Figure 2. The properties of the ACC profile are explored first. The properties of the DEC profile can be obtained straightforwardly once the properties of the ACC profile are revealed.

Figure 2.

ACC and DEC profiles with decreased boundary velocities: (a) ACC profile and (b) DEC profile.

The function $f (t)$ utilized to express the ACC profile, which increases the velocity from the start velocity $v_{s}$ to end velocity $v_{e}$ ( $v_{e} > v_{s}$ ), is termed the feedrate-acceleration function. A jerk-continuous feedrate-acceleration function satisfies all of the following constraints

{\begin{matrix} f (0) = v_{s}, f' (0) = 0, f ″ (T) = 0 \\ f (T) = v_{e} ⩽ v_{max}, f' (T) = 0, f ″ (T) = 0 \end{matrix}

(1a)

{\begin{matrix} v_{s} ⩽ f (t) ⩽ v_{e}, | f' (t) | ⩽ a_{max} \\ | f ″ (t) | ⩽ j_{max}, | f ‴ (t) | ⩽ s_{max} \end{matrix}, t \in [0, T]

(1b)

\int_{0}^{T} f (t) dt = l_{0}

(1c)

where t denotes time; T is the time required to traverse the path; $l_{0}$ is the length of the tool path; the constraint equation (1c) is imposed by the requirement that the traveling distance should be identical to the length of the path and $v_{max}$ , $a_{max}$ , $j_{max}$ and $s_{max}$ are the maximum allowable velocity, acceleration, jerk and snap (or jounce), respectively. In order to construct a time-optimal AD feedrate profile, the “Bang-Bang” or “Bang-Bang-Singular” control is usually adopted in the bi-directional scanning technique.^10,11,25 It requires that at least one of the kinematic quantities $f (t)$ , $f' (t)$ , $f ″ (t)$ and $f ‴ (t)$ reaches its bound at any time. In this sense, at least one of the inequality constraints in equation (1b) is active.

Given the kinematic constraints, a unique feedrate-acceleration function $f (t)$ can be determined by any two of the three parameters $v_{s}$ , $v_{e}$ and $l_{0}$ . In Fan et al.,¹⁰ two algorithms PRO_VV and PRO_VD were developed to determine $f (t)$ under different boundary conditions. Nevertheless, the existence of a feedrate-acceleration function is not guaranteed if all the three parameters are assigned. In fact, the end velocity $v_{e}$ probably has to be changed in this case when a feedrate-acceleration function is required. It is the reason why the boundary velocities of the ACC and DEC feedrate profiles are altered in the process of bi-directional scanning for the feedrate scheduling. As for the feedrate-acceleration function with all the three parameters assigned, we have the following theorem.

Theorem 1

Suppose there is a feedrate-acceleration function $f_{1} (t)$ transiting the velocity from $v_{s}^{1}$ to $v_{e}^{1}$ with a traveling time $T_{1}$ and a traveling distance $l_{0}$ . If the boundary velocities are decreased to lower values $v_{s}^{2}$ ( $v_{s}^{2} ⩽ v_{s}^{1}$ ) and $v_{e}^{2}$ ( $v_{s}^{2} ⩽ v_{e}^{2} ⩽ v_{e}^{1}$ ), there exists an feedrate profile transiting the velocity from $v_{s}^{2}$ to $v_{e}^{2}$ with the same traveling distance $l_{0}$ in the case $(v_{e}^{2} - v_{s}^{2}) / (v_{e}^{2} - v_{s}^{2}) (v_{e}^{1} - v_{s}^{1}) (v_{e}^{1} - v_{s}^{1}) ⩽ 1$ .

Proof

Denote $f_{1} (t) = v_{s}^{1} + f_{0} (t), t \in [0, T_{1}]$ , where $f_{0} (t)$ satisfies the following constraints

\begin{matrix} f_{0} (0) = {f'}_{0} (0) = {f ″}_{0} (0) = 0 \\ f_{0} (T_{1}) = v_{e}^{1} - v_{s}^{1} \\ {f'}_{0} (T_{1}) = {f ″}_{0} (T_{1}) = 0 \end{matrix}

(2)

Then a function $g (t)$ is constructed as follows

\begin{matrix} g (t) = v_{s}^{2} + g_{0} (t), t \in [0, T_{g}] \\ g_{0} (t) = \frac{v_{e}^{2} - v_{s}^{2}}{v_{e}^{1} - v_{s}^{1}} f_{0} (\frac{T_{1}}{T_{g}} t), t \in [0, T_{g}] \end{matrix}

(3)

It is obvious that $g (t)$ defined in equation (3) satisfies the equality constraints of velocity, acceleration, jerk and snap in equation (1a). Assuming that $g (t)$ has the same traveling distance as $f_{1} (t)$ , we have

\begin{matrix} \int_{0}^{T_{g}} g (t) dt = \int_{0}^{T_{g}} (v_{s}^{2} + \frac{v_{e}^{2} - v_{s}^{2}}{v_{e}^{1} - v_{s}^{1}} f_{0} (\frac{T_{1}}{T_{g}} t)) dt \\ = v_{s}^{2} T_{g} + \frac{v_{e}^{2} - v_{s}^{2}}{v_{e}^{1} - v_{s}^{1}} \frac{T_{g}}{T_{1}} (l_{0} - v_{s}^{1} T_{1}) \\ = (\frac{v_{s}^{2} (v_{e}^{1} - v_{s}^{1}) T_{1} + (v_{e}^{2} - v_{s}^{2}) (l_{0} - v_{s}^{1} T_{1})}{(v_{e}^{1} - v_{s}^{1}) T_{1}}) T_{g} = l_{0} \end{matrix}

(4)

Because $l_{0} > v_{s}^{1} T_{1}$ , it is obvious that

v_{s}^{2} (v_{e}^{1} - v_{s}^{1}) T_{1} + (v_{e}^{2} - v_{s}^{2}) (l_{0} - v_{s}^{1} T_{1}) > 0

(5)

According to equations (4) and (5), we deduce that $T_{g}$ exists and $T_{g} / T_{1} > 1$ as illustrated in equation (6) (considering that $l_{0} > v_{s}^{1} T_{1}$ )

\begin{matrix} \frac{T_{g}}{T_{1}} = \frac{(v_{e}^{1} - v_{s}^{1}) l_{0}}{T_{1} (v_{s}^{2} v_{e}^{1} - v_{s}^{1} v_{e}^{2}) + (v_{e}^{2} - v_{s}^{2}) l_{0}} \\ > \frac{(v_{e}^{1} - v_{s}^{1}) v_{s}^{1} T_{1}}{T_{1} (v_{s}^{2} v_{e}^{1} - v_{s}^{1} v_{e}^{2}) + (v_{e}^{2} - v_{s}^{2}) v_{s}^{1} T_{1}} \\ = \frac{v_{s}^{1}}{v_{s}^{2}} > 1 \end{matrix}

(6)

We also have

{\begin{matrix} g' (t) = {g'}_{0} (t) = \frac{v_{e}^{2} - v_{s}^{2}}{v_{e}^{1} - v_{s}^{1}} \frac{T_{1}}{T_{g}} {f'}_{0} (\frac{T_{1}}{T_{g}} t) \\ g ″ (t) = {g ″}_{0} (t) = \frac{v_{e}^{2} - v_{s}^{2}}{v_{e}^{1} - v_{s}^{1}} {(\frac{T_{1}}{T_{g}})}^{2} {f ″}_{0} (\frac{T_{1}}{T_{g}} t) \\ g ‴ (t) = {g ‴}_{0} (t) = \frac{v_{e}^{2} - v_{s}^{2}}{v_{e}^{1} - v_{s}^{1}} {(\frac{T_{1}}{T_{g}})}^{3} {f ‴}_{0} (\frac{T_{1}}{T_{g}} t) \end{matrix}, t \in [0, T_{g}]

(7)

Based on equations (6) and (7), it can be deduced that there exists a function $g (t), t \in [0, T_{g}]$ satisfying the constraints in equations (1a)–(1c) if $(v_{e}^{2} - v_{s}^{2}) / (v_{e}^{1} - v_{s}^{1}) ⩽ 1$ . Note that $g (t), t \in [0, T_{g}]$ is sub-optimal in the sense that none of the kinematic quantities reaches its bound. However, an ACC, ACC+DEC or ACC+CF+DEC feedrate profile determined by $l_{0}$ can be obtained to transit the velocity from $v_{s}^{2}$ to $v_{e}^{2}$ with the same traveling distance $l_{0}$ . The feedrate profile can be constructed in a manner different from equation (3), for example, as the analytical method in Lin et al.⁸ and Zhao et al.¹¹ or the dichotomy method in Lee et al.⁹ and Huang and Zhu.¹⁵ Based on Theorem 1, we have the following corollary.

Corollary 1

Suppose there exists a feedrate-acceleration function $f (t)$ transiting the velocity from $v_{s}^{1}$ to $v_{e}^{1}$ . If the end velocity is decreased to a value in the interval $[v_{s}^{1}, v_{e}^{1}]$ and the start velocity remains unchanged, there always exists a feedrate profile satisfying the new velocity boundary conditions.

However, the existence of a feedrate profile cannot be guaranteed by Theorem 1 if the start velocity is increased to a value in the interval $[v_{s}^{1}, v_{e}^{1}]$ and the end velocity remains unchanged.

Long-block threshold

As mentioned in section “Feedrate-acceleration function,” a unique feedrate-acceleration function with a traveling distance d can be determined by the two boundary velocities $v_{s}$ and $v_{e}$ ( $v_{e} > v_{s}$ ). Thus, a function $d_{max} (v_{e})$ of the end velocity $v_{e}$ can be defined as

d_{max} (v_{e}) = max d (v_{s}, v_{e}), \forall v_{s} \in [0, v_{e}],

(8)

where $d (v_{s}, v_{e})$ is the traveling distance determined by $v_{s}$ and $v_{e}$ . In the case that $v_{e} ⩽ v_{s}$ , a function $d_{max} (v_{s})$ can be defined in a similar way. The value of $d_{max}$ is determined by the higher boundary velocity $v_{m} = max (v_{s}, v_{e})$ and is termed the long-block threshold. If the block length $l_{0}$ is less than $d_{max}$ , the block is termed a short block. Otherwise, the block is termed a long block.

For the long blocks, we have the following theorem.

Theorem 2

For a long block, there always exists a feedrate profile transiting the velocity from any value $v_{1} \in [0, v_{m}]$ to any value $v_{2} \in [0, v_{m}]$ with a traveling length identical to the block length, where $v_{m}$ is the higher one of the two boundary velocities.

Without loss of generality, assuming that $v_{e} > v_{s}$ , Theorem 2 is trivial due to the following two facts:

By the definition of the long block, there always exists a feedrate-acceleration function transiting the velocity from any value $v_{1} \in [0, v_{e}]$ to $v_{e}$ with a traveling distance not greater than $l_{0}$ . Thus, a feedrate profile transiting the velocity form $v_{1}$ to $v_{e}$ with a traveling length $l_{0}$ is always feasible.

Based on Corollary 1, there exists a feedrate profile transiting the velocity from a value $v_{1} \in [0, v_{e}]$ to any value $v_{2} \in [v_{1}, v_{e}]$ with a traveling length $l_{0}$ .

Parallel feedrate scheduling approach

For a given tool path, the procedure for the AD feedrate scheduling consists of three stages: pre-processing, feedrate profile generation and interpolation stages. In the stage of pre-processing, the critical points are identified and the nominal velocity $v_{n}^{i}$ at each critical point is determined. With these critical points, the entire tool path is splitted into several blocks.

In the stage of feedrate profile generation, the bi-directional scanning technique is utilized to smoothly connect the velocities for each block. The bi-directional scanning technique consists of a backward scanning process followed by a forward scanning process. The backward scanning process is carried out from the end to the start of the whole tool path. It attempts to find a feedrate-acceleration function to accelerate the velocity from the end to the start within each block. Therefore, the nominal start velocity of a block may be altered in the backward scanning process. The forward scanning process is carried out from the start to the end of the whole tool path. It attempts to find a feedrate-acceleration function to accelerate the velocity from the start to the end within each block. Therefore, the nominal end velocity of a block may be altered in the forward scanning process. After the bi-directional scanning, the final velocity $v_{f}^{i}$ at each critical point is obtained.

A pair of successive long blocks, as shown in Figure 3, is termed as a long-block duplet. A long-block duplet covers three boundary velocities, that is, $v_{n}^{i - 1}$ , $v_{n}^{i}$ and $v_{n}^{i + 1}$ . For the long-block duplet, we have Corollary 2.

Figure 3.

Long-block duplet and its boundary velocities.

Corollary 2

The middle velocity of a long-block duplet will remain unchanged after the bi-directional scanning, that is, $v_{f}^{i} \equiv v_{n}^{i}$ . Based on Theorem 2, there always exists a feedrate profile transiting the velocity from any value $v_{f}^{i - 1} \in [0, v_{n}^{i - 1}]$ to $v_{n}^{i}$ for the long block $L_{i - 1}$ and transiting the velocity from $v_{n}^{i}$ to any value $v_{f}^{i + 1} \in [0, v_{n}^{i + 1}]$ for the long block $L_{i}$ . Therefore, Corollary 2 is proved.

On the basis of Corollary 2, a parallel approach for feedrate scheduling is proposed. First, the blocks are categorized into long and short blocks according to the corresponding long-block thresholds. Then the overall blocks are splitted into several scheduling units by the middle of long-block duplet, as shown in Figure 4. The scheduling units are categorized into the following two types in terms of their compositions: type A—successive blocks ended by the middle of the long-block duplet and type B—the long block except the ones next to short blocks.

Figure 4.

Illustration of spitting the feedrate scheduling blocks.

The first and last blocks of type A scheduling units are either long blocks or the overall first/last blocks, as shown in Figure 4. Note that the initial and final velocities of the tool path, that is, the start velocity of the first block and the end velocity of the last block, are normally zero and cannot be decreased. Therefore, the boundary velocities of type A scheduling unit will not be changed by the bi-directional scanning technique based on Corollary 2. Moreover, it is obvious that the boundary velocities of type B scheduling unit will also not be changed. Since the boundary velocities of all scheduling units remain unchanged, the feedrate for every scheduling unit can be scheduled separately and simultaneously. Specifically, the feedrates of the type A units can be scheduled by applying the bi-directional scanning technique to each unit, and the feedrates of the type B units can be scheduled directly with the nominal boundary velocities.

Examples

Calculation of the long-block threshold

Since the long-block threshold plays a key role in the parallel feedrate scheduling, its calculation is discussed first. For a feedrate-acceleration function, the long-block threshold is determined by the end velocity, the kinematic constraints and the type of the feedrate profile. The kinematic constraints given in Table 1 will be adopted for all the examples in this article. Three typical feedrate-acceleration functions, that is, the jounce-confined polynomial function, the jerk-confined polynomial function and the sinusoidal-jerk trigonometric function, are considered.

Table 1.

Parameters for feedrate scheduling.

Parameters	Symbols	Values
Sampling period	$T_{s}$	$0.001 s$
Chord error	$δ$	$0.001 mm$
Maximum velocity	$v_{max}$	$100 mm / s$
Maximum acceleration	$a_{max}$	$1000 mm / s^{2}$
Maximum jerk	$j_{max}$	$5000 mm / s^{3}$
Maximum jounce	$s_{max}$	50,000 $mm / s^{4}$

The long-block thresholds are obtained in advance by a straightforwardly search method. Given the end velocity $v_{e}$ , the long-block threshold is adopted as the maximum traveling distance of the feedrate-acceleration function when the start velocity $v_{s}$ increases from zero to $v_{e}$ . The long-block thresholds $d_{max}$ and the start velocities $v_{s}^{max}$ at which the thresholds are achieved are depicted in Figure 5. The legends ConJn, ConJk and ConJkSn denote results of the jounce-confined, jerk-confined and sinusoidal-jerk functions, respectively. These legends are utilized for all the simulation results. As can be seen from the values of $v_{s}^{max}$ in Figure 5, the long-block threshold for a given end velocity is achieved by adopting a non-zero rather than a zero start velocity. This result does not conform to the conventional concepts about the feedrate-acceleration function. As for the conventional concepts, the maximum traveling distance for a given end velocity is supposed to be achieved when the start velocity is zero.^9,10

Figure 5.

Long-block threshold with respect to end velocity: (a) the long-block threshold and (b) the start velocities at which the long-block thresholds are achieved.

The nominal end velocity of a block, which is set as the limit velocity at the critical point, is the same as the nominal start velocity of the next block. Since the long-block threshold is determined only by the higher boundary velocity, the long-block thresholds of two adjacent blocks may be identical. The repetitive calculation can be avoided in this situation.

Feedrate scheduling for a butterfly curve

The butterfly curve as shown in Figure 6 is adopted to illustrate the feasibility of the proposed parallel approach. After the pre-processing, 29 critical points where the curvatures reach local maximum values are detected and the curve is thus splitted into 28 blocks. Meanwhile, the nominal velocity $v_{n}$ at each critical point is determined by the corresponding curvature and the kinematic constraints.^15,26

Figure 6.

Butterfly curve and its curvature: (a) butterfly curve and (b) curvature of the butterfly curve.

In the feedrate profile generation stage, the conventional bi-directional scanning technique is applied to the entire 28 blocks, and we get the feedrate profiles as shown in Figure 7. The feedrate profiles are all continuous and the velocities, accelerations, jerks and jounces (if any) all satisfy the prescribed constraints.

Figure 7.

Feedrate profile for the butterfly curve.

For brevity, only the boundary velocities of the jounce-confined profile are given in Figure 8 to illustrate the feasibility of the parallel approach. The nominal velocities $v_{n}$ are marked by “O,” and the velocities $v_{f}$ after bi-directional scanning technique are marked by “+.” The normal lines and the long bars at the bottom stand for the long blocks, while the bold lines and the short bars at the bottom stand for the short blocks. As discussed in section “Parallel feedrate scheduling approach,” the blocks are splitted into two types of scheduling units by the long-block duplet. As shown in Figure 8, there are seven scheduling units of type A and two scheduling units of type B. It can be seen that the boundary velocities of all the scheduling units keep unchanged. Thus, the proposed parallel approach for feedrate scheduling based on the bi-directional scanning is feasible.

Figure 8.

Boundary velocities before and after the bi-directional scanning.

Feedrate scheduling for a helix curve

To further illustrate the feasibility of the proposed parallel approach, a more complicated curve, a helix curve, is adopted. The curve and its curvature are depicted in Figure 9.

Figure 9.

Helix curve and its curvature: (a) helix curve and (b) curvature of the helix curve.

The curve is splitted into 65 blocks by 66 critical points. The feedrate profiles are given in Figure 10 and the boundary velocities of the jounce-confined profile before and after the bi-directional scanning are given in Figure 11. Although there are 65 blocks for the helix curve, only 11 scheduling units, that is, three of type A and eight of type B, are identified due to the lack of long-block duplets, as shown in Figure 11. The boundary velocities of all the scheduling units keep unchanged in this case, which further demonstrates the feasibility of the proposed parallel approach.

Figure 10.

Feedrate profile for the helix curve.

Figure 11.

Boundary velocities before and after the bi-directional scanning.

Efficiency of the parallel approach

Considering that the butterfly and helix examples present several scheduling units of different types and have few scheduling blocks, it is difficult to compare the efficiency between the proposed parallel and the conventional serial approaches with the butterfly and helix examples. To illustrate the efficiency of the parallel approach, a simulation example which only concerns the jounce-confined feedrate profile generation is constructed. The blocks of the constructed example consists of the same number of successive short blocks separated by the long-block duplet, as shown in Figure 12. Due to the specified composition, the scheduling blocks can be explicitly splitted into several scheduling units of type A. Thus, the efficiency of the proposed and conventional methods can be faithfully compared. The boundary velocities are assigned as zero and $v_{max}$ for the first block, as $v_{max}$ and zero for the last block and as either $v_{max} / 2$ and $v_{max}$ or $v_{max}$ and $v_{max} / 2$ for all the intermediate blocks. The boundary velocities for the intermediate blocks are assigned in such a way that the end velocity of a block is identical to the start velocity of the next block. As can be seen from Figure 5, the long-block threshold is in the interval $(9.449, 23.81) mm$ when $v_{e} = v_{max} = 100 mm / s$ and $v_{s} \in [v_{max} / 2, v_{max}]$ for the jounce-confined feedrate profile. Thus, the length of every short block is set to be $5 mm$ , while the length of every long block is set to be $25 mm$ .

Figure 12.

Constructed example to demonstrate the efficiency of the proposed approach.

Since the simulation is implemented on a personal computer with a quad-core CPU (Intel^® Core™ i5-3470 CPU, 3.20 GHz), three long-block duplets are used to split the blocks into four scheduling units of type A. Four threads (QThreads on Windows are used here. For more information, one may refer to http://wiki.qt.io/QThreads_general_usage) of which each one is responsible for a type A scheduling unit are invoked to realize the proposed parallel approach. The velocity profiles for the proposed parallel and the conventional serial approaches when the number of short blocks of one scheduling unit is 200 are given to show whether the implementation of the algorithms succeeds or not. The velocity profiles are both continuous and have exactly the same contour as illustrated in Figure 13, which implies a successful implementation of the algorithms. The time consumed for feedrate scheduling with respect to the number of short blocks of one scheduling unit is illustrated in Figure 14. The time consumed for the parallel and conventional serial approaches is obtained as the average time of 10 tests with the same simulation parameters. A near linear correlation is found between the computational time and the block number, and an acceleration ratio about 3.7 is achieved by the parallel approach. Considering only four cores are involved in this simulation, the acceleration is significant. In this sense, the proposed parallel approach can achieve a higher efficiency than the conventional methods.

Figure 13.

Velocity profiles for the constructed example when the number of short blocks is 200.

Figure 14.

Consumed time of two approaches and acceleration ratio by the parallel approach.

Conclusion

This article presents a parallel AD feedrate scheduling approach for CNC machining based on the bi-directional scanning technique. The feasibility and high efficiency of the proposed method have been validated by simulations. To our best knowledge, this is the first attempt at introducing the parallel computation in the AD feedrate scheduling. The main contributions in this work are summarized as follows:

By analyzing the properties of the feedrate-acceleration function, the concept of the long block is introduced and it is found that the feedrate profile with deceased boundary velocities for the long block is always available.

Two types of scheduling units are defined. It is demonstrated that the boundary velocities of the scheduling unit keep unchanged in the feedrate scheduling.

By splitting the tool path blocks into scheduling units, a parallel AD feedrate scheduling approach is developed, with which the feedrate of every unit is scheduled simultaneously.

Footnotes

Acknowledgements

The authors wish to express deep gratitude to the editors for their thorough work of editing our manuscript.

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 partially supported by the National Natural Science Foundation of China under Grant Nos. 51325502 and 91648202, and the Science & Technology Commission of Shanghai Municipality under Grant No. 15550722300.

References

Suh

S-H

Kang

Chung

D-H

. Theory and design of CNC systems. London: Springer.

Erkorkmaz

Altintas

High speed CNC system design. Part I: jerk limited trajectory generation and quintic spline interpolation. Int J Mach Tool Manu 2001; 41: 1323–1345.

Kröger

. On-line trajectory generation in robotic systems. Berlin, Heidelberg: Springer.

Siciliano

Sciavicco

Villani

. Robotics: modelling, planning and control. London: Springer.

Zhiming

Jincheng

Zhengjin

Performance evaluation of a real-time interpolation algorithm for NURBS curves. Int J Adv Manuf Tech 2002; 20: 270–276.

Yeh

Hsu

PL.

Adaptive-feedrate interpolation for parametric curves with a confined chord error. Comput Aided Design 2002; 34: 229–237.

Yong

Narayanaswami

A parametric interpolator with confined chord errors, acceleration and deceleration for NC machining. Comput Aided Design 2003; 35: 1249–1259.

Lin

Tsai

Yau

HT.

Development of a dynamics-based NURBS interpolator with real-time look-ahead algorithm. Int J Mach Tool Manu 2007; 47: 2246–2262.

Lee

Lin

Pan

. The feedrate scheduling of NURBS interpolator for CNC machine tools. Comput Aided Design 2011; 43: 612–628.

10.

Fan

Gao

Yan

. Interpolation of parametric CNC machining path under confined jounce. Int J Adv Manuf Tech 2012; 62: 719–739.

11.

Zhao

Zhu

Ding

A real-time look-ahead interpolation methodology with curvature-continuous B-spline transition scheme for CNC machining of short line segments. Int J Mach Tool Manu 2013; 65: 88–98.

12.

Liu

Huang

Yin

. Development and implementation of a NURBS interpolator with smooth feedrate scheduling for CNC machine tools. Int J Mach Tool Manu 2014; 87: 1–15.

13.

Yuan

Zhang

Fan

Time-optimal interpolation for CNC machining along curved tool paths with confined chord error. J Syst Sci Complex 2013; 26: 836–870.

14.

Luo

Zhou

Yin

A universal velocity profile generation approach for high-speed machining of small line segments with look-ahead. Int J Adv Manuf Tech 2007; 35: 505–518.

15.

Huang

Zhu

LM.

Feedrate scheduling for interpolation of parametric tool path using the sine series representation of jerk profile. Proc IMechE, Part B: J Engineering Manufacture 2017; 231(13): 2359–2371.

16.

Nam

Yang

MY.

A study on a generalized parametric interpolator with real-time jerk-limited acceleration. Comput Aided Design 2004; 36: 27–36.

17.

Zhao

Zhu

. Look-ahead interpolation of short line segments using B-spline curve fitting of dominant points. Proc IMechE, Part B: J Engineering Manufacture 2014; 229: 1131–1143.

18.

Qiao

Wang

Liu

. Nanoscale trajectory planning with flexible Acc/Dec and look-ahead method. Int J Adv Manuf Tech 2015; 79: 1377–1387.

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 2014; 79: 1889–1905.

20.

Bobrow

Dubowsky

Gibson

JS.

Time-optimal control of robotic manipulators along specified paths. Int J Robot Res 1985; 4: 3–17.

21.

Bharathi

Dong

Feedrate optimization and trajectory control for micro/nanopositioning systems with confined contouring accuracy. Proc IMechE, Part B: J Engineering Manufacture 2015; 229: 1193–1205.

22.

Dong

Stori

JA.

A generalized time-optimal bidirectional scan algorithm for constrained feed-rate optimization. J Dyn Syst 2006; 128: 379–390.

23.

Zhang

Yuan

C-M

Gao

X-S.

Efficient algorithm for time-optimal feedrate planning and smoothing with confined chord error and acceleration. Int J Adv Manuf Tech 2013; 66: 1685–1697.

24.

Fan

Fang

. Convex optimisation method for time-optimal feedrate planning with complex constraints. Proc IMechE, Part B: J Engineering Manufacture 2015; 229: 111–120.

25.

Zhang

Yuan

C-M

Gao

X-S

. A greedy algorithm for feedrate planning of CNC machines along curved tool paths with confined jerk. Robot Cim: Int Manuf 2012; 28: 472–483.

26.

Sun

Zhou

Guo

Variable feedrate interpolation of NURBS toolpath with geometric and kinematical constraints for five-axis CNC machining. J Syst Sci Complex 2013; 26: 757–776.

Parallel acceleration/deceleration feedrate scheduling for computer numerical control machine tools based on bi-directional scanning technique

Abstract

Keywords

Introduction

Feedrate-acceleration function

Theorem 1

Proof

Corollary 1

Long-block threshold

Theorem 2

Parallel feedrate scheduling approach

Corollary 2

Examples

Calculation of the long-block threshold

Feedrate scheduling for a butterfly curve

Feedrate scheduling for a helix curve

Efficiency of the parallel approach

Conclusion

Footnotes

Acknowledgements

Declaration of conflicting interests

Funding

References