Quantum Prolog

使用大型语言模型生成 Prolog Planner

将大型语言模型 (LLMs) 的强大功能与 Prolog 的组合搜索能力相结合，是一个自然而然的选择，能够在主流自动化规划领域取得实际进展。

• 使用 LLMs 生成 Prolog Planner
  • LLM 生成的 Planner 的最新技术
  • 将容器规划扩展到通用规划
  • Prolog Planner 生成 Prompting 指南
  • 实际的物流优化问题
• 自带 LLM 的浏览器内实时聊天

LLM 生成的 Planner 的最新技术

关于 LLMs 的公开讨论部分围绕着难以实现的高目标，例如“通用 AI”，但 LLMs 毕竟只是统计语言模型，最擅长语言翻译和摘要任务。 虽然可以训练 LLMs 来做几乎任何事情，包括优化和其他数学与推理任务，但非常清楚的是，结果取决于所使用的训练数据集，并且对于该集合之外的问题，结果仍然高度不稳定且不可预测。 这一事实在 aiw 和 posp 等论文中得到了公认。

因此，与其让 LLMs 自己执行规划，不如用 Prolog 的原始组合能力来补充 LLMs，就像人会使用袖珍计算器一样，这是很自然的。 或者，正如 tnltopgwl 所说：

我们的实证结果 [...] 表明，LLMs 更适合翻译而不是规划。

考虑到 Prolog 最初是为自然语言处理而设计的，将 LLMs 用于将自然语言翻译成 Prolog 也是其原始目标的直接扩展。 规划从一开始就是 Prolog 的另一个应用领域，因此许多研究人员正在尝试使用 Prolog、约束逻辑编程 (CLP) 和其他基于逻辑的编程 (LP) 语言作为使用 LLMs 进行代码生成的目标，这并不令人惊讶（请参阅参考文献，其中包含少量报告）。

从业者在观察到 (swipldiscourse1) 以缺乏 Prolog 所具有的内在逻辑基础的特定领域规划语言和形式主义为目标后，也转向了以 Prolog 为目标的解决方案 rrbnl，例如 tnltogw 中讨论的那种，在

最初的有希望的结果遇到了障碍。

虽然思维链 (CoT) 方法报告说 LLMs 的推理能力得到了很大的提高，但这些结果仍然高度特定于训练数据，因此需要既不存在也不能轻易生成的训练集（如下简要讨论），这一点在 cotplanning 中得到了承认：

[我们的结果] 突出了思维链的缺点，尤其是可能的性能提升与生成具有正确推理轨迹的示例所需的人工劳动量之间的严重权衡。

然而，使用模板化解决方案、受控语言和分层、逐步解决子目标来指导 LLMs 的基本 CoT 方法是自然而直接的学科，通过指示 LLMs 生成特定领域的 Prolog 源代码，进一步表明 Prolog 代码非常适合作为 LLM 目标。

将容器规划扩展到通用规划

我们在这里简要提及 WARPLAN，这是 David Warren 创建的早期基于 Prolog 的规划系统之一，David Warren 在 Prolog 世界中以引入 Warren Abstract Machine 作为 1980 年代高性能 Prolog 实现的基础而闻名，许多 Prolog 引擎至今仍在使用它。 WARPLAN 是 STRIPS 规划在 Prolog 中的一个直接实现，只增加了一个动作后置条件的约定，其形式为 add(pred(..)) 和 del(pred(...)) 字面量。

在我们为容器问题开发的规划器中 Planning container shipping using Prolog，我们使用 Prolog asserta/1、assertz/1 和 retract/1 内置函数来编码由动作产生的状态变化。 这样做的优点（除了不局限于单纯的命题状态之外）现在在使用 LLMs 时变得显而易见，因为生成包含普通 asserta/1、assertz/1 和 retract/1 内置函数的 Prolog 动作谓词在现有的 LLMs 和训练数据中直接支持，而 WARPLAN 类的抽象和形式主义则需要额外的训练才能使其可行。

正如 Advanced combinatorial planning 中所解释的，asserta/1 等的破坏性通常不足以捕获即使是稍微详细的规划模型，但这不成问题，因为我们可以自动将动作谓词重写为使用 vardb 功能的形式，正如上述参考资料中所解释的那样。 是的，我们希望 LLM 将我们的输入问题描述翻译成基本上 naive Prolog 代码，并将 LLM 生成的该代码更改为精炼的形式。

