复杂世界中规划的范畴论方法

A CATEGORY THEORETIC APPROACH TO PLANNING IN A COMPLEX WORLD

复杂世界中规划的范畴论方法

https://angelineaguinaldo.com/assets/papers/aguinaldo-prelim-2023.pdf

摘要

人工智能（AI）规划已成为开发智能系统的关键组成部分，有助于在复杂环境中生成和调整计划以实现特定目标。本论文致力于解决复杂领域中的任务规划挑战，尤其是那些包含大量对象与属性、丰富关系与依赖性，以及知识不完整或不断演化的领域。我们的方法旨在应对三个具体问题：（1）难以表达复杂且结构化的世界状态；（2）在推理传递性关系时面临的困难；（3）AI组件在神经符号推理中的集成问题。为解决这些问题，我们提出了一种名为 AlgebraicPlanning 的新语言，该语言基于范畴论中的 C-集（C-sets）和DPO（双推出）重写机制。该语言利用基于本体的类型化图（ontology-based typed graphs）的表达能力，来刻画复杂的世界状态及其内部关系。我们假设，相较于现有规划器，本规划框架将生成更高质量的计划，并提升任务规划在复杂现实世界领域中的适用性。为验证这一假设，我们将设计一种方法，用于评估本框架所生成计划的长度、稳定性、成功率和效率，并与其他规划算法进行比较。我们还将探索该方法在多个不同领域的应用，例如经典规划领域、制造业以及家庭服务机器人。本论文的预期贡献包括：（i）一种用于表示复杂世界状态的稳健语言；（ii）一种基于该形式体系的规划算法；（iii）一种计划质量评估方法；（iv）多个多样化的案例研究；以及（v）范畴论在AI规划中的应用。这些进展将为构建更稳健、更具适应性的智能系统铺平道路，使其能够在复杂环境中有效导航并执行任务。

第一章 引言

在过去的几十年中，人工智能（AI）规划已发展成为智能系统开发中的关键组成部分，使系统能够对行动进行推理，并在复杂环境中实现特定目标。所谓复杂环境，指的是包含多种因素、条件或元素的情境或场景，这些因素使得任务的规划与执行更具挑战性。这些因素可能是动态的、不确定的或相互关联的，并会影响机器人的决策过程。从符号任务规划的视角来看，复杂世界状态指的是这样一种情形：对环境及其各种元素之间关系的表示涉及多个因素，从而使规划问题变得更加困难。这些因素可能与环境中对象的数量、属性、关系和约束有关，也可能与智能体目标的复杂性以及不同智能体之间的交互有关 [37, 71, 32]。在本论文中，我们将特别关注那些具有大量对象与属性、丰富关系与依赖性，以及知识不完整或不断变化的世界状态。基于此，我们不会考虑与分层目标、时间约束和多智能体场景相关的问题。这种对世界状态复杂性的限定视角，在机器人需要在包含大量对象及其相互作用的环境中执行任务的场景中尤为有用，例如制造业中的装配线场景。

例如，设想一个大型工厂中的任务规划场景，该工厂拥有一条高度自动化的装配线，用于生产如图1.1所示的电动汽车。工厂车间包含各种机器、机器人和人类操作员，它们以协调的方式协同工作。装配线由多个工位组成，每个工位负责车辆装配过程中的特定部分。在这一复杂环境中，世界模型需要表示各种对象和关系，例如不同类型的机器（如焊接机、喷漆机和装配机）；各类车辆部件（如车架、发动机、车轮、电池、电子元件以及内外饰部件）；机器、机器人与车辆部件之间的各种兼容性；空间关系（例如机器、机器人和工作站的位置）；以及时间关系（例如调度安排和先后顺序约束）。

现在，尽管存在多种类型的机器人——例如用于运输的移动机器人，或用于操作与装配的机械臂——它们会与不同的工作站进行交互，因此需要不同的任务计划，但工厂车间中的所有机器人都将受益于一种任务规划器，该规划器（a）能够对同样庞大而复杂的世界模型进行推理，且（b）在世界发生微小变化时仍能保持合理的稳定性。

定义一种能够在任务规划中管理世界诸多特征的形式化方法，是本论文的主要贡献之一。如前所述，在为复杂领域设计任务规划框架时，需要考虑诸多因素。以下总结了本论文旨在解决的三个具体问题。

1. 表达复杂且结构化世界状态的困难。当前的表示框架难以捕捉现实世界环境中的丰富关系和精细结构，从而限制了规划领域表达能力 [37, 86]。这使得难以利用领域特定知识并准确建模包含大量对象与关系的复杂世界状态。尽管PDDL 1.2 [51] 中包含了对象类型系统，但在实践中，规划领域内对复杂的类型层级与关系的考虑仍十分有限。例如，在Planning.wiki的“Planners”页面上，107个规划器中仅有七个 [62, 9, 31, 5, 38, 43, 42] 提及使用了类型系统或 :typing 扩展。在这些案例中，类型系统最多仅用于验证谓词，而并非用于基于世界模型进行更复杂的推理。此外，现有规划方法在面对大量文字（literals）时扩展性不佳——当规划问题中的文字数量增加时，规划问题的复杂度也随之上升 [37]。这可能导致大型且复杂的世界状态（尤其是源自类型图如场景图的状态）变得难以规划。
2. 关于传递关系（组合）的推理困难。更具体地说，当前方法并未考虑由关系形成的隐式传递依赖。因此，它们可能难以对由此类关系引发的间接依赖与交互进行推理。在本论文中，我们尤其关注语言在推理传递闭包方面的能力，我们将此称为“组合”（关系或谓词的组合），因为我们相信这一特性将提升为复杂领域生成高质量计划的能力。目前，传递关系需通过详尽精确地枚举相关命题，或通过领域公理 [80] 来表示，而这两种方式都会增加搜索空间的复杂性。在领域公理的情形下，还需进行更多测试以确保其作为语法组件的稳定性 [30]。
3. 难以与其他AI组件集成以支持神经符号推理。将任务规划与其他关键AI组件（如感知与控制）集成仍是一个挑战 [77]。这主要归因于表示不匹配。任务规划器使用符号逻辑语言，而用于感知的神经方法则使用张量，二者均需定义语义。因此，迫切需要一种可互操作的语言，以弥合这两种表示之间的鸿沟。整合这些表示颇具挑战性，因为通常需要为世界的连续与综合特征寻找适当的抽象 [3, 50, 34]。像场景图这类感知形式化的进展，为整合神经与符号知识提供了契机。我们认为，我们的方法通过提出一种作用于类型图、同时保留本体所涵盖关系的规划表示，能够解决神经与符号规划的集成问题。

我们希望，通过运用我们的规划框架解决上述开放性问题，我们能够在一系列复杂领域中生成更高质量的规划方案。

1.1 研究问题

在整个本论文中，我们将聚焦四个指导性的研究问题。

RQ1：在规划过程中使用更具描述性和结构性的形式化方法（如场景图与本体），能在多大程度上拓宽任务规划在更广泛复杂现实领域中的适用性？

RQ2：为在规划过程中保持本体结构，可对现有的基于本体的规划架构做出哪些修改？

RQ3：范畴论能否通过提供清晰一致的形式语义来改进复杂领域中高质量计划的生成？该形式语义涉及类型与传递闭包。

RQ4：开发一种具有清晰一致形式语义（针对类型与传递闭包）的规划语言，在多大程度上能改善规划方案的质量，特别是在复杂领域中？

1.2 我们的方法

复杂世界状态通常涉及大量对象与错综复杂的关系，因此亟需一种稳健的表示语言，能够捕捉领域的内在复杂性。在本论文中，我们提出一种名为 AlgebraicPlanning 的新颖语言，它基于范畴论中的 C-集与 DPO 重写机制，借助基于本体的类型图的强大表达能力，管理复杂世界状态及其内部对象间的关系。我们假设环境是完全可观测且确定性的。知识表示与机器人学中的常见形式化方法（如知识图谱与场景图）均可表示为类型图，使这种语言成为机器人应用中任务规划推理的有用工具。

此外，为了衡量我们的规划框架在多大程度上提升了规划方案的质量，我们将设计一种方法，用于评估规划长度、成功率以及时间与内存效率，并将其与其它规划算法进行比较。最相关的规划器是那些处理类型与传递闭包的规划器，即Metric-FF [42]（含或不含传递闭包的推导公理）[80]。我们还引入了一种方法，用于评估计划相对于规划问题变化的稳定性 [29]。

这种方法的前提是我们开发的一种新型测量手段，用于快速评估规划问题间的距离，以确保模拟中问题分布的公平性。通过提供一种系统性的方式，考察世界变化下的计划稳定性，我们也得以洞察世界中各项特征对于达成目标的相关性。

通过开发一种丰富的表示语言和一种评估计划质量的方法，本论文旨在推动动态环境中AI任务规划的发展，为构建更稳健、更具适应性的智能系统铺平道路。简而言之，本文提出如下假设：

到目前为止，我们已定义了数学形式化体系，开发了一个原型前向规划算法，并开始构建用于测试的基础设施。我们的目标是在本工作的后续部分中，对每个假设进行明确的评估与完善。

1.3 贡献

我们预期本工作将具有以下贡献：

