通过降维实现与主体解耦的接地：解决Asp瓶颈问题的新方法

《Artificial Intelligence》：Body-Decoupled Grounding via Reduction: A Novel Approach on the Asp Bottleneck

　　摘要
答案集编程在许多实际应用中被用作一种易于使用且高效的建模方法。在答案集编程中，规则（包含变量）会与事实相结合以推导出结论。然而，大量的变量和事实会导致所谓的“赋值瓶颈”：规则中的变量需要通过所有可能的域值组合进行赋值，从而导致生成的程序规模过大，可能无法处理。对于那些包含大量变量的复杂规则来说，这一问题尤为突出，因为传统的赋值方法会导致规则中变量数量的指数级增长。本文提出了一种新的方法来克服这一障碍。与传统方法不同，我们的技术将规则体中的原子分开处理，即对每个原子单独进行赋值。具体而言，我们的方法能够将非赋值形式的程序转换为仅依赖于最大谓词阶数的析取式程序，若该阶数固定为常数，则该程序的复杂度为多项式级。我们将这一方法扩展到非赋值的普通程序，并进一步利用类似思路将非赋值的析取式程序转换为赋值的认知逻辑程序，同时依然保持对规则体原子的分离处理。通过实验比较，我们证明了这种新方法在程序规模、赋值时间以及总体运行效率方面均优于传统答案集编程技术。

引言
答案集编程是一种著名的问题建模与求解框架，与其他形式化方法一起，成为知识表示与推理以及符号人工智能领域实际应用的主要推动力。答案集编程可视为命题可满足性问题的扩展，它通过规则形式表达知识，其解为满足所有规则的原子集合，即答案集。与命题可满足性问题类似，高效答案集编程求解器的开发使得该技术不仅可在自然语言理解等学术领域得到广泛应用，还能在工业领域发挥重要作用。此外，答案集编程还有更复杂的扩展形式，例如认知逻辑编程，它能够处理多世界推理，近年来在研究界越来越受到重视。因此，改进答案集编程系统是一个重要且有趣的研究方向。

作为知识表示语言，答案集编程的一大优势在于其一阶变体，即规则直接基于变量定义。这类非赋值逻辑程序在调用求解器之前需要进行赋值处理。因此，传统的答案集编程系统依赖“赋值-求解”技术，即先通过赋值模块将非赋值程序转换为命题形式，再由求解模块计算答案集。这种技术也被应用于规划等领域。为了避免完全赋值，人们提出了基于提升规划的解决方案，同时也有受本文启发而开发的改进方法，这些方法已被用于2023年国际规划竞赛的获胜求解器中。需要指出的是，赋值技术并不仅限于特定形式化方法，还被用于高效的模型计数等任务。不过，对于某些问题类型，这种方法的局限性较为明显，尤其是当赋值导致组合爆炸时，即规则实例化后会生成规模庞大的程序，超出求解器的处理能力。这一问题通常被称为答案集编程的赋值瓶颈。

示例1
答案集编程可以轻松编码许多问题。以选择实体间的关系以避免结构中出现三角形为例，这可以通过图结构来表示，进而用以下非赋值程序进行编码。程序Π在规则(1)中为图中每条边决定是选择该边还是不选择，然后在规则(2)中确保所选边不会形成三角形。
p(a,b)∨pˉ(a,b)←e(a,b).←p(x,y),p(y,z),p(x,z),x≠y,y≠z,x≠z.
在赋值过程中，我们需要考察变量x、y和z的取值。传统赋值方法会为程序域D=dom(Π)中的每一组可能的变量赋值生成一条赋值规则，这些变量均为来自事实集F(Π)的常量符号。这些事实由形如e(a, b)、e(b, c)等的表达式构成，因此|D|相当于图G的顶点数。这样一来，赋值工作的复杂度为O(|D|3)。一般来说，给定程序Π的赋值复杂度为O(|dom(Π)|?)，其中n为规则中出现的不同变量的最大数量。

