LLM+P： Empowering Large Language Models with Optimal Planning Proficiency

LLM+P：赋予大规模语言模型最佳规划能力

摘要：大规模语言模型（LLMs）已经展示了显著的零样本泛化能力：最先进的聊天机器人可以为日常生活中的许多常见问题提供合理的答案。然而，迄今为止，LLMs 还不能可靠地解决长期的机器人规划问题。相比之下，经典的规划器一旦以规范化的方式给出问题，可以使用高效的搜索算法快速找到正确的，甚至是最优的方案。为了结合两者的优势，本文引入了 LLM+P，这是第一个将经典规划器的优势整合到 LLMs 中的框架。LLM+P 接收规划问题的自然语言描述，然后返回用自然语言表达的正确（或最优）解决方案。LLM+P 首先将语言描述转换为规划域定义语言（PDDL）文件，然后利用经典的规划器快速找到解决方案，并将找到的解决方案翻译回自然语言。本文还定义了一组来自机器人规划场景的多样化基准问题。通过对这些基准问题的一组全面实验，我们发现 LLM+P 能够为大多数问题提供最优解决方案，而 LLMs 在大多数问题上甚至无法提供可行的方案。我们还展示了 LLM+P 使家用机器人能够解决由用户用自然语言指定的复杂操作任务。

I. 引言

自人工智能领域诞生以来，研究人员一直致力于创建能够像人类一样自然流畅地进行对话的程序。虽然即使是像1966年推出的Eliza这样相对简单的模型，也能对某些提示生成看似合理的回应，但相对于人类，这些模型的弱点也很容易暴露——它们缺乏真正的“理解”。

尽管大规模语言模型（LLMs）如GPT-4和ChatGPT远远超出了几年前的预期，但在这方面它们并没有太大不同。实际上，现在互联网上充斥着人们让ChatGPT生成连5岁儿童都知道不合适的内容的例子。

鉴于LLMs的设计和训练方式，这种现象并不令人惊讶。它们并非专门为展示理解力而构建，而是被训练成生成在人类先前上下文中可能合理的单词序列。正如Mahowald等人所言【4】，LLMs在语言能力（即知道如何表达）方面表现出了惊人的熟练度，但在功能性能力（即知道说什么）方面则差得多。具体来说，它们很容易被愚弄，例如，当被问到一个简单的算术问题时，如果该问题不在它们的训练语料中，或被要求解决一个需要世界运作知识的全新规划问题时，它们可能无法提供正确的答案。

（注释：GPT-4在规划问题上的一个失败示例：

问题（P1）：你有5块积木。不能将多于一块积木放在另一块积木上。b5在b3上，b4在b2上，b2在b1上，b3在b4上，b1在桌子上，b5是清空的，你的手臂是空的。你的目标是移动这些积木。b1应该在b2上，b3应该在b5上，b4应该在b1上。

GPT-4的回答：

1. 将b5从b3上移到桌子上。

2. 将b3从b4上移到b5上。

3. 将b4从b2上移到桌子上。

4. 将b2从b1上移到b5上。

5. 将b1从桌子上移到b2上。

6. 将b4从桌子上移到b1上。）

难道我们应该努力将所有的算术和规划问题都包含在训练语料中吗？显然，这是徒劳的。另一方面，为什么需要这样做呢？我们已经有了可以保证给出正确答案的计算器和通用符号规划器。因此，一种自然的替代方法，也是我们并不是第一个探索的方法，是将LLMs与这些工具相结合。

基于此动机，本研究的目标是首次使LLMs能够正确地解决规划问题。我们旨在做到这一点，而无需对LLMs本身进行任何修改，甚至无需进行微调【5】【6】。相反，我们引入了一种名为LLM+P的方法，当提出一个自然语言描述的规划问题时，LLM将：

1. 输出一个适合作为通用规划器输入的问题描述；

2. 使用通用规划器解决该问题；

3. 将规划器的输出转换回自然语言（或连接到机器人执行器）。

