论文阅读 | 【EMNLP】LLM-A*: Large Language Model Enhanced Incremental HeuristicSearch on Path Planning

目录

参考资料：

概述：

1 A*算法

2 大语言模型（LLM）

2.1 LLM概念

2.2 发展历程

2.3 LLM 工作原理

2.4 提示技术

3 LLM-A*算法

4 实验

数据集：

实验设置：

实验步骤：

评估指标：

结果分析：

可扩展性分析:

5 结论：

参考资料：

论文链接：https://arxiv.org/abs/2407.02511?context=cs.CL

概述：

本文旨在通过创新方法解决路径规划领域中基于A算法的效率问题。当状态空间规模扩大时，传统算法在计算复杂度和内存占用方面表现出明显不足。本文的核心创新在于将大语言模型（LLM）与经典路径规划算法A进行深度融合。通过整合LLM的强大语义分析能力和A*算法的精确搜索机制，在保持路径有效性的同时大幅降低了系统的运行时间和资源消耗。研究结果表明，在保证路径规划的基本正确性要求的前提下，该方法显著提升了整体运行效率。

1 A*算法

该算法在当前应用中得到广泛应用，并被用作解决路径寻找及图遍历问题的主要方法。该方法巧妙地结合了Dijkstra算法的优势以及贪心最佳优先搜索的特点，在寻找起始节点至目标节点之间的最短路径方面表现卓越。

建议查阅：[路径规划 | A算法原理-博客]( "路径规划 | A算法原理-博客")

该算法在多种实际应用领域展现出色，并且能够快速实现路径规划任务的同时保证所找到路径的有效性。然而它的一个显著缺陷是其搜索过程会产生大量非必要的节点。这一缺陷导致随着地图规模的扩大计算复杂度几乎呈指数级上升从而降低了其实用性和效率

为了解决这一问题，研究团队开发了Jump Point Search (JPS)算法，并采用跳点策略来加快搜索速度。该算法能够在保持路径最优性的前提下，大幅减少需要探索的节点数量，并显著提升二维网格环境中的搜索效率。然而，在面对高维空间或非网格化环境时，即使经过优化的JPS也难以满足性能需求。这是因为其核心机制依赖于特定网格结构和对称性，在更为复杂或非网格化环境中可能不再适用。

2 大语言模型（LLM）

2.1 LLM概念

大型语言模型（LLM）被定义为拥有数十亿至数千亿参数的深度神经网络架构。其目标是通过处理海量数据来识别和学习复杂的模式与特征，并以此提升其表达能力和预测精度。在自然语言处理、计算机视觉、语音识别以及推荐系统等多个领域均有广泛应用，并且由于其强大的泛化能力使其能够准确地预测未见过的数据

大模型的主要强项在于其通过大量数据的学习训练而展现出智能化的生成能力，并最终得以在各种复杂任务中完成相应的功能展现。这些特性使其能够广泛应用于多个领域

文本生成功能：旨在创作出连贯且有条理的文字内容。该功能特别适用于自动化写作以及机器翻译场景中的应用需求。
问答系统模块：专为提供复杂问题的答案设计，并支持通过对话形式进行交互。此模块能够高效处理各类专业领域的问题解答工作。
语义理解与推理系统：负责执行情感分析、识别实体名称以及进行文本分类等核心任务。这些功能有助于提升系统的智能化水平。
智能助手模块：旨在增强机器人与其他系统的交互体验，并实现自动摘要以及信息提取等功能。该模块通过智能化算法优化用户体验。

2.2 发展历程

大语言模型（LLM）的发展历程可以分为三个阶段：

第一阶段主要专注于开发多种自监督学习训练目标（包括mask语言模型、next句子预测等），同时引入了创新性的Transformer架构。该阶段以预训练与微调范式为基础，在大规模预训练策略下结合任务特定微调方法来优化模型性能。其代表模型包括BERT、GPT-2以及XLNet等。

第二阶段则不断扩大训练数据量和模型参数规模，并深入研究了不同类型的架构设计。主要代表包括BART、T5以及GPT-3等模型。这些先进的模型不仅显著提升了参数规模，在架构设计上也实现了创新突破，并从而显著增强了其表达能力和泛化性能。