为了凸显我们提出的新赋值方法，我们先回顾一下已有的答案集编程复杂度结果。不同类型的逻辑程序具有不同的复杂度，这些复杂度通常与其表达能力和结构密切相关。如表1所示，赋值后程序的复杂度相对较低：判断析取式程序是否存在答案集属于多项式层级中的第二层，而普通（且紧密的）程序则属于NP完全问题。虽然非赋值程序中的变量能够提升程序的表达能力并降低编码难度，但其复杂度却反映了赋值可能带来的巨大开销，这也是非赋值程序的复杂度可达NEXPTIME级别的原因。不过，早期针对有限域情况下程序的研究表明，当谓词阶数有限时，程序的复杂度会更低。具体而言，非赋值的普通（且紧密的）程序的复杂度可降至Σ2P级别，而非赋值的析取式程序则可降至Σ3P级别。更有趣的是，即便谓词阶数有限，规则实例化仍可能带来指数级增长。

基于这些研究成果，我们可以发现，在谓词阶数有限的条件下，非赋值程序与赋值程序在某些情况下具有相同的复杂度，这为我们提供了利用归约作为高效替代求解方法的途径。具体而言，这可以实现非赋值逻辑程序与赋值逻辑程序之间的多项式归约，从而提供一种将部分赋值工作交由现代答案集编程/认知逻辑编程求解器处理的替代方案。首先，这种归约似乎适用于从非赋值的普通（且紧密的）程序转换为赋值的析取式程序，不过，随着竞争性认知逻辑编程求解器的不断发展，从非赋值的析取式答案集编程程序转换为赋值的认知逻辑编程程序也可能具有应用前景，因为后者同样属于Σ3P完全问题。

虽然归约本身已经很有吸引力，但通过特定的编码方式，我们可以实现规则体中谓词之间的依赖关系分离，即每个谓词可以单独进行赋值，从而减少实例化次数。尤其是在处理结构极为复杂的庞大规则体时，这一方法尤为有用。以下示例展示了我们所说的“规则体分离赋值”与传统赋值系统的区别。

示例2
回顾示例1中的程序Π。如前所述，传统赋值系统会一次性为规则中的所有变量赋值，其复杂度为O(d3)，一般情况下来说为O(|dom(Π)|?)。而我们的方法有所不同，它在为Π赋值时会对规则体中的各个谓词分别处理，因此生成的赋值程序的规模与赋值原子的数量成线性关系。由于谓词阶数为2，其复杂度为O(|dom(Π)|2)。一般来说，其复杂度为O(|dom(Π)|?)，其中c为与谓词阶数对应的常数。

借助上述复杂度结果，我们提出了一种新的赋值方法，该方法在赋值过程中分离规则体中的各个谓词，这些分离会在后续求解阶段再统一处理。因此，我们从另一个角度思考赋值问题：是否可以在不显式实例化规则的情况下，将非赋值程序转换为赋值程序，同时将部分赋值工作交给现代答案集编程/认知逻辑编程求解器的高效搜索算法来完成？至少对于某些类型的程序而言，这种方法是否具有可行性？

我们的主要贡献如下：
1. 我们提出了一种新的归约方法，可将非赋值的紧密逻辑程序转换为赋值的析取式程序，该方法通过搜索未满足的赋值规则和未赋值的原子来实现赋值过程。与传统赋值方法不同，该方法能够分离规则体中的谓词，这对于结构极为复杂的庞大规则体尤为有用。我们证明，从非赋值的紧密程序转换为赋值的析取式程序在一般情况下是不可避免的。
2. 我们将这一方法扩展到非赋值的普通程序，为此在归约过程中加入了排序机制以确保结果的合理性。基于这些编码，我们还为非赋值的霍恩程序提供了一种计算成本更低的归约方法，该方法能够通过转换为赋值的普通程序来判断程序的一致性及原子是否属于该程序。
3. 我们还将这一方法扩展到认知逻辑程序的归约。由于认知逻辑程序的复杂度更高，我们将其方法也应用于非赋值的析取式程序。所提出的归约方法能够实现答案集的子集最小化，因此无需考虑结果的合理性及排序问题。
4. 我们开发了一个原型系统，该系统能够利用我们所提出的归约方法转换紧密程序中的关键部分，从而通过分离规则体谓词来优化赋值过程。初步实验表明，与现有的最佳赋值工具相比，该方法不仅能显著提升处理速度，还能大幅减小程序的规模。这一成果是对先前发表在《第31届国际人工智能联合会议》和《第26届欧洲人工智能会议》上的论文的扩展，此外，本工作还包含了更多示例和完整证明，同时还增加了非赋值霍恩程序的转换方法。

