Computer Science – Artificial Intelligence
Scientific paper
2011-10-31
Journal Of Artificial Intelligence Research, Volume 32, pages 631-662, 2008
Computer Science
Artificial Intelligence
Scientific paper
10.1613/jair.2486
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.
Culberson Joseph
Felner Ariel
Holte Robert
Yang Fangkai
Zahavi Uzi
No associations
LandOfFree
A General Theory of Additive State Space Abstractions does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with A General Theory of Additive State Space Abstractions, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A General Theory of Additive State Space Abstractions will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-466852