Estimating Search Tree Size with Duplicate Detection
Full Text: 8936-38725-1-PB.pdf
In this paper we introduce Stratified Sampling with Duplicate Detection (SSDD), an algorithm for estimating the number of state expansions performed by heuristic search algorithms seeking solutions in state spaces represented by undirected graphs. SSDD is general and can be applied to estimate other state-space properties. We test SSDD on two tasks: (i) prediction of the number of A* expansions in a given f-layer when using a consistent heuristic function, and (ii) prediction of the state-space radius. SSDD has the asymptotic guarantee of producing perfect estimates in both tasks. Our empirical results show that in task (i) SSDD produces good estimates in all four domains tested, being in most cases orders of magnitude more accurate than a competing scheme, and in task (ii) SSDD quickly produces accurate estimates of the radii of the 4×4 Sliding-Tile Puzzle and the 3×3×3 Rubik’s Cube.
Citation
L. Lelis, R. Stern, N. Sturtevant. "Estimating Search Tree Size with Duplicate Detection". Symposium on Combinatorial Search, (ed: Stefan Edelkamp, Roman Barták), pp 114-122, August 2014.| Keywords: | tree size prediction, A*, state space radius prediction |
| Category: | In Conference |
| Web Links: | AAAI |
BibTeX
@incollection{Lelis+al:SoCS14,
author = {Levi H. S. Lelis and Roni Stern and Nathan R. Sturtevant},
title = {Estimating Search Tree Size with Duplicate Detection},
Editor = {Stefan Edelkamp, Roman Barták},
Pages = {114-122},
booktitle = {Symposium on Combinatorial Search},
year = 2014,
}Last Updated: July 09, 2020Submitted by Sabina P
