无人机避障——路径规划篇(一) 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 算法通过识别跳点,快速跳过不必要节点,减少搜索空间,提高搜索效率,同时保证找到的路径为最短路径,具有高效性、准确性和适应性。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/908242.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

【热门主题】000027 React:前端框架的强大力量

前言:哈喽,大家好,今天给大家分享一篇文章!并提供具体代码帮助大家深入理解,彻底掌握!创作不易,如果能帮助到大家或者给大家一些灵感和启发,欢迎收藏关注哦 💕 目录 【热…

win11安装最新rabbitmq

1、安装Erlang 注意:RabbitMQ需要Erlang支持,所以要先安装Erlang,安装RabbitMQ版本需要与之对应的Erlang版本才行查看对应的RabbitMQ对应的Erlang 版本下载Erlang 2、安装RabbitMQ 下载 RabbitMQ Erlang和RabbitMQ安装过程一直点下一步…

distrobox install in ubuntu 22.04 / 在 ubuntu 22.04 上安装 distrobox (***) OK

要点: 本测试实验,采用的是 podman distrobox 在沙盒 snap 中,安装 distrobox 需要使用 --devmode 开发模式;可以避开 distrobox 的版本检查? distrobox 官方文档显示, Installation https://distrobox.i…

leetcode203. Remove Linked List Elements

给你一个链表的头节点 head 和一个整数 val ,请你删除链表中所有满足 Node.val val 的节点,并返回 新的头节点 。 Given the head of a linked list and an integer val, remove all the nodes of the linked list that has Node.val val, and return …

计算机前沿技术-人工智能算法-大语言模型-最新研究进展-2024-10-31

计算机前沿技术-人工智能算法-大语言模型-最新研究进展-2024-10-31 目录 文章目录 计算机前沿技术-人工智能算法-大语言模型-最新研究进展-2024-10-31目录1. Large Language Models for Manufacturing摘要创新点算法模型实验效果(包含重要数据与结论)推荐…

【AI工作流】FastGPT - 深入解析FastGPT工作流编排:从基础到高级应用的全面指南

文章目录 一、工作流编排概述二、FastGPT的节点类型1. 基础功能插件(1) 文本输出(2) 功能调用(3) 工具(4) 外部调用(5) 其他 2. 系统插件3. 团队插件 三、工作流中的流向结语 在当今快速发展的人工智能领域,工作流编排的能力已成为提升用户体验和应用效率的关键因素…

NVR批量管理软件/平台EasyNVR多个NVR同时管理支持对接阿里云、腾讯云、天翼云、亚马逊S3云存储

随着云计算技术的日益成熟,越来越多的企业开始将其业务迁移到云端,以享受更为灵活、高效且经济的服务模式。在视频监控领域,云存储因其强大的数据处理能力和弹性扩展性,成为视频数据存储的理想选择。NVR批量管理软件/平台EasyNVR&…

光通信——WDM/DWDM/CWDM

一、WDM 波分复用原理:将光纤的低损耗窗口可使用的光谱带宽分割为若干子带宽,然后将待传递的电信号调制到各个子带宽的中心波长光载波上同时传输,是一种能在一根光纤中同时实现多波长信道传输的扩容技术。 WDM复用系统可以分为单向和双向两种…

优化EDM邮件营销,送达率与用户体验双赢

EDM邮件营销需选对平台,优化邮件列表,确保内容优质,进行邮件测试,关注用户反馈调整频率,以保高送达率,提升营销效果。 1. 了解电子邮件送达率的重要性 在开始优化邮件送达率之前,首先需要理解电…

TypeScript起航篇·何为TypeScript?

你好,我是安然无虞。 文章目录 什么是 TypeScriptTypeScript 的特性类型系统TypeScript 是静态类型TypeScript 是弱类型总结: 什么是 TypeScript Hello TypeScript 什么是 TypeScript Typed JavaScript At Any Scale. 添加了类型系统的JavaScript,适用…

鸿蒙系统的优势 不足以及兼容性与未来发展前景分析

2024 年 10 月 22 日:华为正式发布原生鸿蒙操作系统 HarmonyOS next,并正式命名为 HarmonyOS 5,这是鸿蒙系统史上最大的升级,实现了国产操作系统从底层架构到应用生态的全面自主可控。 鸿蒙系统与安卓、iOS 相比,具有…

基于凌鸥LKS32MC037鱼缸用FOC潜水泵控制器

随着老百姓生活水平的提高,室内养殖观赏型鱼类的人越来越多,这就催生了鱼缸内小型潜水泵的市场发展。 早期鱼缸潜水泵都采用的方波驱动的控制器。随着技术的进步和芯片成本的下降,本文介绍的基于无感FOC算法潜水泵控制器已经成熟应用并且大批…

WMV怎么转MP4?五个简单好用的视频格式转换方法!

WMV格式,全称为Windows Media Video,是由微软公司开发的一种视频文件格式。采用先进的视频压缩技术,能够在保持较高视觉质量的同时,显著减小文件体积,经常被用于在网络环境下即时观看或收听高质量的音视频内容。同时&a…

unity搭建场景学习

unity搭建场景学习 创建场景创建gameobject创建材质,用于给gameobject上色拖拽材质球上色上色原理设置多个材质方式设置贴图的方式 效果设置光滑度一些预览设置菜单渲染模型与碰撞模型网格渲染参数1. materials(材质)2. lighting(光照)3. reflection probes(反射探针…

C++ Qt

一、概念 跨平台的图形应用界面应用程序框架。 二、常用快捷键 快捷键解释F4在对应的.cpp和.h之间快速切换ctrl b编译程序ctrl r运行程序ctrl shift ↑ / ↓向上 / 下移动选中的代码ctrl i自动对齐选中的代码 三、对象树 总结:父控件被析构,包含…

爬虫笔记22——当当网图书详情页静、动态数据爬取

当当网动态数据爬取 静态数据爬取动态数据爬取接口参数的获取 静态数据爬取 进入图书详情,这里的图书数据信息比如标题、价格、图片都是非结构化数据,可以使用xpath语法提取。是很简单的数据采集了,就不细说了。 动态数据爬取 滑到下面这里的…

zip文件加密成图片文件-到解密

加密 1,准备:图片 zip文件 2,新建一个.txt 根据自己的对应文件修改: copy 图片名.后缀/b压缩包名.后缀自定义图片名.后缀注意,图片后缀最后保持一至,测试了 jpg png 压缩包 zip 3,把上…

【深度学习】Bert下载和使用(以bert-base-uncased为例)

【深度学习】Bert下载和使用(以bert-base-uncased为例) 代码报错报错原因解决方法解决步骤1.进入Hugging Face,检索bert-base-uncased2.点击Files and versions3.下载文件4.下载的文件放入文件夹5.代码修改 代码报错 bert BertModel.from_p…

Java基于SpringBoot 的校园外卖点餐平台微信小程序(附源码,文档)

大家好,我是Java徐师兄,今天为大家带来的是Java基于SpringBoot 的校园外卖点餐平台微信小程序。该系统采用 Java 语言 开发,MySql 作为数据库,系统功能完善 ,实用性强 ,可供大学生实战项目参考使用。 博主介…

ES索引:索引管理

索引管理 再讲索引(Index)前,我们先对照下 ElasticSearch Vs 关系型数据库: PUT /customer/_doc/1 {"name": "DLBOY" }系统默认是自动创建索引的 如果我们需要对这个建立索引的过程做更多的控制&#xff1a…