Betsy.Herk@A.CS.CMU.EDU (02/27/86)
Speaker: Richard Korf, Asst. Prof., Comp. Sci. Dept., UCLA Date: Friday, March 14 Time: 1:00 - 2:30 Place: 5409 Wean Hall Title: Heuristic search: Algorithms, theory, and learning Abstract: This talk will cover three new research results in the area of heuristic search. The first is a new algorithm, called Iterative-Deepening-A*, that is asymptotically optimal in terms of solution cost, time, and space among all admissible heuristic tree searches. In practice, it is the only known algorithm that is capable of finding optimal solutions to the Fifteen Puzzle. The second is a theory which unifies the treatment of heuristic evaluation functions in single-agent problems and two-person games. The theory is based on the notion of a heuristic as a function that is invariant over optimal solution paths. Based on this theory, we performed some experiments on the automatic learning of heuristic functions. Our program was able to learn a set of relative weights for the different chess pieces which is different from, but competitive with, the classical values.