路径规划是运动规划的主要研究内容之一。连接起点位置和终点位置的序列点或曲线称之为路径，构成路径的策略称之为路径规划。路径规划在很多领域都具有广泛的应用。在高新科技领域的应用有：机器人的自主无碰行动；无人机的避障突防飞行；巡航导弹躲避雷达搜索、防反弹袭击、完成突防爆破任务等。在日常生活领域的应用有：GPS导航；基于GIS系统的道路规划；城市道路网规划导航等。在决策管理领域的应用有：物流管理中的车辆问题(VRP)及类似的资源管理资源配置问题。通信技术领域的路由问题等。凡是可拓扑为点线网络的规划问题基本上都可以采用路径规划的方法解决。

由此可见，路径规划问题具有多领域、大范围的特点，对其的研究会对人们的生活甚至军事方面都具有极其重要的意义与影响！

对于路径规划问题，传统的路径规划算法有多边形拟合法、栅格法、人工势场法、遗传算法等，但这些方法都需要在一个确定的空间内对障碍物进行建模，计算复杂度与机器人自由度呈指数关系，且由于算法在实时性、收敛速度等方面的一系列缺点，使得在实际应用中不能满足效率。

与此同时,RRT算法通过对状态空间中的采样点进行碰撞检测，避免了对空间的建模，能够有效地解决高维空间和复杂约束的路径规划问题。该方法的特点是能够快速有效地搜索高维空间，通过状态空间的随机采样点，把搜索导向空白区域，从而寻找到一条从起始点到目标点的规划路径，适合解决多自由度机器人在复杂环境下和动态环境中的路径规划。

也由于RRT算法在路径规划中具有诸多优势，RRT算法逐渐普及开来，众多国内外学者都对其有所研究与改进。例如使用无锁并发在现代多核CPU上获得超线性加速的PRRT；试图使RRT适应动态环境的DRRT和ERRT；结合了DRRT和ERRT优势的MP-RRT以及RRT*等，都是诸多学者对RRT的改进方案。

虽说国内外的学者对RRT进行了各种方向的研究与改进，但目前来说，RRT*算法是多数学者认为最佳的改进的RRT算法。相比于普通的RRT算法，RRT*算法引入了ChooseParent过程和Rewire过程来提供渐近最优性，当迭代次数接近无穷大时，找到最优解的概率接近100％！RRT*算法的优良性使其也更加具有研究价值，再次对RRT*算法的改进也成为了相当一部分国内外学者的研究方向。

2. 研究的基本内容与方案

内容：

1）了解路径规划的常用方法；

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