Offene Themen
Masterarbeit
Präferenzen im räumlichen Planen
Eine Vielzahl von Brett- und Computerspielen (wie Go, Dame oder auch Tetris) erfordern die Fähigkeit zum räumlichen Planen. Dabei unterscheidet sich die menschliche Herangehensweise von entsprechende Computerprogramme wesentlich. So "präferieren" menschliche Spieler, neben vielen weiteren Faktoren, bestimmte Ansätze und Spieloperationen und übersehen andere. Die Kenntnisse der Unterschiede, Herangehensweisen und Präferenzen sind dabei, neben dem Design kognitiv-adäquater Computer- und Brettspielen, auch für eine kognitve und formale Theorie menschlichen räumlichen Planens von großem Interesse.
Ziel der Arbeit ist die Entwicklung, formale Fundierung und Implementation einer kognitiv-adäquaten Theorie räumlichen Planens anhand eines Spiels und der Vergleich mit formalen Methoden. Neben guten Programmier- und Logikkenntnissen wird eine Offenheit für kognitive Fragestellungen erwartet.
Weitere Informationen und Kontakt: Marco Ragni
Masterarbeit
Lösen räumlicher Analogien
Die Fähigkeit ähnliche Sachverhalte zu identifizieren und darüber Schlüsse zu ziehen ist trotz hoher Rechenleistung im wesentlichen eine rein menschliche Fähigkeit. Wie bedeutsam diese Fähigkeit ist lässt sich auch daran ermessen, dass in einer großen Zahl an Intelligenztests räumliche Analogieaufgaben zum Kanon gehören. In den letzten Jahren hat sich eine Vielzahl von Publikationen mit der Klassifikation solcher Aufgaben beschäftigt, dennoch hat die Entwicklung entsprechender Computerprogrammen damit nicht Schritt gehalten.
Ziel der Arbeit ist die Analyse von Analogieaufgaben mit bestimmten mathematischen Eigenschaften und die Entwicklung eines Computerprogramms zur Lösung der Aufgaben eines Intelligenztests (z.B. HAWIE oder IST-70). Neben sehr guten Programmier- und Logikkenntnissen wird eine Offenheit für kognitive Fragestellungen erwartet.
Weitere Informationen und Kontakt: Marco Ragni
Studienarbeit
Virtuelle Realität
Die Abteilung für Grundlagen der Künstlichen Intelligenz und die Abteilung Kognitionswissenschaft vergeben im Rahmen des DFG geförderten Sonderforschungsbereiches Spatial Cognition (http://www.sfbtr8.spatial-cognition.de) an interessierte Bewerber/innen folgende Studienarbeit:
Sie beschäftigen sich in diesem Projekt an der Weiterentwicklung eines virtuellen Supermarktes (mit im Raum angeordneten Regalen und ihrer Bestückung) und dem Vergleich menschlicher Strategien mit formalen Suchansätzen. Dabei existieren bereits einige Beispielimplementationen und es steht als Entwicklungsumgebung das Vizard Virtual Reality Toolkit (vgl. http://worldviz.com/) zur Verfügung. Gerade in der Supermaktdomäne spielt aber auch der Einfluss von Hintergrundwissen eine wichtige Rolle und soll daher in die Modellierung Eingang finden. Ihre Modellierung und Implementation wird direkt für psychologische Untersuchungen und für Marktforschungszwecke benutzt. Die Bearbeitungsdauer ist auf 2 Monate angesetzt.
Ihre Voraussetzungen:
- Python-Kenntnisse für Vizard und C++-Kenntnisse
- Vertrautheit mit Constraint Satisfaction Problemen wie sie beispielsweise in der Vorlesung Grundlagen der Künstlichen Intelligenz vermittelt werden
Weitere Informationen und Kontakt: Marco Ragni
Bachelorarbeit oder Masterarbeit
Lernen durch Imitation am Beispiel von Tetris
Tetris ist ein berühmtes Blockspiel, nach dem viele Menschen verrückt sind. Eine Sequenz von Blöcken fällt dabei runter auf ein Spielfeld. Ein Spieler muss die fallenden Blöcke so bewegen, dass es so viele horizontale Linien ohne Lücken als möglich entstehen. Zwei Spieler können dabei gegen einander antreten in dem einer N Linien auf einmal löscht und dabei für den Gegner eine N-1 Angriffslinie entsteht.
Das Thema der Arbeit ist, wie man einen intelligenten Agenten dazu bringt, gegen menschliche Gegner Tetris zu spielen. Wir wollen dabei Strategien von verschiedenen Spielern imitieren und diese dann bei menschlichen Gegner anwenden.
Das Thema kann als Bachelor oder Master Arbeit angelegt werden. Die Voraussetzungen sind
- Kenntnisse in C++-Programmierung mit Linux
- Motivation, die nötige Zeit und Arbeit zu investieren
Weitere Informationen und Kontakt: Dapeng Zhang
Bachelorarbeit, Masterarbeit oder Studienarbeit
Lernen mit Tischfußball
Der Tischfußball-Roboter KiRo kann bereits 90% der Spiele gegen menschliche Gegner gewinnen. Um reale Gegner, wie z.B. den Weltmeister, herauszufordern bedarf es eines extensiven Studiums von Spielen mit realen Spielern. Für diese Zwecke wurde der Rekorder KiRe entwickelt, der Tischfußballspiele von realen Spielern aufzeichnet. Mit Hilfe der aufgezeichneten Daten kann eine Serie von Methoden zum maschinellen Lernen implementiert werden, um folgende Aufgaben auszuführen:
- Klassifizierung der Aktionen
- Berechnung der technischen Statistik eines Spiels
- Klassifizierung der Spieler
- Bewertung der Qualität der Aktionen
- Bewertung des Könnens eines Spielers
Jedes Thema kann als Bachelorarbeit, Masterarbeit oder Semesterprojekt aufgebaut werden. Die Voraussetzungen sind:
- Kenntnisse in C++-Programmierung mit Linux
- Motivation, die nötige Zeit und Arbeit zu investieren
Weitere Informationen und Kontakt: Dapeng Zhang
Bachelorarbeit oder Studienarbeit
Lösung raum-zeitlicher Planungsprobleme am
Beispiel des temporalisierten Cardinal Direction Kalküls
In letzter Zeit gab es einige Ansätze qualitative räumliche Kalküle zu temporalisieren. Die resultierenden Erfüllbarkeitsprobleme und Lösungsansätze sind mit klassischen Planungsproblemen verwandt und lassen sich häufig rein aussagenlogisch kodieren. Eine Besonderheit dabei ist, dass dichte und diskrete Strukturen bei der Kodierung eine Rolle spielen.
Ziel dieser Arbeit ist es, die temporalisierte Version von Cardinal Direction als klassisches Planungsproblem zu kodieren und wahlweise einen Solver zu entwickeln, oder verschiedene heuristische Methoden, wie beispielsweise lokale Suche, zu evaluieren.
Weitere Informationen und Kontakt: Marco Ragni
Studienarbeit
SAT-basierte LTL-Modellprüfung in NuSMV
Bei der Modellprüfung wird untersucht, ob ein gegebenes System eine gegebene Spezifikation erfüllt. Ist dies nicht der Fall, wird ein Gegenbeispiel erzeugt, das zeigt, warum die Spezifikation verletzt ist. NuSMV ist ein symbolischer Modellprüfer für Spezifikationen in den Logiken CTL und LTL. Es enthält SAT- und BDD-basierte Algorithmen zur LTL-Modellprüfung, wobei der SAT-basierte Algorithmus in vielen Fällen ineffizienter als der BDD-basierte ist.
Ziel dieser Arbeit ist die Implementierung einer vorgegebenen Modifikation des SAT-basierten Algorithmus in NuSMV (parallele statt nur sequentieller Transitionen), in der Hoffnung, dadurch eine merkliche Effizienzsteigerung zu erzielen. Abschließend soll die Implementierung anhand vorhandener Benchmarks im Vergleich zu anderen Verfahren evaluiert werden.
Voraussetzungen:
- Gute C-Programmierkenntnisse
- Hilfreich: Grundlagen über Planen durch Erfüllbarkeitstests und über Modal- bzw. Temporallogiken
Weitere Informationen und Kontakt: Robert Mattmüller
Bachelorarbeit
Generierung von zufälligen
Realzeitautomaten
Realzeitautomaten (timed automata) sind eine Verallgemeinerung von endlichen Automaten, bei denen es zusätzlich zu den Zuständen und den Alphabet-Symbolen noch Variablen gibt, und zwar reellwertige, Uhren genannt, und ganzzahlige. Die Zustandsübergänge hängen, im Gegensatz zu der Situation bei gewöhnlichen Automaten, von Bedingungen an diese Variablen ab. Realzeitautomaten sind ein verbreitetes Modell zur Modellierung von Systemen. Für die Verifikation und Modellprüfung (model checking) von Realzeitautomaten gibt es das Programm Uppaal.
Im Rahmen des AVACS-Projekts erforscht der Lehrstuhl für GKI die heuristische Suche in den Zustandsräumen von Realzeitautomaten. Zu diesem Zweck sind wir stets an schwierigen Beispielen interessiert. Hierbei ist zu bemerken, dass Automaten mit einer Beschreibung von einigen Dutzend Zeilen leicht Zustandsräume der Größe 1000000 bis 100000000 haben können.
Ziel der Bachelor-Arbeit ist die Generierung solcher Beispiele, entweder ad-hoc oder besser noch automatisch, sodass systematisch der Zusammenhang zwischen bestimmten Parametern (Anzahl der Uhren, Verzweigungsgrad der Zustände, etc.) und der Schwere des Suchproblems und der Performanz der Heuristiken untersucht werden kann.
Weitere Informationen und Kontakt: Jan-Georg Smaus
Bachelorarbeit
Transformation von aussagenlogischen Formeln
in pseudo-Boolesche Constraints
Ein linearer pseudo-Boolescher Constraint (LPB) ist ein Ausdruck der Form a_1 l_1+...+a_m l_m ≥ d. Hierbei ist jedes l_i ein Literal der Form x_i or ¯x_i=1-x_i, d.h., x_i wird 0 wenn x_i falsch ist und 1 wenn x_i wahr ist, und umgekehrt für ¯x_i. Des weiteren sind a_1,...,a_m,d natürliche Zahlen. LPBs sind eine Verallgemeinerung von aussagenlogischen Klauseln. Boolesche Funktionen können mittels LPBs oft kompakter dargestellt werden als mittels konjunktiver oder disjunktiver Normalformen. Z.B. entspricht die LPB 2x_1+¯x_2+x_3+x_4≥2 der DNF x_1\/(¬ x_2/\ x_3)\/(¬ x_2/\ x_4)\/(x_3/\ x_4). Daher gibt es in der Literatur mehrere Ansätze, die Techniken aus dem SAT Solving (aussagenlogische Erfüllbarkeit) auf LPBs zu verallgemeinern. In diesen Arbeiten wird immer davon ausgegangen, dass sich die LPBs aus der Kodierung innerhalb der Problemdomäne natürlich ergeben.
Man kann allerding fragen: könnte es nicht auch interessant sein, beliebige aussagenlogische Formeln in eine äquivalente LPB-Menge zu transformieren, um dann beim Entscheiden der Erfüllbarkeit von der kompakteren Darstellung zu profitieren? Es gibt einen Algorithmus, der dieses Problem teilweise löst: gegeben eine aussagenlogische Formel, die sich als eine einzige LPB darstellen lässt, findet der Algorithmus diese LPB.
Gegenstand der Bachelor-Arbeit ist es, diesen Algorithmus zu implementieren, und einige Experimente zu machen, um abzuschätzen, wie aufwändig die Transformation in der Praxis ist.
Weitere Informationen und Kontakt: Jan-Georg Smaus
Laufende Arbeiten
Diplomarbeit
Domänenspezifische optimale Planer für ausgewählte
Benchmark-Domänen des Internationalen Planungswettbewerbs
Vergeben an: Thomas Keller (seit April 2008)
Beim zweijährlich stattfindenden Internationalen Planungswettbewerb (International Planning Competition, IPC) werden domänenunabhängige Planungssysteme anhand von Handlungsplanungsproblemen aus vorgegebenen Planungsdomänen miteinander verglichen. Die Probleme sind von einem solchen Schwierigkeitsgrad, dass häufig kein domänenunabhängiger Planer alle Probleme optimal lösen kann.
Um für einige dieser Probleme als Vergleichsgrundlage die optimalen Planlängen und optimale Pläne zu ermitteln, sollen im Rahmen dieser Diplomarbeit domänenspezifische optimale Planer für eine Auswahl von Planungsdomänen entwickelt werden. Dazu wird es häufig notwendig sein, Planungsproblemen zugrundeliegende Kombinatorische Optimierungsprobleme zu identifizieren und mit Hilfe von Standardalgorithmen der Kombinatorischen Optimierung zu lösen.
Im Verlauf der Arbeit sollten Domänen mit zunehmend komplexeren Eigenschaften, vom klassischen Planen bis hin zu Planen mit Zeit und Resourcen, gelöst werden.
Diplomarbeit
General Game Playing unter Verwendung automatisch
erzeugter Evaluierungsfunktionen
Vergeben an: Tenda Okimoto (seit April 2008)
Ein General-Game-Playing-System ist in der Lage, mit einer formalen Definition der Regeln eines Spiels als Eingabe dieses effektiv ohne menschlichen Eingriff zu spielen. Im Unterschied zu spezialisierten Game-Playing-Systemen beruhen General-Game-Playing-Systeme nicht auf Algorithmen, die speziell auf bestimmte Spiele zugeschnitten sind, sondern sind in der Lage, unterschiedliche Spiele zu spielen.
Ziel dieser Arbeit ist die Entwicklung eines General-Game-Playing-Systems auf der Grundlage des Referenzsystem Jocular. Der entwickelte Spieler sollte automatisch erzeugte Evaluierungsfunktionen zur Steuerung der Exploration des Spielbaumes verwenden. Die Herleitung der Evaluierungsfunktion aus der Spielbeschreibung sollte auf dem Fuzzy-Logic-Ansatz des Fluxplayer-Systems beruhen. Zusätzlich sollte mit weiteren Distanzheuristiken experimentiert werden.
Das resultierende System sollte anhand von online zugänglichen Benchmark-Spielen gegen andere General-Game-Playing-Systeme und möglicherweise auch gegen menschliche Spieler evaluiert werden.
Studienarbeit
Online-Reputationsmechanismen ohne finanzielle
Belohnungen
Vergeben an: Jens Witkowski (seit November 2007)
Die auf Online-Plattformen eingesetzten Reputationssysteme sind auf das ehrliche Feedback ihrer Teilnehmer angewiesen. Rationale Agenten äußern sich aber nur dann wahrheitsgemäß, wenn der so erzielte Nutzen den durch Lügen erzielbaren Nutzen übersteigt. Durch geeignete Auszahlungsmechanismen (finanzielle Belohnungen für eingereichtes Feedback) kann erreicht werden, dass das ehrliche Verhalten aller Agenten ein Nash-Gleichgewicht ist.
Jurca und Faltings nutzen Lineare Programmierung, um den günstigsten Auszahlungsmechanismus für eine gegebene Situation zu bestimmen. Bislang werden aber nur finanzielle Belohnungen betrachtet, die trotz dieser Optimierung zu hohen Kosten für den Mechanismus führen. Fehlen altruistische oder besonders glaubwürdige Agenten, existieren darüber hinaus mehrere unehrliche Gleichgewichte, von denen einige höhere Auszahlungen erzielen als das ehrliche Gleichgewicht.
In dieser Arbeit wird die Frage untersucht, ob sich diese Nachteile vermeiden lassen, indem man auf finanzielle Belohnungen verzichtet und die Agenten stattdessen mit Informationen über das Feedback anderer Agenten "bezahlt".
Diplomarbeit
Default-Logik in Multiagenten-Systemen
Vergeben an: Andreas Knab (seit November 2007)
Studienarbeit
Präferenzen im syllogistischen Schließen
Vergeben an: Oliver Klug (seit Juni 2007)
Syllogismen sind logische Argumente, die immer nach dem gleichen Muster aufgebaut sind: Eine Konklusion wird aus jeweils zwei Prämissen (quantifizierte Ausdrücke) inferiert. Dabei ist das syllogistische Schließen prinzipiell deduktiv. Interessanterweise unterscheiden sich kognitive Resultate wesentlich von Vorhersagen formaler Modelle.
Ziel der Arbeit ist es, die kognitiven Resultate von Chaters und Oaksford einzuordnen, diese mittels Eulerkreisen zu modellieren und zu implementieren und schließlich die Resultate mittels eines kognitiven Komplexitätsmaßes zu erklären.
Studienarbeit
Fußgänger-Positionsbestimmung mittels
Beschleunigungssensoren und RFID
Vergeben an: Dali Sun (seit Januar 2007)
