用范畴逻辑做人工智能规划 Using categorical logic for AI planning

Using categorical logic for AI planning

用范畴逻辑做人工智能规划

摘要

早餐时间到了！你醒来后走到厨房，发现台面上放着一条面包、一把刀、一个生鸡蛋（带壳）、一个煎锅和一个炉灶。你感到饥饿，而你更希望存在的状态是：台面上放着一个鸡蛋三明治。你对当前状况感到难过，但又觉得有能力去改变它！你比较了自己拥有的东西和想要的东西，回忆起自己掌握的烹饪技巧，并设计出以下步骤：

“工程师并非唯一的专业设计师。任何[或事物]只要能设计出旨在将现有状况转变为理想状况的行动方案，即为设计师。”——赫伯特·西蒙（Simon 1988）

早餐时间到了！你醒来后走到厨房，发现台面上放着一条面包、一把刀、一个生鸡蛋（带壳）、一个煎锅和一个炉灶。你感到饥饿，而你更希望存在的状态是：台面上放着一个鸡蛋三明治。你对当前状况感到难过，但又觉得有能力去改变它！你比较了自己拥有的东西和想要的东西，回忆起自己掌握的烹饪技巧，并设计出以下步骤：

1. 用刀把面包切两片
2. 将面包片放在盘子上
3. 把煎锅放在炉灶上
4. 在煎锅上敲开鸡蛋
5. 等待鸡蛋煮熟
6. 把鸡蛋放在一片面包上
7. 盖上另一片面包

在这个例子中，以及在所有规划问题中，你可以注意到三个概念性的要素：一个计划（plan）、一个规划器（planner）和一个规划问题（planning problem）。计划就是你所设计出的步骤序列；规划器是你进行认知推理的活动；而规划问题则是对当前状态与目标状态的比较，以及你所掌握的技能知识。对于大多数日常任务而言，规划过程几乎是自动完成的，以至于我们很少思考这些区分，甚至意识不到自己正在进行规划。然而，如果我们希望将这一活动交由计算机来执行，就有必要使上述三个概念都具备可计算性。

自动规划（Automated planning）是人工智能（AI）的一个领域，其目标是找出一个动作序列（即一个计划），将世界的当前状态转变为一个更理想的状态，也就是满足某些目标条件的状态。规划器接收一个规划问题，并生成一个计划。一种常见的做法是构建一种语言语法，能够容纳动作的语义、动作的前提条件以及动作的效果。然后，由规划器自行设计其解释、管理这些信息并输出计划所用的语法和语义。例如，在实践中，涉及规划的系统架构通常会调用一个 PDDL 规划器（M. Ghallab 等，1998）作为外部服务。它们对世界状态数据的管理和更新则独立处理，要么将计划步骤转换为数据库更新，要么（更常见的是）在计划执行期间或执行之后重新采样世界状态。显然，使用不同的语言可能导致规划器、数据库和计划使用者之间出现冲突，并降低互操作性。

另一种选择是定义一个通用的抽象模型，为规划器、规划问题和计划统一其语法和语义，从而减少不同表示之间的摩擦。在本篇博客文章中，我将解释如何使用一种范畴论方法——即在余预层（copresheaf）范畴中的双推出（double-pushout, DPO）重写——来实现这些概念的操作化。

1 重写规则的结构

重写规则是将数据从一种状态转换到另一种状态的基本操作。一条重写规则包含三个部分：输入（input）、保留（keep）和输出（output）。 输入部分描述了在该规则能够应用于某个世界状态之前，所需的事物类型及其关系。 输出部分描述了在规则应用之后，世界中存在哪些事物类型及其关系。 保留部分则描述了在输入和输出之间保持不变的事物类型。

例如，如果我们想设计一条关于切一片面包的规则，输入部分可能包含一条面包和一把刀。执行完这个动作后，我们希望得到一条面包、一片切好的面包和一把刀。同时，我们还想说明：最终得到的那条面包和那把刀，与我们最初开始时的是同一个面包和同一把刀。

术语“输入”（input）和“输出”（output）是有意让人联想到传统规划文献中的“前提条件”（pre-conditions）和“后置条件/效果”（post-conditions/effects）。然而，“保留”（keep）这一术语是一个新引入的概念，用于追踪在两个状态之间持续存在的实体。你可能会疑惑：“为什么我不能直接构造一个从输入到输出的映射呢？”有趣的是，“保留”部分为我们提供了关于哪些元素被允许消失的有用信息。如果输入中有一个元素在输出中没有出现，那么一个从输入直接到输出的映射（假设我们的映射是全函数，即 total）将迫使我把这个元素映射到某个东西上，而这在概念上是不准确的。然而，如果该元素没有出现在“保留”部分中，那么我就无需在输出状态中对其加以说明，它就可以自由地消失。

在自动规划中，“框架问题”（frame problem）关注的是如何以公理化的方式说明哪些信息保持不变。虽然这种方法并未精确提供一组公理，但它确实提供了一种机制，用于声明在应用某条规则时哪些事物保持不变。

