A general theory of additive state space abstractions

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