基于进化蚁群算法的移动机器人路径优化

Path optimization for mobile robot based on evolutionary ant colony algorithm

针对蚁群算法进行路径规划中出现的运行时间长、搜索效率低和容易出现死锁的问题,提出一种基于达尔文进化论思想的蚁群算法.首先,针对空白栅格搜索效率低的问题,提出一种蚁群算法简易模式;然后在启发函数中引入目标影响因子和障碍物影响因子以提高算法的全局搜索能力,避免陷入死锁;最后利用达尔文的进化论改进蚁群算法的信息素更新规则用于加快算法的迭代速度,缩小运行时间.在不同规模的栅格地图环境下的实验表明,所提出的进化蚁群算法能够加快迭代速度,提高搜索效率,实现最优路径并避免算法死锁问题.

In order to solve the problems of long running time, low searching efficiency and frequent deadlock in the path planning of ant colony algorithms, this paper proposes an ant colony algorithm based on the Darwin’s theory of evolution. Firstly, a simple mode of the ant colony algorithm is proposed to solve the problem of blind search in blank grids. Then, in order to improve the global search ability and avoid falling into deadlock, the target influence factor and obstacle influence factor are introduced into the heuristic function. Finally, the pheromone updating rules of ant colony algorithm are improved using the Darwin’s theory of evolution to accelerate the iteration speed and shorten the running time of the algorithm. Experiments on raster maps of different scales show that the evolutionary ant colony algorithm proposed in this paper can speed up the iteration speed, improve the search efficiency, achieve the optimal path and avoid the deadlock.