大语言模子遇上寻路算法：LLM-A*如何让路径规划效率提拔50%？ ...

导读：
  这篇论文介绍了一种名为LLM-A*的新型路径规划算法，它团结了传统A*算法和大语言模子(LLM)的优点。紧张创新点在于：
  （1）将LLM的全局理解本领与A*算法的正确寻路本领相团结；
  （2）显著低沉了计算本钱和内存占用；
  （3）在保持路径有效性的同时进步了算法效率；
  （4）特别适合大规模场景的路径规划。
  ©️【深蓝AI】编译
论⽂题目：LLM-A*: Large Language Model Enhanced Incremental Heuristic Search on Path Planning
论文作者：Silin Meng, Yiwei Wang, Cheng-Fu Yang, Nanyun Peng, Kai-Wei Chang
论文地址：https://arxiv.org/abs/2407.02511?context=cs.CL

1、研究背景

路径规划作为机器人和自主导航领域的一个基础性科学问题，一直是研究的重点。它的焦点任务是在给定情况中找到一条从出发点到尽头的有效路径，同时需要避开停滞物、优化路径长度等。这个问题之所以云云紧张，是因为它直接关系到机器人系统、主动驾驶系统、工业主动化设备以及虚拟情况导航等领域的效率、安全性和可行性。
在传统的路径规划方法中，A算法及其变体虽然能够有效地完成规划任务并确保路径的有效性，但它们面临着一个严峻的问题：随着情况和地图规模的扩大，算法的计算本钱和内存需求呈指数级增长。这紧张是因为算法在搜索过程中可能会在一些不太相干的区域花费过多的计算资源，导致整体效率低下。如图1所示，传统A算法在处理同样的路径规划任务时，需要探索大量的状态节点。
比年来，大语言模子(LLM)在各类规划任务中显现出了令人瞩目的效果。这些模子能够处理和理解长文本输入，并通过对情况的整体理解提供有代价的全局性看法，比方识别停滞物、署理和目的的相对位置关系。然而，LLM在处理具体的路径规划任务时也显暴露显着的短板：它们在处理复杂的长期规划和正确的空间推理任务时表现欠佳，往往会生成无效或效率不高的路径。
纵观路径规划算法的发展汗青，我们可以看到一系列紧张的突破。1968年提出的A算法开创性地引入了启发式函数来估算从当前节点到目的的本钱。随后，1984年的最佳优先搜索(BFS)通过优先选择最有希望的节点来改进搜索效率。1985年的迭代深化A(IDA*)巧妙地团结了深度优先搜索和A的启发式方法。1990年的实时学习A(LRTA*)引入了实时学习机制来动态更新启发式值。这些算法的演进展示了研究者们在进步路径规划效率方面的不懈努力。
在处理大规模情况时，研究者们提出了一系列创新方法。比方，1996年提出的HA*实验将大型路径规划问题分解为较小的子问题。2004年的HPA*着重改进了抽象层次之间的转换效率。2011年的JPS通过识别关键的"跳跃点"来显著淘汰需要扩展的节点数量。这些方法都在特定场景下取得了不错的效果。
最新的研究趋势是将大语言模子应用到路径规划中。虽然LLM在处理天然语言规划任务方面表现出色，但在具体的空间推理和路径规划任务中仍面临挑衅。这些挑衅包罗难以处理端到端的规划、空间和时序推理本领有限，以及可能产生不切实际的路径等。一个紧张的研究方向是探索如何将高层规划（关注战略性目的）和低层规划（专注于具体任务执行）有效团结，特别是研究LLM在协助改正低层规划错误方面的潜力。
正是基于对现有方法优缺点的深入理解，作者提出了创新性的LLM-A算法。这种方法巧妙地团结了LLM的全局理解本领和A的正确寻路本领。实验效果表明，与传统A相比，LLM-A在保持路径质量的同时，显著低沉了计算本钱和内存需求，为解决大规模路径规划问题提供了一个新的有效方案。

▲图1 | LLM-A*和A*在寻路过程中的计算和内存效率的比较。©️【深蓝AI】编译

2、研究方法

2.1 A*算法

A*算法作为一种广泛利用的路径搜索和图遍历算法，通过巧妙地团结Dijkstra算法和贪婪最佳优先搜索的优势，在路径规划领域占据着紧张地位。它的焦点思想是在搜索过程中同时思量已知的路径本钱和对未来路径的估计，从而在包管找到最优路径的同时，进步搜索效率。
在A*算法的框架中，利用了两个关键的评估函数来指导搜索过程。启发式函数h(s)负责估算从当前节点到目的节点的本钱，这个估算值需要保持"可接受性"，即不能高于实际本钱。代价函数g(s)则正确记录从起始节点到当前节点的实际路径本钱。这两个函数共同构成了总本钱函数f(s)，即f(s)=g(s)+h(s)，用于在搜索过程中选择最有希望的扩展节点。
在实际应用中，A*算法的效率很大程度上取决于启发式函数的选择。一个好的启发式函数应该既能正确估计到目的的距离，又不会过高估计实际本钱。在一样平常的路径规划问题中，欧几里得距离（直线距离）大概曼哈顿距离常被用作启发式函数，因为它们都满意不会高估实际路径长度的要求。
2.2 LLM-A*算法

