Learning to Win Reachability Games


Daniel Neider, I7

Title Learning to Win Reachability Games
When 15.04.2010, 15:00
Where Seminarraum Informatik 11
Abstract This talk gives a brief introduction in the field of “algorithmic learning”. Algorithmic learning is a generic term for techniques that allow to “learn” (or “infer”) formal languages from some kind of knowledge source, thus, forming itself a kind of synthesis procedure. As an application of algorithmic learning I present a novel approach to solve two-person, zero-sum reachability games on (finite or infinite) graphs. Although there exist efficient linear time algorithms for this problem, such algorithms perform poorly on really huge game graphs. Moreover, for infinite graphs there are no algorithms known that always guarantee to compute the attractor (if it exists). In such situations, algorithmic learning can offer a valuable alternative as it allows to learn a solution without computing it explicitly. My approach is to represent a game symbolically using regular languages and finite state transducers and to construct a “teacher” that guides a learning algorithm until the solution is eventually computed.
Slides download