摘要翻译：
非正式地说，如果S中任意两个状态之间的距离总是大于或等于抽象空间中相应距离的和，则状态空间S的一组抽象是可加的。第一个已知的附加抽象，称为不相交模式数据库，被实验证明在某些状态空间上产生了最先进的性能。然而，以前的应用仅限于具有特殊性质的状态空间，这使得不相交的模式数据库无法定义为几种常用的测试床，如魔方、上旋和煎饼拼图。本文给出了可应用于任何状态空间的加性抽象的一般定义，证明了基于加性抽象的启发式是相容的和可容许的。我们使用这个新的定义为这些测试床创建附加抽象，并通过实验证明，选择好的附加抽象可以大大减少（18,4）-上旋球难题的搜索时间，比现有的17-煎饼难题的搜索时间减少三个数量级。我们还导出了一种测试方法，如果加性抽象返回的启发式值是可证明的太低，并表明使用这种测试可以减少15-拼图和上旋球的搜索时间大约两倍。
---
英文标题：
《A General Theory of Additive State Space Abstractions》
---
作者：
Fan Yang, Joseph Culberson, Robert Holte, Uzi Zahavi, Ariel Felner
---
最新提交年份：
2011
---
分类信息：

一级分类：Computer Science        计算机科学
二级分类：Artificial Intelligence        人工智能
分类描述：Covers all areas of AI except Vision, Robotics, Machine Learning, Multiagent Systems, and Computation and Language (Natural Language Processing), which have separate subject areas. In particular, includes Expert Systems, Theorem Proving (although this may overlap with Logic in Computer Science), Knowledge Representation, Planning, and Uncertainty in AI. Roughly includes material in ACM Subject Classes I.2.0, I.2.1, I.2.3, I.2.4, I.2.8, and I.2.11.
涵盖了人工智能的所有领域，除了视觉、机器人、机器学习、多智能体系统以及计算和语言（自然语言处理），这些领域有独立的学科领域。特别地，包括专家系统，定理证明（尽管这可能与计算机科学中的逻辑重叠），知识表示，规划，和人工智能中的不确定性。大致包括ACM学科类I.2.0、I.2.1、I.2.3、I.2.4、I.2.8和I.2.11中的材料。
--

---
英文摘要：
  Informally, a set of abstractions of a state space S is additive if the distance between any two states in S is always greater than or equal to the sum of the corresponding distances in the abstract spaces. The first known additive abstractions, called disjoint pattern databases, were experimentally demonstrated to produce state of the art performance on certain state spaces. However, previous applications were restricted to state spaces with special properties, which precludes disjoint pattern databases from being defined for several commonly used testbeds, such as Rubiks Cube, TopSpin and the Pancake puzzle. In this paper we give a general definition of additive abstractions that can be applied to any state space and prove that heuristics based on additive abstractions are consistent as well as admissible. We use this new definition to create additive abstractions for these testbeds and show experimentally that well chosen additive abstractions can reduce search time substantially for the (18,4)-TopSpin puzzle and by three orders of magnitude over state of the art methods for the 17-Pancake puzzle. We also derive a way of testing if the heuristic value returned by additive abstractions is provably too low and show that the use of this test can reduce search time for the 15-puzzle and TopSpin by roughly a factor of two.
---
PDF链接：
https://arxiv.org/pdf/1111.0067