AAAI Publications, Fourth Annual Symposium on Combinatorial Search

Font Size: 
Predicting Solution Cost with Conditional Probabilities
Levi Lelis, Roni Stern, Shahab Jabbari Arfaee

Last modified: 2011-07-05


Classical heuristic search algorithms find the solution cost of a problem while finding the path from the start state to a goal state. However, there are applications in which finding the path is not needed. In this paper we propose an algorithm that accurately and efficiently predicts the solution cost of a problem without finding the actual solution. We show empirically that our predictor makes more accurate predictions when compared to the bootstrapped heuristic, which is known to be a very accurate inadmissible heuristic. In addition, we show how our prediction algorithm can be used to enhance heuristic search algorithms. Namely, we use our predictor to calculate a bound for a bounded best-first search algorithm and to tune the w-value of Weighted IDA*. In both cases major search speedups were observed.


Heuristic Search; Solution Cost; Bounded Search

Full Text: PDF