Anmerkung: Diese Liste wird derzeit überarbeitet und erhebt daher keinen Anspruch auf Vollständigkeit.
Bachelorarbeit
Erweiterung eines Planungssystems
zum Lösen von Ein-Personen-Spielen
Autor: Silvan Sievers (Oktober 2009)
Download: (PDF)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.
Die Spiele, die beim AAAI-General-Game-Playing-Wettbewerb erfolgreich gespielt werden müssen, umfassen neben Zwei- und Mehrpersonenspielen auch Ein-Personenspiele. Aus algorithmischen Gründen ist es bei der Entwicklung eines General-Game-Playing-Systems sinnvoll, Ein- und Mehrpersonenspiele getrennt zu behandeln. Da Ein-Personenspiele im Sinne der Spielbeschreibungssprache GDL, in der die Wettbewerbsspiele kodiert sind, im Wesentlichen klassische Handlungsplanungsprobleme sind, kann man sie auch mit entsprechenden Algorithmen lösen.
Ziel dieser Arbeit war die Integration erprobter Algorithmen und Heuristiken aus der klassischen Handlungsplanung in ein in der Entwicklung befindliches General-Game-Playing-System. Das resultierende System sollte anhand von online zugänglichen Benchmark-Spielen evaluiert werden.
Bachelorarbeit
Analyse des SGPlan
Autor: Diana Hille (September 2009)
Download: (PDF)Ziel dieser Arbeit ist es, eine detaillierte Analyse des SGPlan vorzunehmen. SGPlan hat in den letzten internationalen Planungswettbewerben (insbesondere der 4. und 5. IPC) gute Leistungen erzielt. Bisher ist der Quellcode des Planers nicht frei zugänglich gewesen, wurde dann aber im Rahmen der 6. IPC zur freien Verfügung gestellt. Anhand des Codes sollen die bisher erzielten Erfolge, die bisland nur unzureichend durch die dazu veröffentlichten Beschreibungen erklärt wurden, genauer untersucht und auch die algorithmischen Hintergründe näher betrachtet werden.
Bachelorarbeit
Fluent Merging für klassische
Planungsprobleme
Autor: Jendrik Seipp (September 2009)
Download: (PDF)Fluent Merging ist eine Technik zum Umformulieren von klassischen Planungsproblemen, die automatisch oder semi-automatisch verwendet werden kann. Ziel der Umformulierung ist es, das Problem in eine Form zu bringen, die es dem Planungsalgorithmus erlaubt, das Problem mit geringerem Suchaufwand zu lösen oder Lösungen besserer Qualität zu finden. In dieser Arbeit werden verschiedene Ansätze zum Fluent-Merging eingeführt und in aktuellen Planungssystemen evaluiert.
Bachelorarbeit
Einfluss der Finite-Domain-Repräsentation
auf die Performance von Planungssystemen
Autor: Jonas Sternisko (September 2009)
Download: (PDF)Im Gegensatz zur propositionalen Repräsentation von Planungsaufgaben, bei der jede Zustandsvariable nur zwei Werte (wahr und falsch) annehmen kann, können die Variablen bei der Finite-Domain-Repräsentation eine beliebige endliche Domäne haben. Dies ermöglicht oftmals eine deutlich natürlichere Formalisierung der Planungsaufgabe. Zudem werden bestimmte Mutex-Beziehungen explizit erfasst, die ein Planungssystem nutzen kann, um die Aufgabe effizienter zu lösen. Ziel dieser Arbeit ist es, empirisch den Einfluss der Repräsentation der Planungsaufgabe auf die Performanz verschiedener Planungssysteme zu untersuchen.
Bachelorarbeit
Automatische Pattern-Selektion für Pattern-Database-Heuristiken im Nichtdeterministischen Planen
Autor: Manuela Ortlieb (September 2009)
Download: (PDF)Die Arbeit behandelt einen Teilaspekt das Suchen nach starken Plänen für nichtdeterministische Planungsprobleme mit dem Ansatz des Planens durch heuristische Suche unter Verwendung des AO*-Algorithmus und domänenunabhängiger Pattern-Database-Heuristiken. Starke Pläne garantieren das Erreichen eines Zielzustands unabhängig vom Ausgang des Nichtdeterminismus. Der Fokus dieser Arbeit liegt auf der automatischen Erzeugung geeigneter Patterns durch heuristische Suche im Raum der Pattern-Collections, analog zur Arbeit von Haslum et al. im deterministischen Planen. Ziel ist die Implementierung und Evaluierung eines entsprechenden Pattern-Selektions-Algorithmus.
Bachelorarbeit
Lösen allgemeiner Spiele durch heuristische Suche
Autor: Johannes Aldinger (April 2009)
Download: (PDF)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.
Im Rahmen dieser Arbeit wurde auf Grundlage des General-Game-Playing-Systems Jocular ein System entwickelt, dessen automatisch generierte Bewertungsfunktion die aus dem Bereich der Handlungsplanung bekannte FF-Heuristik auf Probleme mit zwei Spielern und numerischen Präferenzen über den Terminalzuständen erweitert.
Bachelorarbeit
Kompakte Kodierungen monotoner boolescher
Funktionen
Autor: David Goergen (Mai 2008)
Eine boolesche Funktion ist monoton, wenn sie sich durch einen kombinatorischen Schaltkreis darstellen lässt, der ausschließlich UND- und ODER-Gatter verwendet. Monotone boolesche Funktionen spielen eine wichtige Rolle in der Komplexitätstheorie und treten in einer Reihe von Anwendungsproblemen auf.
Ziel dieser Arbeit ist es, eine monotone boolesche Funktion, die etwa durch einen Schaltkreis oder ein propositionales Logikprogramm gegeben ist, kompakt zu kodieren, d.h. einen Schaltkreis zu finden, der die Funktion unter Verwendung möglichst weniger Gatter berechnet. Weiterhin soll die Anwendung solcher kompakter Kodierungen auf die Berechnung von Relaxierungsheuristiken in der Handlungsplanung und auf Line-of-Sight-Algorithmen in diskreten 2D-Welten untersucht werden.