1. 贡献一：一种基于范畴论的丰富表示性规划语言。设计并实现一种稳健的语言，用于表示复杂世界状态，能够捕捉各类世界变化。该语言应具备足够的表达能力，以建模对象间的复杂关系，并便于高效推理世界变化对计划稳定性的影响。
2. 贡献二：一种基于该形式化体系的规划算法。识别一种性能良好的基于状态的规划算法，并将其适配至所提出的表示语言。
3. 贡献三：一种用于评估计划质量的方法。开发一种方法，用于评估计划的质量，包括其对世界状态变化的稳定性。该方法应提供一种衡量标准，用以评估不同规划问题之间的差异，确保多样化的规划问题得到恰当表示。
4. 贡献四：探索不同领域中规划应用的案例研究。在不同领域（如经典规划领域、制造业和家庭服务机器人）中研究所提方法的适用性，在这些领域中可研究复杂世界状态与动态环境。这种探索有助于识别潜在的改进方向与扩展路径，展示本方法在多个应用领域的相关性。
5. 贡献五：一个完全基于范畴理论形式化的示例与应用。在多种问题与领域规模上，展示范畴理论形式化方法在AI任务规划中的应用。这一探索为范畴理论的实际应用提供了具体实例。

提案结构

本论文提案共分为七章，全面阐述所提出的方法。第一章 提供研究动机与问题定义，概述研究目标，并介绍论文结构。第二章 回顾知识表示、任务规划与范畴理论相关的背景及前期工作。第三章 讨论使用所提形式化方法建模复杂世界状态的初步成果。第四章 讨论使用所提形式化方法进行规划的初步成果。第五章 提供关于测量问题差异相关工作的概要。第六章 总结所提工作、评估方法与时间表。第七章 通过总结问题与所提贡献来结束本提案。附录A 提供预期实验领域所用的PDDL领域与问题文件示例。附录B 提供AlgebraicPlanning实现的副本。

附录C 提供论文、报告及课外贡献的清单。附录D 提供三个研究领域的阅读书目。

第二章 背景与相关工作

本章分为三个主要部分：第2.1节 规划中的知识表示，第2.3节 任务规划，以及第2.4节 范畴论。

这些是本工作中将要利用的主要主题领域。在此，我们将提供相关工作的背景介绍与概要。

2.1 规划中的知识表示

在本节中，我们将总结有关在任务规划过程中整合语义信息（使用本体和场景图形式化方法）的背景及前期工作。我们的目标是考察语义信息如何被用于任务规划，以提升其在复杂现实世界领域中的适用范围。

2.1.1 现有方法

目前，能够以形式化语言捕捉所需语义的世界状态表示方法寥寥无几。本论文中我们比较的两个候选方案是：带类型的命题（typed propositions）和带类型的图形式化方法（typed graph formalisms），它们均具备处理带类型对象与关系的能力。

2.1.1.1 使用带类型命题

基于STRIPS的世界状态表示方法建立在一种受限的一阶逻辑基础上，其中世界状态被表示为文字（literals）的合取，而每个文字是一个原子命题或其否定 [37]。这些命题可以编码诸如物体位置、各类传感器状态以及其他相关信息等事实。逻辑运算符如AND、OR和NOT被用来将这些命题组合成更复杂的表达式，用以描述世界状态不同部分之间的关系。世界状态可被“提升”至抽象状态，即由谓词合取构成的状态，其中谓词是带类型变量间的n元关系。例如，谓词 on(x - Block, y - Block) 可能表示“一个块x位于另一个块y之上”，或者同样合理地表示其逆向情况。需要强调的是，谓词的语义必须通过非正式方式确立，比如通过外部文档或口头说明。当变量符号（如x和y）被赋予常量符号时，谓词便成为一个实例化文字（grounded literal）。例如，实例化文字 on(b1 - Block, b2 - Block) 可表示“名为b1的块位于名为b2的块之上”。

2.1.1.2 使用带类型图

带类型图是为机器人应用中对象与关系添加结构的强大工具。带类型图的定义见定义2.1.1 [46]。

这提供了一种基于类型图或本体论来建模和推理环境中对象之间关系的方法。可以在机器人建模世界状态的工作[77, 44, 11, 13]和场景图[21, 6]中找到这种应用。

知识图谱 知识图谱是一种知识表示形式，它使用基于图的结构来建模实体之间的关系[14]。它们由节点组成，这些节点代表实体，如对象、动作或概念，以及边，这些边代表这些实体之间的关系。知识图谱提供了一种灵活且富有表现力的方式来表示结构化信息，并能够高效地进行查询和推理。在机器人学中，知识图谱用于表示和推理环境中各种元素之间的关系，例如：对象和机器人之间的空间关系，例如“对象A在对象B的左边”；事件和动作之间的时间关系，例如“动作A必须在动作B之前完成”；概念和实体之间的语义关系，例如“对象A是容器的一种类型”。知识图谱对于机器人中的高级推理任务特别有用，例如符号规划，其中机器人必须考虑复杂的关系和约束来生成有效的计划。

场景图 场景图是知识图谱的一种专门形式，主要用于计算机图形学和机器人学中，以建模场景的层次结构[21, 21]。它们由代表对象、动作和空间关系的节点组成，这些节点以反映场景层次组织的树状结构排列。场景图通过以结构化方式组织信息，使复杂场景的有效表示、操作和渲染成为可能。在机器人学中，场景图用于表示环境的几何和拓扑结构，例如：对象的层次组织，例如“对象A由部分B和C组成”；对象之间的空间关系，例如“对象A在对象B内部”；对象之间的相对位置和变换，例如“对象A相对于对象B旋转了90度”。场景图对于机器人学中的几何推理任务特别有用，例如运动规划、导航和物体操作，其中机器人必须考虑环境的空间结构来规划和执行其动作。

我们认为，类型图比类型图 T 提供的附加谓词更有利于类型谓词，因为它不仅更具表现力，而且可以自然地应用于现有的本体论，如KNOWROB [77, 11]、RoboEarth [78]、AfRob [82] 和其他[69] 在定义世界状态时。

2.1.1.3 传递（组合）关系的需求

特别重要的是，这两种表示方法都缺乏自动传递关系，这是一种隐含的关系，可以帮助推理场景中对象之间的间接交互。传递关系使规划者能够推理场景中对象之间的间接关系。例如，如果对象A在对象B的上方，而对象B在对象C的上方，传递关系允许规划者推断出对象A间接地在对象C的上方。这也可以被认为是从A到C的路径组合。在场景图中包含传递关系也将允许更紧凑和高效的对象关系表示。

在PDDL中，可以使用PDDL 2.2 [26]中的派生谓词来包含传递关系，但它们不能普遍陈述，必须为每个领域定义。在类型图中，可以包含路径方程以建立所有可能路径组合的路径等价性，但这将需要扩展边列表以包含这些额外路径。这两种方法都会显著增加搜索空间的计算复杂性。

我们假设这种结构可以帮助规划者生成更有效和有效的计划，这些计划考虑了这些间接关系，包括分类和关联关系。在本论文中，我们提出证明这种属性在提高现实世界场景中计划的效率和质量方面的价值。

2.1.2 语义知识集成的一般方法

在机器人领域，人们已做出持续努力，通过本体（ontologies）及其他类型化形式体系 [56, 58]，将关于世界的语义信息整合到规划与控制中。大多数工作集中于以下方向：(1) 将传感器数据流直接转换为规划所需的有意义谓词 [12, 65, 47]；(2) 通过公理和数据驱动建模建立默认知识 [78, 79, 57]；(3) 将本体转换为任务相关的谓词 [33, 41, 87, 19]。然而，直接将本体集成以丰富基于广泛接受的形式体系（如PDDL [36]）的机器人任务规划世界状态的实例却寥寥无几。

在上述工作中，只有 Galindo 等人 [33] 和 Cashmore 等人 [19] 的研究符合这一标准。

Cashmore 等人 [19] 设计了一个名为 ROSPlan 的框架，包含两个组件：知识库和规划系统。其架构如图 2.1(b) 所示。该知识库包含一个由领域专家提供的本体子组件，可用网络本体语言（OWL）[10] 表达。另一个子组件负责解释智能体的传感器读数，并根据本体将场景信息补充到知识库中。要启动规划，终端用户必须提供一个领域文件，初始状态则根据知识库内容并依照领域文件的规范进行填充。总体而言，该框架提出了一种合理的高层架构，但并未提供各接口间信息转换的具体细节，因此难以判断该架构在各类领域和规划问题上的实际表现。

Galindo 等人 [33] 采用了一种两部分的知识表示系统，包括：(i) 以场景图（称为 S-Box）形式表示的机器人环境空间信息；以及 (ii) 描述概念间层次关系的本体（称为 T-Box）。他们定义了一个从空间图中的字面对象到本体中术语概念的全函数映射，如图 2.1(a) 所示。S-Box 中观察到的谓词与 T-Box 中观察到的谓词被转换为 PDDL 谓词，从而构成初始状态。此后，规划过程使用现有的带类型规划器（即 Metric-FF [42]）正常进行。该方法的优势在于能够充分利用本体，根据 T-Box 提供的层次结构，将隐含信息作为谓词添加到世界状态中。然而，一旦信息被送入规划器，通过概念公理对领域所做的语义增强便会丢失。这使得无法确保规划过程中概念的一致性得以保持。例如，某个动作可能导致机器人将一张床从卧室移动到厨房，此时在语义模型中该操作是否有效或无效并不明确。尽管这一选择尚存争议，但我们认为，一个动作是否违反语义模型的判断，在形式体系内部应当是明确无歧义的。我们的方法旨在在整个规划过程中保留本体模型中声明的关系。

