• Calendar

November 9, Tuesday
12:00 – 14:00

Heuristic Search in Artificial Intelligence is a general mechanism for path finding and for solving exponential combinatorial problems (e.g., Chess, Rubik's Cube etc,) with the usage of intelligent heuristics. An efficient way to speed up the search is to use a more accurate heuristic function. In the talk we will cover some of the recent developments in creating accurate heuristics. We will also cover the new trend in this field is to effectively apply heuristic search to problems from other areas of computer science such as vertex-cover, graph-partitioning etc,

In particular, we will discuss "Pattern-database heuristics" which are a recent breakthrough that have made a revolution in calculating accurate heuristic functions. Pattern databases are large tables that store solutions to "patterns" or subproblems in the computer's memory. These solutions are then used as heuristics that guide the search. With pattern databases we are able to solve problems thousands of times faster than with previous heuristics.

We will present the basics of pattern databases and then show how to enhance pattern databases by a number of methods such as, compressing large pattern databases into a small amount of memory, use multiple pattern databases, learn pattern databases with neural networks etc, Experimental results of the different methods on a number of domains will be provided.

More information on search can be found in: http://www.ise.bgu.ac.il/faculty/felner/