大语言模型遇上寻路算法：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这两个模型进行基础的提示技术验证，还可以探索更多的模型和更先进的提示工程策略，以获得更全面的算法性能认识。