我们的大量实验证明，LLM+P能够为比单独使用LLM更多的规划问题生成正确的解决方案。虽然本文中展示了在规划问题上的应用，但这种通用方法可以应用于任何我们有健全和完整求解器的类问题，例如算术问题（通过使用计算器）。

II. 背景

本节介绍了我们用于表示由大规模语言模型（LLMs）解决的规划问题的符号，并回顾了经典规划器的标准表示方法。

A. 经典规划问题

形式上，规划问题 P  的输入由一个四元组 < S, s_{init}, S_G, A, f > 定义：

- S 是用于描述世界状态的有限且离散的状态集合（即状态空间）。我们假设状态空间是分解的，使得每个状态 s ∈ S  由一组固定变量的值定义。

- s_{init}  是初始世界状态。

- S_G 是目标状态的集合。 S_G  通常被指定为一组目标条件，这些条件在目标状态中必须全部满足。

- A 是符号动作的集合。

- f 是底层状态转移函数。函数 f  以当前状态和一个动作作为输入，并输出相应的下一个状态。

规划问题 P  的解是一个符号规划  pi ，其形式为 < a_1, a_2,..., a_N >，使得动作  a_1  的前置条件在初始状态  s_{init}  中满足，动作  a_2  的前置条件在执行  a_1  后的状态中满足，以此类推，直到所有目标条件在执行完  a_N  后的状态中全部满足。

B. 规划域定义语言（PDDL）

规划域定义语言（PDDL）是一种经典规划问题的标准化编码语言【7】【8】。规划问题的 PDDL 表示被分为两个文件：域文件和问题文件。域 PDDL 文件提供了世界底层规则的升华表示。它包括一组用于定义状态空间 S  和动作集合  A  的谓词，以及它们的前置条件和效果（即状态转移函数  f ）。问题 PDDL 文件提供了一组对象来具体化域，问题的初始状态  s_{init}  和目标条件  S_G 。存在丰富的符号规划器集成了高效的搜索算法来解决用 PDDL 形式化的规划问题。在这项工作中，我们的目标是将自然语言提示（该提示描述了初始状态  s_{init}  和目标条件  S_G ）转化为 PDDL，并利用符号规划器生成正确的规划方案。我们假设域规则是已知的（参见第III节中的假设）。

III. 方法

本节首先使用一个运行中的例子来研究如何将规划提示公式化为 PDDL，然后介绍 LLM+P 方法。

图1：LLM+P 利用大规模语言模型（LLM）生成给定问题的 PDDL 描述，然后利用经典规划器找到最优方案，并再次使用 LLM 将原始方案翻译回自然语言。

（注释：图1分为上下两个部分，分别展示了 LLM+P 方法的三个主要阶段：问题转换、规划求解和方案翻译。具体步骤如下：

1. 自然语言问题转换为 PDDL 文件：

- 输入问题：图的左上部分展示了输入问题，这通常是由用户用自然语言描述的一个规划问题。

- LLM 生成 PDDL 文件：LLM 被用来将这个自然语言描述转换为规划域定义语言（PDDL）格式。这一步类似于机器翻译，将自然语言问题描述翻译成经典规划器能够理解和处理的形式化问题描述。PDDL 文件包括定义状态空间、动作和目标的详细信息。

2. 经典规划器求解问题：

- PDDL 规划求解：图的中间部分显示了 PDDL 文件被输入到经典规划器中。经典规划器使用其内置的高效搜索算法，基于 PDDL 文件的描述来生成一个解决方案（即一个规划或动作序列）。

- 生成 PDDL 方案：规划器会输出一个 PDDL 方案，该方案描述了如何从初始状态通过一系列动作达到目标状态。这个方案通常是最优的，即在最少步骤内实现目标状态。

3. 方案翻译回自然语言：

- LLM 翻译 PDDL 方案：图的右侧展示了如何再次利用 LLM，将经典规划器生成的 PDDL 方案翻译回自然语言。这个过程使得规划结果更易于理解，用户或机器人可以直接执行这些自然语言描述的步骤。

- 输出方案：最后，系统输出一个用自然语言描述的解决方案，供用户或机器人参考和执行。

总结

