期刊名称：Journal of Automation, Mobile Robotics & Intelligent Systems (JAMRIS)
印刷版ISSN：1897-8649
电子版ISSN：2080-2145
出版年度：2008
卷号：32
页码：631-662
出版社：Industrial Research Inst. for Automation and Measurements, Warsaw
摘要：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 Rubik's 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.
