【《基于栅格地图的改进JPS路径规划算法的实验探究报告》4900字（论文）】

基于栅格地图的改进JPS路径规划算法的实验探究报告目录TOC\o"1-3"\h\u273841.1JPS算法 [45]。该方法消除了A*算法在对称路径上所进行的无用搜索的带来的影响，通过检测到那些在栅格地图中可能构成最终路径的转折点，并将之加入openlist进行处理，因此搜索十分高效。同A*算法类似的是，JPS也维护一个开放集，并且使用和A*算法类似的评价函数从openlist中选出代价最低的节点。但有别于A*算法每次拓展所有可达节点的做法，JPS在沿着直线搜索时，会构建一个行/列向量，并从该向量中识别出那些关键点(跳跃点)，即进行“剪枝”，剪掉非关键点。通过这种方式每次只扩展那些可能产生方向变化的点，并将这些关键点加到openlist中。JPS算法向前搜索的过程中都是由一个跳跃点跳至另一个跳跃点，因此极大地提高了搜索效率。这也是该算法的关键之处，避免在一些可能造成对称路径的地图上遍历过多的无用节点。1.1.1JPS算法原理JPS算法在地图模型中节点的搜索时，必须严格遵守“跳跃规则”。跳跃规则的前提是在已知的地图模型中建立节点之间的位置关系，根据节点的位置关系判断节点的周围是否存在跳跃节点。其关键在于剪枝的过程，涉及到特有的“两个规则，三个定义”。在搜索地图模型中的节点时，JPS算法需要遵循“跳跃规则”才能实现搜索效率的提升。该规则建立在已知的栅格地图中节点的位置关系已知的前提下，根据节点之间的位置关系来确定是否要进行修剪和跳跃的操作。该算法的关键是“剪枝”这一操作，涉及到的“两个规则，三个定义”如下文所述。对于八方向扩展的JPS算法而言，存在直线、对角线两种运动方向，定义直线运动所需的代价为10，对角线运动所需的代价为14。定义节点x为当前节点，它的父节点是px1）规则一，直线移动剪枝在直线运动中，对于n∈neighbours(x)的节点，修剪任何满足式（1.1）约束的当前节点的邻节点： (1.1)其中，π'为从节点px出发不经过节点x到节点n的路径，π为从点px出发经过节点2）规则二，对角线移动剪枝这种情况类似于直线移动剪枝，唯一不同的是，对角线移动剪枝剪除x的路径必须是严格占优的，如式（1.2）所示： (1.2)同上，π'为从点px出发不经过节点x到节点n的路径，π为从点px出发经过节点通过上述两个规则，可以识别和消除搜索空间对称的路径，减少JPS算法在运行过程中对非关键节点处理的数量。(a)(b)图1.SEQ图3.\*ARABIC1对称路径剔除原理图(a)直线移动剪枝(b)对角线移动剪枝Fig1.1Symmetricpatheliminationschematicdiagram(a)Straightmovingpruning(b)Diagonalmovingpruning图1.1(a)为水平向右搜索的修剪情况。根据直线移动剪枝规则，节点4和节点3之间存在两条最优路径和，其中路径没有经过节点，因此3被剪除。同理在图1.1(a)中剪除所有的灰色节点。图1.1(b)为沿右上对角线方向搜索的剪除情况。根据对角线移动剪枝规则，7和9间存在唯一的最优路径，且路径π'不经过节点，因此9被剪除。而7和6间存在最优路径和，因此8被剪除。若节点是开始节点，则节点为空，不剪除任何节点。3）定义一，自然邻节点假设的相邻节点不包含障碍，把应用剪枝规则后保留下来的节点称为的自然邻节点。这些对应于图1.1中由白色区域。4）定义二，强制邻节点(a)(b)图1.SEQ图3.\*ARABIC2强制邻节点确定示意图(a)直线移动情况(b)对角线移动情况Fig1.2Forceneighbornodetodetermineschematicdiagram(a)Straightmoving(b)Diagonalmoving若当前节点的邻节点包含障碍时，无法剪除所有非自然邻节点。图1.2为节点邻域内存在障碍物的情况。对于任一的节点，若其不是节点的自然邻节点，且满足式（1.3），则称该节点为强制邻节点。强制邻节点无须剪除。 (1.3)如图1.2(a)中直线移动情况，由于邻域中存在障碍物，4和3间存在唯一最优路径，因此位置3为强制邻节点。同理，图1.2(b)中位置1为强制邻节点。3）定义三，跳点A*算法以当前节点的八方向邻节点为拓展备选节点，通过比较这些备选节点的代价函数fn令表示水平和竖直搜索方向集合，如果节点以最小的移动步数使，且满足下列条件之一，则节点是从节点沿方向出发的跳点：节点是目标节点；节点至少有一个强制邻节点；若为对角线移动方向，并且存在节点或可满足条件1或条件2，则节点为跳点，节点为其前继跳点。其中，为移动步数。图1.SEQ图3.\*ARABIC3跳点移动规则示意图Fig1.3Schematicdiagramofjumpingpointmovementrules如果当直线运动（水平或垂直方向）和对角线运动可以同时开展时，优先进行直线运动，只有当目前节点直线运动未搜索到跳点时，再进行对角线运动，并且每进行一次对角线运动后，会在该节点处再次进行直线运动搜索跳点，直至找到下个跳点。如图1.3所示，从节点px处先展开直线运动，当移动至障碍物/边界后，沿对角线移动一步，再展开直线运动。直到节点处，发现后继节点有一个强制邻节点，则节点是跳点。将跳点加入openlist，对于openlist中的所有节点，参考式（2.1）并采用曼哈顿距离计算其距离代价估计值。根据代价函数的值按照大小对openlist列表中所有节点进行排序，均选取代价值最小的节点作为下一个当前节点再次进行剪枝和跳点搜索，直到搜索到的跳点为目标节点时停止。从目标节点开始由其parents指针的指向反溯至起点，即可得到一条可行路径。图1.4为同样的环境设置下，A*算法与JPS算法搜索过程对比示意图。其中起点用绿色栅格表示，终点用红色栅格表示，closelist中的节点用灰色栅格表示，openlist中的节点用紫色栅格表示。当终点加入closelist中时,由终点的parents指针向前回溯，直至寻找到起点，此时从起点至终点的路径便组成了。由图可见JPS搜索算法要高效的多。(a)(b)图1.SEQ图3.\*ARABIC4两种算法搜索过程对比示意图(a)A*算法搜索过程(b)JPS算法搜索过程Fig1.4Comparisondiagramofsearchprocessoftwoalgorithms(a)A*algorithmsearchprocess(b)JPSalgorithmsearchprocess1.2JPS算法的改进JPS算法能够提升搜索效率的关键在于其算法中对跳点的设计。由1.1节中介绍的JPS算法原理可知，跳点是该路径中可能会发生转折的节点。相较于A*算法把每个节点的8个邻节点都加入openlist中的方式，JPS算法仅仅将搜索到的跳点加入openlist。这样一来对openlist进行插入节点与删除节点的操作次数会大幅减少。并且因为openlist中的节点数量大大减少，每次查找具有最小代价值的节点也会更加省时。虽然JPS算法相较于A*算法已经极大的提升了搜索效率，但是对于障碍物繁多的复杂地图上，比如在图1.5所示的随机地图上，搜索时间仍然较长。根据JPS算法的搜索规则，在沿着当前节点的搜索方向搜索节点时，若是节点的八邻域中存在障碍物，则该节点具有强制邻节点。根据跳点定义的第二条，则该节点为跳点，需要加入openlist。结合图1.4分析JPS算法效率降低的原因是，由于障碍物的数量多而杂乱，那么产生的强制邻节点的数量也会相应地增多，对应的跳点的数量也会增多。那么JPS算法的核心——减少对openlist的操作的效果就会大打折扣。对此，本文提出了一种改进的JPS算法。图1.SEQ图3.\*ARABIC5随机地图Fig1.5Randommap针对使用传统JPS算法在在障碍物随机分布的地图上会产生过多跳点，导致规划路径耗时变长的问题，所以必须要对跳跃规则进行优化。因为地图中的障碍物繁多，所以此时的跳点只有部分是使路径产生转折的节点，而另一部分则是受到障碍物干扰的“错误”跳点。在原始JPS算法的跳跃规则中，从当前节点进行剪枝操作时，不管修剪方向是对角线还是直线，都将转化为直线修剪，当遇到可跳跃节点时，返回该节点并计算其代价值。因此将跳跃规则优化为当在openlist中选出代价值最小的节点作为当前节点时，沿当前节点的搜索方向进行跳跃，在这个过程中停止搜索跳点，直到遇到障碍物时，再返回该节点，将其加入openlist并计算其代价值。使用这种方式可以有效减小干扰障碍物的影响，使openlist中的节点得到有效的减少，使算法的实时性得到提高。如图1.6所示，为一随机地图的局部，假设px处为一当前节点。传统JPS算法中，搜索到节点a有两个强制邻节点b和c，所以节点a是跳点，并加入openlist。由于h(n)采用曼哈顿距离，选择节点a作为当前节点，将节点b和节点c加入openlist。继续搜索出节点e有强制邻节点d，所以节点e是跳点，加入openlist。选择节点e作为当前节点，将节点d加入openlist，并搜索出节点x有强制邻节点f，所以节点x是跳点，加入openlist改进JPS算法在选择节点a的对角线方向扩展时，则会一直扩展直到遇到障碍物，并将节点x加入openlist。由于减少了部分搜索和对于openlist及closelist的操作，实时性得到极大提升。图1.SEQ图3.\*ARABIC6改进JPS算法示意图Fig1.6ImprovedJPSalgorithmschematicdiagram程序流程图如图1.7所示。图1.SEQ图3.\*ARABIC7改进JPS算法程序流程图Fig1.7FlowchartoftheimproveJPSalgorithm1.3实验结果与分析为评估本文改进后的JPS算法性能，在同一栅格地图上同时使用A∗算法、JPS算法和本文提出的改进JPS算法进行全局路径规划实验。实验所使用的计算机配置为Windows10操作系统，处理器为Inteli5-9600K，主频1.7GHz，运行内存8G，实验环境为VisualStudio2019。随机生成了100*100,200*200,300*300,400*400,500*500大小的栅格地图各10张，障碍率约为10%。在仿真中分别使用以上地图进行路径规划实验，并以程序运行时间、路径长度、openlist和closelist中的节点个数作为评价指标来评判算法的优劣。图1.SEQ图3.\*ARABIC8100*100随机地图Fig1.8100*100Randommap图1.7所示为在100*100的栅格地图中的仿真实验结果。（3，4）为起始点，（94，92）为目标点，水平移动1栅格的距离代价为10，对角线方向移动1栅格的距离代价为14。其中，A*算法生成的路径长度为1304，程序运行时间为15ms，openlist中的节点个数为320，closelist中的节点个数为102，共422个节点；JPS算法生成的路径长度为1310，程序运行时间为4ms，openlist中的节点个数为139，closelist中的节点个数为68，共207个节点；改进JPS算法生成的路径长度为1292，程序运行时间为1ms，openlist中的节点个数为53，closelist中的节点个数为30，共83个节点。为了验证算法的重复性，生成10个不同的100*100大小的随机地图，仿真结果如表1.1、表1.2和表1.3所示。表1.SEQ表3.\*ARABIC1A*算法、JPS算法、改进JPS算法运行时间对比结果Table1.1A*algorithm,JPSalgorithm,improvedJPSalgorithmrunningtimecomparisonresults序号A*（ms）JPS（ms）im-JPS（ms）A*/JPSA*/JPS地图11231412地图21231412地图314314.66714地图416315.33316地图513304.33313地图613411.2513地图719414.7519地图814304.66714地图913304.33313地图101230412平均11.81.20.64.31323表1.SEQ表3.\*ARABIC2A*算法、JPS算法、改进JPS算法路径长度对比结果Table1.2A*algorithm,JPSalgorithm,improvedJPSalgorithmpathlengthcomparisonresults序号A*JPSim-JPSA*/JPSA*/JPS地图11308133813260.9780.986地图21290133413280.9670.971地图313101310131011地图41326135613640.9780.972地图513341334133411地图61310138013420.9490.976地图71308133413340.9810.981地图81332132613261.0051.005地图91344135013320.9961.009地图101296130813160.9910.985平均1315.813371331.20.9840.988表1.SEQ表3.\*ARABIC3A*算法、JPS算法、改进JPS算法扩展节点数量对比结果Table1.3A*algorithm,JPSalgorithm,improvedJPSalgorithmexpansionnodenumberscomparisonresults序号A*（个）JPS（个）im-JPS（个）A*/JPSA*/JPS地图1425203782.9345.449地图2420208732.0195.753地图3441215642.0516.891地图44222061122.0491.768地图5421214741.9675.68