图1直观地展示了 LLM+P 的整体工作流程，突出了一种有效的策略，即通过将 LLM 的自然语言处理能力与经典规划器的搜索和优化能力结合起来，成功地解决复杂的规划问题。这种方法特别适合需要长时间推理和规划的场景，如机器人任务规划。）

A. 大规模语言模型作为 PDDL 编写器

LLMs 在规划（或长时推理）方面表现不佳【9】，但它们擅长描述和翻译文本输入，包括将规划提示重写为 PDDL 格式。直觉上，我们可以将 PDDL 视为与英语不同的语言，因此将规划提示重写为 PDDL 实质上是一个“机器翻译”任务，而 LLMs 在此类任务中表现优异。以下是 GPT-4 无需任何提示工程生成的 PDDL 问题文件示例。我们可以看到，生成的文件看起来具有正确的 PDDL 语法，但使用了一个虚构的谓词（empty），并且遗漏了 b1 在桌子上的初始条件。

（GPT-4 生成的 PDDL 问题文件示例

提示：问题描述（P1） + 直接向我提供描述该规划问题的 PDDL 文件，而无需进一步解释。

GPT-4（生成的问题 PDDL 文件）：

```pddl

(:objects b1 b2 b3 b4 b5 - block)

(:init (on b5 b3) (on b4 b2) (on b2 b1) (on b3 b4) (clear b5) (empty))

(:goal (and (on b1 b2) (on b3 b5) (on b4 b1)))

```）

B. 上下文学习

LLMs 已知能够在不微调其参数的情况下进行上下文学习。我们所说的上下文学习，是指 LLMs 通过简单地基于一些输入-标签对（示例）进行条件推理，从而执行未见过的下游任务的能力【10】。以下是提供给 GPT-4 的一对自然语言和 PDDL 的问题描述作为上下文。当将上下文与上述提示一起包含时，生成的 PDDL 问题文件可以直接由规划器解决。

（注释：包含上下文的 GPT-4 生成的 PDDL 问题文件示例

上下文（阴影部分）：

一个示例规划问题是：你有5块积木。b2 在 b5 上，b5 在 b1 上，b1 在 b4 上，b3 在 b2 上，b4 在桌子上。b3 是清空的。你的手臂是空的。你的目标是移动这些积木。b4 应该在 b3 上。问题的 PDDL 是：

```pddl

(:objects b1 b2 b3 b4 b5)

(:init (arm-empty) (on b1 b4) (on b2 b5) (on b3 b2) (on-table b4) (on b5 b1) (clear b3))

(:goal (and (on b4 b3)))

```

提示：问题描述（P1） + 上下文 + 直接向我提供描述该规划问题的 PDDL 文件，而无需进一步解释。

GPT-4（生成的问题 PDDL 文件）：

```pddl

(:objects b1 b2 b3 b4 b5 )

(:init (arm-empty) (on-table b1) (on b2 b1) (on b3 b4) (on b4 b2) (on b5 b3) (clear b5))

(:goal (and (on b1 b2) (on b3 b5) (on b4 b1)))

```）

C. 大规模语言模型 + 经典规划器（LLM+P）

在介绍了 LLM 编写 PDDL 和上下文学习的能力后，我们准备介绍所提出的 LLM+P 解决方案（图1底部）。特别地，我们假设对于每个问题域，人类专家可以提供一个域描述（即动作的前置条件和效果），这将对该域中发生的所有问题实例保持固定。虽然自动生成描述的问题是另一个有价值的研究问题，但在这项提议的工作中，我们假设描述是以 PDDL 域文件的形式提供的。LLM+P 方法可以直接作为自然语言接口，用于向机器人系统分配任务。例如，假设我们希望一个机器人充当调酒师来制作鸡尾酒。合理的做法是告诉它可以采取哪些行动，但让它自己推断出如何在给定一组要组合的原料的情况下最有效地制作新的鸡尾酒。此外，我们假设代理提供了一个最小示例，演示了该域中简单问题的 PDDL 示例。接下来，代理提供了一个新的（可能非常复杂的）问题（P）。然后，LLM 使用上下文学习来推断与 P 对应的问题 PDDL 文件。一旦生成了问题 PDDL 文件，我们将其与提供的域 PDDL 文件一起输入任何经典规划器，以生成 PDDL 计划【11】。最后，LLM 将 PDDL 计划翻译回自然语言，以完成 LLM+P 管道。

