## 3 Ant Colony Optimization  
ACO is a typical heuristic intelligent search algorithm. It imitates the foraging behavior of an ant colony and finds the optimal path in an unknown environment. Existing research results show that the cooperative communication between ants is based on pheromones. The concentration of pheromone is inversely proportional to the path length. While searching for food in a random environment, ants tend to move to the path with a higher pheromone concentration. As the number of ants walking on the same path increases, the pheromone concentration on the path increases and more ants are attracted to the path. This behavior shows the principle that ants use to choose the optimal path. In order to improve the efficiency of path planning, the concept of heuristic function \(\eta\) and tabu list \(tabu_{k}\) are proposed into the artificial ant colony model. In the random search algorithm, the heuristic function can improve the search efficiency. The tabu list is used to record the nodes that the ants have traveled to ensure they do not return to the previous node.  
At time \(t\), the ant \(k\) moves from current node \(i\) to an unvisited node \(j\) according to the distance information from the ending point and the pheromone intensity on the path. If there are more than one unvisited node, the ant \(k\) will determine the transition probability \(P_{ij}^{k}\) between nodes according to the following formula:  
\[P_{ij}^{k}=\left\{\begin{array}{c}\frac{[\tau_{ij}(t)]^{\bullet}[\eta_{ij}(t )^{\beta}]}{\sum_{\omega\in U}[\tau_{is}(t)]^{\bullet}[\eta_{is}(t)]^{\beta}}, j\in U\\ 0,\textit{otherwise}\end{array}\right\} \tag{2}\]  
where \(U\) is the next optional node set of ant \(k\), \(\alpha\) is the pheromone heuristic factor, \(\beta\) is the expectation heuristic factor, \(\tau_{ij}(t)\) is the pheromone concentration on the path \(ij\) at time \(t\), \(\eta_{ij}(t)\) is the expected heuristic function, defined as the reciprocal of the Euclidean distance between node \(i\) and node \(j\), and \(s\) is any node in the set \(U\). We use \(\sum_{\omega\in U}[\tau_{is}(t)]^{\bullet}\bullet[\eta_{is}(t)]^{\beta}\) to denote the sum of the product of the pheromone concentration and the heuristic function from node \(i\) to each node \(s\).  
\[\eta_{ij}(t)=\frac{1}{d_{ij}} \tag{3}\]  
where \(d_{ij}\) is the Euclidean Distance between two adjacent nodes.  
When all ants complete the path search, the pheromone will evaporate over time. At the same time, the pheromone on the path will increase. The pheromone left on each path will, thus, be updated. The update formula is as follows:  
\[\tau_{ij}(t+1)=(1-\rho)\tau_{ij}(t)+\Delta\tau_{ij} \tag{4}\]  
\[\Delta\tau_{ij}=\sum_{k=1}^{m}\Delta\tau_{ij}^{k}(t) \tag{5}\]  
where \(\rho\) is the pheromone evaporation rate, in order to avoid excessive accumulation of pheromone, \(\rho\)\(\in\)(0, 1), \(\Delta\tau_{ij}(t)\) presents the pheromone added on the path \(ij\) at time \(t\), and \(\Delta\tau_{ij}^{k}(t)\) stands for the pheromone added by ant \(k\) after passing path \(ij\) at time \(t\). This is defined as:  
\[\Delta\tau_{ij}^{k}=\left\{\begin{array}{c}\frac{Q}{L_{k}},\textit{tour}(i, j)\in\textit{tour}_{k}\\ 0,\textit{otherwise}\end{array}\right\} \tag{6}\]  
where \(Q\) is a constant representing the pheromone intensity and \(L_{k}\) is the total length of path that ant \(k\) walked through in a cycle.