到目前为止，我还没有说明规则中“输入”、“保留”和“输出”部分的本质是什么。它们究竟是什么？是图（graphs）？集合（sets）？还是流形（manifolds）？！形式上来说，一条规则是余预层范畴（category of copresheaves）中的一个“跨度”（span），也就是所谓的 C-集（C-sets）。

1.1 什么是 C-集？

设 C 是一个小型范畴，我们将其视为一个模式（schema）。C-集，也称为 C 上的余预层（copresheaf on C），是从模式 C 到范畴 Set 的一个函子。该模式是一个范畴，其对象表示类型，其态射描述类型之间的“是……的一种”及其他函数关系。你可以将它理解为本体论的一种指称语义模型。范畴 Set 是由集合与函数构成的范畴。因此，C-集是一个将类型映射为集合、将类型间的关系映射为函数的函子。C-集是范畴数据库（categorical databases）的一个简单模型（Spivak 2012），并且在 Catlab.jl 中有功能完备的实现（Patterson, Lynch, 和 Fairbanks 2022）。

C-集的态射是函子之间的自然变换。根据此定义，对于任意模式 C，都存在一个由 C-集及其同态组成的范畴 C-Set。

举个例子，我们可以考察一条规则，它告诉我们当我们执行 :slice_bread 时会发生什么。更准确地说，这段代码通过取可表函子（representable functors）的余极限，构造了一个余预层的跨度（● ← ● → ●）。这一陈述的证明可在（Mac Lane 1978, 第 III.7 章）中找到。重要的是要知道，可表函子会追踪所有涉及某个对象 a ∈ C 的态射，通常记作 C(a, —)。

在这段代码中，你可以看到有三个对象：I、O 和 K，它们定义了诸如 Knife 和 knife 之类事物之间的赋值映射（注意大小写的区别）。

然而，这个函子更有用的一个方面在于它对态射及其他对象的隐式赋值。BreadLoaf 和 Knife 在范畴 C中参与了一些态射，这些态射的余域（codomains）涉及其他看似隐藏的对象，例如 Food（食物）、Kitchenware（厨具）和 Entity（实体）（如 SchDB 中所述）。作为一个函子，I 在目标范畴 Set中承担着对这些态射和对象进行赋值的重要职责。正因如此，可以看出，只要模式（schema）充分编码了与其他对象之间的关系，这一特性就能自动管理隐式的输入（前提条件）和输出（效果）。这种对隐式前提条件和效果的处理，分别被称为框架问题中的“限定问题”（qualification problem）和“衍射问题”（ramification problem）（Malik Ghallab, Nau, and Traverso 2004）。

2 应用规则

现在我们已经了解了如何构建规则，接下来就可以看看如何使用这些规则来推导出新的世界状态。

2.1 可应用性条件

如前所述，规则在 C-集范畴中被表示为跨度（spans）。在自动规划的背景下，我们将这些规则视为计划中的动作，用于将世界状态的某些方面从一个状态转换到另一个状态。世界状态本身也只是余预层范畴中的另一个对象。在规划中，只有当世界状态满足某个动作的前提条件（即输入）时，该动作才能被应用。因此，在我们的框架中，如果存在一个从规则的输入部分 I到所讨论的世界状态 Y的单态射（monomorphism），我们就认为该规则是可应用的。单态射是单射函数（injective function）在范畴论中的一般化概念，通常用带钩的箭头（↪）表示。

这一可应用性条件在构建任务计划时，有助于判断应考虑哪些规则。

2.2 应用的机制 一旦我们确定某条规则是可应用的，该如何利用它来引发世界状态的改变呢？我们知道，这条规则描述了规则应用后世界中应当存在什么，以及输入世界状态与结果世界状态之间哪些内容应保持一致。同时我们也知道，余预层范畴是一个初等拓扑斯（elementary topos），这尤其意味着我们可以自由地取极限（limits）和余极限（colimits）。鉴于本文大部分内容都在讨论跨度（spans），这一性质非常便利。因此，为了根据一条规则来实现世界状态的变更，我们可以考虑使用双推出（Double Pushout, DPO）重写方法（Ehrig, Pfender, and Schneider 1973；Brown et al. 2022）。

DPO 重写的一般步骤如下：

1. 找到一个推出补（pushout complement）*
2. 完成左侧的推出（pushout）
3. 完成右侧的推出（pushout）

一张展示使用双推出（DPO）重写方法的卡通图，该图基于对 :slice_bread 规则的图形化改编。

你可以看到，在左上角，描绘了我们所掌握的世界和规则的信息。在我们的世界中，有一台冰箱、一条面包、一个梨（？）、一把刀、一个碗和一个煎锅。我们希望执行 :slice_bread 这个动作。利用 DPO 方法，我们首先可以识别出从规则保留部分（rule-keep）到世界保留部分（world-keep）的一个映射，即推出补（pushout complement）。请记住，推出操作会将跨度的目标对象沿着其顶点“粘合”在一起。因此，我们可以验证所选的推出补是否能生成我们的世界输入（world-input）。一旦我们确认这是有效的，就可以像往常一样构造右侧的推出。由此，我们得到一个新的世界状态：其中所有原有实体仍然存在，并新增了一片面包，这片面包通过某种关系（灰色线）与原来的面包条相连。注意：图中简化的浅蓝色映射应表示每个实体在世界输入（world-input）和世界输出（world-output）中都映射到“它自身”。