我们还指示 LLM 不要 尝试实际生成解决方案谓词，这可能需要进一步解释：我们希望 LLM 提供以下 Prolog 代码：

• 状态子句：动态事实，编码我们的规划领域的当前状态，从初始状态开始
• 动作子句：状态变化谓词，表示我们在文本描述中给出的宇宙中可用的动作，使用 assertz/1 和 retract/1 更改状态子句上的状态变化
• 用于检查是否达到所需状态的状态事实的子句，用作规划搜索的终止。

实际的组合搜索尝试和回溯动作 不是 我们期望 LLM 为我们生成的部分； 我们提供最少的通用规划库代码，以便以标准的 Prolog 方式拾取和回溯 LLM 生成的谓词，如下所示：

% to enumerate state predicates:
% predicates without clause body (and without vars)
state_pred(P/N) :-
  current_predicate(P/N),
  \+ (P = 'action_pred'; P = 'check_pred'; P = 'state_pred'; P = 'main'),
  functor(T, P, N),
  clause(T, true).
% to list a check predidcate:
% the single parameter-less predicate the body of
% which is a conjunction entirely over state primitive predicates
check_pred(P/0) :-
  current_predicate(P/0),
  \+ (P = 'action_pred'; P = 'check_pred'; P = 'state_pred'; P = 'main'),
  clause(P, Body), \+ Body = true.
% to enumerate action predicates:
% any predicate that is neither a state nor a check predicate,
% nor one of the planning lib predicates defined here
action_pred(P/N) :-
  current_predicate(P/N),
  \+ (P = 'action_pred'; P = 'check_pred'; P = 'state_pred'; P = 'main'),
  \+ state_pred(P/N),
  \+ check_pred(P/N).
% main: generic routine for checking if the desired state has been reached
main :-
  check_pred(P/0),
  call(P),
% ... code for informing about having completed planning omitted ...
!.
% main: generic planning routine executed recursively as long as no
% desired state is reached
main :-
  action_pred(P/N),
  functor(T, P, N),
  call(T),
% ... code for informing about pursuing a planning action omitted ...
  main.

Prolog Planner 生成 Prompting 指南

有了我们适度的 Prolog 规划基础设施，我们现在就可以直接提示一个指令调整的 LLM，根据文本问题描述以及以下系统提示来为我们生成规划器（包括 AIPS 物流问题的文本描述作为上下文示例）：

作为一名 Prolog 编程专家，您应该生成从给定的规划问题描述文本中收集的 WARPLAN 风格的 Prolog 源代码。 WARPLAN 风格的 Prolog 规划程序由 Prolog 事实组成，限制为 Datalog 语法，表示规划域在任何时间的当前状态，以及表示可能的操作的子句，这些操作带有查询和检查当前状态的参数，并使用 retract 和 assertz Prolog 内置函数更改状态事实，以及一个用于检查是否达到所需状态的谓词。 尝试调用任何有限数量的动作谓词直到达到所需状态的通用 main 谓词可以省略。
在生成源代码中，包含问题文本描述的部分作为 Prolog 源代码注释，以及表示相应文本片段的状态事实和动作谓词子句。 仅生成 ISO Prolog，而不咨询或以其他方式导入 Prolog 库代码。 不要生成辅助子句。 不要在生成的 Prolog 代码中使用 if-then 或 if-then-else 运算符。 除了带有注释的 Prolog 源代码外，不要生成其他输出。
以下是一个带有 Prolog 解决方案的示例问题文本。
问题描述文本：
必须使用卡车在六个城市（名为 city1、city2、city3、city4、city5 和 city6）的地点之间运输包裹，并使用飞机在这些城市之间运输包裹。 每个城市有两个地点：city1 有地点 city11 和 city12，city2 有地点 city21 和 city22，city3 有地点 city31 和 city32，city4 有地点 city41 和 city42，city5 有地点 city51 和 city52，city6 有地点 city61 和 city62。 最初，package1 位于 city21，package2 位于 city12，package3 位于 city11，package4 位于 city11，package5 位于 city42，package6 位于 city31。
目标是将 package1 移动到 city21，package2 移动到 city62，package3 移动到 city61，package4 移动到 city32，package5 移动到 city62，package6 移动到 city12。
在每个城市，在地点 city11、city21、city31、city41、city51 和 city61，都有一辆卡车将包裹运送到城市内的其他地点。 此外还有两架飞机，分别名为 plane1 和 plane2，位于 city1 的机场 location11 和 city2 的机场 location22。 其他城市的机场在 city3 中有地点 location32，在 city4 中有地点 location42，在 city5 中有地点 location52，在 city6 中有地点 location62。
要移动包裹，必须执行以下一系列操作，直到包裹到达目的地：
动作 load_truck 将包裹放置在给定地点的卡车中。
动作 unload_truck 将包裹从给定地点的卡车中卸载。
动作 fly_airplane 将飞机从一个机场飞到另一个机场。
动作 unload_airplane 将包裹从给定地点的飞机中卸载。
动作 load_airplane 将包裹装载到给定地点的飞机上。
Prolog 程序来解决这个问题：
... (代码如下) ...

