unoaaa基于遗传算法的移动机器人路径规划研究.pdf

摘 要
移动机器人是机器人领域的一个重要发展方向，而路径规划是移动机器人系统中的
一个重要内容，因为它的好坏直接影响到机器人所完成任务的质量，所以路径规划成为
移动机器人领域的一个研究热点。
本文中的移动机器人路径规划包含两方面的内容：避障路径规划和 TSP 路径规划问
题。避障路径规划是指依据某个或某些优化准则，在其工作空间中找到一条从起始点到
目标点能避开所有障碍物的一条最优路径。TSP 路径规划问题是指已知几个城市之间的
相互距离，现有一个推销员必须遍访这几个城市，并且每个城市只能访问一次，最后又
必须返回出发城市，如何安排他对这些城市的访问次序，使其旅行路线总长度最短。
本文首先讨论了路径规划技术的发展现状以及应用方法，也指出了本课题的研究意
义和主要研究的内容。
其次通过对遗传算法和模拟退火算法的研究，分析了各自的优缺点。并把这两个算
法结合构成了遗传模拟退火算法，它兼备了很强的全局和局部搜索能力，在变量数目较
大时尤其突出。把遗传模拟退火算法运用到避障路径规划当中，并采用新型的初始种群
生成算法，仿真结果表明这种算法使移动机器人避障路径规划提高了收敛速度，达到了
较好的规划效果。
最后研究了运用遗传算法求解 TSP 路径规划问题，对基本遗传算法的求解 TSP 路
径规划问题进行了改进。为了解决群体的多样性和收敛速度的矛盾，本文采用了依概率
近邻法来生成初始种群，这种初始种群生成方法较近邻算法略差，但个体多样性水平优
于近邻算法。为了在遗传算法的整体运行过程中保持种群多样性、提高收敛速度，本文
将相似性、群体分级等概念引入到遗传算法中，将等级较高的个体采用启发交叉算法进
行交叉，并采取杰出者记录与“父子混合”选择策略来保证算法的全局收敛性，仿真结
果证明了改进算法的有效性。


关键词：路径规划，遗传算法，模拟退火算法，旅行商问题，近邻法，相似性
I
Abstract
The mobile robot is an important branch of the field of robot. In particular, path-planning
is critical to mobile robot system because it determines the quality of the robot’s task. As a
result, path-planning has attained more and more attention in the field of mobile robot.
In this thesis mobile robot path planning includes two aspects: obstacle avoidance path
planning and TSP path-planning problem. Obstacle avoidance path planning is achieving the
best path from starting point to goal point by avoiding all barriers. The path searching
depends on one or more optimization rules. TSP path-planning is the problem some known
distance between the city, has a salesman to be visited these cities, and visit each city only
once, finally return to the starting city, how to arrange the visit to the city of his order, make
its total shortest length route of travel.
This thesis first discusses the development situation of path planning in technology and
application method, and po