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 在纠正低级规划错误方面的适应性,确保动态条件下的弹性。

 

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【Db First】.NET开源 ORM 框架 SqlSugar 系列

.NET开源 ORM 框架 SqlSugar 系列 【开篇】.NET开源 ORM 框架 SqlSugar 系列【入门必看】.NET开源 ORM 框架 SqlSugar 系列【实体配置】.NET开源 ORM 框架 SqlSugar 系列【Db First】.NET开源 ORM 框架 SqlSugar 系列【Code First】.NET开源 ORM 框架 SqlSugar 系列【数据事务…

企业品牌曝光的新策略:短视频矩阵系统

企业品牌曝光的新策略:短视频矩阵系统 在当今数字化时代,短视频已经渗透到我们的日常生活之中,成为连接品牌与消费者的关键渠道。然而,随着平台于7月20日全面下线了短视频矩阵的官方接口,许多依赖于此接口的小公司和内…

006 MATLAB编程基础

01 M文件 MATLAB输入命令有两种方法: 一是在MATLAB主窗口逐行输入命令,每个命令之间用分号或逗号分隔,每行可包含多个命令。 二是将命令组织成一个命令语句文集,使用扩展名“.m”,称为M文件。它由一系列的命令和语句…

Java基于SpringBoot+Vue的IT技术交流和分享平台(附源码+lw+部署)

博主介绍:✌程序员徐师兄、7年大厂程序员经历。全网粉丝30W、csdn博客专家、掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域和毕业项目实战✌ 🍅文末获取源码联系🍅 👇🏻 精彩专栏推荐订阅👇…

【计算机网络】实验3:集线器和交换器的区别及交换器的自学习算法

实验 3:集线器和交换器的区别及交换器的自学习算法 一、 实验目的 加深对集线器和交换器的区别的理解。 了解交换器的自学习算法。 二、 实验环境 • Cisco Packet Tracer 模拟器 三、 实验内容 1、熟悉集线器和交换器的区别 (1) 第一步:构建网络…

UICollectionView在xcode16编译闪退问题

使用xcode15运行工程,控制台会出现如下提示: Expected dequeued view to be returned to the collection view in preparation for display. When the collection views data source is asked to provide a view for a given index path, ensure that a …

Proteus8.17下载安装教程

Proteus是一款嵌入式系统仿真开发软件,实现了从原理图设计、单片机编程、系统仿真到PCB设计,真正实现了从概念到产品的完整设计,其处理器模型支持8051、HC11、PIC10/12/16/18/24/30/DsPIC33、AVR、ARM、8086和MSP430等,能够帮助用…

Vue教程|搭建vue项目|Vue-CLI2.x 模板脚手架

一、项目构建环境准备 在构建Vue项目之前,需要搭建Node环境以及Vue-CLI脚手架,由于本篇文章为上一篇文章的补充,也是为了给大家分享更为完整的搭建vue项目方式,所以环境准备部分采用Vue教程|搭建vue项目|V…

一款支持80+语言,包括:拉丁文、中文、阿拉伯文、梵文等开源OCR库

大家好,今天给大家分享一个基于PyTorch的OCR库EasyOCR,它允许开发者通过简单的API调用来读取图片中的文本,无需复杂的模型训练过程。 项目介绍 EasyOCR 是一个基于Python的开源项目,它提供了一个简单易用的光学字符识别&#xff…

cocotb pytest

打印python中的print , 应该使用 pytest -s

【C++】STL——map和set

目录 1、序列式容器和关联式容器前 2、set 2.1 set类的介绍 2.2 set的构造和迭代器 2.3 set的增删查 set 的插入 set的查找 set的删除 2.4 multiset和set的差异 3、map 3 .1 pair类型 3.2 map的构造 3.3 map的增删查 map的构造遍历 map的插入 map的删除 map的查…

java基础概念46-数据结构1

一、引入 List集合的三种实现类使用了不同的数据结构! 二、数据结构的定义 三、常见的数据结构 3-1、栈 特点:先进后出,后进先出。 java内存容器: 3-2、队列 特点:先进先出、后进后出。 栈VS队列-小结 3-3、数组 3-…

Docker:在 ubuntu 系统上生成和加载 Docker 镜像

本文将介绍在 ubuntu系统上进行 Docker 镜像的生成和加载方法和代码。 文章目录 一、下载和安装 docker二、加载 docker 文件三、保存你的镜像四、将镜像上传到云端并通过连接下载和加载 Docker 镜像五、Docker 容器和本地的文件交互5.1 从容器复制文件到本地宿主机5.1.1 单个文…

《数据挖掘:概念、模型、方法与算法(第三版)》

嘿,数据挖掘的小伙伴们!今天我要给你们介绍一本超级实用的书——《数据挖掘:概念、模型、方法与算法》第三版。这本书是数据挖掘领域的经典之作,由该领域的知名专家编写,系统性地介绍了在高维数据空间中分析和提取大量…

做异端中的异端 -- Emacs裸奔之路4: 你不需要IDE

确切地说,你不需要在IDE里面编写或者阅读代码。 IDE用于Render资源文件比较合适,但处理文本,并不划算。 这的文本文件,包括源代码,配置文件,文档等非二进制文件。 先说说IDE带的便利: 函数或者变量的自动…

【C++】编程题目分析与实现回顾:从浮点数运算到整型转换的全面解读

博客主页: [小ᶻ☡꙳ᵃⁱᵍᶜ꙳] 本文专栏: C 文章目录 💯前言💯题目一:计算成绩问题分析与优化实现优化后的实现优势 💯题目二:浮点数向零舍入不同实现方式的比较1. 使用强制类型转换 (int)2. 使用标准…

时间表格Java

输入:XXX XXX 小时 分钟 输出: XXX:XXX ~ XXX: XXX XXX:XXX ~ XXX: XXX XXX:XXX ~ XXX: XXX 处理:间隔五分钟、区间45分钟 14:15 ~ 15:0 15:5 ~ 15:50 15:55 ~ 16:40 16:45 ~ 17:30 17:35 ~ 18:20…

Spring AOP 的实现和切点表达式的介绍

1. 快速入手 AOP:就是面相切面编程,切面指的就是某一类特定的问题,也可以理解为面相特定方法编程,例如之前使用的拦截器,就是 AOP 思想的一种应用,统一数据返回格式和统一异常处理也是 AOP 思想的实现方式…

shell脚本30个案例(五)

前言: 通过一个多月的shell学习,总共写出30个案例,分批次进行发布,这次总共发布了5个案例,希望能够对大家的学习和使用有所帮助,更多案例会在下期进行发布。 案例二十一、系统内核优化 1.问题&#xff1…

一文解析Kettle开源ETL工具!

ETL(Extract, Transform, Load)工具是用于数据抽取、转换和加载的软件工具,用于支持数据仓库和数据集成过程。Kettle作为传统的ETL工具备受用户推崇。本文就来详细说下Kettle。 一、Kettle是什么? Kettle 是一款开源的 ETL&#x…