解决示例问题的 Prolog 状态、动作和检查谓词未在此处列出。 如前所述，实际的主要求解例程不是提示的一部分，通用例程将附加到 LLM 生成的结果。 使用上述模板作为系统提示，完整提示中需要包含的是实例问题的描述，作为“用户”角色输入，通常以这样的句子开头：

编写一个 Prolog 程序来查找一系列动作以 ...

注意事项

• 已发现此提示对于训练集中包含 Prolog 的代码指令调整的 LLMs 效果良好，例如 Code Llama 和 Qwen Coder； 从第三代本地 LLMs 的 7B/8B 参数模型（例如 Llama 3.1 或更高版本以及等效的 Qwen Coder（以及 Mistral、Deep Seek）模型）开始可以获得有用的结果。
• 正如您可以从示例问题中看到的那样，描述已经对城市和其他现实世界对象使用了人工名称； 当使用真实的城市名称或规划域中其他对象的真实名称时，我们可以观察到过度拟合，并且系统提示中给出的示例的实例规则会泄漏到参数问题中。
• 建议的上下文大小至少为 12k 个令牌（具体取决于实例问题文本大小）。
• 即使我们在此处要求解决一个具体的实例问题，我们也可以假设生成的 Prolog 代码可以处理具有更改参数的其他实例，例如其他城市和货运，这是因为这些事实被强制以直接的 Prolog 方式编码； 如果我们试图指定一个笨拙的抽象问题描述（对于甚至可能出现这种情况的情况），我们发现结果的可用性要差得多。
• 该提示经过精心设计，专门用于避免或减少生成的 Prolog 源代码中的以下缺陷：
  • LLMs 倾向于在全球 solve 类谓词中编码或预测虚假的硬编码解决方案，这可以通过仅请求翻译动作/状态/检查谓词并省略 main 谓词来解决，如前所述。
  • 通过明确指示 LLM 不使用约束逻辑编程或其他库，或使用非 ISO Prolog“民俗”代码（例如 append/3 和 substract/3）来避免使用它们。
  • 通过相应地提供示例代码来解决状态谓词缺少 dynamic 指令的问题。
  • 通过提供示例代码也可以避免初始状态事实被动态地 assertz 而不是通过常规子句定义（这将导致 Prolog 拒绝 permission_error，因为它试图重新定义 assertz/1）。

请注意，在本网站实际使用的代码中，我们添加了一些输出消息，以告知用户是否/何时找到计划，以及该计划由哪些操作组成。 忽略用于输出找到的解决方案的附加代码，现在搜索计划就像调用主目标一样容易

在浏览器中测试

:- intialization( main )

更多玩具规划问题以及训练/测试数据

通过尝试为我们的运行容器规划示例问题生成规划器，以及以下问题作为额外的验证或上下文示例，获得了结果。

集装箱船包装

一个补充的特别集装箱规划问题，涉及比我们在此处用作运行示例的集装箱规划问题简单得多的船上堆放顺序

飞机/卡车

从“物流”AI 规划竞赛 (AIPS) 问题中衍生的问题，在 osllpds 中进行了部分解释。

码头/工人/机器人

人为问题，涉及在集装箱码头规划机器人厢式运输车和龙门起重机的移动，归因于 dwr（但请注意，该问题早已成为 AI 规划竞赛套件的一部分）。

飞机维护

另一个 AIPS 问题，我们为其创建了文本描述，以使用调度（而不是规划）问题来补充我们的问题套件； 请注意，要识别和拒绝此类问题或将此类问题调度到相应的调度模板，需要模型定制，例如用于文本分类的 QLoRA 专门化。

