UTCS AI Colloquia - Rob Holte, "Towards a High-Performance Rapid Prototyping Tool for State-Space Search"

Contact Name: 
Karl Pichotta
GDC 6.302
Apr 8, 2014 2:00pm - 3:00pm
Bruce Porter



Host:  Bruce Porter

Talk Abstract: State-space search involves finding solution paths in very large state spaces, such as puzzles (e.g. Rubik's Cube), logistics problems, or edit-distance problems (e.g. biological sequence alignment). Traditionally, search performance has been maximized by writing special-purpose code for each new state space. This has the disadvantage that it requires considerable human effort and ingenuity, is potentially error-prone, and it minimizes the amount of code re-use that is possible. An alternative is a rapid prototyping tool in which completely generic algorithm implementations and data structures are used, and the human's role is simply to specify the state space in a high-level language. This maximizes code re-use and minimizes human effort and error but potentially is much less efficient in terms of run time and/or memory usage.

In this talk I describe our research towards getting the best of both approaches by compiling a state space description into C code. I illustrate this approach with psvn2c, a state-space compiler I have developed together with Neil Burch. The second half of the talk focuses on a powerful component of psvn2c called move pruning. It is a fully automatic analysis that can reduce search time by orders of magnitude and equal or outperform human analysis. One major lesson from our work is the need for formal proofs of correctness of move pruning methods.

This talk is aimed at a general computer science audience, it does not require any prior knowledge of state-space search or Artificial Intelligence.

Speaker Bio: Professor Robert Holte of the Computing Science Department at the University of Alberta is a former editor-in-chief of "Machine Learning", a leading international journal, and co-founder and former director of the world-renowned Alberta Innovates Centre for Machine Learning (AICML). His current research is on single-agent heuristic search, primarily focusing on the use of automatic abstraction techniques to speed up search, methods for predicting the run-time of a search algorithm given a particular heuristic, and the use of machine learning to create heuristics. He has approximately 100 scientific papers to his credit, covering both pure and applied research, and has served on the steering committee or program committee of numerous major international Artificial Intelligence conferences. Professor Holte was elected a Fellow of the AAAI in 2011.