JPS算法_系统结构是什么

大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

Jump Point Search算法（JPS算法）

Jump Point Search算法的核心思想就是寻找到规划中的对称性Path并打破他们，从而避免扩展大量无用节点。

前向探索规则（Look Ahead Rule/ Pruning Rule）

JPS的智能性体现在它遵循的Look Ahead规则，主要包含如下几条内容：

裁剪邻居（Neighbor Pruning）

此处，假定处于栅格地图（Grid-based Map）中，且采用八联通结构以及图内无障碍物。则由上一节点抵达当前节点的情况，分直行和对角两种进行分析。

直行（straight）

假设当前从节点抵达下一个为直行（上图所示），如图当前节点为4号节点，下一个节点为x节点。则在考虑x节点的邻居节点时，可以仅仅考虑5号节点，而不考虑其余节点。

上述遵循的筛选规则如下：

• 摒弃劣性节点（Inferior Neighbours），也即图中灰色栅格区域的节点
• 考虑自然节点（Natural Neighbours），也即图中白色栅格区域的节点

所谓劣性节点是指：从父节点（4号节点）不经过当前节点（x节点） 而直接抵达所需代价，小于等于从父节点抵达当前节点（x节点），再抵达劣性节点所需代价的节点。
$$\begin{array}{rl}& ifCost(父节点\to 目标节点（不经过当前节点）)\le Cost(父节点\to 当前节点\to 目标节点):\\ & node=Inferior\\ & else:\\ & node=Natural\end{array}$$
举例说明：

• 1号节点：$4\to 1$所需代价1；$4\to x\to 1$$4\to 1$所需代价$1+\sqrt{2}$，劣性节点
• 2号节点：$4\to 2$所需代价$\sqrt{2}$；$4\to x\to 2$所需代价2，劣性节点
• 3号节点：$4\to 2\to 3$所需代价$1+\sqrt{2}$；$4\to x\to 3$所需代价$1+\sqrt{2}$，劣性节点
• 5号节点：最短为$4\to x\to 5$，自然节点
• 6号节点：对称等同于1号节点，劣性节点
• 7号节点：对称等同于2号节点，劣性节点
• 8号节点：对称等同于3号节点，劣性节点

综上所述，由4号节点抵达x节点，在探索x的邻居节点时，只需要探索5号节点即可。

对角（diagonal）

若如上图所示，由父节点（6号节点）抵达当前节点（x节点），则可认定节点1、4、7、8为劣性节点，其余为自然节点。

分析如下：

• 1号节点：$6\to 4\to 1$所需代价2；$6\to x\to 1$所需代价为$2\sqrt{2}$，劣性节点
• 2号节点：$6\to 4\to 2$所需代价$1+\sqrt{2}$；$6\to x\to 2$所需代价为$1+\sqrt{2}$，自然节点
• 3号节点：最短为$6\to x\to 3$，自然节点
• 4号节点：$6\to 4$所需代价1；$6\to x\to 4$所需代价$1+\sqrt{2}$
• 5号节点：对称等同于2号节点，自然节点
• 7号节点：对称等同于4号节点，劣性节点
• 8号节点：对称等同于1号节点，劣性节点

***此处注意，博主所学教程中未解释为何2、5节点在等同的情况下为自然节点，而非劣性节点。***对此，也许对角情况下同直行不同，特意将等同条件判定为自然而非劣性。

强迫邻居（Forced Neighbors）

假设处于栅格地图环境中，且采用八联通结构并且存在障碍物情况下，依旧分直行和对角两种情况进行考虑。

直行（straight）

如上图所示，在直行条件下，若2号节点所在栅格被障碍物占据，则3号节点的抵达无法通过$4\to 2\to 3$进行，而必须采用$4\to x\to 3$进行。也即3号节点由劣性节点变为强迫节点，不能被抛弃。

对角（diagonal）

如上图所示，在对角条件下，若4号节点所在栅格被障碍物占据，则1号节点的抵达无法通过$6\to 4\to 1$进行，而必须采用$6\to x\to 1$进行。也即1号节点由劣性节点变为强迫节点，不能被抛弃。

跳跃规则（Jumping Rules）

对前向探索规则的学习，可知其满足如下规则：

则此时，若不断进行直行（straight pruning）或不断进行对角（diagonal pruning），则可采用跳跃规则（Jumping Rules）。

直行跳跃（Jumping Straight）

若机器人不断迭代执行直行前向规则（straight pruning rule），如下图所示：

则在前进过程中对邻居节点进行裁剪，直到抵达节点$y$，此时针对障碍物所在位置，可知节点$z$为节点$y$的强迫邻居（Forced Neighbors），称节点$y$为节点$x$的关键节点（Jump Point Successor）。

也即在对节点$x$执行直行探索时，可直接跳跃至一个具有强迫邻居的关键节点$y$上，对途中其余节点无需考虑探索。

对角跳跃（Jumping Diagonally）

对于任何一次跳跃，首先考虑直行跳跃（Jumping Straight），包括水平直行和垂直直行，其次再考虑对角跳跃（Jumping Diagonally）。如下图所示：

当由当前节点对角行至节点$x$时，对其进行直行跳跃探索（图中红色虚线），由于未找到关键节点则忽略相关探索的节点，并使用对角跳跃规则至下一节点。

同样对该节点进行直行跳跃探索，由于无关键节点而再次进行对角跳跃，直至抵达节点$y$。此时对其进行水平直行跳跃，发现节点$z$具有强迫邻居节点，则返回至发现节点$z$的节点$y$，标记其为节点$x$的关键节点（Jump Point Successor）。

