Publicado em: 23/04/2015

Palestra com prof. Robert Holte – Canadá

Nesta sexta-feira, 24/4, o prof. Robert Holte da University of Alberta, Canadá, estará ministrando a palestra Towards a High-Performance Rapid Prototyping Tool for State-Space Search, às 12h45min, no Auditório Prof. Castilho do INF. O evento faz parte da Série de Seminários do Instituto de Informática da UFRGS.

Série de Seminários do Instituto de Informática da UFRGS

———————————————————

SEXTA-FEIRA, 24 de abril de 2015

———————————————————

Horário: 12h45min
Duração: 1h

——————————————————–

Local: Auditório Prof. Castilho
Instituto de Informática, UFRGS
Av Bento Gonçalves 9500, Bloco IV

——————————————————–

Palestrante: Prof. Robert Holte, University of Alberta, Canada

Título: Towards a High-Performance Rapid Prototyping Tool for State-Space Search

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.

Short-bio: PhD. In Computer Science by the Brunel University, England, and current Professor in the Computer Science Department, University of Alberta Canada.

Main research area: Artificial Inteligence (Heuristic Search, Games, Machine Learning, among others). Homepage: http://www.cs.ualberta.ca/~holte