随机路径图法（PRM）

1. 介绍

    随机路径图法由Lydia E. 等人在1996年提出，它的优点在于：

    1）克服了以往一些路径规划方法易于陷入局部极小的缺点
    2）可应用于多自由度的机器人的路径规划中
    3）计算量小

    主要的应用背景有：

    1）核反应工厂冷却管的维护
    2）汽车装配时点对点的焊接
    3）飞机机身的清理
    4）飞机引擎维护时拆解行为规划

    用随机路径图（PRM）法寻找给定地图中两点之间的路径，PRM进行路径规划的步骤：

    学习阶段：在给定图的自由空间里随机撒点（自定义个数），构建一个路径网络图。
    查询阶段：查询从一个起点到一个终点的路径。
    

2. PRM学习阶段

    PRM学习阶段包含两部分内容：
    A. 构造无向路径网络图R=(N,E)，其中N代表随机点集，E代表所有可能的两点之间的路径集。

        构造过程的伪代码如下：

    具体考虑以下四个问题：
    1）怎样随机撒点？（伪代码第（4）步）
          a. 必须是自由空间里的随机点
          b. 每个点都要确保机器人与障碍物无碰撞
    2）怎么构造区域规划器，连接两点？（伪代码第（8））
          a. 保证区域规划器的确定性和快速性
          b. 均衡单次调用的时间和总的调用次数
          c. 离散化局部路径，进行防撞检查
    3）通过什么规则来选取邻域点？（伪代码第（5）步）
          a. 领域点的距离在一定范围
          b. 领域点的个数有上限
    4）如何选择距离函数D（伪代码第（7）步）

          a. D(c,n)被定义为：

                                        

    B. 扩充难于连线区域的点
    该部分内容旨在找出那些在“困难”区域的点，并且扩充这一区域点的个数。通过给每个点引入权重系数w(c)来决定那些区域需要增加点。
    启发式的权重选择法：
        I. w(c)与一定半径范围内邻点的个数成反比
        II. w(c)与最近的没有和c相连点的距离成反比
        III. 局部规划器与c点连接失败的概率成正比

       

        Lydia E.的文章中使用了第3种启发式的算法：

         

    前一个公式是计算局部区域规划器连接点c时失败的概率，n(c)是试图连接c的总次数，f(c)是失败的次数，如果c与n连接失败，那么c和n的连接失败次数都要加一。

    构造路径图步骤时间一般占学习阶段总时间的2/3，而扩充点步骤一般占总时间的1/3。

3. PRM查询阶段

    学习阶段已经构造了无向路径网络图R=（N,E），进入查询阶段时只需根据设定的起点s和终点g，选择合适的路径，具体过程如下：
    1）将s和g点与路径网络中的两个点x,y分别连接
    2）寻找无向路径网络图中x与y连接的路径，这样就可以将起点和终点连接起来，构成全局路径。
    3）得到全局路径后，可以使用平滑的方法寻找捷径，优化路径。
    主要的难点在于寻找s到x的路径，g到y点的路径。采用局部规划器和距离函数D结合的方法寻找。如果失败了，就采用random-bounce行走的方法寻找连接路径。

    可参照MathWorks官网中ROS系统下的路径规划了解其MATLAB代码的实现。

参考文献：

[1] L.E. Kavraki, P. Svestka, J.-C. Latombe, M.H. Overmars, "Probabilistic roadmaps for path planning in high-dimensional configuration spaces," IEEE Transactions on Robotics and Automation, vol. 12, no. 4, pp. 566-580, Aug 1996.

[2] http://cn.mathworks.com/help/robotics/examples/path-planning-in-environments-of-different-complexity.html