JPS算法_系统结构是什么

大家好，又见面了，我是你们的朋友全栈君。

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节点），再抵达劣性节点所需代价的节点。 i f C o s t ( 父 节 点 → 目 标 节 点 （ 不 经 过 当 前 节 点 ） ) ≤ C o s t ( 父 节 点 → 当 前 节 点 → 目 标 节 点 ) : n o d e = I n f e r i o r e l s e : n o d e = N a t u r a l \begin{aligned} &if\quad Cost(父节点\to目标节点（不经过当前节点）)\leq Cost(父节点\to当前节点\to目标节点):\\ &\qquad node = Inferior\\ & else:\\ &\qquad node = Natural \end{aligned} ​ifCost(父节点→目标节点（不经过当前节点）)≤Cost(父节点→当前节点→目标节点):node=Inferiorelse:node=Natural​ 举例说明：

• 1号节点： 4 → 1 4\to1 4→1所需代价1； 4 → x → 1 4\to x\to1 4→x→1 4 → 1 4\to1 4→1所需代价 1 + 2 1+\sqrt2 1+2 ​，劣性节点
• 2号节点： 4 → 2 4\to2 4→2所需代价 2 \sqrt2 2 ​； 4 → x → 2 4\to x\to2 4→x→2所需代价2，劣性节点
• 3号节点： 4 → 2 → 3 4\to2\to3 4→2→3所需代价 1 + 2 1+\sqrt2 1+2 ​； 4 → x → 3 4\to x\to3 4→x→3所需代价 1 + 2 1+\sqrt2 1+2 ​，劣性节点
• 5号节点：最短为 4 → x → 5 4\to x\to5 4→x→5，自然节点
• 6号节点：对称等同于1号节点，劣性节点
• 7号节点：对称等同于2号节点，劣性节点
• 8号节点：对称等同于3号节点，劣性节点

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

对角（diagonal）

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

分析如下：

• 1号节点： 6 → 4 → 1 6\to4\to1 6→4→1所需代价2； 6 → x → 1 6\to x\to1 6→x→1所需代价为 2 2 2\sqrt2 22 ​，劣性节点
• 2号节点： 6 → 4 → 2 6\to4\to2 6→4→2所需代价 1 + 2 1+\sqrt2 1+2 ​； 6 → x → 2 6\to x\to2 6→x→2所需代价为 1 + 2 1+\sqrt2 1+2 ​，自然节点
• 3号节点：最短为 6 → x → 3 6\to x\to3 6→x→3，自然节点
• 4号节点： 6 → 4 6\to4 6→4所需代价1； 6 → x → 4 6\to x\to4 6→x→4所需代价 1 + 2 1+\sqrt2 1+2 ​
• 5号节点：对称等同于2号节点，自然节点
• 7号节点：对称等同于4号节点，劣性节点
• 8号节点：对称等同于1号节点，劣性节点

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

强迫邻居（Forced Neighbors）

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

直行（straight）

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

对角（diagonal）

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

跳跃规则（Jumping Rules）

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

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

直行跳跃（Jumping Straight）

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

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

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

对角跳跃（Jumping Diagonally）

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

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

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

优先级队列（Priority Queue）

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

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

完整跳跃演示

第一次探索

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

第二次探索

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

第三次探索

同第二次探索情况。

第四次探索

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

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

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

JPS 算法流程

JPS算法的伪代码同 A ∗ A^* A∗一样： 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 ∗ A^* A∗算法的邻居节点为几何意义上的邻居，而JPS算法的邻居节点为跳跃所得的邻居。

JPS算法演示

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

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

第一个关键节点

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

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

弹出绿色节点

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

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

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

第二个关键节点

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

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

第三个关键节点

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

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

抵达目标点

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

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

优先级队列的排序

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

算法比较

在复杂环境下，JPS算法的效果远远超过 A ∗ A^* A∗算法：

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

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

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

版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。

发布者：全栈程序员栈长，转载请注明出处：https://javaforall.cn/191333.html原文链接：https://javaforall.cn