基于RRT*的路径规划算法研究

基于RRT*的路径规划算法研究(任务书,开题报告,论文12000字)
摘要
在自主移动机器人的路径规划问题中，快速拓展随机树算法（rapidly-exploring random tree , RRT）是常用的算法之一。但RRT算法寻求的可行路径往往存在路径不具有最优性的问题，因此有学者在RRT算法的基础上，提出一种改进的RRT*算法，使所得可行路径具有渐进最优性。本文旨在将RRT*算法与RRT算法进行实验对比，分析RRT*算法相对于RRT算法在路径最优化上的改进程度。其次，为了加快算法的收敛速度，又对RRT*算法增加了目标偏向策略，同样地对RRT*算法和增加了目标偏向策略的RRT*算法进行对比实验，分析它们在收敛速度上的差距。所有的仿真实验均在MATLAB平台上完成，使用RRT算法、标准RRT*算法和增加了偏置概率P的RRT*算法分别对不同类型的地图进行多次测试，记录三种算法的时间代价与路径代价，对比所得数据，具体分析三种算法各自的优势与缺点。
关键词：自主移动机器人；路径规划；RRT算法；RRT*算法；目标偏向策略。
 
ABSTRACT
In the path planning problem of autonomous mobile robots, the rapid-exploring random tree (RRT) algorithm is one of the commonly used algorithms.However, the feasible paths sought by RRT algorithm often have the problem that the paths are not optimal. Therefore, on the basis of RRT algorithm, some scholars propose an improved RRT algorithm--RRT* algorithm, which makes the feasible paths have asymptotic optimality.This paper aims to compare the RRT* algorithm with the RRT algorithm and analyze the improvement of the RRT* algorithm relative to the RRT algorithm in path optimization.Secondly, in order to speed up the convergence of the algorithm, the target bias strategy is added to the RRT* algorithm. Similarly, the RRT* algorithm and the RRT* algorithm with the target bias strategy are compared to analyze their differences in convergence speed.All simulation experiments were performed on the MATLAB platform. The RRT algorithm, the standard RRT* algorithm and the RRT* algorithm with the added bias probability P were used to test different types of maps separately. Record the time cost and path cost of the three algorithms, then compare the data we got and analyze the advantages and disadvantages of each of the three algorithms specifically.
Key Word : Autonomous mobile robot ; path planning ; RRT ; RRT* ; Target bias strategy. 

目录
摘要    I
ABSTRACT    II
第1章绪论    1
第2章算法分析    3
2.1问题分析    3
2.2标准RRT算法分析    3
2.3标准RRT*算法分析    5
2.4加入偏置概率P的RRT*算法分析    8
第3章 MATLAB仿真分析    12
3.1仿真环境地图的建立    12
3.1.1实验地图的设定与仿真平台介绍    12
3.1.2无障碍地图    12
3.1.3多通路圆形障碍地图    12
3.1.4单通路复杂迷宫图    13
3.2实验结果对比分析    13
3.2.1无障碍地图    13
3.2.2多通路圆形障碍地图    16
3.2.3单通路复杂迷宫图    19
第4章结论与展望    23
参考文献    25
致谢    26