LLM*：路径规划的大型语言模型增强增量启发式搜索
LLM*：路径规划的大型语言模型增强增量启发式搜索
路径规划是机器人技术和自主导航中的一个基本科学问题，需要从起点到目的地推导出有效的路线，同时避开障碍物。传统算法如A能够确保路径有效性，但随着状态空间的增长，计算和内存效率会严重降低。大型语言模型（LLMs）虽然在环境分析中表现出色，但在详细的空间和时间推理方面存在不足。本文提出了LLM，一种新的基于LLM的路线规划方法，它协同地结合了A*的精确寻路能力与LLMs的全局洞察力。
图 1： 寻路过程中 LLM。LLM 利用 LLMs作为路径点来指导搜索过程，显著减少了访问状态的数量，从而导致操作和存储使用量低于 A*
路径规划的挑战
路径规划是确定从初始点到目的地点的路径的计算过程，该路径符合特定标准，例如避开障碍物、最小化行驶距离或时间以及满足其他约束。这个问题在多个领域都至关重要，例如机器人、自动驾驶汽车导航、工业自动化和虚拟环境导航，因为它直接影响操作系统的效率、安全性和可行性。
现有的路径规划算法能够有效地完成规划任务并确保其路径的有效性。然而，随着环境和地图的扩大，像A*及其变体这样的算法遇到了计算和内存需求的指数级增长。发生这种情况是因为寻路过程可能会变得次优，算法可能会花费不必要的精力来探索不太相关的区域，从而导致随着地图大小的扩大，时间复杂度呈指数级增加。
与此同时，大型语言模型（LLMs）在各种规划任务中取得了显着的里程碑。这些模型展示了对长期上下文输入进行处理和推理的能力，以提供有价值的全局见解，以反映他们对环境的理解，例如识别障碍、代理和目标的相对位置。但是，他们难以完成复杂的长期规划和复杂的空间推理任务，例如基于格网的路径规划。LLMs 通常会生成无效或未接地的路径，导致路径不完整或发生冲突，表明它们在处理详细空间复杂性的能力方面存在差距。
LLM*算法的创新
在这项工作中，我们提出了LLM*，一种新的基于LLM的路线规划方法，它将传统的A算法与来自大型语言模型的全局洞察力协同起来。如图1所示，这种混合方法利用LLM生成的航点来指导路径搜索过程，从而显著降低计算和内存成本。此外，通过将A的标准L2基于距离的启发式方法与从这些航点派生的新启发式值集成，LLM*解决了LLM，从而确保输出路径的有效性。
实验结果
我们在各种环境中进行了广泛的实验，以比较A和LLM（将LLAMA3与少数镜头提示集成）的性能。实验结果表明，A在计算操作和存储需求方面呈指数级增长，环境规模呈线性增加。相比之下，LLM显示出近乎线性的增长模式，表明具有卓越的可扩展性。这表明LLM在计算和内存方面都明显更高，使其更适合更大的环境。此外，我们的主要实验结果表明，LLM不仅在可扩展性方面表现出色，而且在基线计算和内存效率方面也优于A*。LLM与A相比，操作和存储比率显著降低，平均需要的操作和存储不到A*寻路过程所需操作和存储的一半左右，从而为大规模路径规划提供了强大而高效的解决方案。
相关工作
传统算法
Pathfinding在人工智能、机器人技术和计算机图形学中一直发挥着关键作用，开发了许多算法来应对各种挑战。基础方法中，由Hart、Nilsson和Raphael于1968年引入的A*算法因其使用启发式方法来估计从当前节点到目标节点的成本而脱颖而出，平衡了贪婪的最佳优先搜索与均匀成本搜索以实现有效的寻路。同样，1984年提出的Pearl最佳优先搜索（BFS）根据启发式值对节点进行优先级排序，但由于它专注于最有前途的节点，可能导致路径更长。
A的扩展旨在提高其效率和适应性。Korf于1985年提出的迭代深化A（IDA*）将深度优先搜索与A的启发式方法相结合，创造了一种内存高效的方法。Korf还在1990年推出了实时学习A（LRTA*），将实时学习与动态更新启发式值相结合，从而提高了在不断变化的环境中的性能。Russell于1992年提出的简化内存有界A*（SMA*）通过选择性地忘记不太有希望的路径来解决内存限制问题，使其适用于资源有限的应用程序。
进一步的增强包括Stentz1994年的动态A*（D*），它随着环境的变化重新计算路径，证明在未知或不断发展的地形中导航有效。Koenig等人于2004年推出的终身规划A*（LPA*）在动态和大规模环境中逐步更新路径。Harabor和Grastien于2011年提出的跳跃点搜索（JPS）通过识别关键的“跳跃点”来优化基于网格的地图的A*，从而减少扩展节点的数量。Nash等人于2007年提出的Theta*允许在节点之间进行视线检查，从而产生更直接的路径。
分层方法，例如Holte等人1996年的分层A*（HA*），通过抽象层次结构将大型寻路问题分解为较小的子问题，从而降低了计算复杂性。Botea等人于2004年推出的分层路径查找A*（HPA*）改进了抽象级别之间的过渡，以实现高效的大地图路径查找。
专业方法也有很大贡献。Demyen和Buro于2006年提出的基于三角测量的寻路（TRA*）使用三角测量来导航多边形环境，适用于非基于网格的设置。Koch于2011年推出的特定于网格的分层路径查找（GHPA*）通过集成分层和特定于网格的优化来优化网格映射寻路。
大型语言模型
大型语言模型（LLMs）最近在自然语言处理任务和其他领域取得了显著的成功。Shridhar等人强调了高级规划中的LLMs，特别是在长期规划和空间推理方面的挑战。我们的研究重点转移到连续环境，与基于网格的地图相比，它提供了更逼真的设置。连续空间更符合现实世界的条件，为人类交互提供更自然的界面，并允许更高的空间推理精度。
LLMs在空间推理方面表现出不同的熟练程度。我们的研究进一步评估了机器人运动和路径规划环境中的LLMs，解决了端到端规划中的局限性。了解高级别和低级别规划之间的相互作用至关重要。高级规划涉及战略目标，而低级规划侧重于详细的任务执行。我们的研究探讨了LLMs在纠正低级规划错误方面的适应性，确保动态条件下的弹性。