2.2 场景图的集成

场景图的近期发展催生了一些新框架，试图在任务规划过程中高效利用这些对世界的描述性模型。场景图是知识图谱的一种专门形式，其对象、属性和关系被限定为通过基于视觉的感知与推理所获得的事实 [54, 6, 21]。在场景图中，本体通常用于将场景数据对齐到类层次结构中。然而，与前述情况类似，相关方法仍然稀缺。我们已识别出少数几项尝试 [2, 64]，试图在任务规划中正式地、有效地使用场景图。

Agia 等人 [2] 着眼于解决任务规划中场景图复杂性管理的问题。场景图是表示机器人所感知环境的有用抽象，但往往过于复杂——包含大量顶点和边——导致难以在大规模场景下进行有效推理。为缓解这一问题，规划器可采用一些过程，以确定场景中哪些属性最为相关，同时保留类层次结构和对象特征所提供的语义信息。为此目的设计的一个规划器示例是 SCRUB 规划器 [2]。SCRUB 是一种与具体规划器无关（planner-agnostic）的过程，它对状态空间进行剪枝，仅保留场景图中相关的事实。它与 SEEK [2] 配合使用，SEEK 也是一种与规划器无关的过程，利用图神经网络 [72] 生成的重要性评分对场景中的对象进行打分。根据某个阈值，所有相关对象的祖先对象均作为事实保留在状态中。SCRUB 和 SEEK 这两个过程显著减少了刻画世界状态所需的事实数量。这些事实随后被转换为二元谓词，并传递给经典规划器。这种方法提供了一种基于启发式的相关事实识别机制，但与大多数启发式方法一样，存在局限性，例如近似不准确的问题。我们所提出的组合方法则利用现有的语义结构来确定场景中对象与关系的相关性。

Miao 等人 [64] 采取了另一种利用场景图描述世界状态和动作模型的方法。在他们的方法中，动作算子通过初始状态子图、最终状态子图以及中间子图来指定。对于这些子图中的每个对象和关系，全局场景图会通过将动作模型中提及的对象添加到场景图中而进行更新。当且仅当全局场景图包含初始子图中的对象时，该动作才可应用。如果最终状态子图中引用了场景中不存在的对象，则这些对象会作为孤立顶点引入。随后，通过查询包含类型层次结构的外部知识库（如 ConceptNet [73]），将这些顶点连接到全局场景图中。该过程会搜索匹配的对象类型，识别场景图中已存在的父类型，并从该对象定义一条指向现有类型的边。这种处理世界状态变化的方法较为脆弱，因为它依赖于外部知识库被正确且完整地实例化，才能恰当地整合新信息。

Jiao 等人 [48] 提出了一种使用名为 contact graph+（cg+）的三维场景图表示进行高效序列任务规划的方法。该表示通过识别有效的机器人-场景交互来抽象场景布局。目标构型可自然地在接触图上指定，并通过结合遗传算法与随机优化方法生成。任务计划的初始化通过计算初始接触图与目标构型之间的图编辑距离（Graph Editing Distance, GED）实现，从而生成对应于可能机器人动作的图编辑操作。该方法的优势在于能够通过组织场景实体，利用图编辑来预测动作结果，从而弥合机器人感知与执行之间的鸿沟。作者强调，机器人成功完成了那些难以用传统规划语言（如规划领域定义语言 PDDL）指定的复杂序列物体重排任务，展示了在接触图上进行机器人序列任务规划的高度可行性与潜力。该方法的一个局限在于不适用于非操作类任务。此外，该方法依赖于在构建接触图表示之前获取准确的三维场景信息。

总体而言，在规划过程中将语义信息融入世界状态表示已引起一定关注。这些方法满足了利用本体支持丰富且复杂世界表示的需求，但在广泛任务范围内仍无法在规划过程中保留本体信息。在我们的方法中，本体是规划形式体系不可分割的一部分，并配有专门用于操作此类数据的工具。此外，由于本体中的对象和关系被用于识别图中的相关子结构，我们假设该方法能够在无需预测对象相关性的情况下扩展至大规模场景图。

2.3.1 状态转换系统模型的规划

状态转换系统模型是规划问题的一种形式化表示，它描述了问题的状态空间和可以在状态之间移动的可能动作。在这个模型中，一个规划问题可以定义为一个元组

，其中：

状态转换系统模型的规划通常用于自动化规划系统中，这些系统使用搜索算法来探索状态空间并找到实现目标的动作序列。搜索算法通常使用启发式方法来指导搜索并提高其效率。状态转换系统模型提供了一种结构化的方法来表示规划问题，并推理可能采取的动作序列以实现目标。状态、动作和转换函数的表示方式在本论文中是一个重点比较。

2.3.2 STRIPS（斯坦福研究所问题求解器）

STRIPS（斯坦福研究所问题求解器）是一种在20世纪60年代末和70年代初由Richard Fikes和Nils Nilsson在斯坦福研究所开发的规划形式化方法。STRIPS是一种自动化规划系统的早期例子，并且经常被用作其他更复杂规划系统的基础。STRIPS规划形式化方法遵循状态转换系统模型，并将世界表示为一组状态。规划问题涉及找到一系列动作，将初始状态转换为目标状态。

在STRIPS中，世界被表示为一组命题或谓词。动作被定义为前提条件，即必须满足的动作执行条件，以及效果，即描述动作执行时世界变化的效果。动作的效果由两组表示：添加列表和删除列表。添加列表包含动作执行时变为真的谓词，而删除列表包含动作执行时变为假的谓词。STRIPS中的规划过程包括搜索可能的动作序列空间，以找到一个从初始状态开始并达到满足目标条件的状态。这通常是通过使用搜索算法实现的，如深度优先搜索或最佳优先搜索，并结合启发式方法来指导搜索过程。

STRIPS规划问题的解决方案是一系列动作，当在初始状态 I 中执行时，会导致一个状态，其中目标 G 中的所有文字都为真。规划过程涉及找到满足目标的同时尊重动作的前提条件和效果的动作序列。STRIPS规划形式化方法为许多后续规划表示方法奠定了基础，如ADL（动作描述语言）和PDDL（规划领域定义语言），这些方法扩展并改进了原始STRIPS概念。

2.3.3 PDDL（规划领域定义语言）

PDDL（规划领域定义语言）是一种提供STRIPS扩展的语言，支持更丰富的特性，如类型变量、时间规划和数值量词。PDDL问题指定动作、对象和目标，以及问题的初始状态。目前，PDDL是最广泛使用的规划问题和领域的规范语言。虽然PDDL试图将规划问题表示为状态转换系统，但其语法的形式语义并不存在：没有对其意义的精确数学定义。在任何情况下，确实存在PDDL语法的形式定义。PDDL语言以领域独立的方式描述规划问题，将领域描述与问题描述分开。基于PDDL1.2的PDDL领域描述由以下组成：

• 定义领域中对象类别的类型有限集合。
• 描述对象及其关系的属性的谓词有限集合。
• 动作的有限集合，其中每个动作都指定了参数、前提条件和效果。

PDDL问题描述由以下组成：

• 属于领域描述中定义的类型的有限对象集合。
• 初始状态，一组在规划过程开始时为真的谓词实例，描述对象的属性。
• 目标，一组在计划执行后必须在最终状态中为真的基文字。

为专为 Blocksworld 设计的领域所编写的示例领域文件与问题文件，可在附录 A 中找到。

PDDL 还包含众多语言扩展，这些扩展为 PDDL 增添了有用的功能，例如偏好 [35]、时间约束 [66] 以及对否定文字的支持 [30]。尽管这些扩展使 PDDL 成为一种更强大、更灵活的语言，可用于指定规划问题和领域，但它们在与规划算法结合使用时也会引入额外的复杂性，并可能引发不一致性 [45]，因为尚不清楚这些扩展如何普遍影响搜索空间。因此，在规划中开发具有清晰且一致形式语义的语言，对于提升规划器的性能至关重要。在我们的方法中，我们旨在为规划过程中的传递闭包与类型提供形式语义，以提升整体计划质量。

2.3.4 评估计划质量

作为评估指标的计划质量可分解为若干与计划及规划过程相关的特征。AI 规划中用于评估计划质量的一些常见标准包括 [45]：

• 计划长度（Plan length）：指实现目标的计划中所包含的顺序步骤数量。
• 效率（Efficiency）：指计划执行的速度及其对可用资源的利用程度。
• 成功率（Success Rate）：指计划在多种可能场景下是否能够实现预期目标。
• 稳定性（Stability）：指计划在面对环境中的句法或语义变化时的稳健程度 [29]。
• 灵活性（Flexibility）：指计划适应不断变化的情境或新信息的难易程度。

