运动规划之搜索算法:前端规划、后端轨迹生成到状态求解( 八 )

``` heuristic*= (1.0 + p) ```

  • 1.
其中这里的启发因子需要满足
p < 移动一步的最小代价 / 期望的最长路径长度 。
  • 1.
假设你不希望你的路径超过1000步(step),你可以使p = 1 / 1000 。添加这个附加值的结果是,A比以前搜索的结点更少了 。如下图所示 。
运动规划之搜索算法:前端规划、后端轨迹生成到状态求解

文章插图
当存在障碍物时,当然仍要在它们周围寻找路径,但要意识到,当绕过障碍物以后 , A搜索的区域非常少:
运动规划之搜索算法:前端规划、后端轨迹生成到状态求解

文章插图
  1. Steven van Dijk的建议是:直接把h放到比较函数中 。当f值相等时,比较函数将会通过比较两个节点h的大小实现启发因子的功能,打破比较平衡点 。
  2. Cris Fuhrman的建议的启发因子是:给每个节点加一个决定性的任意数,例如所在坐标系中位置的hash值
  3. 最后一种方法类似于fr.NET坐标系的做法:对比起点到终点的直连线段的投影距离,计算方法入下:
dx1 = current.x - goal.xdy1 = current.y - goal.ydx2 = start.x - goal.xdy2 = start.y - goal.ycross = abs(dx1*dy2 - dx2*dy1)heuristic += cross*0.001
  • 1.
  • 2.
  • 3.
  • 4.
  • 5.
  • 6.
其目的是:计算初始->目标向量和当前->目标向量的向量叉乘(cross-product) 。当向量偏离方向后,其叉乘将会提供一个较大的启发因子 。结果是,这段代码选择的路径稍微倾向于从初始点到目标点的直线 。当没有障碍物时,A不仅搜索很少的区域,而且它找到的路径看起来非常棒:
运动规划之搜索算法:前端规划、后端轨迹生成到状态求解

文章插图
跳点搜索
Jump Point Search (JPS) 是一种改进的 A_ 算法 , 它保留了 A_ 算法的主体框架,但在寻找后继节点的操作上进行了优化 。在 A 算法中,会将当前节点的所有未访问邻居节点加入 openlist 。而 JPS 则使用一些方法将有“价值”的节点加入 openlist 。JPS 的核心就是寻找跳点 (Jump Point),在 JPS 中,就是将跳点加入 openlist 。跳点就是路径的转折点 。
运动规划之搜索算法:前端规划、后端轨迹生成到状态求解

文章插图
JPS明智地进行探索,因为它总是根据规则向前看 。强调了其在搜索过程中的智能性和前瞻性 。
JPS 算法的基本流程与 A 一致,代价函数 f(n) 仍然表示如下:f(n)=g(n)+h(n) 。
JPS 算法的优点在于,由于它只扩展跳点,跳点间的栅格被跳过,不加入 OpenList , 因此,它的搜索效率比 A 算法提高了一个等级 。
在实现JPS前先了解它的规则
  1. 强迫邻居:节点X的邻居节点有障碍物,且X的父节点P经过X到达N的距离代价,比不经过X到达N的任一路径的距离代价都?。?则称N是X的强迫邻居 。

运动规划之搜索算法:前端规划、后端轨迹生成到状态求解

文章插图
  1. 跳点(Jump Point):什么样的节点可以作为跳点
    (1)节点 A 是起点、终点.
    (2)节点A 至少有一个强迫邻居.
    (3)父节点在斜方向(斜向搜索),节点A的水平或者垂直方向上有满足 (1)、(2) 的节点
    在搜索过程中它可以将水平和垂直方向两个分量,分解为一个方向为(1, 0)的水平搜索,一个方向为(0, 1)的垂直搜索
    同理斜向有四种方向
    左上 (-1, 1) ——>对应的水平 (-1, 0) , 垂直 ( 0, 1)
    右上 ( 1, 1) ——>对应的水平 ( 1, 0),垂直 ( 0, 1)
    右下 ( 1, -1) ——>对应的水平 ( 1, 0),垂直 ( 0, -1)
    左下 (-1, -1) ——>对应的水平 (-1, 0),垂直 ( 0, -1)
    如上所说(3)的情形即为如下

运动规划之搜索算法:前端规划、后端轨迹生成到状态求解

文章插图

运动规划之搜索算法:前端规划、后端轨迹生成到状态求解

文章插图