第三阶段标志着AI内容生成技术（Artificial Intelligent Generated Content）时代的到来，在这一阶段中人工智能系统拥有了突破性的进展：其参数规模突破了千万亿大关，并采用了先进的自回归架构设计。该阶段的大规模AI不仅具备对话交互功能还有生成内容能力的同时也同时具备多模态应用能力。在人机交互方面更加注重一致性致力于打造既可靠又安全且无害的人工智能系统。其中最具代表性的实例包括Instruction GPT Chat GPT Bard以及GPT-4等知名产品

2.3 LLM 工作原理

LLM的本质是利用深度学习技术来模仿人类的语言理解和生成过程。具体而言，在这个过程中主要依赖于以下几种核心技术：信息处理、模型训练以及推理逻辑等关键环节的支持

该方法能够具备高效的文本生成和理解能力，并通过复杂的神经网络模型来模拟人类语言的处理机制

Transformer架构：Transformer架构是当前最主流的深度学习架构之一，并且它通过注意力机制（Attention Mechanism）捕捉文本中词语之间的长距离依赖关系以增强上下文理解能力。

预训练与微调：大型语言模型（LLM）主要通过在大量未标注的数据上进行预训练来学习一般性的语言规律。随后，在具体的任务领域中使用少量标注数据对其进行微调优化。

自监督学习：大型语言模型采用自监督学习方法以解决诸如预测被遮挡的单词（Masked Language Modeling, MLM）以及判断句子间的逻辑关系（Next Sentence Prediction, NSP）等下游任务，并从未经标注的大规模文本数据中自主提取语言规则。

2.4 提示技术

随着大语言模型（LLM）技术的不断进步

少样本学习（Few-Shot Learning）： 此方法通过LLM接收少量真实动作序列作为提示信息，并旨在使模型能够基于这些有限实例快速适应新任务。研究发现，在不同领域中基于特定任务示例的数量对模型性能的具体影响程度存在显著差异（Cao 等, 2019；Razeghi 等, 2022）。

思维链条（Chain of Thought, CoT）：该方法由Wei等（2022）提出并取得显著成果；它通过系统性地进行推导帮助LLM完成特定场景下的多级推理与决策任务；这种系统性方法已被广泛应用于复杂问题求解中；本文将CoT策略优化应用至路径规划问题中以提升算法效率

递归路径评估（Recursive Path Evaluation, RePE）： 递归路径评估法引导LLM按顺序构建路径，并对每个阶段均需进行详细评估。该方法将复杂的空间导航问题划分为环境分析、路径生成及路径评估三个关键环节，并通过递归的方式依次解决这些问题以提高导航精度。尽管该方法不依赖于外部反馈信息而专注于内在推理机制来处理问题，在每个节点上仍允许持续的动态调整以优化整体规划效果。

3 LLM-A*算法

LLM-A* 算法是对传统 A* 算法的一种创新性地扩展，在这一过程中巧妙地将大语言模型（LLM）的全局理解能力与 A* 的精确局部搜索机制相结合。该算法继承了 A* 基本框架的特点，在优化输入处理流程的同时显著提升了搜索效率，并对搜索机制做出了相应改进。

首先，在输入层面进行了增强，在传统LLM的基础上增加了障碍物状态变量obs这一关键组件。该变量用于生成目标节点列表T，并通过向LLM提供当前环境信息来创建该列表。为了确保T列表的有效性与可靠性，在构建过程中需遵循以下两个基本原则：第一项原则是必须包含实际的起点与终点信息（若无法满足，则会自动插入），第二项原则是确保所有目标点都不位于障碍物内部（若有重叠情况，则会自动移除）。通过这种机制设计，在保证路径规划质量的同时提升了算法的整体性能。

在搜索过程中采用了一种类似于A算法的方法，在实现路径规划的过程中模仿A算法采用了启发式函数、成本函数以及open和close列表进行操作。当扩展相邻节点时该系统会检查当前处理的节点是否属于目标集合T中的一个当系统发现当前处理的节点不是终点目标时则该系统会将新的目标设为开放列表中的下一个候选节点并重新评估开放列表中所有状态的成本值这一机制使得LLM-A*能够更加灵活地应对复杂多变的环境情况

为提升搜索效率

LLM-A* 在继承原始 A* 灵活性的同时也展现了独特的创新性，在路径规划领域展现出广泛的应用潜力和强大的适应能力

LLM-A*的伪代码如下：