这些标准可单独或组合使用，以评估由规划系统生成的计划的质量。上述所有标准均有助于评估我们方法所生成计划的质量；然而，我们将省略对“灵活性”的测量，因为这需要在本项目范围内开发有效的自适应算法，而这将留待未来工作完成。

2.3.4.1 实验设置

Howe 和 Dahlman [45] 总结了用于基准测试规划算法的标准实验设置，如图 2.2 所示。在评估我们的方法时，将大致遵循这一设置。具体细节将在第 6 章中讨论。

2.4 范畴论

在本节中，我们将阐明使用范畴论的动因，提供作为范畴论必要基础的定义，并概述相关工作。

Eilenberg 与 MacLane [27] 在 20 世纪 40 年代中期研究代数拓扑时首次提出了范畴论的概念，其初衷是作为一种在代数与拓扑之间传递定理的工具。在此过程中，他们提供了一种数学语言，将众多数学乃至非数学概念提升为“实体之间的映射”以及“这些映射的复合”这一层面。范畴论提供了一个数学框架，有助于理解不同数学对象的结构及其相互关系，并特别强调在高阶映射中保持复合性。近年来，人们也投入了大量精力，利用此类结构来定义一种通用框架，以实现对基于本体的数据库进行一致且形式化的操作 [18, 68, 75, 67, 74]。

范畴论已在多个领域找到了重要应用，包括系统工程与设计 [16, 17, 20]、面向软件系统设计的模型驱动工程 [53, 24] 以及物理学 [8, 1]。范畴论已被应用于各种工程与科学问题，例如数据库迁移 [76, 74]；异构信息与传感器融合 [70, 49, 52]；科学知识表示 [40]；以及自动装配规划 [15]。然而，在人工智能领域，具有说服力的应用实例仍然很少。机器人学与规划领域中为数不多的例子 [3, 4, 63] 展示了一些有前景的用例，但尚未在具有实际规模的广泛问题上进行测试。

在本论文中，我们致力于将范畴论的应用拓展至人工智能任务规划，以解决在复杂领域中确保生成高质量计划的问题。

在第 4 章中，我们提出，这可以通过将符号规划问题视为在类型化图（typed graphs）上进行的一系列保结构的图重写（graph rewrites）来实现。

2.4.1 范畴论的核心概念

在讨论形式化定义之前，我们希望先对范畴及其核心概念做一个入门性阐述。在接触一种新的数学语言时，应牢记：这类结构本质上是一种语言，它提供了可用于讨论特定概念的“类型”与“语法规则”。例如，图（graphs）仅有两种类型：(i) 节点（nodes）和 (ii) 边（edges）；并且只有一条语法规则：一条边最多只能存在于两个节点之间。利用这些类型和语法规则可以表达很多内容，但要建模更复杂的概念，往往仍需将其转换为其他结构。

范畴论定义了以下两种类型：(i) 对象（objects）和 (ii) 态射（morphisms）。乍看之下，图与范畴在类型数量上的相似性似乎暗示它们具有同等的表达能力。然而，范畴配备了一长串语法规则，从而支持更丰富的构造。以下列举了范畴论中一些基础性的语法规则：

• 态射是存在于至多两个对象之间的有向关系（类似箭头），具有源对象（source）和目标对象（target）。
• 若前一个态射的目标等于后一个态射的源，则这两个态射可进行复合。
• 这种复合运算是结合的（associative）。
• 对每个对象都存在一个特殊的箭头，称为恒等箭头（identity arrow），它将该对象映射到自身。
• 范畴由一组对象和态射构成。

这些构成了范畴的基本规则。这种语言最突出的特征是态射的复合概念。由于这些定义具有简洁性和普适性，使得我们可以在每个概念内部嵌入更复杂的结构，同时仍保持范畴语言内部的封闭性。例如，我们可以将一个范畴本身视为一个对象，而范畴之间的态射则可视为函子（functor）。函子被定义为在范畴的对象与态射之间的一种映射，且该映射在两侧均保持态射的复合结构。我们还可以对对象和态射的定义施加进一步限制。例如，范畴之间的态射可以是一个仅将对象映射到对象而忽略箭头的函子，即“对象上的双射函子”（bijection-on-objects functor）。另一个例子是，我们可能希望将范畴中的对象限定为仅包含集合，而箭头限定为函数——这就构成了“集合范畴”（Category of Sets）。

总结并进一步阐述，范畴论围绕若干基本概念展开，这些概念构成了其在计算机科学中应用的基石 [55]：

• 范畴（Categories） ：一个范畴由对象以及这些对象之间的态射（箭头）组成，并满足特定性质。对象可代表不同类型的实体，而态射则代表对象之间的关系或变换。
• 函子（Functors） ：函子将一个范畴映射到另一个范畴，并保持原范畴的结构。函子在范畴之间转换对象与态射，同时维持它们之间的关系。函子也可被视为从一个范畴构造另一个范畴的方法。
• 自然变换（Natural Transformations） ：自然变换是一种高阶结构，用于关联两个函数。它提供了一种在保持底层结构的前提下比较和转换函子的方式。
• 极限与余极限（Limits and Colimits） ：极限与余极限是范畴论中的泛性质（universal properties），它们捕捉了对象与态射各种聚合与分解操作的本质。

2.4.2 类别、函子、自然变换

可以在定义2.4.1中看到类别的更正式定义。

2.4.4 范畴论在计算机科学中的现有应用

除了前述内容之外，我们还想强调范畴论在计算机科学领域的若干应用，包括：编程语言、类型系统、领域特定语言（DSL）以及形式化验证。在编程语言方面，范畴论影响了函数式编程语言（如 Haskell）的设计，提供了诸如单子（monads）、函子（functors）和箭头（arrows）等概念 [81]。这些抽象机制为程序的结构组织及其行为推理提供了强大而富有表达力的方式。同伦类型论（homotopy type theory）领域也受益于范畴论的概念，利用它来构建更具表达力和灵活性的数据结构与算法表示 [60, 7]。

与本工作最相关的范畴论应用，是那些涉及数据建模、知识表示以及图变换系统的研究。范畴论已被用于对复杂数据结构和知识库进行建模与推理，为结构化信息的表达与操作提供了一种手段。这方面最著名的成果体现在 Spivak [76, 74] 与 Patterson [67] 对“本体日志”（ontology-logs，简称 o-logs）以及函子式数据迁移（functorial data migration）的探索中。在这些工作中，范畴论被用于对本体进行建模和推理，为结构化信息的表达与操作提供了一个数学框架。此外，该方法已被证明可与资源描述框架（RDF）——一种语义网标准数据格式——实现互操作 [74]。在数据库领域，范畴论已被用于模式映射与集成。函子可用于表示不同模式之间的数据转换，而自然变换则可表达不同模式映射之间的关系。这为跨异构数据库的数据集成与转换提供了一种系统化的方法。

2.4.4.1 函子式数据迁移

函子式数据迁移是一种植根于范畴论的方法，由 Spivak 于 2012 年提出 [74]，为在不同数据库模式之间转换和迁移数据提供了一个结构清晰且严谨的框架。在该框架中，数据库模式被表示为一个小范畴（small category），其中范畴的对象对应模式中的表，态射则表示表之间的关系。该模式的一个实例则被表示为一个取值于集合的函子（set-valued functor）：该函子为每个对象（即表）分配一个行集合，并为每个态射分配一个函数，用以表示相应表的行之间的关系。

该论文指出，给定两个模式（表示为范畴）之间的一个态射，存在三种“数据迁移函子”，可用于以规范的方式将实例从一个模式转换到另一个模式。这些函子可同时对所有表进行投影、并集和连接操作，从而可替代合取查询（conjunctive queries）与析取查询（disjunctive queries）。

总体而言，这一框架利用范畴论为数据库模式及其实例的表示与操作提供了一种严谨且数学基础坚实的方法。该框架可被适配到我们的问题中：将目标本体视为模式范畴，而通过感知手段获得的本体中各类的实例则视为集合。关于该实现的更多细节见第 3 章。

2.4.4.2 图重写系统

范畴论对图变换与重写系统的发展也作出了贡献，为表达和分析复杂的基于图的算法与数据结构提供了一个通用框架 [18]。特别是，范畴论已被用于形式化和分析图变换系统——在这些系统中，图用于表示结构，而图之间的变换则代表计算步骤。双推出（Double-Pushout, DPO）方法是一种广泛应用的、基于范畴论的图变换形式体系，它建立在推出（pushouts）与拉回（pullbacks）的概念之上，能够对图重写规则进行精确且可组合的描述。在此背景下，范畴论为项重写系统（term rewriting systems）的结构与行为建模和推理提供了途径，并对其性质与正确性提供了深刻见解。关于该方法如何应用于规划的更多细节，见第 4 章。

总之，范畴论为理解和建模计算机科学中的抽象结构与关系提供了一个通用而强大的框架。其应用涵盖众多领域，包括编程语言、系统工程、物理学和科学建模，推动了更具表达力、灵活性和严谨性的软件系统与工具的发展。然而，更相关的是，范畴论已被应用于数据建模与知识表示的多个方面，例如本体、数据库模式映射以及知识表示形式体系。通过利用范畴论的表达能力及其可组合性，这些应用得以在一个严谨而灵活的框架下对复杂的关系、结构和算法进行推理。在本论文中，我们将大量借鉴这些应用分支。

