Optimization of cutting trajectory to improve manufacturing time in computer numerical control machine using ant colony algorithm

Abstract

This article presents a novel method to construct an autonomous, intelligent computer-aided design/computer-aided manufacturing programming system for the cutting device controller (e.g. a computer numerical control laser cutting machine tool) based on ant colony algorithm. The computer numerical control cutting device should be able to optimize trajectory autonomously between cutting objects. In order to find the best sequence of operations that achieves the shortest trajectory, ant colony is proposed. The shortest cutting trajectory can be formulated as a special case of traveling salesman problem. The integration of ant colony algorithm and traveling salesman problem can be included in commercial computer-aided design/computer-aided manufacturing packages to optimize the cutting trajectory.

Introduction

Computer-aided design (CAD)/computer-aided manufacturing (CAM) software has this ability to improve the efficiency of machine tools in the case of numerical control (NC) programming. Nowadays, automatic NC programming can be covered by several CAD/CAM software packages, which have been applied to different cutting processes. Both manual programming and automatic programming by CAD/CAM packages do not use optimum techniques for shortest trajectory. In this case, it may take a long time to complete the machining operation. To cut objects that are placed within a plate using computer numerical control (CNC) machining, it is required to determine a path for cutting tool. The total time of cutting process depends on this path. This time consists of travel time, which is the time that CNC machine cutting tool moves between objects, and cutting time, which is the time that cutting tool spends to cut the object in material.

The minimum cutting tool traveling time will result in maximum production efficiency. A review on related works shows that most of the researches have been done and focused on minimization of cutting time,^1–5 while it is much more important that cutting device would be able to optimize trajectory between cutting objects autonomously. However, there are some other researches that have studied the traveling time using various methods.^6–9 By minimizing cutting trajectory between objects, the travel time will be minimized correspondingly.

It is possible to formulate cutting trajectory as a special case of traveling salesman problem (TSP). TSP is one of the combinatorial optimization problems that have been studied widely in several literature.^10–12 In TSP, a salesman seeking the shortest tour among N cities must visit each city once and finally return back to the starting city. This problem apparently seems simple, but actually it is still one of the most challenging problems in operational research. The solution for this problem can be listing each possible tour and finally finding the shortest one. In this case, where N is the number of cities, the number of possible tours will be N!. So, when N is large, it becomes so difficult and maybe impossible to find the shortest tours among large number of answers in polynomial time. So, it is one of the nondeterministic polynomial (NP)-complete problems. ¹³

Some researchers use linear optimization to solve this problem, ¹⁴ while as an optimal solution to this problem, heuristic algorithms often give a better solution that is slightly different from the optimal solution and relatively running on shorter times. Several heuristic algorithms have been applied to solve TSP, such as tabu search, ¹⁵ neural networks, ¹⁶ cuckoo search, ¹⁷ genetic algorithm, ¹⁸ simulated annealing, ¹⁹ particle swarm optimization, ²⁰ ant colony optimization (ACO) algorithm^21,22 or a combination of different heuristic algorithms. ²³

This work is structured as follows: in the next section, we present the problem description. The ant colony algorithm (our solution for solving problem) is in section “Ant colony algorithm,” after that we show experimental results and advantages of our idea. Finally, we draw conclusions and identify possible improvements to be investigated in the future.

Problem description and formulation

In order to find shortest trajectory for CNC cutting machine when a set of objects are placed in unsymmetrical locations, we propose ant colony algorithm. Ant colony can effectively find the sequence of cutting operations with shortest trajectory. The integration of ant colony algorithm and TSP can optimize the cutting trajectory. In this article, we will restrict our attention to TSPs in which cities (cutting objects) are situated on a plane and a path exists between each pair of cities (cutting objects) (i.e. the TSP graph is completely connected). Finding the shortest trajectory can be formulated as a special case of TSP. Cities in this problem are represented by nodes on the boundary of the objects and the salesman is exactly the cutting tool. The distance between cities is given by Manhattan distance because in most of the CNC machines, the top of cutting tool is located by two servo motors, one that moves horizontally and the other that moves vertically.

The goal is to seek the shortest length tour which each node exactly has been visited once. This case has one main difference with TSP, that is, in TSP the salesman is coming back to the starting city, while in our problem, the tool completes its tour when it reaches the last cutting object. In order to formulate this problem as TSP, we have defined many nodes (cities) on boundary of each cutting object (Figure 1). In this model, when the current node is on the boundary of the cutting object, the next node is not allowed to be on the same cutting object, it means we enforce the next selected node to be on the boundary of different cutting object.

Figure 1.

Cutting objects and their boundary nodes.

Ant colony algorithm

ACO algorithm is a subdivision of a larger area referred to as swarm intelligence. Swarm intelligence is the modeling and simulation of social insects’ behavior such as bees, ants and so on. System optimization and self-organization learning are two of many reasons why researchers are attracted in simulating the behavior of insects. ²⁴ ACO simulates the cooperative foraging behaviors of ants while ants go out finding food and bring their food back to the nest. Generally, ants do not have a good vision or communication system and an individual ant could not live much longer. However, a group or a swarm of ants can cooperatively perform complex tasks such as collecting food or doing division of labor.