相关工作
答案集编程的起源可追溯到Prolog语言，但其最基础的理论发展来自于稳定模型语义的定义，这一定义随后催生了答案集的概念。其理论基础为“此地-彼地逻辑”，这一理论为后续的深入研究奠定了基础。关于这些发展的综述可见相关经典文献。实际上，答案集编程之所以能取得实际应用的成功，得益于早期就出现了高效的赋值工具。

预备知识
在讨论我们的归约方法之前，我们先简要回顾一些基本概念。我们按照常规方式使用数学向量X=〈x?,…,x?〉、Y=〈y?,…,y?〉，向量组合方式为〈X,Y〉:=〈x?,…,x?,y?,…,y?〉，判断x?是否属于X的方法为x?∈X。此外，Y?X=〈y??,?,y??〉表示Y中不在X中的元素，按出现顺序排列，即{y??,?,y??}={y∈Y∣y?X}。在不失一般性的前提下，我们假设向量中的元素都按照某种固定的总顺序排列；对于给定的集合S，……

紧密答案集编程的规则体分离赋值
本节介绍一种我们称之为“规则体分离赋值”的新赋值方法。通过这种方法，我们可以利用非赋值的紧密程序与赋值的析取式程序在复杂度上的相似性，通过一种归约方法R来实现赋值。该归约方法的编码方式使得规则体中的原子相互独立，从而将赋值工作分解开来，有效降低了变量实例化的组合复杂度，相比整体处理规则体而言更为高效。我们首先介绍这一方法的原理……

将规则体分离赋值方法应用于其他类型的程序
在本节中，我们将把规则体分离赋值的方法扩展到其他类型的程序。这可以看作是对前述方法的延伸，因为在处理某些复杂程序时，需要额外的处理步骤。

实现的原型系统与实验
为了在实际环境中展示我们的方法，我们开发了一个名为newground 5的开源原型软件工具。该newground系统实现了我们为非赋值的紧密程序设计的归约方法R′，从而通过搜索实现规则体分离赋值，具体实现方式如第4节所述。为此，我们将newground设计为一个可重用的模块，该模块能够将非赋值的输入程序转换为赋值的程序……

讨论、结论与未来工作
本研究探讨了是否可以通过一种转换方法高效地对非赋值逻辑程序进行赋值，从而避开答案集编程的赋值瓶颈。为此，我们引入了体解耦接地技术，通过一种新的简化方法来处理具有强接地特性的Asp规则。借助对有界谓词元数下的非接地、普通及紧密程序的复杂性研究，我们首先展示了将接地、析取式程序进行简化的方法，以此作为潜在的CRediT作者贡献说明。维克托·贝辛：写作——审稿与编辑，写作——初稿撰写，软件，资源，项目管理，方法论，调查研究，形式分析，数据整理，概念构建。马库斯·赫彻：写作——审稿与编辑，写作——初稿撰写，指导，软件，资源，项目管理，方法论，调查研究，形式分析，数据整理，概念构建。马蒂亚斯·柯尼格：写作——审稿与编辑，写作——初稿撰写，项目管理。斯特凡。利益冲突声明：作者声明他们没有已知的可能影响本文所述工作的财务利益或个人关系。维克托·贝辛|马库斯·赫彻|马蒂亚斯·柯尼格|斯特凡·沃尔特兰