总结一下，LLM+P 所需的假设是：

1. 机器人知道何时基于与人类用户的对话触发 LLM+P。

2. 提供了一个域 PDDL 文件，以定义机器人能够执行的动作。这一规范与任务无关——与任务相关的实体在 LLM 生成的问题 PDDL 中指定。

3. 提供了一个用自然语言描述的简单问题及其对应的问题 PDDL 文件。

IV. 相关工作

本节首先概述了经典规划算法，然后总结了在规划任务中使用大规模语言模型（LLMs）的最新进展。最后，讨论了近期关于用外部模块增强 LLMs 的研究。

A. 经典规划

自动化规划（或称为经典规划）技术可用于计算达成给定目标所需的一系列动作【12】【13】【14】。自动化规划算法已广泛应用于机器人系统中。Shakey 是第一个配备规划组件的机器人，其规划组件是使用 STRIPS 构建的【15】。一些之前的通用规划架构也被证明对机器人规划有用，如 PRODIGY【16】和 HTN【17】。近期为机器人设计的经典规划系统常使用规划域定义语言（PDDL）或应答集编程（ASP）作为规划器的底层动作语言【18】【19】【20】【21】。例如，研究人员已将经典规划算法用于为移动机器人安排递送任务的动作序列【22】，推理自动驾驶车辆在城市行驶中的安全且高效的行为【23】，以及为移动机器人团队规划动作【24】。任务和运动规划（TAMP）是一个层次化的规划框架，将经典规划与连续空间中的机器人运动规划相结合【25】【26】。

B. 利用大规模语言模型进行规划

近年来，开发了各种大规模语言模型（LLMs），例如 Bert【27】、CodeX【28】、Opt【29】、GPT-3【10】、ChatGPT【30】、GPT-4【2】、Llama【31】、Llama2【32】和 PaLM【33】。由于这些 LLMs 使用大量的离线文本数据进行预训练，它们可以展现出惊人的零样本泛化能力，这可以用于机器人规划任务【34】【35】【36】【37】【38】【39】【40】【41】【42】【43】【44】【45】。例如，Huang 等人展示了 LLMs 可以用于家庭领域的任务规划，通过迭代增强提示实现【38】。SayCan 是另一种方法，它使机器人规划能够通过权力函数考虑动作的可行性，其中服务请求用自然语言指定【34】。

C. 用外部模块增强 LLMs

近期开发的方法显示，通过将 LLMs 与外部模块结合，可以提高下游任务的性能。例如，WebGPT【59】是通过结合网络知识对 GPT-3 进行微调的版本，用于回答开放式问题。Lazaridou 等人研究了如何利用像 Google 这样的搜索引擎作为 LLMs 的外部工具【60】。MemPrompt【61】提出了一个人在循环系统中，其中不断增长的错误和用户反馈记忆被作为过往经验添加到提示中，以更准确地回答新问题。REPLUG【62】是另一种检索增强的语言模型范式，将语言模型视为黑盒，并增加了一个可调的检索模型。具体地，人们已经研究了使用计算器进行计算【63】【64】。在与我们相关的非常近期的工作中，Schick 等人训练了一个名为 ToolFormer 的模型，该模型可以决定何时以及如何通过在提示中在线增强来调用某些工具 API【65】。在本文中，我们提议经典规划器可以是另一个特别有用的外部模块。与此相比，LLM+P 不依赖于任何微调或 LLMs 的重新训练。通过简单地整合来自经典规划器的知识，LLM+P 将长期推理和规划能力整合到现有的 LLMs 中。

V. 实验

我们进行实验以回答以下几个问题：

1. LLM-AS-P 的表现如何？在多大程度上可以直接使用最先进的 LLMs 和基于 LLM 的推理方法进行规划？（几乎不能使用）

