Predicting optimal solution cost with conditional probabilities

Abstract

Heuristic search algorithms are designed to return an optimal path from a start state to a goal state. They find the optimal solution cost as a side effect. However, there are applications in which all one wants to know is an estimate of the optimal solution cost. The actual path from start to goal is not initially needed. For instance, one might be interested in quickly assessing the monetary cost of a project for bidding purposes. In such cases only the cost of executing the project is required. The actual construction plan could be formulated later, after bidding. In this paper we propose an algorithm, named Solution Cost Predictor (SCP), that accurately and efficiently predicts the optimal solution cost of a problem instance without finding the actual solution. While SCP can be viewed as a heuristic function, it differs from a heuristic conceptually in that: 1) SCP is not required to be fast enough to guide search algorithms; 2) SCP is not required to be admissible; 3) our measure of effectiveness is the prediction accuracy, which is in contrast to the solution quality and number of nodes expanded used to measure the effectiveness of heuristic functions. We show empirically that SCP makes accurate predictions on several heuristic search benchmarks.