How good is “good enough” ? Bounded cost and Probably Approximately Correct Heuristic Search


Many Artificial Intelligence applications require searching for a path in very large state spaces. Heuristic search algorithms, such as the well-known A* algorithm, guarantee to return the optimal (shortest) path. On the other hand, local search algorithms such as Hill Climbing, Simulated Annealing and Genetic Algorithms often find a path quickly, but do not given any guarantee on the quality of the resulting path.

Between these two extremes, we propose two novel settings in which a path is found quickly, but with some guarantee on it quality.


In the first setting, the search algorithm is required to find a path in the state space with cost less than a given constant. This task is relevant in scenarios where a fixed budget is available to execute a plan and we would like to find such a plan while minimizing the search effort. For this setting we introduce the Potential Search (PTS) algorithm, which is specifically designed to solve this problem. PTS is a best-first search that expands nodes according to the probability that they will be on a path whose cost is less than to the given budget. In the second setting we investigate, the search algorithm is required to find a path that is approximately optimal with high probability. This setting is inspired by the PAC learning framework in Machine Learning, and we call it PAC Search correspondingly. We propose a framework for PAC search algorithms and demonstrate several practical PAC search algorithms.

We demonstrate experimentally on various search benchmarks the benefits of the proposed bounded-cost search algorithms and PAC search algorithms.


This research presented in this talk is a summary of two published papers:

· "Potential Search: a bounded-cost search algorithm", joint work with Rami Puzis and Ariel Felner, presented and accepted as a full paper to the International Conference on Automated Planning and Scheduling (ICAPS) 2011.

· "PAC heuristic search", joint work with Ariel Felner and Robert C. Holte, presented and accepted as a full paper to the International Symposium on Combinatorial Search (SoCS) 2011.


28/03/2012 - 15:00
Roni Stern
דוא"ל להרשמה: 
Ben-Gurion University
building 1103, Room 329