• Calendar

March 29, Tuesday
12:00 – 13:30

Search algorithms are usually designed to return either optimal, suboptimal or any solution. In the talk I will address a different but very realistic search task: find solution with cost smaller than or equal to a given fixed constant. This task is relevant in scenarios where a fixed budget is available and we would like to find solution under the given budget with minimum search effort. For this problem, we introduced an algorithm called Potential Search (PTS) which is a best-first search that expands nodes according to the probability that they will lead to a solution whose cost is less than the given budget. Surprisingly, it is often possible to implement PTS even without explicitly calculating these probabilities, by learning the error model of the available heuristic. In addition, PTS can be modified to an anytime search algorithm. Experimental results show that PTS outperforms other relevant algorithms in most cases, and is more robust.

In the second part of the talk, I will present a novel algorithm that can predict the cost optimal solution of a given search problem. The proposed prediction algorithm builds on the CDP formula (Zahavi et. al., JAIR 2010) used to predict the number of nodes expanded in a single iteration of IDA*. Experiments on benchmark search domains show that the prediction is extremely accurate. In addition, the predicted cost can be used to enhance existing search algorithm. Experiments show that combining the prediction algorithm with Potential Search is able to find almost optimal solutions with orders of magnitude less nodes expanded when compared to A*.