Jump Point Search算法的核心思想就是寻找到规划中的对称性Path并打破他们,从而避免扩展大量无用节点。
JPS的智能性体现在它遵循的Look Ahead规则,主要包含如下几条内容:
此处,假定处于栅格地图(Grid-based Map)中,且采用八联通结构以及图内无障碍物。则由上一节点抵达当前节点的情况,分直行和对角两种进行分析。
假设当前从节点抵达下一个为直行(上图所示),如图当前节点为4号节点,下一个节点为x节点。则在考虑x节点的邻居节点时,可以仅仅考虑5号节点,而不考虑其余节点。
上述遵循的筛选规则如下:
所谓劣性节点是指:从父节点(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 举例说明:
综上所述,由4号节点抵达x节点,在探索x的邻居节点时,只需要探索5号节点即可。
若如上图所示,由父节点(6号节点)抵达当前节点(x节点),则可认定节点1、4、7、8为劣性节点,其余为自然节点。
分析如下:
***此处注意,博主所学教程中未解释为何2、5节点在等同的情况下为自然节点,而非劣性节点。***对此,也许对角情况下同直行不同,特意将等同条件判定为自然而非劣性。
假设处于栅格地图环境中,且采用八联通结构并且存在障碍物情况下,依旧分直行和对角两种情况进行考虑。
如上图所示,在直行条件下,若2号节点所在栅格被障碍物占据,则3号节点的抵达无法通过 4 → 2 → 3 4\to2\to3 4→2→3进行,而必须采用 4 → x → 3 4\to x\to3 4→x→3进行。也即3号节点由劣性节点变为强迫节点,不能被抛弃。
如上图所示,在对角条件下,若4号节点所在栅格被障碍物占据,则1号节点的抵达无法通过 6 → 4 → 1 6\to4\to1 6→4→1进行,而必须采用 6 → x → 1 6\to x\to1 6→x→1进行。也即1号节点由劣性节点变为强迫节点,不能被抛弃。
对前向探索规则的学习,可知其满足如下规则:
则此时,若不断进行直行(straight pruning)或不断进行对角(diagonal pruning),则可采用跳跃规则(Jumping Rules)。
若机器人不断迭代执行直行前向规则(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 Straight),包括水平直行和垂直直行,其次再考虑对角跳跃(Jumping Diagonally)。如下图所示:
当由当前节点对角行至节点 x x x时,对其进行直行跳跃探索(图中红色虚线),由于未找到关键节点则忽略相关探索的节点,并使用对角跳跃规则至下一节点。
同样对该节点进行直行跳跃探索,由于无关键节点而再次进行对角跳跃,直至抵达节点 y y y。此时对其进行水平直行跳跃,发现节点 z z z具有强迫邻居节点,则返回至发现节点 z z z的节点 y y y,标记其为节点 x x x的关键节点(Jump Point Successor)。
JPS算法的优先级队列内元素包含两类内容:使用跳跃规则发现的关键节点(Jump Point Successor);当前探索节点 x x x的强迫邻居节点(Forced Neighbors)。
如上述对角跳跃中探索的示例图中,关键节点为 y y y、强迫邻居为 w w w,则同样将其加入优先级队列。
当前节点(绿色节点)首先进行水平、垂直直行探索,未发现关键节点;进一步进行对角探索。
对第一次探索得到的节点进行水平、垂直直行探索,未发现关键节点;进一步执行对角探索。
同第二次探索情况。
对第三次探索得到的节点执行水平直行探索时,发现一个关键节点(黄色节点),它具有强迫节点(紫色节点)。
需要注意的是,从绿色节点无法一次直接跳跃至黄色节点,跳跃的规则为只能进行一次对角跳跃或直行跳跃。
则弹出的关键节点应该为探索得到黄色节点的对角跳跃节点(下图蓝色节点)
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)+CostnmPushnodemintothequeueifg(m)>g(n)+Costnmg(m)=g(n)+CostnmendEndLoop 他们的不同在于邻居节点的定义不同:
A ∗ A^* A∗算法的邻居节点为几何意义上的邻居,而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