下面逐行进行分析 ：

    1: Input: START state s0, GOAL state sg, OBSTACLE state obs, heuristic function h, cost function g, Large Language Model llm

输入信息包括起点状态s0等信息、终点状态sg、障碍物状态obs、启发式函数h、代价函数g以及大语言模型llm。

    2: Output: Path P from s0 to sg

• 第2行 : 输出是从起点 s0 到终点 sg 的路径 P。

    3: Initialize the OPEN list O = {s0}, CLOSE list C = {}, TARGET list T = llm(s0, sg, obs), TARGET state t = T.start, g(s0) = 0, f(s0) = h(s0), P = {}

• 第3行 : 初始化：

OPEN列表O记录起始节点s₀。
CLOSE列表C初始化为空集合。
TARGET列表T由大语言模型llm生成，并输入起始节点s₀、目标节点sg以及障碍物状态obs作为参数。
当前目标节点t被设定为T的第一个元素（即T[0]）。
起始节点s₀的成本g(s₀)初始化为零。
起点的总成本f(s₀)基于启发式函数h(s₀)计算得出。
路径P被初始化为空列表。

    4: while O ≠ {} do

• 第4行 : 当 OPEN 列表 O 不为空时，继续循环。

    5:   sa ← state in O with the lowest f-cost

• 第5行 : 选择 OPEN 列表 O 中具有最低 f 成本的状态 sa。

 6:   if sa = sg then

    
 7:     return reconstruct_path(sa)

• 第6-7行: 如果当前状态 sa 是终点 sg，则返回重构路径 reconstruct_path(sa)。

 8:   Remove sa from O

    
 9:   Add sa to C

• 第8-9行 : 将状态 sa 从 OPEN 列表 O 中移除，并添加到 CLOSE 列表 C 中。

 10:   for all neighbors sn of sa do

    
 11:     if sn ∈ C then
    
 12:       continue

对于状态 sa 的所有邻居 sn，在其位于 CLOSE 列表 C 中时避免处理。

 13:     if sn = t and sg ≠ t then

    
 14:       t = T.next
    
 15:       update f-cost of s in O

• 第13-15行: 若 sn 是当前目标状态 t 且非终点 sg，则将当前的目标状态设为 T 中的状态序列中的后继节点，并相应地调整 OPEN 表中的所有节点的成本评估值。

    16:     Tentative cost g_tent = g(sa) + cost(sa, sn)

• 第16行: 计算从状态 sa 到邻居 sn 的临时代价 g_tent。

    17:     if sn ∉ O or g_tent < g(sn) then

• 第17行: 当邻居 sn 未被包含在 OPEN 列表 O 中时；同时满足以下两种情况之一：即临时成本 g_tent 小于 sn 的当前成本 g(sn)；则执行以下操作。

 18:       Update path to sn to go through sa

    
 19:       g(sn) = g_tent
    
 20:       f(sn) = g(sn) + h(sn) + cost(t, sn)

• 第18-20行: 更新路径，使 sn 通过 sa。设置 sn 的代价 g(sn) 为 g_tent，并计算新的 f 成本。

 21:       if sn ∉ O then

    
 22:         Add sn to O

• 第21-22行 : 如果 sn 不在 OPEN 列表 O 中，则将其添加到 O 中。

    23: return failure

• 第23行 : 如果循环结束仍未找到路径，则返回失败。

4 实验

数据集：

由人工精选出的1, 57; 64; 69; 78; 89]张5[; 64; 69; 78; 89]×[; 64; 69; 78; 89]尺寸的地图构成了该数据集；这些地图均源自随机生成的数据库；每个地图都设置了十个独特的起始点与终点坐标；因此；由此得出共有1, [64; 69; 78; 89]份样本数据；该组数据集满足用于搜索算法连续空间环境的基本要求

• x范围：环境边界范围内的最小和最大x坐标值分别为x_min和x_max
• y范围：环境边界范围内最小和最大的y坐标值分别为y_min和y_max
• 水平屏障：由一系列方程定义的障碍线集合，在二维平面中表现为垂直于y轴的一系列直线段
• 垂直障碍：由一系列方程定义的障碍线集合，在二维平面中表现为平行于x轴的一系列直线段
• 起始目标：每个地图包含10对独特的起始点与目标点位置对

