路径规划是机器人技术和自主导航中的一个基本科学问题，需要从起点到目的地推导出有效的路线，同时避开障碍物。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 年）。