LLM-A*算法是对传统A算法的创新性扩展，它将大语言模子的全局洞察本领与A算法的正确当地搜索机制相团结，从而在保持路径有效性的同时进步搜索效率。如图2所示，这个算法在生存A基本框架的同时引入了几个关键的创新点。 首先，LLM-A*在输入层面就有所创新。
除了与A相同的基本输入外，算法还引入了一个停滞物状态变量obs。这个变量被用来生成TARGET的列表T，这个列表包含了从出发点到尽头的一系列路径节点，是通过向大语言模子提供当前情况信息生成的。TARGET列表必须满意两个紧张束缚：一是必须包含实际的出发点和尽头（如果生成的列表不满意这个要求，算法会主动插入起尽头），二是全部目的点都不能位于停滞物内（如果发现目的点与停滞物重叠，该点会被主动移除）。
在搜索过程中，LLM-A*算法采用了一种独特的机制。它利用了与A相似的启发式函数h(s)、代价函数g(s)，以及open list和close list。但在扩展邻人节点时，算法会查抄当前扩展的节点是否到达了TARGET列表中的目的点t。如果到达了当前目的点且该点不是尽头，算法就会将目的更新为列表中的下一个点，并重新计算OPEN列表中全部状态的f值。
LLM-A*对总本钱函数f(s)进行了改进，新的计算公式为f(s)=g(s)+h(s)+cost(t,s)，此中cost(t,s)表现从当前状态到目的点的代价。这个额外的代价项引入确实会带来一定的计算开销，这个开销会随着TARGET列表的长度和open list的巨细线性增长。但是，通过大语言模子提供的全局指导，算法显著淘汰了需要探索的状态空间，因此在整体效率上仍旧具有显着优势。
在通用适用性方面，LLM-A保持了原始A算法的灵活性，可以适用于各种路径规划任务和情况。与一些专门针对特定场景（如网格地图）优化的算法（如JPS和GHPA*）相比，LLM-A表现出更强的通用性，能够有效处理多样化和大规模的情况。这种全面的适用性使得LLM-A成为一个可靠的A*算法替代方案。

▲图2｜ LLM-A*算法©️【深蓝AI】编译

2.3 提示词技巧

作者在3.3节中介绍了三种用于LLM-A*算法的提示技能，分别是少样本学习、思维链和递归路径评估。
首先是少样本学习（Few shot Learning）。这种方法采用直接向大语言模子展示真实动作序列作为提示的方式。基于之前研究表明模子性能会随着特定任务示例数量的变化而显著变化，目的是找到能够提拔模子正确性和学习效率的最佳示例数量。
其次是思维链（Chain of Thought）方法。这种技能源自Wei等人2022年的研究，其焦点思想是引导大语言模子进行逐步推理。这种方法在需要多层次推理和决策的任务中表现出了显著的效果。作者将这种方法应用到路径规划中，通过引导模子展示详细的思索过程和每个步调的评估，帮助模子更好地理解路径生成的原理。
第三种是递归路径评估（Recursive Path Evaluation， RePE）技能。这种方法计划用来指导大语言模子逐步生成路径，特别夸大对每个步调的评估。RePE方法将路径规划问题分解为三个子问题：情况分析、路径生成和路径评估。这种方法虽然与ReAct方法、Step Back QA和自我反思等技能有相似之处，但有其独特之处：它不需要情况反馈，而是专注于一步步推进，仅依靠内部推理，通过情况分析和路径评估来构建路径。这种方法不但有助于LLM更正确地进行导航，还能在每个关键点进行连续评估和调解，从而可能提拔整体路径规划的正确性。
3、实验

3.1 数据集

作者为了测试算法的性能，构建了一个包含大量样本的专业数据集。具体来说，他们从随机生成的地图聚集中手动选择了100张50×30的地图，并为每张地图设置了10个不同的出发点和尽头组合。这样总共产生了1000个测试样本（这个例子可以在图1中看到可视化效果）。这些数据都符合搜索算法在连续空间中的尺度测试情况要求。
3.2 实验设置和效果

