An Introduction to Heuristic Search
In this talk I will give a general introduction to heuristic search, one of the earliest subfields of Artificial Intelligence. I will begin with simple examples but then show that the range of potential applications is, in fact, very broad. Likewise, I will start with the simplest algorithms for solving heuristic search problems and develop them into more sophisticated ones by introducing two key ideas: bidirectional search, and search guided by a heuristic function. Each of these techniques is extremely effective in speeding up search but for many years there was no known way to usefully combine them. Insights produced by a theoretical study last year allowed my colleagues and I to design a near-optimal bidirectional heuristic search algorithm. This talk is meant to be accessible to a general audience, no backg round in Artificial Intelligence is assumed.