Department of Computer Science Technische Universitaet Muenchen
Home People Teaching Research Publications Info Sitemap
Team | Research | Teaching | Publications | Presentations | Photos | Jobs | Contact

Ausgewählte Themen aus dem Bereich Künstliche Intelligenz und Robotik - Constraintbasierte Modelle und Algorithmen in der Künstlichen Intelligenz

Vorlesung im Sommersemester 2008

Durchführung

Zeit und Ort: Dienstags, 10:00-11:30 Uhr in Raum 02.09.023
Beginn: 15. April 2008
Credits: 3.0 ECTS (2 SWS)
Modul: IN3150 (Ausgewählte Themen aus dem Bereich Künstliche Intelligenz und Robotik)
Dozent: Dr. Martin Sachenbacher


Prüfung

Die Prüfung wird am 24. Juli 2008 als mündliche Prüfung (Dauer ca. 30 Minuten) durchgeführt. Die Prüfung findet im Raum 00.13.034 (Büro des Dozenten) statt. Bitte melden Sie sich bis 18. Juli per Mail an den Dozenten (Name, Matrikelnummer, bevorzugte Zeit) zur Prüfung an.

Zeiteinteilung:

09:30 Uhr - 10:05 Uhr: Witali Aswolinskiy
10:05 Uhr - 10:40 Uhr:
10:40 Uhr - 11:15 Uhr: Michael Weiß
11:15 Uhr - 11:50 Uhr: Andreas Artmeier
11:50 Uhr - 12:25 Uhr: Paula Volkmar-Velez


Inhalt

  • Modellieren mit Constraints: Constraint satisfaction problems (CSPs), constraint optimization problems (soft CSPs), boolean constraints (SAT, QBF);
  • Algorithmen für das Constraintlösen: Search, inference, hybrids of search and inference, look-back and look-ahead methods;
  • Techniken für große Constraintnetzwerke: Exploiting structure in real-world problems, structural decomposition, conflict learning, randomization and restart techniques;
  • Anwendungen und Fallbeispiele: Constraint-based frequency allocation in cellular networks, constraint-based computing for flexible machine control software, programming of fault-aware autonomous systems, immobots

Termine

15. April: Vorlesung 1: Organisatorische Hinweise, Einleitung und motivierende Beispiele
Folien: PDF
22. April: Vorlesung 2: Constraint Satisfaction Probleme, Systematische Suche und lokale Suche
Folien: PDF, Einschub 1 (Pedro Meseguer) PDF, Einschub 2 (Pedro Meseguer) PDF
Software: Java Applet zur lokalen Suche für CSPs
29. April: Vorlesung 3: Constraint Satisfaction Probleme, Vollständige Inferenz, Bucket Elimination
Folien: PDF, Einschub (Pedro Meseguer) PDF (ohne die Folien 6-15)
6. Mai: Vorlesung 4: Constraint Satisfaction Probleme, Unvollständige Inferenz, Kombination von Suche und Inferenz
Folien: PDF, Einschub 1 (Pedro Meseguer) PDF, Einschub 2 (Pedro Meseguer) PDF
Software: Java Applet zur unvollständigen Inferenz (Arc Consistency) für CSPs mit Kreuzworträtsel-Beispiel aus der Vorlesung
13. Mai: Keine Vorlesung (Pfingstferien)
20. Mai: Vorlesung 5: Constraint Satisfaction Probleme, Constraintprogrammierung, Primäre/Duale Formulierung, Globale Constraints
Folien: PDF, Einschub (Pedro Meseguer) PDF
27. Mai: Vorlesung 6: Gecode Open Constraint Solving Library, Constraint Optimization Probleme (Soft CSPs), Valued CSPs und Semiring-basierte CSPs
Folien: PDF, Einschub 1 (Guido Tack) PDF, Einschub 2 (Thomas Schiex) PDF
3. Juni: Vorlesung 7: Constraint Optimization Probleme (Soft CSPs), Systematische Suche und lokale Suche, Vollständige Inferenz und Suche
Folien: PDF, Einschub (Thomas Schiex) PDF
10. Juni: Vorlesung 8: Constraint Optimization Probleme (Soft CSPs), Unvollständige Inferenz (lokale Konsistenz), Large-Scale Constraint Reasoning: Randomisierung
Folien: PDF, Einschub 1 (Thomas Schiex) PDF, Einschub 2 (Carla Gomez) PDF
17. Juni: Vorlesung 9: Large-Scale Constraint Reasoning: Zufall und Struktur in Constraintproblemen, Heavy Tail-Verteilungen, Phase Transition-Phänomene
Folien: PDF, Einschub (Carla Gomez) PDF
24. Juni: Vorlesung 10: Entfällt!
1. Juli: Vorlesung 11: Large-Scale Constraint Reasoning: Restart-Techniken und Backdoor-Phänomene; Boolesche Constraints (SAT)
Folien: PDF, Einschub 1 (Carla Gomez) PDF, Einschub 2 (Ashish Sabharwal und Bart Selman) PDF
8. Juli: Vorlesung 12: Quantifizierte Constraint-Probleme: Definition und Anwendungsmöglichkeiten
Folien: PDF, Einschub (Ashish Sabharwal und Bart Selman) PDF
15. Juli: Keine Vorlesung (Prüfungsvorbereitung)


Literatur

Es gibt kein Lehrbuch, welches die komplette Vorlesung abdeckt. Folgende Bücher bzw. Buchkapitel decken Teile des Inhalts ab:
  • Rina Dechter: Constraint Processing. Morgan Kaufmann, 2003
  • Francesca Rossi, Peter Van Beek, Toby Walsh: Handbook of Constraint Programming. Elsevier, 2006
  • Carla P. Gomes, Henry Kautz, Ashish Sabharwal, Bart Selman: Satisfiability Solvers. In: Handbook of Knowledge Representation, Elsevier Series on Foundations of Artificial Intelligence, Vol. 3, 2008. PDF

Computer Science IX | Technische Universität München