The Higher Education and Research forge

Home My Page Projects Code Snippets Project Openings Complex Surface Machining Optimization
Summary Activity SCM

SCM Repository

authorMahfoud Herraz <mahfoud@debian>
Tue, 31 Mar 2020 09:53:19 +0000 (11:53 +0200)
committerMahfoud Herraz <mahfoud@debian>
Tue, 31 Mar 2020 09:53:19 +0000 (11:53 +0200)
Publis/ICME2020/biblio.bib
Publis/ICME2020/main.tex

index 037651c..7be3448 100644 (file)
     doi = {10.1177/0954405416640175}
 }
 
+@article{xu_rival_1993,
+       title = {Rival penalized competitive learning for clustering analysis, {RBF} net, and curve detection},
+       volume = {4},
+       issn = {1045-9227},
+       doi = {10.1109/72.238318},
+       abstract = {It is shown that frequency sensitive competitive learning (FSCL), one version of the recently improved competitive learning (CL) algorithms, significantly deteriorates in performance when the number of units is inappropriately selected. An algorithm called rival penalized competitive learning (RPCL) is proposed. In this algorithm, not only is the winner unit modified to adapt to the input for each input, but its rival (the 2nd winner) is delearned by a smaller learning rate. RPCL can be regarded as an unsupervised extension of Kohonen's supervised LVQ2. RPCL has the ability to automatically allocate an appropriate number of units for an input data set. The experimental results show that RPCL outperforms FSCL when used for unsupervised classification, for training a radial basis function (RBF) network, and for curve detection in digital images.{\textless}{\textgreater}},
+       number = {4},
+       journal = {IEEE Transactions on Neural Networks},
+       author = {Xu, L. and Krzyzak, A. and Oja, E.},
+       month = jul,
+       year = {1993},
+       keywords = {unsupervised learning, Algorithm design and analysis, Clustering algorithms, clustering analysis, competitive learning, curve detection, Data analysis, digital images, Digital images, Image coding, image recognition, Kohonen's supervised LVQ2, neural nets, Pattern analysis, Pattern recognition, Power capacitors, radial basis function network, rival penalized competitive learning, Signal processing algorithms, Subspace constraints, unsupervised classification},
+       pages = {636--649},
+       file = {IEEE Xplore Abstract Record:/home/mahfoud/Zotero/storage/YIGBAGFN/238318.html:text/html;IEEE Xplore Full Text PDF:/home/mahfoud/Zotero/storage/JUMJE8K2/Xu et al. - 1993 - Rival penalized competitive learning for clusterin.pdf:application/pdf}
+}
+
+@article{szekely_hierarchical_2005,
+       title = {Hierarchical {Clustering} via {Joint} {Between}-{Within} {Distances}: {Extending} {Ward}'s {Minimum} {Variance} {Method}},
+       volume = {22},
+       issn = {1432-1343},
+       shorttitle = {Hierarchical {Clustering} via {Joint} {Between}-{Within} {Distances}},
+       url = {https://doi.org/10.1007/s00357-005-0012-9},
+       doi = {10.1007/s00357-005-0012-9},
+       language = {en},
+       number = {2},
+       urldate = {2019-06-11},
+       journal = {Journal of Classification},
+       author = {Szekely, Gabor J. and Rizzo, Maria L.},
+       month = sep,
+       year = {2005},
+       keywords = {Hierarchical Cluster, Minimum Variance, Pattern Recognition, Statistical Theory},
+       pages = {151--183},
+       file = {Szekely et Rizzo - 2005 - Hierarchical Clustering via Joint Between-Within D.pdf:/home/mahfoud/Zotero/storage/VL2FRAEF/Szekely et Rizzo - 2005 - Hierarchical Clustering via Joint Between-Within D.pdf:application/pdf}
+}
+
index 57e711e..18c0653 100644 (file)
@@ -180,12 +180,12 @@ The figure \ref{fig:choi3} shows an example of surface partitioning obtained on
  \centering
  \includegraphics[width=\columnwidth]{choi200x200.png}
  % choi200x200.png: 1517x885 px, 300dpi, 12.84x7.49 cm, bb=0 0 364 212
- \caption{Example of surface partitioning}
+ \caption{Example of a surface partitioned into $K=3$ zones}
  \label{fig:choi3}
 \end{figure}
 
-\subsection{Dividing the disconnected zones}
-Carrying out the {\em K-Means} algorithm is fast, even with fine tessellation meshes (for example the partitioning scheme presented in figure \ref{fig:choi3} needs only 684~ms for being fully computed). But sometimes this procedure provides disconnected zones, like in the case depicted by figure \ref{fig:ccs}. In this case, the green zone is disconnected. This zone must be split apart into two zones to prevent the toolpath planning algorithm trying to mill it in a single run without lifting the cutter, which may cause severe damages to the surface and lead to unexpected result.
+\subsection{Dividing disconnected zones}
+Carrying out the {\em K-means} algorithm is fast, even for fine tessellation meshes (for example the partitioning scheme presented in Figure \ref{fig:choi3} is fully computed within only 684~ms) . However, it may happen that the above procedure provides disconnected zones, like in the case depicted by Figure \ref{fig:ccs}, where the green zone is disconnected. This green zone must then be further partitioned split apart into two zones to prevent the toolpath planning algorithm to mill it in a single run without lifting the cutter, which may cause severe damages to the surface, and lead to unexpected result.
 
 \begin{figure}[ht]
  \centering
@@ -195,7 +195,7 @@ Carrying out the {\em K-Means} algorithm is fast, even with fine tessellation me
  \label{fig:ccs}
 \end{figure}
 
-Therefore, a connectivity check procedure should be performed to ensure that the zones provided by the algorithm are unsegmented. To do so, a connected component search algorithm is applied on the result provided by the {\em K-Means} partitioning procedure. Finding connected components is a well-known polynomial problem in graph theory (for an undirected graph), but to be able to use it with a partitioning scheme, the graph corresponding to this partitioning scheme must be defined first. This definition is a two steps procedure: First each sample point is defined as a vertex of the graph. Then sample points are analysed by pairs: two sample points belonging to the same cluster are connected together with an edge if and only if they are issued from side by side elementary meshes. Once the graph corresponding to the partitioning scheme is defined, the  connected component search is performed using the software package  JGraphT \cite{jgrapht}. At the end of this search, if a zone appears to be disconnected, this zone is simply divided into several disconnected zones. The time needed to perform this task is heavily dependant on the number of sample points, but even if it is a bit longer than {\em K-Means} procedure itself, it's still short enough to be used interactively. For example, the connected component search on the partitioning scheme presented in figure \ref{fig:ccs} took 14914~ms. As expected, for this particular partitioning scheme, this procedure results in four different zones (figure \ref{fig:ccsDone}).
+We therefore propose a connectivity-check procedure to ensure that the provided zones are connected. The connected-component search algorithm is applied on the results of {\em K-means} algorithm. Finding connected components is a well-known polynomial problem in graph theory, but to be able to use it with a partitioning scheme, an undirected graph corresponding to this partitioning scheme must first be defined. Each sample point corresponds to a vertex of the graph. Any two sample points belonging to a same cluster are connected with an edge if and only if they come from side-by-side elementary meshes. Once the graph corresponding to the partitioning scheme is defined, the  connected component search is performed using the software package  JGraphT \cite{jgrapht}. As a result, any disconected zone is simply sub-divided into several connected zones. The time needed to perform this task is heavily dependant on the number of sample points. However, even if it is a bit longer than the {\em K-means} procedure itself, it is still short enough to be used interactively. For example, the connected-component search on the surface presented in Figure \ref{fig:ccs} requiered less than 15~s. As expected, for this particular case, this procedure results in four different zones displayed on Figure \ref{fig:ccsDone}.
 
 \begin{figure}[ht]
  \centering
@@ -205,10 +205,8 @@ Therefore, a connectivity check procedure should be performed to ensure that the
  \label{fig:ccsDone}
 \end{figure}
 
-Using a clustering algorithm like {\em K-Means} is thus a fast and efficient choice to deal with the zones partitioning issue. 
-
 \section{Optimizing machining direction within each zone}
-Once the zone partitioning scheme defined, the optimal milling process for machining such zones still needs to be determined. For a given zone $z$, let's call $\mathbf{X}$ the vector of the numerous variables that can have an impact on machining time and $\mathbf{P_i(\mathbf{X})}$, the $i^{th}$ point of the toolpath ($i=1..n(\mathbf{X})$). For each zone, the optimization problem can then be expressed as:
+Once the zone partitioning-scheme defined, the optimal milling process for machining th resulting zones  needs to be determined. For a given zone $z$, let's call $\mathbf{X}$ the vector of the numerous variables that can have an impact on machining time and $\mathbf{P_i(\mathbf{X})}$, the $i^{th}$ point of the toolpath ($i=1..n(\mathbf{X})$). For each zone, the optimization problem can then be expressed as:
 \begin{equation}\label{eq:optProbGlobal}
 \begin{aligned}
   \min_{\mathbf{X}} \quad & machining\_time(\mathbf{X}) \\
@@ -217,23 +215,23 @@ Once the zone partitioning scheme defined, the optimal milling process for machi
 \end{equation}
 where
 \begin{itemize}
-    \item $sh_i(\mathbf{X})$ the scallop height at the vicinity of the point $\mathbf{P_i}(\mathbf{X})$
-    \item $sh_{max}$ the maximum scallop height allowed for this surface.
+    \item $sh_i(\mathbf{X})$ is the scallop height at the vicinity of the point $\mathbf{P_i}(\mathbf{X})$
+    \item $sh_{max}$ is the maximum scallop height allowed for this surface.
 \end{itemize}
 
-From an optimization point of view, this is a fairly difficult problem as it is complicated to characterize the entire search space. Moreover, even for a given path, the machining time cannot be calculated analytically. Actually, it is the result of a computer summation algorithm. Therefore, the machining time has to be considered as a black-box objective function. Indeed, it's not so easy to model this black-box objective function, because a lot of variables are involved and so are the number of constraints. In a first approach, some choices can be made to make it simpler. First of all, only the 3-axis machines are taken into account. Second a given toolpath generation strategy is chosen: the strategy of {\em zig-zag} parallel planes. This strategy is widely used in the industry as it ensures that the entire surface is covered and it is easy to implement. Using this strategy, the paths are defined as the intersection of part surface and vertical parallel planes. The distance between two adjacent planes (called step-over distance $sod$)  is defined as the maximum distance such as the scallop height constraint $sh$ is respected for the whole path. In addition, this choice facilitates the management of the quality criterion. Indeed, from a given path, the position of the adjacent plane is quite easy to determine: defining it from the worst point of the previous path is sufficient. This is enough to ensure that the quality criterion will be satisfied for the entire trajectory. From the optimization point of view, this strategy is very useful because the constraints are moved silently into the objective function. Using a fast scallop height calculation method \cite{redonnet_study_2013}, the toolpath planning process is rapid enough to be used as the objective function of an optimization procedure. 
+From an optimization point of view, this is a fairly difficult problem as it is complicated to characterize the entire search space. Moreover, even for a given path, the machining time cannot be calculated analytically. Actually, it is the result of a computer summation. Therefore, the machining time has to be considered as a \textit{black-box} objective function involving numerous variables and constraints. In a preliminary approach, some choices can be made to simplify it. First of all, we restrict our study to 3-axis machines. Second a given toolpath generation strategy is chosen: the strategy of {\em zig-zag} parallel planes. This strategy is widely used in the industry as it ensures that the entire surface is covered and it is easy to implement. The paths are thereby defined as the intersection of part surface and parallel vertical planes. The distance between two adjacent planes (called step-over distance, noted $sod$)  is defined as the maximum distance such as the scallop-height constraint \ref{eq:optProbGlobal} is respected for the whole path. This choice facilitates the management of the quality criterion. Indeed, from a given path, the position of the adjacent plane is  easy to determine: it suffices to consider the worst point, in terms of sallop-height, of the previous path. This is enough to ensure that the quality criterion will be satisfied for the entire trajectory. From the optimization point of view, this strategy is very useful because the constraints are thereby satisfied by construction. Using a fast scallop height calculation method \cite{redonnet_study_2013}, the above-dscribed toolpath planning process is rapid enough to be used as the objective function of an optimization procedure. 
 
-Finally, with this strategy the only parameter that left to be defined is, for each zone, the direction of the parallel planes used to run the machining strategy. For the zone $k$, the problem may be summarized as:
+The only parameter that remains to be defined is, for each zone, the direction of the parallel planes used to run the machining strategy. For the zone $Z_k$, the problem may be summarized as:
 \begin{equation}\label{eq:optProbSimple}
   \min_{\Theta_k} \quad machining\_time(\Theta_k)
 \end{equation}
-where $\Theta_k$ is the angle defining the machining direction of zone $k$ with reference to $\mathbf{X}$ axis.
+where $\Theta_k$ is the angle defining the machining direction of zone $Z_k$ with reference to the $\mathbf{X}$ axis.
 
-This problem is thus reduced to a single variable, but the objective function is still a black–box function, {\em i.e.} its analytic form is not known. Therefore, its calculation needs a full toolpath planning and may be time expensive, especially if running  the whole procedure within a time suitable for interactive usage is the aim. Actually it can be solved using a simple optimization algorithm, like the Nelder-Mead algorithm used in \cite{redonnet_optim_2018} to solve it over the entire surface. But given the previous considerations on the computation time, in the present study, a more efficient blackbox optimization approach was chosen. An extensive review of blackbox optimization methods can be found in \cite{AuHa2017a}. Practically,  the software package used to perform optimization is {\em NOMAD} \cite{Nomad, AuLeTr09a} which uses algorithms described in \cite{Le2011a, AuDe2006}. Using this package makes the resolution more flexible, and suitable for parallel computing.
+This is a univariate (one-dimensional) optimization problem whose objective function is, again,  a blackbox. Therefore, the optimization process may be time expensive, especially if running  the whole procedure within a time suitable for interactive usage is the aim. Actually it can be solved using a simple optimization algorithm, like the Nelder-Mead algorithm used in \cite{redonnet_optim_2018} to solve it over the entire surface. However, given the previous considerations on the computation time, in the present study, a more efficient blackbox optimization approach is chosen. An extensive review of blackbox optimization methods can be found in \cite{AuHa2017a}. The software package used in this study to perform optimization is {\em NOMAD} \cite{Nomad, AuLeTr09a} which uses algorithms described in \cite{Le2011a, AuDe2006}. Using this package makes the resolution more flexible, and suitable for parallel computing.
 
-In order to run the optimization procedure an initial guess of the angle $\Theta_k$ is useful. For this, the $\theta$ value of the corresponding centroid have been chosen. It more or less represents the overall steepest slope direction in the zone. As this direction is the most effective when using a toroidal cutter, it should be close to the optimal direction.
+In order to run the optimization procedure an initial guess of the angle $\Theta_k$ is advised. For this, we choose the $\theta$ value corresponding to centroid of zone $Z_k$ as it may be interpreted as the overall steepest-slope direction in the zone. As this direction is the most effective when using a toroidal cutter, it should be close to the optimal direction.
 
-Applying this optimization procedure on the surface used in \cite{keun_choi_tool_2007} (figure \ref{fig:choi3}) provides the toolpath planning depicted in figure \ref{fig:choiToolpath}.
+Applying this optimization procedure on the surface studied in \cite{keun_choi_tool_2007} (see also Figure \ref{fig:choi3}) provides the toolpath planning depicted in figure \ref{fig:choiToolpath}.
 \begin{figure}[ht]
  \centering
  \includegraphics[width=\columnwidth]{choi_toolpath.png}
@@ -241,20 +239,17 @@ Applying this optimization procedure on the surface used in \cite{keun_choi_tool
  \caption{Example of toolpath optimization}\label{fig:choiToolpath}
 \end{figure}
 
-To carry out the parallel planes strategy, a cutter of outer radius 5~mm and torus radius 2~mm have been used, and the maximum scallop height have been set to 0.01~mm, which is a value commonly used in industry.
+To carry out the parallel-plane strategy, a cutter of outer radius 5~mm and torus radius 2~mm have been used, and the maximum scallop height have been set to 0.01~mm, a value commonly used in industry.
 
-Using the optimised toolpath, the two symmetric zones need about 36~s to be machined while the front zone needs about 28~s. Thus the total machining time is about 100~s. This value should be considered taking into account the bulk of the part which is about $50\times75$~mm on the $(\mathbf{X},\mathbf{Y})$ plane.
+Using the optimized toolpath, the two symmetric zones of Figure \ref{fig:choiToolpath} need about 36~s to be machined, while the front zone requires about 28~s. Thus, the total machining time is around 100~s. This value should be considered taking into account the fact that the bulk of the part is about $50\times75$~mm.% on the $(\mathbf{X},\mathbf{Y})$ plane.
 
 \section{Discussion}
-This section deals with some points that worth to be noted.
-
-Some others clustering algorithms have been tested, such as the {\em Hierarchical clustering} algorithm or the {\em Rival penalized competitive learning} algorithm. But at this point, the {\em K-Means} algorithm is the one giving the best results.
 
-The choice of the metric used in clustering algorithm has a deep impact on the results. The features vector components and the metric, both worth a deep study.
+Some other clustering algorithms have been tested, such as the {\em Hierarchical clustering} algorithm \cite{szekely_hierarchical_2005} or the {\em Rival penalized competitive learning} algorithm \cite{xu_rival_1993}. However, they are more sensitive to algorithm parameters such as learning coefficient and mesh size. The metric choice has a deep impact on the results, and deserves thereby attention in a deeper study.
 
-The optimization process duration is heavily dependant on the implementation parameters chosen. It could last from few seconds to several minutes, depending on whether the surrogate model is used or not, the stopping criteria chosen, the meshing size and so on. More work needs to be done to find out the best compromise between duration of the calculation and precision of the result.
+The optimization process duration is heavily dependant on the implementation parameters chosen. It could last from few seconds to several minutes, depending on whether the surrogate model is used or not, the stopping criteria chosen, the meshing size and so on. More work needs to be done to find out a good trade-off between CPU time and precision of the results.
 
-Toolpath planning for milling of free-form surfaces is a field of research where very few authors release enough data to make relevant comparisons between methods. Nevertheless, a comparison may be done between the method presented in the present paper and the one presented by Y.K. Choi and A. Banerjee in \cite{keun_choi_tool_2007} because numerical result values are published in their paper. However, this comparison should be considered cautiously because the cutter used in their paper is a ball-end cutter. It also worth to be noted that measurement units used in their paper are inches, thus conversion to millimeters gives unusual values. Cutter radius used in~\cite{keun_choi_tool_2007} is $0.125~\mathrm{in} = 3.175~\mathrm{mm}$, thus a toroidal cutter with same outer radius have be chosen to carry out the comparison. The torus radius was set to $0.05~\mathrm{in} = 1.27~\mathrm{mm}$. Choi \& Banerjee present two experimental simulations: one with a maximum scallop height ($sh_{max}$) equals to $0.01~\mathrm{in} = 0.254~\mathrm{mm}$ and the other using $sh_{max} = 0.05~\mathrm{in} = 1.27~\mathrm{mm}$. Besides, the machining time is not precised in \cite{keun_choi_tool_2007}, thus only total toolpath lengths are compared. The resulting values are summarized in table \ref{tab:cmp}.
+Toolpath planning for milling of free-form surfaces is a field of research where very few authors release enough data to allow relevant comparisons between methods. Nevertheless, a comparison can be conducted between the method introduced in this paper and the one proposed by Y.K. Choi and A. Banerjee in \cite{keun_choi_tool_2007} because numerical result values are published in their paper. However, this comparison should be considered with caution because the cutter used in their paper is a ball-end cutter. remark also that the measurement units in their paper are inches, thus conversion to millimeters gives unusual values. the cutter radius used in~\cite{keun_choi_tool_2007} is $0.125~\mathrm{in} = 3.175~\mathrm{mm}$; thus we choose a toroidal cutter with same outer radius to carry out the comparison. The torus radius was set to $0.05~\mathrm{in} = 1.27~\mathrm{mm}$. Choi \& Banerjee present two experimental simulations: one with a maximum scallop height $sh_{max}=0.01~\mathrm{in} = 0.254~\mathrm{mm}$, and the other using $sh_{max} = 0.05~\mathrm{in} = 1.27~\mathrm{mm}$. Besides, the machining time is not precised in \cite{keun_choi_tool_2007}, we only compare total toolpath lengths. The resulting values are summarized in table \ref{tab:cmp}.
 
 \begin{table}[ht]
 \centering
@@ -268,18 +263,18 @@ Toolpath planning for milling of free-form surfaces is a field of research where
 \end{tabular}\\
 \vspace{1pt}
 \raggedleft
-\begin{footnotesize}unit: millimeters\end{footnotesize}
+\begin{footnotesize}units: millimeters\end{footnotesize}
 \caption{Comparison results with Choi \& Banerjee method}\label{tab:cmp}
 \end{table} 
 
-Computation time is not specified in \cite{keun_choi_tool_2007}, but for information, running the full method proposed in the present paper (clustering and optimization) takes less than 1 min.
+Computation time is not specified in \cite{keun_choi_tool_2007}, but simply to give a rough idea, running the full method proposed in the present paper (clustering and optimization) takes less than 1 min.
 
-These results show a significant improvement of performances using the clustering/blackbox optimization method. But once again, they should be taken cautiously because the surface is quite small and the maximum scallop heights values are quite high. It would be interesting to be able to compare both methods on parts more representative of industrial ones, using parameters commonly used in industry.
+These results show a significant improvement of performances using the proposed clustering/blackbox optimization method. But once again, they should be considered with caution because the surface is rather small and the maximum scallop height values are relatively high. It would be interesting to be able to compare both methods on parts that are more representative of industrial practice, and using parameters commonly used in industry.
 
 \section{Conclusion}
-In the context of machining freeform surfaces, the toolpath optimization problem is rather complicated. The two-step approach presented in this paper provides the optimal solution, given the restricting choices made. First, a {\em K-Means} algorithm is carried out to define machining zones. A zone segmentation verification is done, and then, for each zone, a blackbox optimization procedure is carried out to define the optimal machining direction for the considered zone.
+In the context of machining freeform surfaces, the toolpath optimization problem is rather complicated. The two-step approach presented in this paper provides the optimal solution, given the restricting choices made. First, a {\em K-Means} algorithm is carried out to define machining zones. A zone segmentation verification is done, and then, for each zone, a blackbox optimization procedure is carried out to define an optimal machining direction.
 
-This work is a first attempt to address the toolpath planning optimization problem using a clustering/blackbox optimization approach. Further work may include improvements of both the clustering step and the optimization step. In regard to this last point, the choice of a blackbox optimization software may be very helpful to integrate step by step new degrees of complexity into the optimisation model.
+This work is a first attempt to address the toolpath planning optimization problem using a clustering/blackbox optimization approach. Further work may include improvements of both the clustering step and the optimization step. In regard to this later point, the choice of a blackbox optimization software may be very helpful to integrate step by step new degrees of complexity into the optimisation model.
 
 \bibliography{biblio}