这些参数确定了每个地图的结构及运行规则，在保证基于搜索算法的标准实验环境下实现了结果的一致性和可比性。同时该系统具备良好的可扩展能力支持可扩展性测试

实验设置：

模型选用策略：在验证LLM-A*算法的过程中,本研究采用GPT-3.5-Turbo与LLAMA 3-Lite 8B 16-bit版本以权衡性能与经济性.研究中设定提示包含基本指令,并遵循以下结构:首先提供标准的五个示例,其次采用三段式的思维链条进行推理,最后基于上下文学习设计一个三段式递归路径评估机制

实验步骤：

实验重点关注两个关键方面:效率和可扩展性。

对于效率的研究中提到本文评估了寻路过程所需的操作次数与存储空间，并将其分别作为时间和空间复杂度进行分析。此外，在研究中我们通过生成路径长度来衡量路径效率。实验采用了基于原始样本量构建50×30的地图，并基于此选择该规模的基础是为了确保研究结果的有效性与可行性；如果实验规模超出该范围，则会导致运行时间显著延长

为了全面评估系统的可扩展性特征，在最小到最大10个不同地图尺度范围内进行了多维度测试研究。具体而言，分别对A*算法以及LLM改进型A星算法进行了性能指标的实验验证，并考察其在面对规模逐渐扩大的环境时的表现。

评估指标：

我们基于运算效率（运算效率）、内存效率（内存效率）以及路径优化程度（路径质量）等指标对LLM-A算法与传统A算法进行比较分析。通过计算LLM-A算法与传统A算法间的运算次数（操作）、内存占用量（存储）、搜索树深度（路径长度）以及抗异常数据能力更强（提供较少受异常值影响的平衡视图）等参数的几何平均值来综合评价两者的性能表现。

运算与存储比率 : 基于LLM-A*/A* 的几何平均值来计算LLM-A相对于A 的运算与存储比率（记为LLM-A*/A*)。数值越低则效率越高，在具体应用中可观察到当数值达到50%时，则表示LLM-A仅消耗了与A相比一半的运算与存储资源。

相对路径长度：通过对比LLM-A*、A及LLM-only方法至最优路径的路径长度来衡量路径质量。这些比率的几何平均值表明LLM-A路线与最优路线的接近程度。

有效路径比率 ：该指标衡量的是成功寻径尝试的成功率，在实际应用中通常表示这些路径既不会发生自体碰撞也不会出现执行失败的情况。通过计算这些参数之间的关系可以进一步验证该算法在一致性生成有效路径方面的有效性。

生长因子：我们通过执行一系列计算操作来获取并存储增益因子数据，并采用其算术平均值来分析效率提升情况。这些数据帮助我们从50 ×30规模环境向更大规模扩展提供了统一量化分析依据。

结果分析：

表1详细列举了三种寻路方法的对比分析：经典A算法、LLM-only方法以及我们提出的LLM-A方法。以A算法为基准，在第4.3节中已经明确说明其评价指标数值设为100，则表示性能水平与A算法相当。基于尺寸为50×30的原始地图进行评估

表1对三种寻路方法进行了定量研究：经典的A算法、LLM-only方法以及本文提出的LLM-A算法。这些方案在标准地图（50×30）上进行测试。其中LLM-only方案并未明确地逐个遍历网格空间来探索路径，并因此其操作与存储效率相对较低。表中详细列出了GPT-3.5与LLAMA3模型分别采用三种提示策略的结果：分别是基于Few-Shot学习的方法、基于思维链（CoT）的技术以及基于递归路径评估（RePE）的方法。

研究表明，在与传统A算法相比时，LLM-A显著提升了操作性能和存储效率。具体而言，在采用LLM-A模型时，在操作方面的得分达到了57.39%，而在存储方面的得分则为74.96%。与LLAMA3模型相比，在运算资源消耗上降低了约44.59%，同时减少了64.02%的存储需求，并且路径长度相较于基准有所增长（分别增加了2.44%和2.47%）。这些结果表明，在所有应用场景下均实现了100%的有效路径覆盖率，并且观察到的路径长度相对于最优路径的增长仍然较为有限。值得注意的是，在单独使用LLM-only方法时由于缺乏LLM-A提供的启发式指导或A固有的确定性保证而导致其在路径规划方面表现低于LLM-A和A算法；将LLM技术整合至LLM-A中不仅显著提升了其操作能力和存储效率还使其性能超越了传统A*算法

