LLM*:路径规划的大型语言模型增强增量启发式搜索

路径规划是机器人技术和自主导航中的一个基本科学问题,需要从起点到目的地推导出有效的路线,同时避开障碍物。A* 及其变体等传统算法能够确保路径有效性,但随着状态空间的增长,计算和内存效率会严重降低。相反,大型语言模型 (LLMs) 通过上下文理解在更广泛的环境分析中表现出色,提供对环境的全局洞察。然而,它们在详细的空间和时间推理方面存在不足,通常会导致无效或低效的路线。在这项工作中,我们提出了LLM*,一种新的基于 LLM路线规划方法,它协同地结合了 A* 的精确寻路能力与 LLMs。这种混合方法旨在提高时间和空间复杂性方面的寻路效率,同时保持路径有效性的完整性,尤其是在大规模场景中。通过整合两种方法的优势,LLM* 解决了传统算法的计算和内存限制,而不会影响有效寻路所需的有效性。

 

图 1: 寻路过程中 LLM。LLM* 利用 LLMs作为路径点来指导搜索过程,显著减少了访问状态的数量,从而导致操作和存储使用量低于 A* 

路径规划是确定从初始点到目的地点的路径的计算过程,该路径符合特定标准,例如避开障碍物、最小化行驶距离或时间以及满足其他约束 LaValle (2006);Hart et al. (1968b);Karaman 和 Frazzoli (2011)。这个问题在多个领域都至关重要,例如机器人、自动驾驶汽车导航、工业自动化和虚拟环境导航,因为它直接影响操作系统的效率、安全性和可行性Thrun et al. (2005);Karaman 和 Frazzoli (2011);Fiorini 和 Shiller (1998);Fox 等 人 (1997)。

现有的路径规划算法能够有效地完成规划任务并确保其路径的有效性。然而,随着环境和地图的扩大,像 A* 及其变体这样的算法 Hart et al. (1968b);Korf 等 人(2001 年);Harabor 和 Grastien (2011);Jansen 和 Buro (2007) 遇到了计算和内存需求的指数级增长。发生这种情况是因为寻路过程可能会变得次优(参见图 1),在这种情况下,算法可能会花费不必要的精力来探索不太相关的区域,从而导致随着地图大小的扩大,时间复杂度呈指数级增加。

与此同时,大型语言模型(LLMs)在各种规划任务中取得了显着的里程碑 Naveed 等 人(2023 年);Yin 等 人(2023 年);Chen 等 人 (2023a);Shinn 等 人(2024 年);Dou 等 人 (2024)。这些模型展示了对长期上下文输入进行处理和推理的能力,以提供有价值的全局见解,以反映他们对环境的理解,例如识别障碍、代理和目标的相对位置。但是,他们难以完成复杂的长期规划和复杂的空间推理任务,例如基于格网的路径规划。LLMs 通常会生成无效或未接地的路径,导致路径不完整或发生冲突,表明它们在处理详细空间复杂性的能力方面存在差距 Aghzal et al. (2023)。

在这项工作中,我们提出了 LLM*,一种新的基于 LLM 的路线规划方法,它将传统的 A* 算法与来自大型语言模型的全局洞察力协同起来。如图 1 所示。1,这种混合方法利用LLM 生成的航点来指导路径搜索过程,从而显著降低计算和内存成本。此外,通过将 A* 的标准 L2 基于距离的启发式方法与从这些航点派生的新启发式值集成,LLM* 解决了 LLM,从而确保输出路径的有效性。

我们在各种环境中进行了广泛的实验,以比较 A* 和 LLM* (将 LLAMA3 与少数镜头提示集成)的性能。如图 3 所示,A* 在计算操作和存储需求方面呈指数级增长,环境规模呈线性增加。相比之下,LLM* 显示出近乎线性的增长模式,表明具有卓越的可扩展性。这表明 LLM* 在计算和内存方面都明显更高,使其更适合更大的环境。此外,我们的主要实验结果(如表 1 所示)表明,LLM* 不仅在可扩展性方面表现出色,而且在基线计算和内存效率方面也优于 A*。LLM* 与 A* 相比,操作和存储比率显著降低,平均需要的操作和存储不到 A* 寻路过程所需操作和存储的一半左右,从而为大规模路径规划提供了强大而高效的解决方案。

