基于采样的路径规划
采样基础：
不用显式的构造机器人的工作空间及其边界，只需要指出单个机器人是否发生了碰撞
完备的规划器、概率完备的规划器、解析完备的规划器（和概率完备的规划器类似，但采样是基于固定的栅格）
Probabilistic Road Map（概率路图）
PRM的两个阶段：
-
学习阶段：随机撒点，生成一个图结构
- 采样：基于一定的采样规则，随机采样；删除有障碍碰撞的点
- 连接（起点和终点要连接）：过远的点之间不用连接，删除掉连接有障碍物碰撞的线段
-
查询阶段：快速找到路径（利用A*和Dijkstra算法）
优点：概率完备、效率高
缺点：要求先学习再查询（在学习阶段的时候没有把生成路径作为重点）
Lazy collision-checking（惰性障碍检测）
障碍检测是一个费时操作
惰性障碍检测：随机采点和生成线段时不考虑障碍（Lazy）
生成路径，然后检测路径上的边和点是否无障碍碰撞
删除有碰撞的点和边，重新生成路径（相当于减少了不必要的障碍物检测）
Rapidly-exploring Radom Tree（快速搜索随机树）
增量式构建搜索树，终点加入搜索树时，就可以构建出一条路径
第一步：先随机采一个点A，连接起点O和点A，从起点O处向点A的方向移动一定距离，得到一个新的点B。如果起点O和点B连线没有障碍物，则点B连同线段OB加入到树中。
- 随机采样得到点
- 找到树中离点最近的点
- 从点向点移动一定距离，得到新的点，和点的连线
- 如果和没有与障碍物碰撞的话，将它们加入到树中
- 当拓展到终点或者其附近时，可以直接利用树的性质，得到路径（找父节点）
缺点：
-
不是最优路径
-
有改进空间。比如在狭窄的空间中，拓展速度较慢
改进RRT的几个核心函数，便可以改进RRT
Kd-tree——改进Near( )函数
双向RRT（从起点和终点同时生成树），当两个树连接时就找到了路径
双向RRT可以解决一部分narrow passage的情况
Rapidly-exploring Random Tree*（保证了全局最优性）
RRT*和RRT的不同之处在于：
-
当是时，RRT直接将添加到搜索树里
-
当是时，RRT*将进行一些处理，再把添加到搜索树中
-
采用一定的方式包络的邻域，得到处于邻域内的一些点（）
-
选择了从起点到距离最近的路径，并将路径上的该点作为的父亲节点
-
将以及边添加进搜索树中
-
剪枝：修改搜索树的连接（）
看能否通过走来减小邻域内其他节点的代价
-
RRT*在找到路径后，仍会不断进行剪枝的过程，优化路径
Kinodynamic-RRT*
考虑机器人的动力学约束（改进Steer()函数）
Anytime RRT*
优化和改进的方法
Informed RRT*
Informed RRT*将采样过程围绕在生成的路径的附近
- 路径生成部分（和RRT*一样）
- 当路径生成后，把采样范围限制在椭圆里面（把起点和终点作为椭圆的两个焦点，把路径的代价作为）
- 路径不断优化，采样范围进一步收缩。
Cross-entropy motion planning
- 路径生成部分（和RRT*一样）
- 这些节点构成了一个多高斯模型，这个多高斯模型的每一部分都以节点为均值，指定的方差为方差（在每个圈内进行采样），得到几条新的路径
- 规定下一轮的采样空间：对多个轨迹的多个节点求均值，这些均值又构建出一个新的多高斯模型，重复上一步