2. LLM+P 的表现如何？与 LLM-AS-P 相比表现如何？（好得多）

3. 上下文在 LLM+P 的成功中起到了什么作用？（至关重要）

4. LLM+P 能否帮助服务机器人在现实任务中变得更有效率？（可以）

A. 基准问题

我们展示了从过去的国际规划竞赛中借用的七个机器人规划域，以及每个域自动生成的20个任务【67】。以下是这些规划域的列表，并附有每个域的简要说明。

1. BLOCKSWORLD：给定一组在桌子上的积木堆，一个机器人被要求将它们重新排列成指定的目标配置。

2. BARMAN：一个机器人调酒师被要求根据顾客的订单使用可用的原料和容器制作鸡尾酒。

3. FLOORTILE：一组机器人被要求在地砖上使用油漆颜色图案。机器人可以四处移动并改变颜色，但不能踩在已经涂色的瓷砖上。

4. GRIPPERS：一组带有两个夹具的机器人被赋予将物体在不同房间间移动的任务。

5. STORAGE：给定一组起重机，目标是使用起重机将板条箱抬起并放入仓库中。板条箱最初存储在不同区域，起重机可以在存储区域之间移动。

6. TERMES：一个机器人被要求通过携带和放置积木来建造复杂的结构，还要爬上积木以便能够建造塔。

7. TYREWORLD：机器人被要求通过例如充气轮胎、拧紧螺母和在完成后将工具放回后备箱等操作，按正确的顺序更换轮胎。

对于每个问题 \( P \)，它包含一个自然语言描述和一个真实的 PDDL 问题文件。每个域还包括一个示例问题描述、对应的 PDDL 文件和计划描述，作为各种方法中的上下文。我们假设每个问题域都有一个用户或域专家在处理该域中的任何规划问题之前提供的域 PDDL 文件。为了实现可重复性，此数据集在我们的代码库中公开提供。

B. 实验设置

我们在所有实验中都使用 OpenAI 提供的 GPT-4 模型【2】。我们将温度设置为0，并使用最高概率响应。因此，LLM 返回的响应是确定性的。一旦生成了文本 PDDL 响应，我们将其输入 FAST-DOWNWARD 规划器，并尝试使用 SEQ-OPT-FDSS-1（保证最优）和 LAMA（不保证最优）两个别名，最大搜索时间为200秒。我们报告最优别名的成功率，对于超时的域，我们显示次优别名的成功率（括号内）。对于基线方法，我们手动计算最优计划的数量，并报告正确计划的数量（如果有任何次优计划，则在括号中）。

我们还评估了一个名为“思维树”（Tree of Thoughts）的近期 LLM 推理方法，简称 LLM-AS-P（TOT）。我们调整了原始 ToT 实现中的广度优先搜索算法【68】以用于规划。在每个树节点上，LLM 被提示提供允许的动作列表，然后调用 LLM 评估树上新路径作为部分计划的可能性。相同的200秒时间限制被应用。

C. 结果与分析

将 LLM-AS-P 和 LLM+P 应用于7个域的结果如表1所示。

表 I：应用无上下文的 LLM-AS-P（LLM−）、有上下文的 LLM-AS-P（LLM）、思维树（LLMToT）、无上下文的 LLM+P（LLM+P−）和 LLM+P 在不同域上的成功率 %。

发现（LLM-AS-P）：

1. 我们观察到，尽管 LLM-AS-P 为每个问题提供了自然语言的计划，但大多数计划不可行。主要原因是 LLM-AS-P 缺乏推理前提条件的能力。

2. 在大多数情况下，无论是否提供示例计划作为上下文，LLM-AS-P 都以相同的方式失败。特别是在 BLOCKSWORLD 域中，LLM-AS-P 无法跟踪诸如 ON 和 CLEAR 之类的属性。在 BARMAN 域中，LLM-AS-P 的计划未能在再次使用前清洁酒杯。