阿拉伯数字相关工作

路径规划中的传统算法。

Pathfinding 在人工智能、机器人技术和计算机图形学中一直发挥着关键作用,开发了许多算法来应对各种挑战。在基础方法中,由 Hart、Nilsson 和 Raphael 于 1968 年引入的 A* 算法因其使用启发式方法来估计从当前节点到目标节点的成本而脱颖而出,平衡了贪婪的最佳优先搜索与均匀成本搜索以实现有效的寻路Hart et al. (1968a)。同样,1984 年提出的 Pearl 最佳优先搜索 (BFS) 根据启发式值对节点进行优先级排序,但由于它专注于最有前途的节点 Pearl (1984) ,因此可能导致路径更长。

A* 的扩展旨在提高其效率和适应性。Korf 于 1985 年提出的迭代深化 A* (IDA*) 将深度优先搜索与 A* 的启发式方法相结合,创造了一种内存高效的方法 Korf (1985)。Korf 还在 1990 年推出了实时学习 A* (LRTA*),将实时学习与动态更新启发式值相结合,从而提高了在不断变化的环境中的性能 Korf (1990)。Russell 于 1992 年提出的简化内存有界 A* (SMA*) 通过选择性地忘记不太有希望的路径来解决内存限制问题,使其适用于资源有限的应用程序 Russell (1992)。

进一步的增强包括 Stentz 1994 年的动态 A* (D*),它随着环境的变化重新计算路径,证明在未知或不断发展的地形中导航有效 Stentz (1994)。Koenig 等人于 2004 年推出的终身规划 A* (LPA*) 在动态和大规模环境中逐步更新路径 Koenig 等 人 (2004)。Harabor 和 Grastien 于 2011 年提出的跳跃点搜索 (JPS) 通过识别关键的“跳跃点”来优化基于网格的地图的 A*,从而减少扩展节点的数量Harabor 和 Grastien (2011)。Nash 等人于 2007 年提出的 Theta* 允许在节点之间进行视线检查,从而产生更直接的路径 Nash 等 人 (2007)。

分层方法,例如 Holte 等人 1996 年的分层 A* (HA*),通过抽象层次结构将大型寻路问题分解为较小的子问题,从而降低了计算复杂性 Holte 等 人 (1996)。Botea 等人于 2004 年推出的分层路径查找 A* (HPA*) 改进了抽象级别之间的过渡,以实现高效的大地图路径查找 Botea 等 人(2004 年)。

专业方法也有很大贡献。Demyen 和 Buro 于 2006 年提出的基于三角测量的寻路 (TRA*) 使用三角测量来导航多边形环境,适用于非基于网格的设置 Demyen 和 Buro (2006)。Koch 于 2011 年推出的特定于网格的分层路径查找 (GHPA*) 通过集成分层和特定于网格的优化来优化网格映射寻路 Koch (2011)。

路径规划中的大型语言模型。

大型语言模型 (LLMs) 最近在自然语言处理任务和其他领域取得了显著的成功 Naveed et al. (2023)。Shridhar 等 人 (2020b);Song 等 人(2023 年);Shah 等 人(2023 年)探讨了高级规划中的 LLMs,强调了长期规划和空间推理方面的挑战 Aghzal 等 人(2023 年)。我们的研究重点转移到连续环境,与基于网格的地图相比,它提供了更逼真的设置。连续空间更符合现实世界的条件,为人类交互提供更自然的界面,并允许更高的空间推理精度。

