基于采样的路径规划方法

    与基于图搜索的方法相比,基于采样的路径规划算法不需要显式构建整个配置空间和边界。

0.概念

    Complete Planner(完备规划器)

    Probabilistic Complete Planner(概率完备的规划器)

    Resolution Complete Planner(解完备规划器)


1.概率路图(PRM)

    PRM是一个以图结构为基础的路径规划算法,该算法分为两个阶段:学习阶段和查询阶段。PRM首先在地图中撒一些点,然后将这些点连接成为一个图,最后在图上寻找一条从起点到终点的路径。

PRM的学习阶段:在C-空间中采样了N个点,然后将落在障碍物中的点剔除掉。

图片1.jpg

    然后将每个点与它相邻的点(一定距离内)连接起来,剔除碰到障碍物的连接。

图片2.jpg

PRM的查询阶段:从构建的图上的起点使用图搜索算法(A*、Dijkstra)规划一条从起点到终点的路径。但是这比直接使用图搜索算法效率要高得多,因为PRM在原始地图的基础上构建了一个更加简化的地图。 


PRM特点

    优点:概率完备,计算量更小。

    缺点:需要解决边界值问题,在构建图的过程中不专注与生成路径,因此不够高效。


改进:懒惰障碍物检测方法(Lazy collision-checking)

    在构建路图的过程中需要对每一条连接的线进行障碍物检测,这非常消耗时间,尤其是在复杂或高维的环境中。因此这个改进方法的思路是在采样点和生成路径的过程中不检测障碍物,即Lazy。然后直接在生成的图上进行路径规划,如下图所示:

图片3.jpg

    然后再对生成的路径进行障碍物检测,剔除路径上经过障碍物的点和它周围的路径。之后再次执行路径规划:

图片4.jpg

    虽然这个过程中在需要多次进行路径规划,但是它避免了在构建路图时需要花费大量的时间进行碰撞检测,因此总体更加节省时间。


2.快速搜索随机树(RRT)

    RRT算法的伪代码如下:

图片5.jpg

    RRT算法可以直接生成一条从起点到终点的路径,而不需要经过两个阶段。如上面的伪代码所示,RRT的每一步就是根据某个分布函数从地图中采样一个点x_rand,然后从树中搜索离x_rand最近的节点,从x_near往x_rand前进一个StepSize得到一个新的点x_new和路径Ei,同时进行碰撞检测,如下图所示:

图片6.jpg

    若边Ei无碰撞,则将节点x_new和边Ei加入到树中。重新迭代,直到找到目标点。实例如下:

图片7.jpg

RRT算法的优缺点

    优点:它比RRT有更强的方向性,而流程更加简单。

    缺点:规划出来的路径不是最优路径,在整个空间上进行采样,在效率上还有很大的改进的空间。

优化:使用KD-Tree

    使用KD-Tree来存储点,这样可以非常高效的查找到某个点周围距离近的点。

图片8.jpg

优化:双向RRT

    从起点和终点同时增量式构造RRT,即每一个采样点会同时使两个树增长,直到两棵树连起来。通过这种方式可以更快的构造一条路径。

图片9.jpg


3.RRT的改进算法

    RRT算法生成的路径存在一些问题,比如并不是最短路径,其次生成的路径不是非常适合移动机器人去执行的。因此有人提出了RRT的改进算法。

RRT*

    目的是改进RRT生成的路径不是最优的问题,其算法流程图如下:

图片10.jpg

    可以看到RRT*在获得了新的点x_new之后,不像RRT那样直接将x_new加入到树中,而是在x_new这个点的半径r内搜索出树上的一些相邻点。然后计算从起点经过这些点达到x_new的代价,并选择代价最小的相邻点作为父节点,加入到树中。如下图所示:

图片11.jpg

    如下图所示,在x_new加入到树中后,比较x_new到x1的代价是否比原来达到x1的代价更小,若是,则更新x1的父节点为x_new;x2同理。这就是伪代码中T.rewrite()函数的功能。

图片12.jpg

    这个过程不断迭代,最终生成一条比较接近最优的路径。

Kinodynarmic-RRT*

    针对RRT算法生成的路径不平滑的问题,有人提出了可以生成符合机器人动力学约束的路径的算法:Kinodynamic-RRT*,该算法改进了RRT*的Steer()函数,使得节点之间的路径更加平滑:

图片13.jpg

Anytime-RRT*

    在机器人前进过程中实时优化树的节点,并以机器人的运动过程中的位置作为起点。


4.先进的路径规划方法

Informed RRT*

    论文:Informed RRT*: Optimal sampling-based path planning focused via direct sampling of an admissible ellipsoidal heurist。RRT*在找到一条从起点到终点的路径之后,会持续不断的对路径进行优化,而且这个优化根据新的采样点在整个地图上进行优化的,这事实上比较低效。而Informed RRT*将优化的范围限制在路径周围的椭圆内,因此大大提高了效率。

图片14.jpg

    从下图可以看到,最左边的路径是一开始生成的路径,其外圈的椭圆就是Informed RRT*采样的范围。从下图左到右可以看到,随着优化的进行,生成的路径越来越接近最优,而椭圆越来越窄,从而采样的范围越来越小。

图片15.jpg

交叉熵运动规划

    (Cross-entropy motion planning)这个算法用于对生成路径的优化方法,如下图所示:

图片16.jpg

    最左边是生成的、未优化的路径,对该路径上的每个节点周围进行采样,这里是以高斯分布进行采样,每个节点采样一个点,这些新采样的点构成了一条新的路径。当然也可以每个节点新采样多个点,如上图右所示,新采样了2条路径。然后对这些新生成的路径与原来的路径一起,取平均,得到一条新的路径。这就完成了一个迭代,多次迭代后得到最终的路径。实例如下:

图片17.jpg


其它变体:

Lower Bound Tree RRT (LBTRRT)  

https://arxiv.org/pdf/1308.0189.pdf


Sparse Stable RRT    

http://pracsyslab.org/sst_software


Transition-based RRT (T-RRT)

http://homepages.laas.fr/jcortes/Papers/jaillet_aaaiWS08.pdf


Vector Field RRT

https://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=6606360


Parallel RRT (pRRT)

https://robotics.cs.unc.edu/publications/Ichnowski2012_IROS.pdf


5.实现 

    Open Motion Planning Library(OMPL)




    Moveit with ROS





下一篇: 没有了

首页 所有文章 机器人 计算机视觉 自然语言处理 机器学习 编程随笔 关于