Contact    Jobs
Search:

Seminar: Games, Synthesis and Robotics

Instructors: Bernd Finkbeiner, Markus Rabe,
Peter Faymonville and Andrey Kupriyanov
Lecture Room: SR 016 Building E 1 3
Lecture Time: Tuesdays 14:15 – 15:45

Seminar (7 CP)
Sommersemester 2011

Content

In this seminar, we will explore the theory and applications of infinite games. In particular, we consider the automatic synthesis of control software for robots. We offer seminar topics broadly classifiable into two categories: Foundational aspects, i.e. game solving, variants of synthesis and temporal logic and applied aspects, i.e. robotic control software in combination with our hardware platform, three e-puck robots.

Useful links

Solution of Church’s Problem: A Tutorial
Wolfgang Thomas

Related Course: AG&V

The AG&V lecture (Automata, Games, and Verification) covers background and additional topics related to the seminar. We recommend (but do not require) attending AG&V in parallel.

Seminar structure

Read, discuss, give a talk, then implement a prototype or write a summary.

Weekly Summaries

Please hand in your short (ca. half a page) summaries every week before the seminar talk via e-mail .

Structure:

  • Summarize the three most important points of the paper
  • Summarize the contribution of the paper
  • Indicate problems / flaws of the paper
  • Indicate further research directions

Grading Policy

Grading will be based on:

  • Your technical talk + following discussion
  • Participation in discussions of other papers
  • Attendance
  • Implementation project or summary
  • Weekly summaries

Please let us know in advance if you will miss a meeting.

List of topics

Tutorial

Date Paper
19-04-2011 Tutorial: Synthesis
Bernd Finkbeiner

Efficient Synthesis

Date Paper
26-04-2011 Temporal Logic-based Reactive Mission and Motion Planning
Hadas Kress-Gazit, Georgios E. Fainekos and George J. Pappas
 
03-05-2011 Synthesis of Reactive(1) Designs
Nir Piterman, Amir Pnueli and Yaniv Sa’ar
 
10-05-2011 Hierarchical Synthesis of Hybrid Controllers from Temporal Logic Specifications
Georgios E. Fainekos, Antoine Girard and George J. Pappas
 
17-05-2011 Bounded Synthesis
Sven Schewe and Bernd Finkbeiner

Timed Systems

Date Paper
24-05-2011 A Theory of Timed Automata
Rajeev Alur and David Dill
 
31-05-2011 Efficient On-the-fly Algorithms for the Analysis of Timed Games
Franck Cassez, Alexandre David, Emmanuel Fleury, Kim G. Larsen and Didier Lime
Additional literature: On the Synthesis of Discrete Controllers for Timed Systems
Oded Maler , Amir Pnueli , Joseph Sifakis

Planning/Synthesis with Incomplete Information

Date Paper
07-06-2011 Church’s Problem Revisited
Orna Kupferman and Moshe Vardi
 
14-06-2011 Planning Graph Heuristics for Belief Space Search
Daniel Bryce, Subbarao Kamphampati and David E. Smith
 
21-06-2011 Non-communicative multi-robot coordination in dynamic environments
Jelle R. Kok, Matthijs T.J. Spaan, Nikos Vlassis
 
28-06-2011 A new representation and associated algorithms for generalized planning
Siddharth Srivastava, Neil Immerman, Shlomo Zilberstein

Beyond LTL and Distribution

Date Paper
05-07-2011 Design and Synthesis of Synchronization Skeletons using Branching Time Temporal Logic
Edmund Clarke and E. Allen Emerson
 
12-07-2011 Alternating-Time Temporal Logic
Rajeev Alur, Thomas A. Henzinger and Orna Kupferman
 
19-07-2011 to be announced