第三章初步成果 I：用于表示复杂世界状态的 C-集

在本章中，我们将介绍初步工作，展示如何利用范畴论中的 C-集（C-sets）来表示类型化图（typed graphs）。这一形式体系对于编码包含大量对象与关系的复杂世界状态非常有用。

3.1 我们的方法：使用 C-集

为了在保留类型化图优势的同时纳入传递关系（也称为组合关系，compositional relations），我们提出采用 Spivak 于 2012 年提出的 C-集形式体系 [74]。这是可行的，因为根据 [18]，所有类型化图均可表示为 C-集。该形式体系的关键特性在于，它能够利用函子（functors）捕捉逻辑语法（theories）与语义（models）之间的关系，同时保持组合结构。这一范式被称为函子语义（functorial semantics）[61]。它与一阶逻辑的标准形式体系不同之处在于，它将语言的语法（我们可以将其视为本体）视为一个独立于其语义的代数对象。C-集的示意图见图 3.1。

这种表示方式利用范畴 C-Set 为类型化图提供了指称语义（denotational semantics）。设 C 表示一个小范畴，称为模式（schema）。一个 C-集（也称为 C 上的余预层，copresheaf on C）是从 C 到集合范畴 Set 的一个函子。该模式是一个范畴，其对象被解释为类型，其态射则描述类型之间的“is-a”关系及其他函数式关系。集合范畴 Set 是由集合及其间的函数构成的范畴，它提供了关于世界状态的实例数据（即语义）。因此，C-集是一个函子，它将类型映射为集合，将类型间的关系映射为函数。在此解释下，C-集是一种简单但有效的关系数据库模型 [75]。需要注意的是，这些集合之间通过函数而非一般关系相互关联。这一特性为 C-集所表示的实例间关系增添了额外的结构。这种限制是必要的，以确保组合性（即传递性）关系能够被良好定义。

一个 C-集 X 的“元素范畴”（category of elements，见定义 2.4.4），记作 ∫X，将 X 的数据打包成一个类似于知识图谱的范畴。具体而言，元素范畴中的一个态射可被解释为一个资源描述框架（Resource Description Framework, RDF）三元组 [67]，这是一种用于知识图谱和场景图的常见基于文本的序列化格式。图 3.1 即以这种风格描绘了一个 C-集。C-集的正式定义见定义 3.1.1。

C-集的范畴是一个拓扑斯（topos），这是一种行为特别良好的范畴，例如其中所有极限与余极限均存在。在描述我们如何通过动作转换世界状态时，这一特性将非常有用。

3.1.1 C-集之间的态射

对于重写系统而言，通常由 C-集提供态射。这些态射包含大量数据，因为它们必须使函子的各个组件相互匹配，以保持组合性。在实践中，将这种过程纳入任务规划或任何其他场景并不实用。因此，Brown 等人 [18] 提出了一种通用的态射匹配算法，可视为一种结构模式匹配。

在两个 C-集 X 和 Y 之间寻找一个态射 m: X → Y 的问题，可以转化为一个带类型的约束满足问题（CSP）。具体做法是：取这两个 C-集的元素，并将其作为 CSP 中的变量和定义域。回顾一下，在约束满足问题（CSP）中，变量是问题中可取不同值的元素；变量的定义域是该变量所能取的所有可能值的集合。CSP 的目标是为每个变量分配一个值，使得所有约束条件均被满足 [71]。CSP 中的类型由索引范畴 C 的对象给出。对于 C 中的每个态射 f: c → c'，以及每个元素（由 X(c) 给出），都会引入一个约束。

该 CSP 的解恰好是这两个 C-集之间的 C-集同态（C-set homomorphisms），即自然变换 [18]。

这意味着该算法仅考虑满足类型关系的赋值。带类型的 CSP 搜索空间的增长率为 O(n^k)，其中 n 是目标（Y）的大小，k 是源（X）的大小 [18]。作为参考，一般的图同态匹配问题是 NP-完全的，这使得该算法比一般图同态匹配问题更易于处理。

3.1.2 使用 C-集的优势与局限

C-集为规划提供了若干优势。通过利用 C-集，我们可以保持组合性，从而有效建模复杂的关系。此外，C-集支持表达否定适用性条件，这对于表示影响世界动态性的约束与限制至关重要。这一点将在第 4.1.3 节中讨论。它们还支持定量属性及其评估，如加法、减法、乘法及其他算术运算。最后，关系实例的函数性要求有助于防止矛盾谓词的出现——例如，一个物体同时处于两个位置（这在 STRIPS 中可能被表达为 on(b1 - Block, table - Table) 和 on(b1 - Block, floor - Surface)）。

目前，使用 C-集来建模世界状态也存在一些局限性。一个潜在的挑战是在设计本体时需考虑自动传递闭包，虽然有益，但可能是一个非直观的过程。此外，C-集与运动规划之间的联系尚未被探索，而这对于机器人或自动驾驶车辆等特定应用至关重要。C-集也不支持有序比较，例如“小于”或“大于”关系，这在比较属性或评估特定条件时限制了其表达能力。最后，该形式体系当前仅支持对象间的二元关系；而在形式本体中，可以表达 n 元关系。

综上所述，尽管 C-集在建模世界状态方面具有诸多优势，但重要的是要意识到其局限性，并根据具体应用场景的需要，考虑替代方法或增强方案。C-集的一个实现可在 Julia 包 Catlab.jl 中找到。一个使用 C-集定义的世界状态示例见附录 B.1.2.1 和 B.1.2.2。

第四章初步成果 II：基于 C-集与 DPO 重写的规划

在本章中，我们将讨论为构建一种基于 C-集与双推出（Double-Pushout, DPO）重写的规划语言所开展的初步工作。该语言不仅具备足够的表达能力，可在类型化图上执行规划，还额外提供了保留模式范畴（即本体）中组合关系（compositional relationships）的优势。本章将通过一个示例，说明在所提出的表示方法中，一个动作与 STRIPS-PDDL 表示中的动作有何不同。

具体而言，我们建议对场景图规划架构进行一项改进：不再在多种语言之间进行转换，而是将框架的各个组件提升到本章将讨论的统一共享语言中。图 4.1 展示了从面向场景图规划的多语言架构向单一语言架构的转变。为了解现有工作在此领域的局限性，我们请读者参阅第 2 章的相关综述。我们提出的架构消除了向另一种规划表示形式翻译的必要性，而是将计划视为一系列作用于场景图的重写规则。

4.1 我们的方法：使用 C-集与 DPO 重写

我们提出将 C-集与一种称为双推出（DPO）重写的、用于调整世界状态的过程相结合，并使其与第 2.3.1 节所述的基于状态转移系统的规划模型保持一致。

4.1.1 C-Set 中的动作作为“跨度”（Spans）

动作规则在 C-Set 范畴中被指定为“跨度”（spans）。这些动作规则的组成部分与经典表示中的动作模式（action schemas）类似。具体而言，动作规则是 C-Set 中的一个跨度（I ← K → O），其中左侧 I 表示前提条件（precondition），右侧 O 表示效果（effects），中间的 K 称为“粘合对象”（glue），它表示在输入与输出之间保持不变的数据。

在实现过程中，我们选择将 C-集的跨度表示为代表性函子（representable functors）的余极限（colimits）。这种转换是可行的，因为根据 Yoneda 嵌入（见引理 2.4.1），对于动作规则中的每一个 C-集 F，都存在一个从 F 到 C 上某个代表性函子的自然变换。如定义 4.1.1 所述，协变代表性函子将范畴 C 中的对象 A 映射到以 A 为源对象的所有态射所构成的集合。这种转换还带来一个额外优势：当某个对象（例如 A）被显式标识时，能够自动匹配其隐含的子结构。

这种范畴论的动作规则描述方式与经典方法的不同之处在于：它采用了一种声明式（declarative）的方法，不显式说明应从状态中添加或删除哪些原子（atoms），而是描述状态中应当包含什么内容，并通过双推出（DPO）重写过程（见第 4.1.3 节）来解决冲突。

4.1.2使用单态的适用性

回顾一下，在经典规划中，当一个前提条件的命题是世界状态的子集，或者该前提条件与世界状态之间存在逻辑蕴涵关系时，该前提条件就被认为在该世界状态下得到满足。在范畴论的语境中，这些概念通过单态射（monomorphisms）得以推广。单态射将单射函数（injective function）的概念推广到任意范畴中。在集合范畴 Set 中，单态射恰好就是单射函数。在 C-Set 范畴中，单态射是这样一类自然变换：其每个分量都是单射函数；例如，图之间的单态射就是一个图同态，其顶点映射和边映射均为单射。将单态条件（见定义 4.1.2）应用于态射，对于动作的可应用性至关重要，因为它确保前提条件中的两个不同实体不会被映射到世界状态中的同一个实体。

换句话说，一个态射 f是单态的（monic），当且仅当任意两个态射若与 f进行后复合（post-composition）后结果相同，则这两个态射本身必须相等。