真实的物流优化问题

虽然为玩具示例生成解决方案当然令人印象深刻，但现实问题涉及更详细的业务、海洋、地理、燃料定价/消耗等规则，以及定义成本模型和承担物流过程中的优化角色，例如承运人与航运公司与集装箱码头运营商。

正如我们已经选择的玩具规划问题所见，虽然存在许多经典的规划问题作为 AI 规划竞赛的 PDDL 程序，但这些问题的文本描述已经缺乏或不存在。 甚至最初的 STRIPS 机器人规划问题也以平面图（图形而不是文本描述）的形式呈现，用于移动 Shakey 机器人，并具有额外的块世界类操作，涉及拾取、推动和攀爬。

因此，很想指示更大的 LLMs（405B 或更新的 70B 模型），其中包含更大的训练数据文本集，以生成问题描述（作为文本），这与这些大型 LLMs 的主要用例一致，即为专门化较小的 LLMs 生成训练数据。 但是，我们指示例如 llama 405B 模型为现实的标准物流规划问题（例如泊位分配问题）生成独立的描述的结果，虽然并非完全令人沮丧，但表明需要进行大量的手动检查和编辑； 事实上，直接在 Prolog 中编写解决方案更容易。

现实的规划问题通常不以文本形式表示这一事实表明，从头开始的完全独立的文本描述可能对特别问题更有用，但不一定对现阶段的物流有用。 毕竟，物流优化是既定的规划领域，并且进展可能会以使用实验和常规软件工程实践的增量步骤发展，而 Prolog 作为一种标准化编程语言当然非常适合。

将规划器扩展到解决方案

无论是生成的、手工制作的还是经过润色的，将 Prolog 规划器扩展到实际解决方案都涉及此处未讨论的附加现成组件：

• 集成服务/消息传递和用户界面（专门针对物流，这涉及常见的 EDIFACT 消息传递，用于与已创建并广泛用于物流软件的装载清单和其他供应链数据消息进行交换）。
• 添加业务规则，例如用于集装箱码头/堆场的领域模型，涵盖厢式运输车和其他码头设备。
• 编码通用知识和领域知识，并将 RAG 管道集成到 Prolog 中（例如用于调度谓词的业务日历）。
• 通过就地完成和工具调用迭代改进计划。
• 在适应大规模组合搜索的云 (FaaS) 平台上运行 Prolog 和集成软件。

链接/参考文献

posp

Kambhampati, S., Valmeekam, K., Guan, L., Verma, M., Stechly, K., Bhambri, S., Sayldyt, L., Murthy, A., Position: LLMs Can't Plan, But Can Help Planning in LLM-Modulo Frameworks Proceedings of the 41 st International Conference on Machine Learning, Vienna, Austria. PMLR 235 2024

aiw

Nezhurina, M., Cipolina-Kun, L., Cherti, M., Jitsev, J. Alice in Wonderland: Simple Tasks Showing Complete Reasoning Breakdown in State-Of-the-Art Large Language Models NeurIPS Scientific Methods for Understanding Deep Learning Workshop (SciDL) 2024

tnltopgwl

Xie, Y., Yu, C., Zhu, T., Bau, J., Gong, Z., Soh, H. Translating Natural Language to Planning Goals using LLMs

dwr

Nau, D., Ghallab, M., Traverso, P. (2004) Automated Planning: Theory & Practice. San Francisco, CA, USA Morgan Kaufmann Publishers Inc

osllpds

Paul, G., Röger, G., Keller, T., Helmert, M., Optimal Solutions to Large Logistics Planning Domain Problems Vol. 8 No. 1 (2017): Tenth Annual Symposium on Combinatorial Search

swipldiscourse1

LLM and Prolog, a Marriage made in Heaven? https://swi-prolog.discourse.group/t/llm-and-prolog-a-marriage-in-heaven/7666/2

rrbnl

Borazjaniz, N., Pinatadosi, S.T. Reliable Reasoning Beyond Natural Language https://arxiv.org/abs/2407.11373

warplan

Warren D. (1974) A System for Generating Plans Dept. of Computational Logic, University of Edinburgh School of Artificial Intelligence

cotplanning

Stechly, K., Valmeekam, K., Kambhampati S.] Chain of Thoughtlessness? An Analysis of CoT in Planning Proceedings of the 38tth Conference on Neural Information Processing Systems (NeurIPS 2024)