Predicting optimal solution cost with bidirectional stratified sampling

摘要: Optimal planning and heuristic search systems solve state-space problems by finding a least-cost path from start to goal. As byproduct of having an optimal they also determine the solution cost. In this paper we focus on problem determining cost for directly, i.e., without actually that We present efficient algorithm, BiSS, based ideas bidirectional stratified sampling produces accurate estimates Our method is guaranteed return in limit as sample size goes infinity. show empirically our makes predictions several domains. addition, scales state spaces much larger than can be solved optimally. particular, estimate average 6x6, 7x7, 8x8 Sliding-Tile Puzzle provide indirect evidence these are accurate.