优先级队列（Priority Queue）

JPS算法的优先级队列内元素包含两类内容：使用跳跃规则发现的关键节点（Jump Point Successor）；当前探索节点$x$的强迫邻居节点（Forced Neighbors）。

如上述对角跳跃中探索的示例图中，关键节点为$y$、强迫邻居为$w$，则同样将其加入优先级队列。

完整跳跃演示

第一次探索

当前节点（绿色节点）首先进行水平、垂直直行探索，未发现关键节点；进一步进行对角探索。

第二次探索

对第一次探索得到的节点进行水平、垂直直行探索，未发现关键节点；进一步执行对角探索。

第三次探索

同第二次探索情况。

第四次探索

对第三次探索得到的节点执行水平直行探索时，发现一个关键节点（黄色节点），它具有强迫节点（紫色节点）。

需要注意的是，从绿色节点无法一次直接跳跃至黄色节点，跳跃的规则为只能进行一次对角跳跃或直行跳跃。

则弹出的关键节点应该为探索得到黄色节点的对角跳跃节点（下图蓝色节点）

JPS 算法流程

JPS算法的伪代码同$A^{\ast }$一样：
L o o p i f   q u e u e   i s   e m p t y : r e t u r n   f a l s e ; b r e a k ; R e m o v e   t h e   n o d e   n   w i t h   t h e   l o w e s t   f ( n ) = g ( n ) + h ( n )   f r o m   t h e   p r i o r i t y   q u e u e M a r k   n o d e   n   a s   e x p a n d e d i f   t h e   n o d e   n   i s   t h e   g o a l   s t a t e : r e t u r n   t r u e ; b r e a k ; F o r   a l l   u n e x p a n d e d   n e i g h b o u r s   m   o f   n o d e   n : i f   g ( m ) = = i n f i n i t e : g ( m ) = g ( n ) + C o s t n m P u s h   n o d e   m   i n t o   t h e   q u e u e i f   g ( m ) > g ( n ) + C o s t n m g ( m ) = g ( n ) + C o s t n m e n d E n d   L o o p \begin{aligned} &Loop\\ &\qquad if\:queue\:is\:empty:\\ &\qquad\qquad return\:false;\\ &\qquad\qquad break;\\ &\qquad Remove\:the\:node\:n\:with\:the\:lowest\:f(n)=g(n)+h(n)\:from\:the\:priority\:queue\\ &\qquad Mark\:node\:n\:as\:expanded\\ &\qquad if\:the\:node\:n\:is\:the\:goal\:state:\\ &\qquad\qquad return\:true;\\ &\qquad\qquad break; \\ &\qquad For\:all\:unexpanded\:neighbours\:m\:of\:node\:n:\\ &\qquad\qquad if\:g(m)==infinite: \\ &\qquad\qquad\qquad g(m)=g(n)+Cost_{nm}\\ &\qquad\qquad\qquad Push\:node\:m\:into\:the\:queue\\ &\qquad\qquad if\:g(m)>g(n)+Cost_{nm} \\ &\qquad\qquad\qquad g(m)=g(n)+Cost_{nm}\\ &\qquad end\\ &End\:Loop \\ \end{aligned} ​Loopifqueueisempty:returnfalse;break;Removethenodenwiththelowestf(n)=g(n)+h(n)fromthepriorityqueueMarknodenasexpandedifthenodenisthegoalstate:returntrue;break;Forallunexpandedneighboursmofnoden:ifg(m)==infinite:g(m)=g(n)+Costnm​Pushnodemintothequeueifg(m)>g(n)+Costnm​g(m)=g(n)+Costnm​endEndLoop​
他们的不同在于邻居节点的定义不同：

$A^{\ast }$算法的邻居节点为几何意义上的邻居，而JPS算法的邻居节点为跳跃所得的邻居。

JPS算法演示

如下图，为一次JPS完整演示的问题描述：

从起点（绿色节点）到终点（红色节点），黑色节点为障碍物节点。

第一个关键节点

此处省略推演（同上述完整跳跃演示），当探索至黄色节点时，对其进行水平直行探索：

发现关键节点（紫色节点）具有一个强迫邻居（蓝色节点），则认为黄色节点为第一个关键节点加入优先级队列。

弹出绿色节点

继续对黄色节点进行对角探索：

未发现任何关键节点且节点无法继续对角探索，则完成第一次探索。

起点（绿色节点）弹出优先级队列，加入已经探索完毕的队列（Close List）中。

第二个关键节点

对上图中黄色节点进行探索，发现下一个关键节点（下图中黄色节点）：

当前节点的探索完毕，加入Close List中。

第三个关键节点

对黄色节点进行直行、对角探索：

两次探索后，发现目标点（红色节点）。JPS算法将目标点假定为强迫邻居节点，则判断当前节点为关键节点：

抵达目标点

对黄色节点进行直行探索：

抵达终点，路径规划如下：

优先级队列的排序

对于加入优先级队列的节点，同$A^{\ast }$算法一样，对$f(n)$进行排序，代价值小的先被弹出进行探索：

算法比较

在复杂环境下，JPS算法的效果远远超过$A^{\ast }$算法：

这是因为JPS算法能够减少加入Open List中的节点的个数，仅仅对关键节点进行探索。

但是同样，JPS算法存在增添计算在探索是否存在障碍物上，如下图所示环境，JPS算法将优先想左边不断探索直至抵达边缘后在进行向右探索：

此外，JPS仅能应用于Uniform Grid Map中，也即两个相邻的节点边权重为1，对角为$\sqrt{2}$的栅格地图中