Abstract:To solve the problems of ant colony algorithm in complex grid environment, such as local optimization, many turning points and slow convergence, dynamic extended neighbourhoods ant colony optimization (DENACO) algorithm was proposed. Firstly, the method of dynamic extended neighborhoods was applied in the ant search mode to obtain the optimal convergence path length and reduce the number of inflection points and the number of path nodes. Meanwhile, a computational method and increment rule of pheromone were defined to reduce space costs, and the upper and lower limits of pheromone were set to avoid premature convergence of the algorithm to local optimality. Secondly, the adaptive adjustment factor and target point factor were introduced into the heuristic function, and a weight coefficient was set to improve the global search ability of the algorithm. Moreover, an iteration threshold of the algorithm was set. When the iteration exceeded the threshold, the pheromone concentration factor and heuristic factor values were updated to improve the convergence speed of the algorithm. Finally, a double optimal strategy of nodes of path was proposed. Two optimization methods were used to further optimize the planned path, and the best was taken as the final optimization result to improve the comprehensive quality of the path. Simulation experiments on raster maps of different complexities and scales showed that compared with the traditional ant colony algorithm and other comparison algorithms, the path planned by DENACO algorithm was superior. It had a shorter path length, reduced number of inflection points, accelerated convergence speed, and significantly fewer path nodes. These results indicated that the DENACO algorithm was highly feasible and applicable.