Predicting Solution Cost with Conditional Probabilities

Authors

  • Levi Lelis University of Alberta
  • Roni Stern Ben Gurion University
  • Shahab Jabbari Arfaee University of Alberta

DOI:

https://doi.org/10.1609/socs.v2i1.18196

Keywords:

Heuristic Search, Solution Cost, Bounded Search

Abstract

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.

Downloads

Published

2021-08-19