## 3 Improved Adaptive Ant Colony Algorithm  
### Basic Ant Colony Optimization  
Ant colony optimization is a metaheuristic algorithm inspired by the behavior of ants in nature. It imitates the foraging behavior of ant colonies to find the optimal trajectory in an unknown environment. Two factors determine the next step of ants, which are heuristic information and pheromones. Heuristic information is obtained from the surrounding environment, and pheromones are the directional information emitted by the group. In the process of food searching, the ants release pheromones on the trajectory they walked by, which will attract other ants. As the number of ants on the same trajectory increases, pheromones are gradually accumulated, and more ants are attracted to the trajectory. According to the surrounding environment and experience, the transition probability of ants can be calculated by Equation (2).  
\[p_{i,j}^{k}(t)=\left\{\begin{array}{ll}\frac{\left[\tau_{i,j}(t)\right]^{a} \left[\tau_{i,j}^{k}(t)\right]^{\delta}}{\sum\limits_{s\in\ A_{i}}\left[\tau_{ i,j}(t)\right]^{a}\left[\tau_{i,j}^{k}(t)\right]^{\delta}},&j\in\ A_{i}\\ 0,&j\
otin\ A_{i}\end{array}\right. \tag{2}\]  
where \(p_{i,j}^{k}(t)\) is the transition probability of the \(k\)-th ant from point \(i\) to point \(j\) at the \(t\)-th iteration, \(\tau_{i,j}(t)\) is the pheromone concentration from point \(i\) to point \(j\), \(\eta_{i,j}^{k}(t)\) is the heuristic function of the \(k\)-th ant from point \(i\) to point \(j\), \(A_{i}\) is a set of feasible points adjacent to \(j\), and \(\alpha\) and \(\beta\) are weights that control the relative importance of \(\tau_{i,j}\) and \(\eta_{i,j}\). If the proportion of \(\alpha\) is larger, then ants tend to choose the trajectory that most of the previous ants have walked. If the proportion of \(\beta\) is larger, ants tend to choose the trajectory to traverse based on the heuristic information in the environment. Heuristic function and pheromone concentration directly affect the behavior of ants searching for trajectories. The heuristic function \(\eta_{i,j}^{k}(t)\) can be calculated by Equation (3), where \(d_{jg}\) is the Euclidean distance between the next node \(j\) and the end point \(g\).  
\[\eta^{k}_{i,j}(t)=\frac{1}{d_{jg}} \tag{3}\]  
When all the ants complete the trajectory search, the pheromones will accumulate on the passing trajectory. The pheromone \(\tau_{i,j}(t)\) is updated once per iteration, as shown in Equation (4).  
\[\tau_{i,j}(t+1)=(1-\rho)\tau_{i,j}(t)+\sum\limits_{k=1}^{m}\Delta\tau_{i,j}^{ k}(t) \tag{4}\]  
\[\Delta\tau_{i,j}^{k}(t)=\left\{\begin{array}{ll}Q/L_{k},&\text{if ant $k$ visits $i$ and $j$}\\ 0,&\text{otherwise}\end{array}\right. \tag{5}\]  
Figure 2: (a) The moving direction of the robot; (b) The planned trajectory limited by the height threshold.  
Here \(\Delta\tau^{k}_{i,j}(t)\) is the pheromone increment left by ant \(k\) after passing the trajectory between \(i\) and \(j\), at the \(t\)-th iteration. \(\rho\) is the pheromone volatilization factor, which adjusts the accumulation speed of the pheromone. Moreover, \(m\) is the total number of ants. Generally, \(\Delta\tau_{i,j}(0)=C\), \(C\) is the initial pheromone constant. \(Q\) is a constant, and \(L_{k}\) is the total length of the trajectory passed by ant \(k\) in this iteration, which is inversely proportional to \(\Delta\tau^{k}_{i,j}(t)\).