The main reason that makes such a group effective is pheromone, a chemical substance left by ants as they move. This substance provides the communication ability for ants. Basically, ants move randomly, but when they meet a pheromone trail, they decide whether to follow it or not. They prefer to follow it and leave their own pheromone on the trail that reinforces the path. The quantity of pheromone on the potential path of interest adjusts the probability which an ant selects one path over the other. So, paths that are more regularly traveled by some ants become more attractive for other ants, and consequently, those paths that they are less traveled become less expected for ants.

As time passes, pheromone on a path evaporates. First, ant will use all probable paths, depositing pheromone as they move. But those ants choosing the shorter path will return to the nest and bring food first. The shorter path has more pheromone because it is fresh and has not yet evaporated, so ants will be more attracted to this path. The dynamics of above descriptions is shown in Figure 2, which shows a group of ants over several pathways between nest and food source in different time steps. In initial state, the ants are randomly distributed, but finally they choose the shortest path.

Figure 2.

Dynamics of pheromone trial—finally ants choose the shortest path.

However, there is always a probability that an ant will not choose a reinforced pheromone trail. This probability (even a small value) permits to search the other paths, which is useful in that it permits for finding a shorter or new source of food.

The above description for behavior of ants in finding food has a strong relationship with the TSP. This problem in Birattari et al. ²¹ has been formulated by ACO. In this algorithm, ant “k” in city “r” selects the city “s” to travel among those that are not in its working memory M_k (list of cities that ant “k” has traveled) with the following probabilistic formula

$$s=\{\begin{array}{cc}\hfill \arg max\{[\tau (r,u)]·{[\eta (r,u)]}^{\beta }\}\hfill & \hfill \text{if}q\le q_0\hfill \\ \multicolumn{1}{c}{S}& \hfill \text{otherwise}\hfill \end{array}$$

(1)

where τ(r,u) is the pheromone intensity between two nodes(city) r and u; η(r,u) is a problem-specific value referred by some authors, which here is selected to be the inverse of the distance between cities r and u; β is a parameter that evaluates the relative importance of pheromone intensity and proximity; q is a random value with constant probability in [0,1], q₀ (0 ≤q₀≤ 1) is a parameter and S is a variable chosen randomly based on the following probability function (2), which considers trials that are shorter and have more amount of pheromone trail

$$p_k(r,s)=\{\begin{array}{cc}\hfill \frac{[\tau (r,s)]·{[\eta (r,s)]}^{\beta }}{{\sum _{u\ne M_k}[\tau (r,u)]·[\eta (r,u)]}^{\beta }}\hfill & \hfill \text{if}s\notin M_k\hfill \\ \multicolumn{1}{c}{0}& \hfill \text{otherwise}\hfill \end{array}$$

(2)

where p_k(r,s) is the probability that ant k selects the path to move from city “r” to “s.”

Pheromone intensity is changed locally and globally. In global trial updating, only best-so-far tour evaporates and deposits pheromone (exploitation), while in local updating, after an edge is passed, a small amount of pheromone is evaporated immediately from the edge (exploration).

The updating rules consist of two terms: the first is the evaporation of the existing pheromone (local updating) and the second is the amount of added pheromone on the trail (global updating). These rules are shown in equations (3) and (4)

$$\tau (r,s)\leftarrow (1-\lambda )·\tau (r,s)+\lambda ·{\tau }_0$$

(3)

where τ₀ is a parameter. Local updating is also inspired by trail evaporation in real ants

$$\phi (r,s)\leftarrow (1-\rho )·\phi (r,s)+\rho ·\Delta \phi (r,s)$$

(4)

where Δφ(r,s) equals the inverse value of shortest tour and ρ is a parameter (0 < ρ < 1). Global updating is comparable to a reinforcement learning scheme in which better results and solutions achieve higher reinforcement.

Experimental results

In this section, we will study the case that includes 12 objects that are nested in a plat. We set parameters of ant colony system algorithm as follows

$$\beta =2,\lambda =0.1,\rho =0.9,q_0=0.9$$

The number of iterations to be run was 50. The average computation time per run was 300 s on an Intel^® Core™ 2 Duo, 1.66 GHz, 1 GB RAM, using MATLAB 2008a as the programming software.

Figure 3 shows an optimal solution, that is, an optimal cutting trajectory strategy. The polyline shows a cutting trajectory; a regular cutting trajectory strategy length is 2627 units (Figure 4), and in this cutting trajectory strategy, start points are default start points and cutting sequence is based on horizontal movement of cutting tool. The optimal cutting strategy length using our algorithm is only 1321, making the difference of 50.28%. Figure 5 shows change in the length of cutting trajectory by growing iteration in ant colony algorithm.

Figure 3.

Optimal cutting trajectory.

Figure 4.

Default selected trajectory.

Figure 5.

Length of best trajectory—iteration.

Conclusion

Using ant colony method for optimizing, the cutting trajectory has been illustrated. Ant colony offers a new method for generating an optimal cutting trajectory. The proposed method is a contribution to the intelligent manufacturing systems, and its preliminary results are optimistic. In future, we will find shortest trajectory for objects that have two or more starting points.