基于动态扩展邻域蚁群算法的移动机器人路径规划

针对蚁群算法易陷入局部最优、路径转折点多、收敛速度慢的问题，提出一种基于动态扩展邻域蚁群算法（Dynamic extended neighbourhoods ant colony optimization，DENACO）。在蚂蚁搜索方式上采用动态扩展邻域方法，并定义新的信息素计算方式和增量规则，在取得更优收敛路径长度的同时，减少路径转折点数量及路径节点数量；引入自适应调整因子改进启发函数，提高算法的全局搜索能力，并设定迭代阈值，提升算法的收敛速度；提出一种路径节点双优化策略，对规划好的路径进一步优化，提高路径综合质量。不同复杂度及不同规模栅格地图中的仿真实验表明，DENACO算法所规划的路径更优，路径转折点数量减少，收敛速度加快，路径节点数量明显减少，表明算法具有更高的可行性和适用性。

Path Planning of Mobile Robots Based on Dynamic Extended Neighbourhoods Ant Colony Algorithm

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.