LLMs 在空间推理方面表现出不同的熟练程度 Ilharco et al. (2020);帕特尔和帕夫利克 (2021);Bubeck 等 人(2023 年);Abdou 等 人(2021 年);Yang et al. (2023b) 在空间推理和规划方面面临局限性 Agrawal (2023);Xie et al. (2023);Wu 等 人(2023 年)。我们引入了连续环境中路径规划的基准,集成了空间和时间推理。之前的基准 Côté 等 人(2019 年);Shridhar 等 人(2020a);Ruis 等 人(2020 年);Wu et al. (2021) 经常忽视时间规划方面。我们的研究进一步评估了机器人运动和路径规划环境中的 LLMs解决了端到端规划中的局限性 Liu et al. (2023);Chen 等 人 (2023b);Xie et al. (2023);Silver 等 人(2022 年)。

了解高级别和低级别规划之间的相互作用至关重要 Latif (2024);Yang 等 人(2023a);Ding 等 人(2024 年);周 et al. (2024)。高级规划涉及战略目标,而低级规划侧重于详细的任务执行。我们的研究探讨了 LLMs 在纠正低级规划错误方面的适应性,确保动态条件下的弹性。

 

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

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

相关文章

C#基础题总结

16.一张单据上有一个5位数的号码为6**42,其中百位数和千位数已模糊不清,但知道该数能被 57 和 67 除尽。设计一个算法,找出该单据所有可能的号码。 17.编程序求2~10000以内的完全数。一个数的因子(除了这个数本身&…

Android数据存储——文件存储、SharedPreferences、SQLite、Litepal

数据存储全方案——详解持久化技术 Android系统中主要提供了3中方式用于简单地实现数据持久化功能,即文件存储、SharedPreference存储以及数据库存储。除了这三种方式外,还可以将数据保存在手机的SD卡中,不给使用文件、SharedPreference或者…

【动手学电机驱动】STM32-FOC(8)MCSDK Profiler 电机参数辨识

STM32-FOC(1)STM32 电机控制的软件开发环境 STM32-FOC(2)STM32 导入和创建项目 STM32-FOC(3)STM32 三路互补 PWM 输出 STM32-FOC(4)IHM03 电机控制套件介绍 STM32-FOC(5&…

ubuntu 安装proxychains

在Ubuntu上安装Proxychains,你可以按照以下步骤操作: 1、更新列表 sudo apt-update 2、安装Proxychains sudo apt-get install proxychains 3、安装完成后,你可以通过编辑/etc/proxychains.conf文件来配置代理规则 以下是一个简单的配置示例&…

ZooKeeper 基础知识总结

先赞后看,Java进阶一大半 ZooKeeper 官网这样介绍道:ZooKeeper 是一种集中式服务,用于维护配置信息、命名、提供分布式同步和提供组服务。 各位hao,我是南哥,相信对你通关面试、拿下Offer有所帮助。 ⭐⭐⭐一份南哥编写…

visionpro官方示例分析(一) 模板匹配工具 缺陷检测工具

1.需求:找出图像中的这个图形。 2.步骤 使用CogPMAlignTool工具,该工具是模板匹配工具,见名知意,所谓模板匹配工具就是说先使用该工具对一张图像建立模板,然后用这个模板在其他图像上进行匹配,匹配上了就说…

代码随想录算法训练营第六十天|Day60 图论

Bellman_ford 队列优化算法(又名SPFA) https://www.programmercarl.com/kamacoder/0094.%E5%9F%8E%E5%B8%82%E9%97%B4%E8%B4%A7%E7%89%A9%E8%BF%90%E8%BE%93I-SPFA.html 本题我们来系统讲解 Bellman_ford 队列优化算法 ,也叫SPFA算法&#xf…

LAMP环境的部署

一、软件安装介绍 在Linux系统中安装软件有rpm安装、yum安装、源码安装等方法,在这里主要给大家介绍 yum 安装,这是一种最简单方便的一种安装方法。 YUM(Yellow dog Upadate Modifie)是改进版的 RPM 管理器,很好地解…

搭建文件服务器并使用Qt实现文件上传和下载(带账号和密码)

文章目录 0 背景1 搭建文件服务器2 代码实现文件上传和下载2.1 在pro文件中添加网络支持2.2 创建网络管理类2.3 文件上传2.4 文件下载 3 扩展(其他方法实现文件上传和下载)3.1 python3.2 npm3.3 ftp服务器 4 完整的代码 0 背景 因为需要使程序具备在远程…

matlab导出3D彩色模型(surface类转stl,并对白模上色)

在matlab中绘制3维图形时,需要将3维图形导出到PPT中展示。但是直接导出图片效果欠佳,无法全方位展示。 最近学习了如何将matlab中的图形导出为stl模型,然后再采用简单的方法对模型上色。 中间尝试过matlab导出stl、ply、3dm等多种格式&…

Java项目中加缓存

Java项目中加缓存 1.更新频率低;但读写频率高的数据很适合加缓存; 2.可以加缓存的地方很多:浏览器的缓存;CDN的缓存;服务器的缓存; 本地内存;分布式远端缓存; 加缓存的时候不要…

VTK的基本概念(一)

文章目录 三维场景的基本要素1.灯光2.相机3.颜色4.纹理映射 三维场景的基本要素 1.灯光 在三维渲染场景中,可以有多个灯光的存在,灯光和相机是三维渲染场景的必备要素,如果没有指定的话,vtkRenderer会自动创建默认的灯光和相机。…

【C知道】数据包捕获(wire shark)

请解释一下数据包捕获和分析工具(如Wireshark)的工作原理和用途。 数据包捕获和分析工具,例如Wireshark(以前称为 Ethereal),是一种网络协议分析软件,它允许用户实时监控计算机网络中的数据传输…

浮点数计算,不丢失精度

在js中对于浮点数直接计算会存在精度丢失的情况,为了保证精度问题,可以做如下处理: 浮点数精度计算 主要流程如下: 浮点数转换成整数 示例代码如下 /** 将一个浮点数转成整数,返回整数和倍数。如 3.14 >> 314…

计算机网络八股整理(三)

目录 计算机网络八股(三)传输层1:说一下tcp的头部?2:tcp三次握手的过程说一下?拓展linux中查看tcp状态: 3:tcp为什么需要三次握手建立连接?4:tcp三次握手,如果…

C#基础控制台程序

11.有一个54的矩阵,要求编程序求出其中值最大的那个元素的值,以及其所在的行号和列号。 12.从键盘输入一行字符,统计其中有多少个单词,单词之间用空格分隔开。 13.输入一个数,判断它是奇数还是偶数,如果…

小程序-基于java+SpringBoot+Vue的微信小程序养老院系统设计与实现

项目运行 1.运行环境:最好是java jdk 1.8,我们在这个平台上运行的。其他版本理论上也可以。 2.IDE环境:IDEA,Eclipse,Myeclipse都可以。推荐IDEA; 3.tomcat环境:Tomcat 7.x,8.x,9.x版本均可 4.硬件环境&#xff1a…

LeetCode—74. 搜索二维矩阵(中等)

仅供个人学习使用 题目描述: 给你一个满足下述两条属性的 m x n 整数矩阵: 每行中的整数从左到右按非严格递增顺序排列。 每行的第一个整数大于前一行的最后一个整数。 给你一个整数 target ,如果 target 在矩阵中,返回 true…

命令行使用ssh隧道连接远程mysql

本地电脑A 跳板机B 主机2.2.2.2 用户名 B ssh端口号22 登录密码bbb 远程mysql C 地址 3.3.3.3 端口号3306 用户名C 密码ccc A需要通过跳板机B才能访问C; navicat中配置ssh可以实现在A电脑上访问C 如何实现本地代码中访问C呢? # 假设本地使…

海康VsionMaster学习笔记(学习工具+思路)

一、前言 VisionMaster算法平台集成机器视觉多种算法组件,适用多种应用场景,可快速组合算法,实现对工件或被测物的查找测量与缺陷检测等。VM算法平台依托海康威视在图像领域多年的技术积淀,自带强大的视觉分析工具库,可…