如前所述，由于规则是通过代表性函子（representable functor）实现的，因此除了规则中显式表达的内容之外，还可能识别出额外的对象和态射。这种扩展的结构起到了附加约束的作用，从而限制了在给定世界状态下可应用的规则数量。

4.1.3 使用双推出（DPO）重写进行状态转移

我们提出的新见解是：动作规则本质上就是双推出（Double-Pushout, DPO）重写规则。DPO 重写是一种图重写方法，特别适用于图变换的代数化方法。事实上，DPO 重写可直接从图重写推广到 C-集重写 [18]。下文所述的 DPO 方法用于针对给定规则，计算世界状态与前提条件之间所有可能的匹配，并确定哪些匹配与效果部分兼容。其结果是一组可应用于目标图的变换步骤。

作为一个例子，图4.2展示了一个动作规则如何将初始状态更改为最终状态。在这个图中，规则规定初始状态中的圆应该被梯形替换，而正方形和三角形应该保留。左下角的初始状态满足前提条件，因为它包含一个涉及正方形、三角形和圆的匹配模式。这意味着可以找到一个单态射，将圆从初始状态识别出来。中间状态是通过识别模式，沿着胶合线连接前提条件，产生的初始状态。这从初始状态中移除了圆。最终状态是通过取跨度（中间 ← 胶合 → 效果）的推出来构建的。这产生了一个梯形替换原始圆的模式。图4.2中展示的例子说明了规则可以同时涉及前提条件中包含实体的创建和效果中不包含该实体的销毁。这允许在更新世界状态时非单调。

处理负条件 类别表示能够处理形式为负前提条件和效果的约束，使用DPO重写和负应用条件（NACs）[32]。NACs是一种通过指定在规则应用之前或之后世界状态中不应存在的条件来限制动作规则应用的方法。换句话说，负应用条件指定了一组在规则应用之前或之后世界状态中不应匹配任何部分的模式。使用NACs在动作规则中允许更精确和灵活地指定处理负前提条件和效果。

4.1.4 一个例子：移动面包片

在本节中，我们讨论了经典、基于STRIPS和基于类别的表示之间的差异。比较总结在表4.1中。我们还通过一个例子，如图4.3所示，来说明经典表示在跟踪隐含效果方面的局限性。在这个示例领域中，一个面包片（bread loaf）和面包片的切片（slice 0, slice 1, slice 2）都在一个台面（countertop）上。目标是将面包片，以及隐含地，将其所有切片从台面移动到厨房台面（kitchentable）。这个例子说明了经典表示在保持世界全局语义方面的失败，因为通过传递关系，动作仅更新世界的一部分。使用C-set重写的双重推出方法，类别表示能够做到这一点。

处理结构化知识 这个例子展示了一些值得注意的语义特征。在这个领域中，规划表示必须能够编码以下事实，无论是显式还是隐式，在不同时间点：

(a) 面包片是面包的一部分 (b) 面包片在台面上 (c) 面包片在台面上 (d) 面包片在厨房台面上

在类别表示中，事实 (a) 通过态射 is part of : BreadSlices → BreadLoaf 在模式中被捕获。事实 (b) 关于面包片在台面上的事实通过一个抽象称为 Object 来细化。这是为了使态射 on : Object → Object 能够表示一个对象在另一个对象上的一般概念，而不是面包片在台面上的更具体关系。事实 (c) 和 (e) 通过命题 on(bread, countertop) 和 on(bread, kitchentable) 被捕获。直观上，因为面包片在台面上，构成面包片的切片也在台面上。在类别表示中，这通过复合态射被捕获。在经典表示中，这是通过明确陈述每个切片在台面上来完成的。事实 (c) 和 (e) 通过命题 partOf(slice_n, bread) 为 n = 0, 1, 2 来被捕获。事实 (d) 通过命题 on(bread, countertop) 和 on(bread, kitchentable) 被捕获。

处理动作的适用性 在类别表示中，动作的适用性由从规则输入到世界状态的C-Set中的单态射的存在决定。回想一下，一个（协变）代表函数将对象

映射到具有 x 作为源的态射集合。当你使用可表示的呈现动作时，代表给出了显式条件和隐式条件，这些条件在可表示的计算时出现。这提供了一种在规则中具有隐式条件的机制。在这个例子中，初始状态满足涉及 BreadLoaf、Object 和 Countertop 的输入动作规则。在经典表示中，动作 moveObj(bread, countertop, kitchentable) 的适用性是通过世界状态是否包含命题 on(bread, countertop) 来确定的。

处理隐含的传递性 将面包片从台面移动到厨房台面的动作在这个例子中是适用的。在类别表示中，这个动作通过C-Set中的一个跨度来建模，其左脚包含关于面包片在台面上的知识，而右脚包含关于面包片在厨房台面上的知识。跨度的顶点声明面包片本身在整个变化过程中被保留。在经典表示中，动作模式描述了从位置 s 到另一个位置 t 移动对象 x 的通用动作。动作运算符通过将 x 分配给 breadloaf，s 分配给 countertop，t 分配给 kitchentable 来接地。一旦应用此动作，期望的新状态是考虑到面包片从台面移动到厨房台面，因为它们是面包片的一部分。在类别表示中，初始状态中存在的相同复合态射存在于最终状态中；然而，态射的目标已从台面更改为厨房台面。这捕获了对面包片位置发生的隐含变化。在经典表示中，新状态捕获了面包片在厨房台面上的事实，但没有捕获面包片在厨房台面上的事实。这是由于惯性框架公理，该公理指出所有在效果中未明确说明的事实在动作应用后仍然保持为真。在实践中，这种错误可能会导致规划者由于世界状态的不一致性而指示代理单独移动每片面包。

虽然这个例子展示了一个简化的厨房世界，但很容易想象一个更大的领域，例如制造领域，从动作应用时保留全局语义中受益。

4.1.5 使用代数规划进行前向规划和回溯

由于我们的框架组件与状态转换系统规划模型的组件相一致，因此可以利用在设计高效规划算法和整合启发式方法方面所做的长期工作。

考虑到一个计划是一系列动作，这些动作将初始世界状态更改为满足某些目标标准的一个状态。为了在我们的框架中设置一个规划问题，我们需要指出C-Set中的两个对象，即初始状态和目标状态。然后，我们可以将一个计划视为一系列规则，当应用于初始状态时，构造一个对象，使得从目标状态到该对象存在一个单态射。我们借鉴自动化规划领域的成功方法来实现一个带有回溯的前向搜索算法[37]。此实现的伪代码可以在算法2中找到。退出标准涉及检查是否存在从目标到当前世界状态的单态射。

与其他规划算法一样，这种方法容易受到循环和非终止问题的影响。这发生在规则可能无限期适用的场景中，如果世界规范没有捕获在应用规则时销毁对象的方法。例如，在制作三明治的例子中，切面包并没有以任何方式减少面包块，这意味着我们的规划器可能会无限次地切面包块。将属性C-Set或“acsets”整合到这个框架的未来计划中，这将允许用户为每个实体指定属性，例如BreadLoaf → NumSlices。这种结构将提供一种明确的方法来进行算术和其他操作，这可能有助于跟踪资源限制。目前，我们使用一种临时方法，即规则限制字典，它指定了在计划中可以应用规则的最大次数。此实现将在AlgebraicJulia生态系统中作为本论文的一部分提供。源代码的副本可以在附录B.3中找到。

第五章持续成果 —— 衡量问题差异

为了支持我们的假设，有必要设计一种方法，用于评估在问题发生变化时计划的稳定性。为此，我们希望提供一种衡量新规划问题与旧规划问题之间差异的方法，以确保为每个领域生成一组公平的问题变化样本。我们相信，前几章所概述的形式体系能够提供相关且有益的结构，从而对问题的变化进行严谨定义。特别地，我们主张该形式体系能够捕捉到世界状态之间差异的信息性结构，而这是 STRIPS 比较方法无法提供的。这将有助于开发一种度量方法，用于比较针对特定问题实例和目标的世界状态。在本章中，我们通过一个简单的 Blocksworld 示例来说明我们预期该度量方法可能如何运作。

5.1 示例：Blocksworld

让我们设想我们处于一个简单的规划领域，例如 Blocksworld 领域。我们从三个积木 A、B、C 开始，其中积木 A 在桌子上，积木 B 在 C 的上面。目标是安排积木，使得 B 在 A 上方，而 A 又在 C 上方。示意图如图 5.1 所示。初始世界状态用 STRIPS 语言描述可能如下所示：

5.1.4 比较对世界状态的更改

如果我们比较所有三种世界状态的变化，我们可能会说原始问题与新问题之间的变化从小到大依次为：变化 I < 变化 II < 变化 III。这个顺序是根据生成新计划后观察到的变化来确定的。然而，我们还可以查看结构差异性作为我们离初始状态有多远的指标。

那么，我们如何衡量这种变化呢？如果我们继续使用STRIPS和PDDL的语言，我们可以通过计算一组接地谓词的编辑距离来衡量世界变化。这有一些缺点，因为变化 I 和变化 III 中的世界变化将被视为相等，因为它们都添加了一个新的接地谓词。这将是对世界变化的粗略评估，在更复杂的设置中不会有太大用处。此外，我们还可以考虑接地谓词集合的Jaccard相似度；然而，这个度量对问题设计者在描述世界状态时想要多么详细很敏感。例如，如果问题设计者想要包括Blockworld词汇表中的所有有效谓词（在“x - block ?y - block”、“ontable ?x - block”、“clear ?x - block”），持有“x - block”的另一个同样有效的初始问题将是：

