## 4 Collision Free Path Optimization
### Collision Free Path Optimization Based on ACO  
When the ACO is applied for the welding robot path planning, the starting point of the welding torch is the nest of the ant colony and the destination is the food resource. Hence, the path planning based on the ACO is the food searching process for the ant colony. The communication between the ants is realized based on pheromones. The shortest path can be found through the mutual cooperation among the individuals. The chart of the welding robot local path planning is shown in Figure 5.  
Figure 5: Chart of welding robot collision free path optimization.  
Steps of the local welding path planning with collision-free based on ACO are given as follows:  
Step 1. Realize the environment modeling based on the grid method.  
Step 2. Initialize the parameters of the ACO. Based on the empirical value, the weight of the pheromone \(\alpha\) is set as 1, the weight of heuristic pheromone \(\beta\) is set as 11, the evaporation coefficient of pheromone \(\rho\) is set as 0.9, and the pheromone quality coefficient \(Q\) is set as 5. The iteration number \(N\) is set as 50, and the population quantity \(M\) is set as 50. Initialize the coordinates of the starting point and the terminal point. Initialize the pheromone matrix, and the pheromones for all points are set as 0.5. The above parameter settings are shown in Table 2.  
Step 3. Set iterator \(n\) as 1.  
Step 4. Set the number of ant \(k\) as 1.  
Step 5. Clear tabu list \(tabu_{k}\) for the ant \(k\), add the starting point to \(tabu_{k}\), and clear foraging path \(rout_{k}\) for ant \(k\).  
Step 6. Calculate the probability of each node according to Equation (3). In this paper, the ants' step length is set as 5 mm and the number of nodes that can be chosen as the next node is no larger than 6. The positive and negative directions of the 3D coordinate system are set as the directions of the ants' movement in this paper. Hence, the number of directions of the ants' movement is 6. When there are neighboring nodes that are obstacle points, the number of next nodes that the ant can choose is lower than 6. Select the next node according to the roulette wheel and add the node to the \(tabu\) list \(tabu_{k}\) and foraging path \(rout_{k}\).  
Step 7. If the ant reaches the destination or reaches a dead end, jump to Step 8. Otherwise, return to Step 6. A dead end means that, for the current node, there are not any nodes that can be found as the next node.  
Step 8. If the ant reaches the destination, calculate the path length \(L\) according to Equation (2). If the ant reaches a dead end, the path length \(L\) is set to infinity. Calculate the left pheromone according to Equations (4) and (5).  
Step 9. If \(k\) is less than \(M\), \(k=k+1\), and return to Step 5. Otherwise, jump to Step 10.  
Step 10. Update the pheromone matrix according to Equations (4) and (5).  
Step 11. If \(n<N\), \(n=n+1\), and return to Step 4. Otherwise, jump to Step 12.  
Step 12. Select the shortest foraging path (\(rout\)), which is the result of collision-free welding path planning.  
Set Weld Joint 3 and Weld Joint 7 as the starting point and terminal point, respectively. The result of the path planning is shown in Figure 6, and the path length is 330 mm. The iterative process of the ant colony algorithm is shown in Figure 7.  
Figure 6: Welding robot path planning between two weld joints. (**a**) View A; (**b**) View B.