无人机避障——路径规划篇（一） JPS跳点搜索算法A*算法对比

JSP 跳点搜索算法与改进 A*算法对比

一、算法概述:

跳点搜索(Jump Point Search,JPS)算法:一种用于路径规划的启发式搜索算法。它主要用于在网格地图(如游戏地图、机器人运动规划地图等)中快速找到从起点到终点的最短路径。该算法在改进 A*算法的基础上进行了优化,通过跳过一些不必要的节点来提高搜索效率。

在网格地图中,跳点是那些能够让搜索路径跳过多个中间节点的特殊节点。这些跳点通常位于障碍物的拐角处或者是能够直接朝着目标方向前进的节点。例如,当一个节点的邻居节点能够让路径更直接地指向目标,且中间没有障碍物时,这个邻居节点就可能是一个跳点。

JPS 算法相比改进 A*算法能够显著减少搜索的节点数量。改进 A*算法需要遍历起点到终点之间的大量中间节点,而 JPS 算法通过识别跳点,能够跳过那些在最优路径上不太可能出现的节点,从而加快搜索速度。在复杂的大型网格地图中,这种效率提升尤为明显。在找到最短路径方面,JPS 算法和改进 A*算法具有相同的性能。只要启发式函数是可接受的(即不会高估节点到终点的成本),JPS 算法找到的路径也是最短路径,和改进 A*算法找到的路径长度相同。

[注意] JSP 跳点搜索算法采用曼哈顿距离，如果测试采用切比雪夫距离，速度会比用曼哈顿慢一些，但是也比改进A*算法快一个数量级左右。改进 A*算法采用切比雪夫距离测试。

二、测试结果:

任务目标:从左上角(0,0)坐标到右下角坐标,障碍物随机分布,但要保证有路径可以到达目标点,对算法的时间和轨迹长度进行记录分析。

(a)左边 JSP 算法,右边改进 A*算法,地图 50*50,障碍物数量:200

1) 时间优势明显:

从测试结果可以看出,JPS 算法在时间性能上明显优于改进 A*算法。在相同的测试环境下 ,JPS 算 法 的 运 行 时 间 仅 为 0.024201393127441406 秒 , 而 改 进 A*算 法则 需 要0.14796710014343262 秒。这表明 JPS 算法能够更快地找到路径,提高了系统的响应速度。

2) 轨迹长度一致:

测 试 结 果 还 显 示 ,JPS 算 法 和 改 进 A*算 法 规 划 出 的 轨 迹 长 度 一 致 , 均 为70.46803743153541。这说明 JPS 算法在保证高效性的同时,并没有牺牲路径的质量。它能够找到与传统算法相同的最短路径,确保了路径的最优性。

(b)左边 JSP 算法,右边改进 A*算法,地图 50*50,障碍物数量:400

1) 时间优势明显:

从测试结果可以看出,JPS 算法在时间性能上明显优于改进 A*算法。在相同的测试环境下 ,JPS 算 法 的 运 行 时 间 仅 为 0.016303300857543945 秒 , 而 改 进 A*算 法则 需 要0.29836177825927734 秒。这表明 JPS 算法能够更快地找到路径。

2) 轨迹长度近似:

测试结果还显示,JPS 算法的轨迹长度为 73.39696961966995,改进 A*算法规划出的轨迹长度 72.22539674441612,基本一致。

(c) 左边 JSP 算法,右边改进 A*算法,地图 50*50,障碍物数量:600

1) 时间优势明显:

从测试结果可以看出,JPS 算法在时间性能上明显优于改进 A*算法。在相同的测试环境下 ,JPS 算 法 的 运 行 时 间 仅 为 0.015148162841796875 秒 , 而 改 进 A*算 法则 需 要0.6297142505645752 秒。这表明 JPS 算法能够更快地找到路径,速度快了将近 40 倍。

2) 轨迹长度近似:

测试结果还显示,JPS 算法的轨迹长度为 76.32590180780447,改进 A*算法规划出的轨迹长度 75.05382386916231,基本一致,相差一个栅格距离左右。

(d) 左边 JSP 算法,右边改进 A*算法,地图 50*50,障碍物数量:800

1) 时间优势明显:

从测试结果可以看出,JPS 算法在时间性能上明显优于改进 A*算法。在相同的测试环境下 ,JPS 算 法 的 运 行 时 间 仅 为 0.013298988342285156 秒 , 而 改 进 A*算 法则 需 要0.48139333724975586 秒。这表明 JPS 算法能够更快地找到路径,速度快了将近 40 倍。

