每周一篇论文-规划算法Jump Point Search-Online Graph Pruning for Pathfinding on Grid Maps

论文背景

机器人和视频游戏等应用领域中常见的问题是等权重的网格化搜索，在自然界中是规则的，该域通常具有高度的路径对称性（Harabor和Botea 2010；Pochter等人2010）。在这种情况下，对称性表现为路径（或路径段），它们共享相同的起点和终点，具有相同的长度，除移动发生的顺序外，其他方面都相同。除非处理得当，否则对称性可能会迫使搜索算法评估许多等效状态，并阻止朝着目标的真正进展。

直接点就是: 这种之前的搜索算法对于对称等价的搜索没有很好的处理方法，该论文提出的JPS就是为了解决这个问题而提出的。

上左图，A*算法会搜索很多对称等价的路径，这样会浪费很多搜索的时间。上右图JPS就通过剪枝避免了对称的搜索，加快到达目标节点的过程。

论文贡献和结果

1. 详细描述了跳跃点算法；
2. 理论结果表明，用跳点搜索保持了最优；
3. 将提出的方法与两种最先进的搜索空间缩减算法进行比较的实证分析。在文献中的一系列合成基准和真实基准上进行了实验，发现跳转点将标准A*的搜索时间性能提高了一个数量级甚至更多。

论文原话翻译：

均匀成本网格环境中的寻路是机器人和电子游戏等应用领域中常见的问题。最先进的是分层寻路算法，它速度快，内存开销小，但通常返回次优路径。在本文中，我们提出了一个新的搜索策略，针对网格，它是快速的，最优的，不需要内存开销。我们的算法可以被描述为一个宏算子，它只识别和有选择地展开网格图中的某些节点，我们称之为跳跃点。连接两个跳转点的路径上的中间节点永远不会展开。我们证明了这种方法总是计算最优解，然后进行了深入的实证分析，并将我们的方法与文献中的相关工作进行了比较。我们发现带有跳转点的搜索可以将A*的速度提高一个数量级甚至更多，并且报告了在当前技术状态上的显著改进。

论文实现

作者定义了一套搜索的规则，下面介绍各个规则：

跳跃规则

对于上图来说，我们在A算法的角度来说，是应该将x点周围的8个方向的邻居点都加到open List，表示这些邻居都是等待检索的。但是，在图上的实际情况是，【（a）为例子】我走到x，x的下一步A应该扩展的node为【1，2，3，5，8，7，6，1】，为啥我要扩展【1，2，3，6，7，8】明显路径【4->x>{1/2/3/6/7/8}】，所走的路径长度并不能比直接从4不经过x，直接到达。也就是不能优于【4->{1/2/3/6/7/8}】。所以就有了JPS算法，它的处理是直接不把【1，2，3，6，7，8】加入openList中，直接往右走5，通过这样剪枝的方法来加快算法速度。

强迫邻居

上图的（b）和（d）从x到3和1这两个路径被定义为强迫的，3和1是强迫节点。因为x到3和1的路径长度为根号2，如果x经过其他节点到达的话，路径长度为2.

跳点

当前点 x 满足以下三个条件之一：

• 节点 x 是起点/终点。
• 节点 x 至少有一个强迫邻居。
• 如果父节点在斜方向（意味着这是斜向搜索），节点x的水平或垂直方向上有满足条件a，b的点。
  只有在上面的图中会被我们选择到加入openList的点就是跳点。
  论文原话:( In this section we introduce a search strategy for speeding up optimal search by selectively expanding only certain nodes on a grid map which we term jump points. We give an example of the basic idea in Figure 1(a). )

下图（a）中y是跳点；（b）中x，y，z 是跳点。

下图是直线跳跃和对角线跳跃的规则，按照这种规则上图（a）从p(x) 直接跳到y，将y加入openList；图（b）从p(x)直接跳到y，jiangy加入openList中，为啥要将y加入呢？因为y是跳点。

算法过程

JPS 寻路算法（Jump Point Search）
实现原理
JPS 算法和A* 算法非常相似，步骤大概如下：

1. openlist取一个权值最低的节点，然后开始搜索。（这些和A*是一样的）
2. 搜索时，先进行直线搜索（4/8个方向，跳跃搜索），然后再斜向搜索（4个方向，只搜索一步）。如果期间某个方向搜索到跳点或者碰到障碍（或边界），则当前方向完成搜索，若有搜到跳点就添加进openlist。

• 跳跃搜索是指沿直线方向一直搜下去（可能会搜到很多格），直到搜到跳点或者障碍（边界）。一开始从起点搜索，会有4个直线方向（上下左右），要是4个斜方向都前进了一步，此时直线方向会有8个。

3. 若斜方向没完成搜索，则斜方向前进一步，重复上述过程。因为直线方向是跳跃式搜索，所以总是能完成搜索。
4. 若所有方向已完成搜索，则认为当前节点搜索完毕，将当前节点移除于openlist，加入closelist。
5. 重复取openlist权值最低节点搜索，直到openlist为空或者找到终点。

缺点：

有情况下JPS是不太好的，下图如果定义的规则是先右，上开始搜索，JPS就会一直搜索完右上的全部区域，然后到搜索右下的全部区域，这就很费时间了，违背了JPS的设计出发点。但是应该也是可以避免的，再开始是给他一个向目标点的牵引就OK，感觉而已，结果得试试，哈哈。

参考：

1. https://www.bilibili.com/video/BV19t4y1x7Nk/?spm_id_from=333.880.my_history.page.click&vd_source=47a84a9de9cf75b64d0416fc4cd34394
2. https://blog.csdn.net/weixin_45929038/article/details/123133488
   可视化网站：https://qiao.github.io/PathFinding.js/visual/

感觉写好一篇blog很难呀😭，慢慢完善。