【作者】 陈伟；

【导师】 郭立新；

【作者基本信息】 东北大学 ， 导航制导与控制， 2008， 硕士

【摘要】 路径规划是移动机器人研究的一个重要方向,它作为自主式移动机器人导航的基本环节之一,是按照某一性能指标搜索一条从起始状态到目标状态的最优或近似最优的无碰路径。智能算法在这一领域的应用正在引起人们的注意。而粒子群优化算法(Particle Swarm Optimization, PSO算法),这种源于鸟群和鱼群群体运动行为的研究,是一种新的群体智能优化算法。它的主要特点是原理简单、参数少、收敛速度较快,所需领域知识少。将该方法应用于移动机器人路径规划,是本文的研究重点。主要内容如下：(1)系统详尽地介绍了移动机器人路径规划的定义和分类,讨论了移动机器人路径规划研究意义、国内外研究进展和基本研究方向；PSO算法基本原理、多种改进形式、及其应用情况。(2)采用链接图建立机器人工作空间障碍物顶点模型,用Dijkstra算法求得一条从起始状态到目标状态的可行避碰次优路径。(3)应用原始PSO算法对求得的可行避碰次优路径进行优化,以求得全局最优路径。通过仿真结果,指出了原始PSO算法在粒子数目较少、迭代次数较少的情况下存在成功率低、易陷入局部极小的问题。(4)针对存在的问题,提出了基于惯性权重与位置限量相结合的改进PSO算法。通过仿真试验,该方法在粒子数目较少、迭代次数较少的情况下仍然可以取得较高的成功率、较好的寻优结果。说明该方法是高效可行的。(5)由于PSO算法中存在随机变量,实际应用中如果对时间进行限制,那么必然要减少粒子数目和迭代次数。随之而来的就是造成算法成功率的下降。针对这一问题,提出了检验最优值算法,当最优值不符合设置条件,将再次执行算法。根据仿真结果,证明了该算法是切实有效的。更多还原

【Abstract】 Path planning is an important field of mobile robot research, and as a basic part of mobile robot navigation, it aims to search for a non-collision path from the starting point to the target point according to an optimal or sub-optimal performance target. Intelligent computing has aroused extensive attention as a way of solving this problem. Particle swarm optimization (PSO) is a new swarm intelligent optimization algorithm, inspired by the swarm behavior of bird flock and fish school. Its peculiarities are simplicity in principle, less parameters, fast convergence and less professional knowledge needed. To apply the PSO algorithm to solve the path planning of mobile robot is the main task of this study. They are as follows:(1) It introduces the definitions and classifications about path planning of the mobile robot in detail, discusses the signification, development and, research areas of mobile robots. It also indicates basic principles of PSO algorithm, improved algorithms and its application.(2) The MALINK graph was used to describe the obstacle extreme points in the working space of the mobile robot. By means of Dijkstra algorithm a feasible non-collision suboptimal path can be obtained from a starting point to the target point.(3) Apply the original PSO algorithm to optimize the feasible non-collision suboptimal path so as to obtain the global optimal path. After reviewing the simulation results, we can find the original PSO algorithm is subjected to low success rate or fall in a local minimum on the condition of small number of particles, small number of iterations.(4) In view of the problems above-mentioned, the improved PSO algorithm based on combination of inertia weight and location limitation was proposed. Simulation results show that the improved algorithm can obtain high success rate and good optimized results on the condition of lesser particles and lesser iteration circles. This indicates that the improved algorithm is efficacious and valid.(5) Due to the random variables in PSO algorithm, it has to reduce the number of particles and iteration number if limiting the computation time in practice. Then it might reduce the success rate of the algorithm. For this problem, an algorithm to check the optimized result was proposed and this algorithm might conduct a run again if the optimal result does not meet the given conditions. The simulation results show that the algorithm is valid.更多还原