改进蚁群算法在机器人路径规划上的应用研究

发布时间：2018-03-26 00:08

本文选题：移动机器人　切入点：路径规划　出处：《安徽大学》2017年硕士论文

【摘要】：随着人工智能技术在当今社会的逐步发展与进步,其在生活与生产中的运用愈加广泛,也吸引了更多的研究者投入其中,人工智能已然成为可当今社会炙手可热的研究热点。人工智能的研究分支众多,其中智能机器人的研究随着技术的不断进步受到了越来越多的关注。为了提高机器人完成任务的效率,我们希望机器人能够拥有自主安全寻路的功能。通常,路径规划的目标不仅限于寻找起点与终点之间的可行路径,还要在众多可行的道路中,规划出一条路程短,耗时短且安全性高的路径,以此来提高工作的效率。近年来,在路径规划的问题上,国内外专家学者给出了各自的问题解决方案,并在各自的问题模型中得出了有效的结果,其中包括遗传算法、粒子群算法、人工免疫算法、神经网络法、人工势场法等。在众多的应用算法中,蚁群算法自提出以来,就受到了广泛的关注。本文主要描述了在移动机器人路径规划这一研究课题下,基于蚁群算法展开的分析研究以及改进优化。论文的主要工作如下:1.文中系统地探讨了蚁群算法的思想和实现步骤,从经典蚁群算法的理念谈起,分析了在路径规划问题中蚁群算法表现出的优缺点。蚁群算法应用仿生的手段,根据蚂蚁在觅食过程中的寻路行为,通过给以后代正反馈信息,逐步收敛得出全局最优路径,有着鲁棒性强等优点。但同时也有搜索时间较长,容易陷入局部收敛的问题。2.文中列举了众多学者对蚁群算法做出的改进与优化,其中有些是在经典蚁群算法的算法基础上加以改进,有些则让蚁群算法与其他算法相结合,取长补短,使得蚁群算法日益优化。不同的改进策略在相对应的应用场景中都得到了较好的效果,文中绪论部分对这些改进做出分析与论述。文中提出的主要创新点如下:1.针对经典蚁群算法在复杂环境下的机器人路径规划问题中表现出的收敛速度慢,容易陷入局部最优等问题,本章提出一种改进算法。依据方向指导信息来优化初始信息素的分布,加快搜索速度,缩减搜索初期的时间消耗;通过优化信息素的挥发与更新规则,保留局部与全局优秀路径的优势信息,改善收敛速度慢的问题;基于区域安全因素对转移概率进行改进,从而避免陷入局部最优和死锁等问题。为了验证改进的有效性,通过栅格法对仿真环境二维建模,对不同复杂度和规模的地图进行仿真实验。2.在带有路径代价的多目标规划问题上提出一种改进蚁群算法。在前文中提到的初始信息素分布规则的基础上,添加路径代价因子,为初始蚂蚁提供寻路方向。依据多目标规划的特性,提出一种蚂蚁群体划分的策略,赋予不同群体的蚂蚁不同的规划任务,从分到总地适应多目标规划需求。另外,在信息素的分布上,根据蚂蚁群体任务的不同设置不同的规则,再经过转移概率的优化选择,在仿真实验中得出了不错的结果。
[Abstract]:With the gradual development and progress of artificial intelligence technology in today's society, its application in life and production has become more widespread, and attracted more and more researchers into it. Artificial intelligence has become a hot research hotspot in today's society. The research of intelligent robot has attracted more and more attention with the development of technology. In order to improve the efficiency of robot to complete the task, we hope that the robot can have the function of finding its own path safely. The goal of path planning is not only to find the feasible path between the starting point and the end point, but also to plan a path that is short, time consuming and high safety among the many feasible paths, in order to improve the efficiency of the work in recent years. On the problem of path planning, experts and scholars at home and abroad give their own solutions, and get effective results in their respective problem models, including genetic algorithm, particle swarm optimization algorithm, artificial immune algorithm, neural network method. The artificial potential field method and so on. In many application algorithms, the ant colony algorithm has received extensive attention since it was put forward. This paper mainly describes the research subject of path planning of mobile robot. The main work of this paper is as follows: 1. This paper systematically discusses the idea and implementation steps of ant colony algorithm, starting with the idea of classical ant colony algorithm. The advantages and disadvantages of ant colony algorithm in path planning are analyzed. Ant colony algorithm uses bionic means, according to the path finding behavior of ants in the course of foraging, by giving positive feedback information to offspring, the global optimal path is gradually converged. It has the advantages of strong robustness, but also has the problem of long search time and easy to fall into local convergence. In this paper, the improvement and optimization of ant colony algorithm made by many scholars are listed. Some of them are improved on the basis of the classical ant colony algorithm, and some of them combine the ant colony algorithm with other algorithms to complement each other. The ant colony algorithm is becoming more and more optimized. Different improved strategies have better results in the corresponding application scenarios. In the introduction part of the paper, we analyze and discuss these improvements. The main innovation points in this paper are as follows: 1. The convergence speed of classical ant colony algorithm in the robot path planning problem in complex environment is slow. In this chapter, an improved algorithm is proposed to optimize the distribution of initial pheromone according to the direction guidance information, accelerate the search speed and reduce the initial time consumption. By optimizing the rules of volatilization and renewal of pheromone, the advantage information of local and global excellent paths is preserved, and the problem of slow convergence is improved, and the transfer probability is improved based on regional security factors. In order to verify the effectiveness of the improved method, the simulation environment is modeled by grid method. Simulation experiments on maps with different complexity and scale. 2. An improved ant colony algorithm for multi-objective programming with path cost is proposed. Based on the initial pheromone distribution rules mentioned above, the path cost factor is added. According to the characteristics of multi-objective programming, a strategy of ant population division is proposed, which gives ants of different populations different planning tasks, and adapts to the needs of multi-objective planning from division to total. In the distribution of pheromone, according to the different rules of ant colony task, and through the optimal selection of transfer probability, a good result is obtained in the simulation experiment.
【学位授予单位】：安徽大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：TP18;TP242

【参考文献】