3. 最复杂的域是那些具有复杂空间关系的域。LLM-AS-P 方法（无论是否有上下文）在此类问题中完全失败。在 FLOORTILE 域中，LLM-AS-P 生成了“移动到瓷砖 0-4 并将瓷砖 1-2 涂成黑色”，但机器人只能涂相邻的瓷砖。在 TERMES 和 STORAGE 中，LLM-AS-P 忽略了机器人不能在它占据的同一位置卸下积木/板条箱的要求。

4. LLM-AS-P（TOT）在每个树节点上调用 LLM 提供可用动作列表，然后调用 LLM 评估每条新路径作为部分计划。我们发现 LLM 能够对部分计划进行合理的排序，但它经常无法识别计划是否达到了目标。由于 LLM 调用次数较多，LLM-AS-P（TOT）在大多数情况下超时，因此不适合解决长时间规划问题。

发现（LLM+P）：

1. 提出的 LLM+P 为大多数问题生成了最优计划。大多数失败的情况是由于错误指定的问题文件，例如缺少初始条件之一（例如在 FLOORTILE 中没有连接瓷砖），导致规划问题无法解决。

2. 在没有上下文的情况下（即没有示例问题及其对应的问题 PDDL），我们观察到 LLM 无法生成正确的问题 PDDL 文件。因此，上下文对于 LLM+P 的工作至关重要。

D. 机器人演示

我们验证了 LLM+P 能够通过部署在一个实际的机器人上高效解决现实中的服务机器人问题，该机器人被分配了整理家庭的任务。用户要求机器人将芥末瓶从咖啡桌移动到食品储藏室，并将空罐头从侧桌扔掉。由于侧桌和回收箱位于从咖啡桌到食品储藏室的途中，最优的计划是将芥末瓶带到侧桌，扔掉罐头后重新抓住它，总代价为22。图2显示了 LLM+P 发现的最优计划。提示和生成的 PDDL 的部分内容如下。LLM-AS-P 输出了一个次优计划，该计划先将瓶子带到食品储藏室，然后返回取罐头，总代价为31。

（注释：LLM+P 生成的整理问题 PDDL

问题 (P)：你是一台配备一个夹具的家用机器人。咖啡桌和侧桌之间的距离是10，咖啡桌和储藏室之间的距离是20……你现在在咖啡桌旁，有一个芥末瓶……你的目标是将物品移动到它们的目的地……

LLM+P 生成的问题 PDDL：

```pddl

(:objects coffee-table side-table recycle-bin pantry - location

mustard-bottle soup-can - object)

(:init (= (total-cost) 0)

(= (distance coffee-table side-table) 10)

(= (distance coffee-table pantry) 20)

... (robot-at coffee-table)

(at mustard-bottle coffee-table)

(at soup-can side-table)

(hand-empty) )

(:goal (and (at mustard-bottle pantry) (at soup-can recycle-bin)))

(:metric minimize (total-cost))

```）

图 2：整理计划的最优方案演示。机器人从咖啡桌开始：1) 拿起瓶子，2) 导航到放有侧桌和回收箱的房间，3) 放下瓶子，4) 抓住罐头，5) 将罐头放入回收箱，6) 重新抓住瓶子，7) 导航到厨房，8) 将瓶子放入储藏室。

VI. 结论与未来工作

在这项工作中，我们提出利用经典规划器来赋予大规模语言模型（LLMs）最佳的规划能力。LLM+P 框架的关键设计选择是将 LLM 的重点放在将规划问题从自然语言翻译成结构化的 PDDL 格式上。此外，我们展示了让 LLM 意识到一个简单的（问题，PDDL）对作为示例（或上下文）对上下文学习的重要性。

一些扩展 LLM+P 框架的有趣方向包括：

1. 使 LLM 能够自动识别何时以及如何应用 LLM+P；

2. 减少 LLM+P 对人工提供信息的依赖，可能涉及微调。

Liu B, Jiang Y, Zhang X, et al. Llm+ p: Empowering large language models with optimal planning proficiency[J]. arXiv preprint arXiv:2304.11477, 2023.

1Language Technologies Institute, Carnegie Mellon University

2Allen Institute for Artificial Intelligence

3University of Washington

4NVIDIA 

5UC San Diego 

6Google Research, Brain Team