3 开始规划（带回溯的前向搜索）！

现在我们已经知道如何选择规则以及如何应用规则，就可以开始进行规划了。回想一下，一个计划是一系列动作，用于将初始世界状态转变为满足某些目标条件的状态。在我们的框架中，要构建一个规划问题，需要在余预层范畴中指定两个对象：初始状态和目标状态。然后，我们可以将一个计划视为一系列规则，当这些规则依次应用于初始状态后，所构造出的对象中存在一个从目标状态到该对象的单态射（monic map）。

我们借鉴了自动规划领域中已有的成功方法，实现了一种带回溯的前向搜索算法（Malik Ghallab, Nau, and Traverso 2004，第4章）。算法的终止条件是检查当前世界状态中是否存在一个从目标状态到该状态的单态射。

这种刻意的排版选择是为了表明哪些数据是数学上严谨的（用数学符号表示），哪些数据是启发式或权宜之计、并非源自范畴形式化体系（用等宽字体表示）。特别地，我们称 Y、G 和 r_I 是余预层范畴中的对象。

与其他规划算法一样，该方法也面临与循环和非终止相关的问题。这种情况发生在：当应用规则时，世界状态的描述未能捕捉到某种方式来销毁某个对象。例如，在当前模型中，切面包并不会以任何方式减少面包条的数量，这意味着我们的规划器理论上可以无限次地切同一块面包。未来，本框架将整合带属性的 C-集（“acsets”），使用户能够为每个实体指定属性，例如 BreadLoaf → NumSlices。这一结构将提供一种明确定义的方式，用于对属性进行算术运算及其他操作，从而有助于跟踪资源限制。目前，我们采用一种临时方法——一个名为 rule_limit 的字典，用于指定在计划中每条规则最多可应用的次数。

4 为何采用范畴论抽象？

你可能会疑惑：既然已经存在可用的自动规划系统，这种形式化方法究竟有何优势？事实上，当前的实践面临若干局限，而我认为范畴论的视角有助于应对这些问题。

1. 一种传播隐式前提条件和效果的方法。如前所述，框架问题关注的是在显式条件已知的情况下，如何处理隐含的世界状态。正如我们所见，由于我们使用了从范畴 C到集合范畴 Set的函子，隐式效果（即所谓的“衍射问题”，ramification problem）和隐式前提条件（即“限定问题”，qualification problem）得到了自然处理。这使得规则设计者可以只建模最重要的变化，并确信相关联的变化会自动随之传递。

2. 动作与事件的统一抽象。现有规划器无法处理外部事件。而在本框架中，动作和事件属于同一类型——即范畴数据库的重写规则。这意味着在动态规划环境中，我们可以支持两种操作模式：(a) 应用一条重写规则来捕捉某个外部事件，并更新当前世界状态；或 (b) 在当前世界状态与目标状态之间搜索一个计划。这种共享的抽象使我们能够接收新信息并继续规划，而无需重新定义整个规划问题。

3. 比一阶逻辑更具结构化的语言。对于试图在实际应用中使用自动规划的从业者而言，用一阶逻辑公式表达规划问题往往显得笨拙且缺乏结构。构成这些公式的基本命题原子需要仔细建模语义，却缺乏明确指导。例如，一些原子可能是 breadloaf_on_table=True、slice_on_table=False 和 knife_in_hand=True；但也可能是 breadloaf_sitting_on_table=True 和 knife_in_left_hand=True，具体取决于动作如何使用这些原子，二者可能具有等效作用。而在本体论（或模式 schema）指导下对知识进行建模，为表达规划问题中的世界状态条件提供了一种更自然的方式。

4. 支持层次结构与并发性的途径。目前尚无方法处理彼此独立的动作排列之间的等价性。前向和后向规划都假设动作序列是全序的；计划空间规划（plan-space planning）虽允许部分有序的计划集合，却无法处理相互依赖的动作。此外，现有规划器也缺乏处理同时发生动作的机制（Brachman and Levesque 2004, 第15.3.1节）。若使用范畴语言来表达计划、规划器和规划问题，将为我们打开通向其他数学结构的大门，例如操作子（operads，用于层次结构）和幺半范畴（monoidal categories，用于并发性）。

尽管有上述优势，我们仍有许多工作要做。本文描述了一种以范畴方式表述规划问题的方法，并将现有规划算法适配到这一抽象框架中。然而，我们尚未说明如何以更结构化的方式描述计划——而不仅仅是一系列规则的序列。此外，我们希望进一步探索范畴论如何帮助设计新的规划算法，特别是层次化规划器。如果你有任何想法，欢迎在下方分享你的见解！

原文链接：https://topos.institute/blog/2022-09-20-ai-planning-csets/