ontable(A) AND on(B, C) AND ontable(C) AND clear(B)

添加这个谓词将改变我们观察到的世界变化量，尽管在语义上是等价的。我们希望差异度量能够对人类设计者所做的决策具有鲁棒性。

如果我们考虑变化 I 和变化 III 之间的语义差异，即添加了 on(D, C) 和 on(D, table)，我们将注意到 D 与其他对象在场景中有显式和隐式交互。在变化 I 中，D 参与了与 A、B 和 C 的一系列交互；而在变化 III 中，D 仅与桌子交互。因此，对于问题差异度量来说，理想的情况是对世界语义变化敏感，而不是仅仅对句法变化敏感。

我们提出使用 C-集作为表达世界状态以及相应问题变化的手段。若采用代数规划（Algebraic Planning）来考虑此例，我们将使用图 5.3 所示的范畴 C 来表达领域本体。该范畴包含三个对象：Block、Table 和 Thing；并包含三条由图 5.3 中三个箭头表示的态射。虚线代表知识表示中的“is-a”关系，例如 (Block, block-is-a, Thing) 和 (Table, table-is-a, Thing)。唯一的非分类学关系是描述积木“在某物之上”的关系。回顾第 3.1 节，C-集是本体范畴 C 与语义范畴 Set 之间的函子。因此，每个框体被映射为集合，每条态射被映射为函数。我们可以如图 5.4 所示，使用 AlgebraicPlanning 表达从 I 到 III 的变化。

每一项变化均表示为 C-集范畴内三个 C-集函子构成的一个跨度（• ← • → •）。在每个函子中，灰色虚线箭头代表“is-a”关系，黑色实线箭头则代表从 Block 到 Thing 的函数映射，对应范畴 C 中的态射 on(Block, Thing)。

对于我们的原型差异度量，我们可以采用函子 F 的格罗滕迪克构造（Grothendieck construction），也记作 Gr(F)。该构造将函子 F 提升为一个范畴，其中包含代表函数映射中所有集合内每个元素的对象和态射。格罗滕迪克构造的更正式定义见定义 2.4.4。例如，Gr(F) 中的一些对象是 (Block, A)、(Block, B)、(Thing, 2) 和 (Table, table)。该构造还包括复合映射作为范畴中的态射。例如，若存在态射 phi: (X, x₁) → (Y, y₀) 和 chi: (Y, y₀) → (Z, z₂)，则复合态射 chi ∘ phi 也将作为 Gr(F) 中的态射被包含。由于 Gr(F) 本身也是一个范畴，恒等态射同样被包含在内。

作为一个例子，我们可以将初始问题设为 F，并枚举 Gr(F) 中的对象与态射：

对象：(Block, A), (Block, B), (Block, C), (Thing, 0), (Thing, 1), (Thing, 2), (Thing, 3), (Table, table)

态射：(on, A:3), (on, B:2), (on, C:3), (block-is-a, A:0), (block-is-a, B:1), (block-is-a, C:2), (table-is-a, table:3), id_(Block, A), id_(Block, B), id_(Block, C), id_(Thing, 0), id_(Thing, 1), id_(Thing, 2), id_(Thing, 3), id_(Table, table)

在 Gr(F) 中，我们共有 8 个对象和 15 个态射，其中 7 个是非恒等态射。

我们的原型差异度量 dδ(F, G) 如公式 5.1 所示，可以表示为 Gr(F) 和 Gr(G) 中非恒等态射之间的 Jaccard 相似性的补集，分别记作 Gr(F)*₁ 和 Gr(G)*₁。

δ(F, G) = 1 − 2(|Gr(F)*₁ ∩ Gr(G)*₁|) / (|Gr(F)*₁| + |Gr(G)*₁|) （5.1）

用于获取 C-集变换的同态匹配算法 3.1.1 可用于识别两个函子之间的匹配。这将允许我们考虑 Gr(G) 与 Gr(F) 之间态射的交集，从而衡量结构相似性，而非句法相似性。

这意味着对于变化 I，差异度量为 δ(F, G) = 1 − 2(7)/(7 + 9) = 0.125。基于此度量，我们还观察到变化 II 的差异值为 0.286，变化 III 的差异值为 0.375。而 δ(F, F) 的差异值为 0。

使用这种语言，对象间的关系在模式中具有严格的定义要求。相比之下，在 PDDL 中，此类要求并未被强制执行。例如，在 PDDL 中，可以说 on(A, B) 和 on(D, B)。这种情况需通过仔细描述世界状态或添加针对 Blocksworld 领域的具体公理来处理。对于 AlgebraicJulia，该度量将随模式规模成比例变化。

5.1.5 任务规划领域

任务规划在机器人学中有诸多应用。在本论文中，我们旨在展示这一方法在多种规划领域的适用性。为此，我们选择了一个基准规划领域——Blocksworld，以及两个与制造业仓库自动化和家庭服务自动化相关的应用实例。

5.1.5.1 Blocksworld

Blocksworld 领域是人工智能（AI）规划领域中一个历史悠久且被广泛研究的基准问题。它是一个简化的、但具有代表性的求解问题领域，长期以来被用于测试和评估各种 AI 规划算法与技术。该领域包含一组有限的积木和一张桌子，积木可以相互堆叠，也可以放置在桌子上。目标是在某些约束和规则下，通过操作积木达到指定的构型。

在 Blocksworld 领域中，状态被表示为一组谓词的集合，用于描述积木之间的关系及其位置。该领域中常用的典型谓词包括：on(X, Y)，表示积木 X 直接位于积木 Y 之上；ontable(X)，表示积木 X 位于桌子上；以及 clear(X)，表示积木 X 顶部没有其他积木。Blocksworld 中规划问题的目标是将初始积木构型转换为目标构型。

该领域使我们能够在一个自由度有限的环境中评估我们的方法。这意味着该领域中只有一个可变参数，即积木的数量。关系的数量也将与积木数量成正比，因为在这个世界中，每个积木最多只能与另一个对象（另一块积木或桌子）发生交互。

5.1.5.2 家庭服务自动化

在未来，任务规划将在家庭服务自动化中发挥关键作用，尤其是在厨房任务辅助方面，机器人需要协助完成各种烹饪和清洁任务。这类场景涉及复杂的操作、与多种对象的交互，以及对食谱或操作流程的推理。任务规划可以帮助机器人将复杂的厨房任务（如准备一顿饭）分解为更小、可管理的子任务。它还能确定执行动作的最优顺序，同时考虑任务间的依赖关系、烹饪时间和资源约束。

厨房通常包含大量对象和工具，如厨具、电器和食材。任务规划使机器人能够推理这些对象的属性和功能（affordances），为每项任务选择合适的工具和动作，并确保正确操作和处理。此外，厨房环境具有动态性和不确定性，可能出现条件变化或意外事件，如洒漏或食材短缺。

近年来，面向厨房助手的机器人任务规划在学术界和工业界均受到广泛关注。Beetz 等人 [13] 通过开发一个能制作煎饼的系统，展示了自主机器人在厨房中的潜力，该系统涉及复杂的操作任务以及对动作、对象和依赖关系的推理。类似地，Tenorth 和 Beetz [77] 开发了 KnowRob——一个知识处理框架，使自主个人机器人能够通过知识表示与推理技术执行各种厨房任务，例如制作三明治。

在家庭服务与厨房自动化的背景下，许多研究聚焦于开发能够处理多种厨房任务（如备餐、摆桌和洗碗）的机器人系统 [23]。然而，任务规划在厨房助手中的成功集成仍是一项持续的挑战，因为它涉及解决对象识别、操作以及在时空约束下规划动作等问题。尽管如此，机器人操作、规划算法和人机交互方面的进步，正不断为未来更强大、更高效的厨房助手机器人铺平道路。我们认为这是一个评估我们框架在“中等规模”问题上表现的合适领域。此外，该领域对机器人学和任务规划领域的非专家也易于理解。

三明治制作问题具体而言，我们将聚焦于三明治制作问题，以展示在厨房环境中应用任务规划技术时所面临的挑战与机遇。在此问题中，机器人必须自主执行一系列动作来制作三明治，包括选择食材、切面包、涂抹酱料以及堆叠各层，同时遵守特定的空间约束和目标。厨房环境具有动态性和不确定性，要求机器人生成对变化情境（如食材可用性、用户偏好或意外障碍）具有鲁棒性的稳定计划。

5.1.5.3 制造与装配

任务规划为传统机器人编程方法提供了一种高层替代方案，能够实现对任务和环境更抽象、灵活且可扩展的表示。传统机器人编程通常需要显式定义一系列底层动作、控制策略或行为以达成特定目标。这种方法耗时、缺乏灵活性，且难以适应新任务或新环境。相比之下，任务规划专注于使用高层表示对世界进行推理，因此是一种通用且适应性强的机器人编程方法。

