大家好，又见面了，我是你们的朋友全栈君。
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} &ifquad Cost(父节点to目标节点（不经过当前节点）)leq Cost(父节点to当前节点to目标节点):\ &qquad node = Inferior\ & else:\ &qquad node = Natural end{aligned} ifCost(父节点→目标节点（不经过当前节点）)≤Cost(父节点→当前节点→目标节点):node=Inferiorelse:node=Natural 举例说明：
- 1号节点： 4 → 1 4to1 4→1所需代价1； 4 → x → 1 4to xto1 4→x→1 4 → 1 4to1 4→1所需代价 1 2 1 sqrt2 1 2 ，劣性节点
- 2号节点： 4 → 2 4to2 4→2所需代价 2 sqrt2 2 ； 4 → x → 2 4to xto2 4→x→2所需代价2，劣性节点
- 3号节点： 4 → 2 → 3 4to2to3 4→2→3所需代价 1 2 1 sqrt2 1 2 ； 4 → x → 3 4to xto3 4→x→3所需代价 1 2 1 sqrt2 1 2 ，劣性节点
- 5号节点：最短为 4 → x → 5 4to xto5 4→x→5，自然节点
- 6号节点：对称等同于1号节点，劣性节点
- 7号节点：对称等同于2号节点，劣性节点
- 8号节点：对称等同于3号节点，劣性节点
综上所述，由4号节点抵达x节点，在探索x的邻居节点时，只需要探索5号节点即可。
对角（diagonal）
若如上图所示，由父节点（6号节点）抵达当前节点（x节点），则可认定节点1、4、7、8为劣性节点，其余为自然节点。
分析如下：
- 1号节点： 6 → 4 → 1 6to4to1 6→4→1所需代价2； 6 → x → 1 6to xto1 6→x→1所需代价为 2 2 2sqrt2 22 ，劣性节点
- 2号节点： 6 → 4 → 2 6to4to2 6→4→2所需代价 1 2 1 sqrt2 1 2 ； 6 → x → 2 6to xto2 6→x→2所需代价为 1 2 1 sqrt2 1 2 ，自然节点
- 3号节点：最短为 6 → x → 3 6to xto3 6→x→3，自然节点
- 4号节点： 6 → 4 6to4 6→4所需代价1； 6 → x → 4 6to xto4 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 4to2to3 4→2→3进行，而必须采用 4 → x → 3 4to xto3 4→x→3进行。也即3号节点由劣性节点变为强迫节点，不能被抛弃。
对角（diagonal）
如上图所示，在对角条件下，若4号节点所在栅格被障碍物占据，则1号节点的抵达无法通过 6 → 4 → 1 6to4to1 6→4→1进行，而必须采用 6 → x → 1 6to xto1 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:\ &qquadqquad return:false;\ &qquadqquad 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:\ &qquadqquad return:true;\ &qquadqquad break; \ &qquad For:all:unexpanded:neighbours:m:of:node:n:\ &qquadqquad if:g(m)==infinite: \ &qquadqquadqquad g(m)=g(n) Cost_{nm}\ &qquadqquadqquad Push:node:m:into:the:queue\ &qquadqquad if:g(m)>g(n) Cost_{nm} \ &qquadqquadqquad 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) CostnmPushnodemintothequeueifg(m)>g(n) Costnmg(m)=g(n) CostnmendEndLoop 他们的不同在于邻居节点的定义不同：
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