值得注意的是，在LLM-A*中使用RePE方法所获得的相对路径长度增量是最小的。GPT-3.5模型的具体增量数值为2.41%。这一结果表明，在递归路径评估方面（Recursive Path Evaluation, RePE），逐步发展的内在推理能力显著提升了模型生成更优路径点的能力，并由此形成了更为有效的路径选择机制。然而，在对比实验中发现，在基于LLM-only的方法中（即仅依赖LLM进行操作而不结合其他提示技术），RePE的表现则显得略逊色于思维链(CoT)与few shot提示两种更为成熟的优化策略。这种局限性不仅降低了他们在顺序推理出详细路径序列方面的熟练程度，并且还导致了某些异常现象的发生与误解行为的确立。这些限制因素最终导致系统在某些情况下可能生成不正确或不可信的路径选择结果。

可扩展性分析 :

该图表呈现了在地图尺寸被放大后a算法与LLM-A算法的计算效率及内存效率的对比分析：

基于10次随机抽样试验所得的数据均值进行系统性比较。
研究者们系统性比较了两种算法（结合LLAMA3与few-shot提示）在不同缩放倍数下的计算资源消耗与内存占用。
前者（A算法）在执行运算量与存储资源消耗方面呈现指数级增长。
后者（LLM-A结合LLAMA3与few-shot提示）则展现了接近线性的可扩展性能。

通过图3的数据可以看出，在不同环境规模下进行比较时，LLM-A在计算效率和内存利用率方面均优于传统A算法。随着传统A算法在操作复杂度和存储需求上呈指数级增长趋势时，LLM-A通过接近线性的扩展性优势实现了更好的资源利用效率。这种性能优势主要源于LLM-A*算法中融入的学习增强启发式机制。该机制允许其在节点探索过程中规避不必要的计算开销，并更加直接地导向目标节点。从实验结果可以看出，在面对规模更大的复杂场景时，两者的性能差距逐渐扩大。

定性分析：

从图1的结果中可以直观地看出, LLM-A只需执行140次操作即可精确找到最优路径, 其所需的操作次数仅为A所需时间的大约十分之一, 并且这种方法不仅节省了计算资源. 两种方法均采用了优先级队列这一数据结构, 在探索过程中基于每个状态节点评估的成本（即f值）来选择下一步进行搜索. 然而, 在启发式搜索策略上存在本质差异的关键点在于两者的计算方式.

如图所示, LLM-A不仅依赖于A的传统启发信息, 还综合考虑了由大型语言模型生成的关键节点信息, 从而其启发性评价随之演变为动态变化. 当算法在搜索过程中达到某个目标节点时, 会切换到下一个目标节点以继续探索, 并每当遇到新的目标节点后, 都会对之前访问的所有节点重新评估其启发性信息. 这种机制使得LLM-A*在整个搜索过程中能够逐步调整探索重点, 从而能够在更有利的方向上进行高效搜索

与之相比，在每一轮搜索中,A算法始终使用相同的启发信息来进行状态评估.这种固定的启发策略可能会导致算法在搜索过程中过度依赖固定信息而忽略可能存在的更优路径,特别是在复杂环境中,可能导致A算法在死角区域出现长时间的无效探索.此外,A*'s search efficiency may thus be compromised in such scenarios.

5 结论：

本研究开发了一种新型路径规划算法方案LLM-A该算法在计算复杂度与内存占用方面表现更优其同时在路径稳定性与最优化性能上优于LLM单模态方法采用自适应权重策略将LLM生成的关键点提取出的启发性评估融入到A框架内实现了确定性路径保证该混合策略不仅有效弥补了LLM单模态方法与传统A*算法各自的不足而且显著提升了寻路效率

局限性
约90%的路径由LLM-A生成均为最优解；然而该算法无法确保所有生成路径均为最优解；尽管这些例外情况相对较少出现；但它们揭示了该算法在某些情况下可能无法达到最短或最优的效果；未来研究应着重于提高生成路径的有效性；实验主要基于GPT-3.5-TURBO和16位精度训练的LLAMA3 8B模型的基本提示设计；尽管这些模型及其提示方案已足以验证LLM-A算法的基本稳定性和可靠性；进一步测试可采用多样化的模型架构及高级提示工程策略