Daniel Neider, I7
|Title||Learning to Win Reachability Games|
|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.|
- Subscribe to the ics feed.
- No Events