目前，工业编程方法包括示教编程（lead-through programming）和离线编程（off-line programming）。示教编程仍是工业界最广泛使用的机器人编程方法。在示教编程中，操作员手动引导机器人末端执行器到达期望位置，并通过示教器（teach pendant）将该位置保存到轨迹中 [83]。每个位置可附加额外信号，用于触发抓取或焊接等动作。这类似于定格动画师移动物体并逐帧拍摄。与定格动画类似，这种方法直观易懂，但非常耗时，且每次任务或工作单元配置变更时都需重复整个过程 [85]。这导致了重新编程期间的停机时间，并需要专业技能来编写高效且协同的轨迹。

为减少停机时间，人们引入了离线编程方法 [83]。这些方法需要一个高保真的机器人及工作单元数字模型，以及一个规定任务如何完成的过程式程序 [59]。离线编程语言具有灵活性，支持传感器输入处理，并允许实现高级感知算法和仿真。然而，这种方法要求机器人工程师具备开发复杂计算机程序的能力，因此可及性较低。实践中，大多数机器人级程序都是针对特定机器人平台、传感器和算法的“点解决方案”。

为缓解这一问题，一种称为目标导向机器人编程（Goal-oriented robot Programming, GoP），也称为任务级编程的方法被用于以参与任务的对象操作来描述目标 [59]。这使得任务可以功能性地表达，即关注“需要完成什么”。GoP 系统需要访问一个包含环境和机器人几何模型的知识库（例如离线编程中创建的数字模型），该知识库通常被称为世界模型。世界模型可利用计算机辅助设计（CAD）模型（包含质量、惯性、运动学描述、关节限制等）和仿真引擎（生成动力学）构建，并通过摄像头等传感器进行更新，以反映真实世界的变化。GoP 系统提供了一个编程框架，支持使用运动基元（motion primitives）、技能和任务来组合程序 [14]。GoP 系统还需要一个编译器，将任务级规范转换为机器人级规范。编译器的功能是从初始状态到目标状态，生成操作环境中对象的机器人级程序。GoP 提供任务级规范，但将编写目标导向程序的责任留给机器人工程师。任务规划则有望替代工程师，自动确定正确的程序。我们认为这是一个评估我们框架在大规模问题上表现的合适领域。机器人任务编程通常需要在世界模型中表示大量物理和空间信息，因此非常适合用于实证评估我们的方法能处理多大规模的领域。

机床照管问题（Machine-Tending Problem）具体而言，任务规划在自动化和优化制造流程（如机床照管应用）中可发挥关键作用。在此类场景中，机器人负责向机床加载和卸载材料、工件或工具，以确保制造过程的平稳运行、效率和生产力。例如，任务规划可帮助机器人在多台机床之间确定最优的装卸操作序列，同时考虑生产流程的约束和目标。这将确保高效的资源分配、最小化空闲时间并最大化吞吐量。此外，在现实制造环境中，场景往往是动态的，可能出现意外事件，如机床故障、生产订单变更或资源限制 [25]。理论上，任务规划应对这些变化具有鲁棒性。然而在实践中，由于领域模型定义不足，经典方法很少能做到这一点，这使得难以准确评估计划变更的影响 [22]。

5.1.5.4 机床照管与三明治制作的比较

三明治制作问题与机床照管问题之间存在诸多相似之处，也有显著差异。主要区别在于厨房领域中对象的多样性规模。例如，在厨房场景中，对于某一特定食材，可能存在多个有效候选；因此，推理替代选项对该领域的成功至关重要。此外，三明治所需的食材和工具会因消费者偏好而大幅变化。相比之下，机床照管场景中的材料类型和零件加工方法是标准化且明确定义的。在机床照管场景中，零件的属性通常比三明治食材更丰富。能够使用同一套表示方法对这两种场景进行推理，将充分展示本方法在处理大量对象、类别和约束（如替代关系和描述性属性）方面的强大能力。

第六章拟开展的工作与时间安排

本论文最终旨在解决在复杂世界状态发生变化的情况下，计划适应（plan adaptation）的问题。

6.1 拟开展工作的概述

以下是对本研究提案中所提出研究工作的高层次总结：

初步成果 I —— 用于表示复杂世界状态的 C-集在此工作中，我们提出了一种对类型化图形式体系的新颖应用，即 C-集（C-set）。该形式体系能够表达具有函数性和组合性属性的本体及其实例。具体而言，我们展示了其在以原则性方式将世界状态编码为场景图方面的实用性。该形式体系通过在语法范畴与语义范畴之间建立函子关系（称为函子语义，functorial semantics），从而在类及其对应实例之间诱导出组合性或路径等价关系。这一方法具有以下优势：(i) 有效管理具有丰富类型-类层次结构的领域中的对象、关系和属性；(ii) 确保世界状态明确地遵循所规定的结构（即本体）；(iii) 处理由本体中可组合路径所引发的隐式传递关系。更多细节见第 3 章。

初步成果 II —— 基于 C-集与 DPO 重写的规划在此工作中，我们提出在人工智能任务规划中使用 C-集来表示世界状态。任务规划负责识别一系列高层动作，将初始状态转换为目标状态。该领域存在的一些问题包括：难以管理大规模且复杂的世界状态，以及难以保持传递闭包。我们认为，这些问题源于现有表示语言（如 PDDL 和 STRIPS）的局限性。为支持这一观点，我们通过一个示例展示了所提出的 C-集形式体系能够有效应对上述问题。更多细节见第 4 章。

正在进行的工作 —— 衡量问题差异在此工作中，我们探讨了所提出的 C-集形式体系如何为我们提供衡量规划问题变化的结构基础。我们概述了三个可应用范畴论结构进行任务规划的领域。我们计划通过一系列案例研究，展示在人工智能任务规划中采用函子语义的可用性与优势。这些案例包括：一个经典规划任务、制造业中的机床照管（machine-tending）以及家庭服务自动化中的三明治制作（sandwich-making）。

6.2 评估

回顾一下，本工作的部分目标在于支持以下假设。

为支持该假设，我们将进行一项类似的实验，但评估重点将放在基于固定问题的计划稳定性上。

1. 根据第 5.1.5 节所述，选择并构建基于 Blocksworld、三明治制作和机床照管领域的规划域，并分别使用我们的形式体系与 PDDL 进行建模。
2. （新增）针对每个领域，确定一个能生成基准计划的问题。该问题应尽可能基于真实场景。
3. 针对每个领域，构建一个包含 p 个问题的问题集，其分布根据所提出的度量方法均匀设定。目前，合理的 p 值为 100；但在实验过程中，根据实际情况，更多或更少的测试用例可能更具可行性或意义。
4. 使用默认参数设置 MetricFF，并针对每个领域，配置 MetricFF 以处理与传递闭包相关的派生谓词，我们称此版本为 MetricFF-Transitive。我们预计这将是一个耗时的过程。
5. （新增）运行 (a) 我们提出的规划方法，(b) MetricFF，以及 (c) MetricFF-Transitive，均针对基准问题，设定上限时间为 30 分钟，以获得解决方案 π₀。
6. 运行 (a) 我们提出的规划方法，(b) MetricFF，以及 (c) MetricFF-Transitive，均针对问题集，设定上限时间为 30 分钟，以获得各问题的解决方案 πᵢ（其中 i = 1, ..., p）。
7. 记录 π₀ 与 πᵢ 之间的计划稳定性。
8. 对比假设分析并讨论结果。我们还将突出任何值得注意的、特定于领域的观察结果，例如那些产生计划稳定性 D(π₀, πⱼ) = 0 的有趣场景——这意味着计划未发生任何变化。

第七章 结论

总之，本研究提出了一种在复杂环境中进行人工智能规划的新颖方法。通过聚焦于开发一种基于范畴论、并利用基于本体的类型化图的稳健表示语言——AlgebraicPlanning，我们旨在更有效地捕捉复杂世界状态，并对其中对象间的关系进行推理。我们着力解决当前人工智能规划面临的三个核心问题：（1）难以表达复杂且结构化的世界状态；（2）难以对传递关系进行推理；（3）难以将任务规划与其他人工智能组件集成以支持神经符号推理。我们相信，应对这些挑战将使我们能够生成更高质量的计划，并提升任务规划在复杂现实世界领域中的适用性。

为验证我们的方法，我们提出了若干假设，并将据此评估我们方法的性能。我们计划开展一系列案例研究，探索在多种不同领域（如经典规划、制造业和家庭服务机器人）中的规划问题，以全面衡量我们方法的适用广度与深度。此外，我们还旨在贡献一种计划质量评估方法，提供一种系统化的方式来考察计划在面对世界状态变化时的稳定性，并深入理解世界中各项特征对达成目标的相关性。

从更广阔的视角来看，本工作将为范畴论形式体系在人工智能任务规划中的应用提供一个具体实例，为该领域注入新的视角，并可能为未来在这些交叉领域的研究铺平道路。鉴于现实世界环境的复杂性与动态性，推进人工智能任务规划的发展对于未来智能系统的进步至关重要。因此，本工作的贡献不仅具有学术意义，也将对众多行业和实际应用产生切实影响。

原文链接：https://angelineaguinaldo.com/assets/papers/aguinaldo-prelim-2023.pdf