在大语言模子的选择上，研究团队利用了GPT-3.5-TURBO和LLAMA3-8B-16bit这两个模子来验证LLM-A*算法的有效性。选择这两个模子是思量到它们在妥当性和本钱效益方面的均衡。对于提示计划，团队准备了三种不同范例的提示：简单指令提示、尺度的5样本示例学习、带有3样本的思维链提示，以及带有3样本的递归路径评估提示，用于上下文学习。
实验重点关注两个关键方面：效率和可扩展性。在效率测试方面，研究团队评估了路径规划过程中的运算次数和所需存储空间，这两个指标分别定义为时间复杂度和空间复杂度。同时，他们还评估了生成路径的长度来权衡路径效率。这些指标被用来计算一个综合效率得分，如表1所示。为了更好地展示算法效率，团队选择在原始样本巨细的50×30地图上进行效率实验。选择这个尺寸是因为它既能充分展示算法的效率特性，又能保持计算需求在可接受范围内。作者特别指出，高出这个规模的实验运行时间会变得过长。

▲表1｜ 三种寻路方法的定量分析©️【深蓝AI】编译

实验效果表现LLM-A*在运算效率和存储效率方面都取得了显著提拔。具体来说，当利用GPT-3.5模子时，LLM-A*的运算量降至原来的57.39%，存储需求降至74.96%，而路径长度仅增加了2.44%。更令人印象深刻的是，利用LLAMA3模子时，LLM-A*的表现更为出色，运算量降至44.59%，存储需求降至64.02%，路径长度仅增加2.47%。值得注意的是，LLM-A*在全部测试场景中都保持了100%的有效路径率，而且相比最优路径的长度增加幅度相当小。
相比之下，单纯利用LLM的方法在路径效率和有效性方面的表现都不如LLM-A和A算法。这紧张是因为单独利用LLM缺乏启发式指导和确定性包管，这些恰恰是LLM-A中得到了很好的生存。LLM的洞察本领与A*算法的团结显著提拔了操作效率和存储效率。
在不同提示方法的对比中，递归路径评估（RePE）方法在LLM-A*中表现最好，利用GPT-3.5模子时路径长度仅增加2.41%。这表明RePE的逐步推进和内部推理本领有助于生成更优的路径点。但有趣的是，在纯LLM方法中，RePE的表现反而不如思维链和少样本提示方法。这反映出LLM在端到端路径规划和空间-时间推理方面的局限性，可能导致产生不切实际或无效的路径。
在可扩展性测试方面，研究团队对A*和LLM-A*算法进行了从1到10不同比例的测试，以研究它们在渐渐增大的情况中的表现。图3展示了A和LLM-A在不同规模情况下的表现对比。效果表明，随着情况规模从1倍扩展到10倍，A算法在计算量和存储需求上都呈现指数级增长，而LLM-A则保持接近线性的增长趋势，表现出更好的可扩展性。这种优势在更大规模的情况中表现得尤为显着。

▲图3｜ 计算效率©️【深蓝AI】编译

3.3 定性分析和总结

从图1的可视化效果可以直观地看到，LLM-A*算法仅需要140次运算就能找到最优路径，这比A算法所需的859次运算少了近五分之四，同时存储需求也显著低沉。两种算法都利用优先队列来存储已到达状态的f值，并选择f值最小的状态进行探索。但两者的根本区别在于它们计算f值或启发式值的方式不同。
如图4所示，LLM-A*算法的独特之处在于它不但利用了A*尺度的启发式值，还利用了LLM生成的路径点来调解启发式值，从而形成一个动态变化的启发式函数。这种动态调解是通过在搜索过程中不停更新目的状态实现的：每当算法到达当前目的状态时，就会切换到下一个目的状态，并重新计算全部已到达状态的启发式值。这使得算法能够根据大语言模子在不同搜索阶段提供的发起来调解搜索方向。
相比之下，传统A*算法对每个状态利用的是静态的启发式值，这个值在整个搜索过程中保持稳定。这种静态方法可能导致算法在情况中探索大量非最优路径，包罗一些死胡同区域。作者通过实验观察表明，LLM-A*的动态启发式计谋能够更有效地引导搜索方向，淘汰不必要的状态探索。
4、结论

在本研究的结论部分，作者夸大了LLM-A*这一新型路径规划算法的突出成就。这个算法在计算效率和内存利用效率方面都显著优于传统的A*算法，同时相比纯LLM方法，在路径的妥当性和最优性方面也表现更好。LLM-A*的成功源于它巧妙地将大语言模子生成的路径点（作为全局性看法）与A*算法简直定性包管相团结，有效地克服了纯LLM方法和传统A*算法各自的局限性。
作者特别指出，LLM-A*保持了A*算法的通用适用性，这意味着它可以应用于各种不同范例的路径规划任务和情况。这种广泛的适用性使得LLM-A*成为一个很好的A*算法替代方案，尤其是在处理大规模场景时表现出色。
最后，作者也提到了算法的局限性。虽然LLM-A*生成的路径约90%都是最优的，但该算法并不能包管总是找到最优路径。这些非最优的情况虽然相对较少，但表明算法在包管路径最优性方面尚有改进空间。别的，研究紧张利用了GPT-3.5-TURBO和LLAMA3-8B-16bit这两个模子进行基础的提示技能验证，还可以探索更多的模子和更先进的提示工程计谋，以得到更全面的算法性能认识。

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。