A General Theory of Additive State Space Abstractions
  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.