2) 轨迹长度更优:

测试结果还显示,JPS 算法的轨迹长度为 74.56854249492375,改进 A*算法规划出的轨迹长度 75.15432893255065,JSP 轨迹长度更优,轨迹距离基本一致。

(e) 左边 JSP 算法,右边改进 A*算法,地图 50*50,障碍物数量:1000

1) 时间优势明显:

从测试结果可以看出,JPS 算法在时间性能上明显优于改进 A*算法。在相同的测试环境下 ,JPS 算 法 的 运 行 时 间 仅 为 0.024592161178588867 秒 , 而 改 进 A*算 法则 需 要2.0019431114196777 秒。这表明 JPS 算法能够更快地找到路径,速度快了将近 80 倍。

2) 轨迹长度更优:

测试结果还显示,JPS 算法的轨迹长度为 83.74011537017756,改进 A*算法规划出的轨迹长度 85.39696961966993,JSP 轨迹长度更优,更加明显。

(f) 左边 JSP 算法,右边改进 A*算法,地图 100*100,障碍物数量:1000

1) 时间优势明显:

从测试结果可以看出,JPS 算法在时间性能上明显优于改进 A*算法。在相同的测试环境下 ,JPS 算 法 的 运 行 时 间 仅 为 0.057212114334106445 秒 , 而 改 进 A*算 法则 需 要1.4029386043548584 秒。这表明 JPS 算法能够更快地找到路径,速度快了将近 30倍。

2) 轨迹长度较长:

测试结果还显示,JPS 算法的轨迹长度为 149.6223663640861,改进 A*算法规划出的轨迹长度 143.5218613006978,改进 A*算法轨迹长度更优,更加明显。

(g) 左边 JSP 算法,右边改进 A*算法,地图 100*100,障碍物数量:2000

1) 时间优势明显:

从测试结果可以看出,JPS 算法在时间性能上明显优于改进 A*算法。在相同的测试环境下 ,JPS 算 法 的 运 行 时 间 仅 为 0.04240727424621582 秒 , 而 改 进 A*算 法 则需 要5.168658018112183 秒。这表明 JPS 算法能够更快地找到路径,速度超过了 100 倍。

2) 轨迹长度较长:

测试结果还显示,JPS 算法的轨迹长度为 152.30865786510137,改进 A*算法规划出的轨迹长度 148.45079348883237,改进 A*算法轨迹长度更优,但是差距不大。

(h) 左边 JSP 算法,右边改进 A*算法,地图 100*100,障碍物数量:4000

1) 时间优势明显:

从测试结果可以看出,JPS 算法在时间性能上明显优于改进 A*算法。在相同的测试环境下 ,JPS 算 法 的 运 行 时 间 仅 为 0.03251481056213379 秒 , 而 改 进 A*算 法 则需 要8.00110912322998 秒。这表明 JPS 算法能够更快地找到路径,速度超过了 260 倍。

2) 轨迹长度接近:

测试结果还显示,JPS 算法的轨迹长度为 158.99494936611666,改进 A*算法规划出的轨迹长度 157.86500705120545,差距不大。

(i)左边 JSP 算法,右边改进 A*算法,地图 100*100,障碍物数量:5000

1) 时间优势明显:

从测试结果可以看出,JPS 算法在时间性能上明显优于改进 A*算法。在相同的测试环境下 ,JPS 算 法 的 运 行 时 间 仅 为 0.18164896965026855 秒 , 而 改 进 A*算 法 则需 要20.16622757911682 秒。这表明 JPS 算法能够更快地找到路径,速度超过了 110 倍。

2) 轨迹长度较长:

测试结果还显示,JPS 算法的轨迹长度为 196.45079348883257,改进 A*算法规划出的轨迹长度 182.6934341759518,改进 A*算法距离上具有优势。

三、结论:

        JPS 算法在路径规划中展现出明显优势。与改进 A*算法相比,JPS 算法运算时间极快,无论地图成倍扩大还是障碍物成数量级增加,其运算速度都保持较高水平,而改进 A*算法在地图和障碍物变复杂后,计算速度落后 JPS 算法一到两个数量级。从轨迹长度看,虽然任务复杂度提升后 JPS 轨迹长度整体略长于改进 A*算法,但差距不大。JPS 算法通过识别跳点,快速跳过不必要节点,减少搜索空间,提高搜索效率,同时保证找到的路径为最短路径,具有高效性、准确性和适应性。