Uni-Logo

Diplomarbeiten

Anmerkung: Diese Liste wird derzeit überarbeitet und erhebt daher keinen Anspruch auf Vollständigkeit.

Alexander Bisaliev
Efficient Determination of Equilibrium Strategies for Extensive Two-Player General-Sum Games with Simultaneous Moves With an Application to General Game Playing
April 2011
Kai Siebold
Transformation von aussagenlogischen Formeln in pseudo-Boolesche Constraints
Februar 2011

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.

Hartmut Hanke
Prozedurales Domänenkontrollwissen für temporales Planen
Oktober 2010

Domänenkontrollwissen kann verwendet werden, um die möglichen Pläne einer Planungsaufgabe einzuschränken. Dadurch wird der Suchraum verkleinert und es ist so möglich, Planungsaufgaben zu lösen, die zu schwierig für ein domänenunabhängiges Planungssystem wären. Eine Möglichkeit, solches Domänenwissen zu definieren, ist, die möglichen Pläne abstrakt mit Hilfe einer prozeduralen (Golog-ähnlichen) Sprache zu beschreiben. Baier hat solch eine Sprache vorgestellt und gezeigt, wie man dieses Domänenwissen in die ursprüngliche PDDL-Beschreibung kompilieren kann und es so für beliebige klassische Planungssysteme nutzbar machen kann.

Ziel dieser Diplomarbeit ist es, diese Methode für temporales Planen weiterzuentwickeln. Die prozedurale Beschreibungssprache muss hierzu um geeignet gewählte temporale Konstrukte mit einer klar definierten Semantik erweitert werden. Im nächsten Schritt soll dann eine Kompilierung angegeben werden, die das Domänenkontrollwissen in die gegebene temporale PDDL-Beschreibung integriert. Eine Implementierung dieser Kompilation und eine experimentelle Evaluation runden die Arbeit ab.

Jens Witkowski
Ehrliches Feedback für Reputationsmechanismen
Mai 2009
Download: (PDF)

Reputationsmechanismen wie die von Amazon und eBay bieten eine effiziente Methode zur Verhinderung von Marktversagen auf elektronischen Marktplätzen. Existierende Systeme nehmen an, dass das Feedback der Agenten ehrlich ist. Diese Annahme steht im Gegensatz zu Erkenntnissen aus der Spieltheorie sowie empirischen Untersuchungen, die nahelegen, dass das abgegebene Feedback unehrlich beziehungweise verzerrt ist. Für solche Reputationsmechanismen, die ausschließlich negative Auslese bekämpfen (wie beispielsweise die Produktbewertungen bei Amazon) ist es möglich einen Feedback-Mechanismus zu entwerfen, der rationale Agenten dazu bringt ehrliche Bewertungen abzugeben. In dieser Arbeit haben wir untersucht, ob sich ein ähnlicher Mechanismus für solche Reputationsmechanismen entwerfen lässt, die in Märkten mit moralischer Versuchung ("moral hazard") eingesetzt werden. Durch ein von uns auf Basis der Situation bei eBay aufgestelltes Modell mit ausschließlich moralischer Versuchung, konnten wir zeigen, dass es keinen einzig auf den Vergleich von Aussagen basierenden Feedback-Mechanismus gibt. Für ein Marktmodell mit sowohl negativer Auslese als auch moralischer Versuchung erzielen wir hingegen ein positives Resultat und entwickeln ein auf Linearer Programmierung basierendes "Feedback Plug-in", das in bestehende Reputationsmechanismen eingebunden werden kann.

Stefan Schleipen
Vereinfachung numerischer Planungsprobleme
April 2009
Download: (PDF)

Obwohl bei internationalen Planungskonferenzen, z.B. der International Planning Competition (IPC), neben klassischen Problemen auch numerische Problemstellungen behandelt werden, ist die Zahl numerischer Planer in den letzten Jahren überschaubar geblieben. Im Gegensatz zu den klassischen Planern, deren Anzahl seither gestiegen ist. So ist auch die Qualität klassischer Planer im Vergleich zu den Numerischen wesentlich besser. Inhalt dieser Arbeit ist es numerische Probleme so zu verändern, dass sie mit klassischen Planern gelöst werden können. Dazu müssen die numerischen Teile des Problems extrahiert, konvertiert und wiederum in die Problemstellung zurückgeführt werden. In diesem Zusammenhang erfolgt eine Analyse der gestellten Probleme zur Erkennung numerischer Variablen und Konstanten. Es werden Methoden zur Reduktion der Wertebereiche (optimal bzw. approximierend) und zur Konvertierung von numerischen Problemen in STRIPS konforme Probleme vorgestellt.

Pascal Bercher
Anwendung von Pattern-Database-Heuristiken zum Lösen nichtdeterministischer Planungsprobleme
März 2009
Download: (PDF)

Die vorliegende Arbeit behandelt das Suchen von starken Plänen nichtdeterministischer Planungsprobleme mit dem Ansatz des Planens durch heuristische Suche unter Verwendung des AO*-Algorithmus und von domänenunabhängigen Pattern-Database-Heuristiken. Starke Pläne garantieren das Erreichen eines Zielzustands unabhängig vom Ausgang des Nichtdeterminismus. Der Fokus dieser Arbeit richtet sich auf die Pattern-Database-Heuristiken, die im klassischen Planen Anwendung finden und nun auf nichtdeterministisches Planen übertragen werden. Es wird gezeigt, unter welchen Bedingungen man durch Addition von Pattern-Database-Heuristiken eine zulässige und informative Heuristik konstruieren kann. Der Suchalgorithmus und die Heuristik wurden vollständig implementiert. Anhand dieser Implementierung wurden drei Domänen untersucht. Die Ergebnisse dieser Experimente werden schließlich diskutiert. Dabei zeigt sich, dass Pattern-Database-Heuristiken, insbesondere durch Ausnutzung von Additivität, auch im nichtdeterministischen Planen sehr gute Ergebnisse erzielen können.

Christoph Betz
Komplexität und Berechnung der h+-Heuristik
Februar 2009
Download: (PDF)

In dieser Arbeit wird die von Hoffmann eingeführte h+-Heuristik für domänenunabhängige Planungssysteme einer domänenabhängigen Analyse unterzogen. Zum einen wird die Komplexität der Heuristikberechnung in bestimmten Planungsdomänen wie Logistics oder Blocksworld betrachtet, zum anderen wird die Heuristikfunktion für bestimmte Domänen implementiert und im Vergleich zu etablierten domänenunabhängigen Heuristiken empirisch evaluiert.

Alexander Schimpf
Implementierung eines Verfahrens zur Erzeugung von Büchi-Automaten aus LTL-Formeln in Isabelle
Dezember 2008
Download: (PDF) (Code; ZIP)

In dieser Diplomarbeit wird mit Hilfe des interaktiven Theorembeweisers Isabelle/HOL ein Verfahren zur Erzeugung von Büchi-Automaten aus LTL-Formeln implementiert und die Korrektheit dieser Konstruktion bewiesen. Aus der Isabelle-Spezifikation wird schließlich unter Verwendung des Codegenerators von Isabelle/HOL ausführbarer Code der Implementierung erzeugt. Ausgehend von der ursprünglichen Idee des Verfahrens von Gerth, Peled, Vardi und Wolper konnte die Korrektheit der Konstruktion bestätigt werden.

Thomas Keller
Optimales domänenspezifisches Planen in der Transport- & Routenplanungsfamilie
November 2008
Download: (PDF)

Die klassische, domänenunabhängige Handlungsplanung ist ein Gebiet, das heute von vielen Forschungsgruppen mit sehr unterschiedlichen Methoden untersucht wird. Trotz großer Fortschritte in den letzten Jahren mehren sich aber die Anzeichen, dass klassische Verfahren wie die heuristische Suche oder das Planen als Erfüllbarkeitsproblem bald an eine Grenze stoßen werden.

Eine Möglichkeit, dennoch immer komplexere Planungsaufgaben zu lösen, könnte darin liegen, domänenspezifische Erkenntnisse in die Planung miteinfließen zu lassen. Diese Arbeit beschäftigt sich daher mit zwei dafür relevanten Themen: Zum einen werden Möglichkeiten formalisiert, mit deren Hilfe Teilprobleme erkannt und Planungssystemen zusätzliche Informationen über Domänen zugänglich gemacht werden können. Zum anderen werden zwei Planer für Domänen der Transport- und Routenplanungsfamilie vorgestellt, und dabei aufgezeigt, in welcher Form deren Analyse durchgeführt werden kann.

Die Ergebnisse, die mit den implementierten Planern erzielt wurden, zeigen dabei deutlich auf, dass die Ausnutzung domänenspezifischen Wissens zu sehr viel leistungsfähigeren Planern führt.

Tenda Okimoto
General Game Playing unter Verwendung automatisch erzeugter Evaluierungsfunktionen
September 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.

Andreas Knab
Default-Logik in Multiagenten-Systemen
Juli 2008
Jan Rehm
Zufälliges Erstellen von Realzeitautomaten im Uppaal-Format
Januar 2008
Download: (PDF)

In dieser Arbeit geht es um den Entwurf und Vergleich verschiedenen Methoden, Realzeit- Automaten (engl. timed automata) zufällig derart zu generieren, dass die entstehenden Automaten als Testmuster interessant sind, mit denen man die Performanz des Model Checker Uppaal testen kann. Dazu werden bereits vorhandene Ansätze zum zufälligen Generieren von zufälligen deterministischen und nicht-deterministischen endlichen Auto- maten betrachtet und diese mit dem Generieren von Realzeit-Automaten verglichen, um Unterschiede in der Problemstellung aufzuzeigen und anschlieÿend mögliche Lösungen für diese Probleme zu präsentieren. Das aus diesen Lösungen resultierende Programm generiert bei passenden Eingaben Testmuster und dazugehörige Queries für Uppaal, die mit einer 50/50 Wahrscheinlichkeit entweder als satised oder not satised gelten, eine Verteilung, die für das Model Checking interessant ist, da keine vorherige Aussage gemacht werden kann, ob das gestellte Problem lösbar ist oder nicht.

Oliver Pier
Terminologien, Defaults und Wahrscheinlichkeiten: ein integrativer Ansatz zur Wissensrepräsentation und Wissensverarbeitung
November 2007
Dennis Jung
Eine automatentheoretische Heuristik für klassische Planungsprobleme
Juli 2007
Download: (PDF)

Das Verifizieren von Invarianten in der Modellprüfung ist eine Aufgabenstellung, die sehr nah mit der klassischen Handlungsplanung verwandt ist. Daher ist es oft möglich, Ideen aus dem einen Gebiet auf das andere zu übertragen. In dieser Arbeit wird eine automatentheoretische Heuristik aus der Modellprüfung auf Handlungsplanungsprobleme angewandt und mit anderen bekannten Heuristiken wie der FF-Heuristik verglichen.

Mathias Exner
Zu um Funktionen erweitertem ADL gleichausdrucksstarke Basic-Action-Theorien
Juni 2007

Die Integration von Aktionsformalismen wie Golog und von Planungstechniken, für die normalerweise PDDL als Beschreibungssprache Verwendung findet, würde große Vorteile bringen. Als erster Schritt in diese Richtung wurde eine Teilmenge des Situationskalküls, auf dem Golog basiert, identifiziert, die die gleiche Ausdrucksstärke wie das ADL-Fragment von PDDL hat.

In dieser Arbeit soll dieses System um die arithmetischen Funktionen von PDDL erweitert werden. Hierzu sollen Bedingungen an das Situationskalkül formuliert werden, die zur gleichen Ausdrucksstärke führen. Diese Eigenschaft soll anhand von Kompilationstechniken bewiesen werden, die dann auch gleich ein Verfahren zur Übertragung von Problemen des einen Formalismus in den anderen ergeben. Diese Übertragung soll implementiert werden. Zusätzlich soll für einige der gemachten Einschränkungen gezeigt werden, dass sie notwendig sind, beziehungsweise inwieweit eine Lockerung möglich ist, ohne die Gleichheit der Ausdrucksstärke zu verlieren.

Diana Dragojevic
Transformation von SPS- in Realzeitautomaten
Mai 2007
Download: (PDF)

Die Arbeit befasst sich mit der Transformation von SPS-Automaten in Realzeitautomaten. Solch eine Übersetzung ist interessant, da es momentan keinen Modellprüfer gibt, der SPS-Automaten direkt als Eingabesprache akzeptiert. Die einzige existierende Übersetzung ist Teil von Moby/RT einem CASE-Tool für SPS-Automaten. Moby/RT verifiziert SPS-Automaten indem sie diese zuerst in Uppaals Eingabesprache übersetzt und danach mit Uppaal verifiziert. Allerdings verwendet Moby/RT dazu nur einen kleinen Teil der akzeptierten Eingabesprache, was die erzeugten Realzeitautomaten unnötig aufbläht.

In dieser Arbeit wird eine Übersetzung beschrieben, die aktuelle Sprachfeatures verwendet. Die so entstandenen Realzeitautomaten sind natürlicher als die von Moby/RT, da eine Transition im SPS-Automaten durch eine Transition im Realzeitautomaten repräsentiert wird.

Micha Altmeyer
Multiagenten-Planung mittels ATL Model Checking
Mai 2007
Paul Dischinger
Identifikation von Phasenübergängen in Handlungsplanungsbenchmarks
Mai 2007
Download: (PDF)

Bei vielen NP-vollständigen Entscheidungsproblemen sind sogenannte Phasenübergänge zwischen einem Bereich mit nur schwach eingeschränkten positiven und einem Bereich mit stark eingeschränkten negativen Instanzen zu beobachten. Diese Übergänge lassen sich meist durch einen problemabhängigen Ordnungsparameter charakterisieren. Von Instanzen, die weit von der Phasengrenze entfernt liegen, kann häufig leicht gezeigt werden, dass es sich um positive bzw. negative Instanzen handelt. Viele der wirklich schweren Instanzen liegen in der Nähe der Phasengrenze.

Im Rahmen dieser Arbeit werden Phasenübergänge in Handlungsplanungs-Benchmarkproblemen empirisch untersucht und beschrieben, da die Kenntnis der Phasenübergänge potentiell die Erzeugung besonders schwerer Benchmark-Instanzen erlaubt.

Christian Dornhege
Planen und Lernen autonomer Roboter-Verhalten auf schwer zugänglichem Terrain
April 2007
Download: (PDF)

Ziel dieser Diplomarbeit ist es ein Verfahren zur Exploration auf schwer zugänglichem Terrain, das Hindernisse wie Paletten und Rampen beinhaltet, zu entwickeln. Im Vergleich zu Umgebungen wie zum Beispiel Schotter oder Gras, die auch erhöhte Anforderungen an die Mobilität des Roboters stellen, ist es bei sehr steilen Strukturen nicht mehr möglich nur zwischen befahrbar und Hindernis zu unterscheiden und das Vorankommen des Roboters durch ein einziges Verhalten zu gestalten. Es ist vielmehr notwendig, dass der Roboter sich der spezifischen Hindernisse bewusst ist und dafür spezielle Fähigkeiten besitzt und ausführen kann.

Um Hindernisse überhaupt zu erkennen, werden deshalb während der Fahrt Höhenkarten mit einem geneigten 2D-Laserscanner erstellt und diese dann klassifiziert. Aus Höhenkarten und einer Menge von Fähigkeitsbeschreibungen für verschiedene Hindernisse werden dann automatisch Verhaltenskarten erstellt. Diese kodieren mittels der Fähigkeitsbeschreibungen direkt Informationen für die auszuführende Fähigkeitsroutine in die Karte. Dadurch wird die Planung mittels normaler A*-Suche unter Berücksichtigung der spezifischen Voraussetzungen zu Ueberquerung von Hindernissen ermöglicht. Experimente, die unter anderem einen vollständig autonomen Lauf in einem Testparcours, bei dem eine Palette und eine Rampe zu überqueren war und eine Höhenkarte erstellt wurde, beinhalten, demonstrieren die Möglichkeiten des entwickelten Systems.

eyerich
Subsumption deterministischer Aktionsschemata
April 2007
Download: (PDF)
Benjamin Lempp
Algorithmen für teilerfüllendes Planen
März 2007
Download: (PDF)

Teilerfüllendes Planen ist eine Erweiterung der klassischen Handlungsplanung, bei der es dem Agenten freigestellt ist, ein vorgegebenes Ziel nur teilweise zu erfüllen. Die Planqualität wird dabei durch Abwägung zwischen dem Nutzen der erreichten Teilziele und den Kosten des Plans bewertet.

Im Rahmen dieser Diplomarbeit werden Algorithmen für teilerfüllendes Planen implementiert, wobei der Schwerpunkt auf der Auswahl der zu erreichenden Teilziele liegt. Für die eigentliche Aktionsplanung wird für eine gegebene Teilzielmenge dabei ein klassisches Planungssystem eingesetzt. Die Ergebnisse verschiedener Ansätze werden untereinander und mit anderen Algorithmen für teilerfüllendes Planen verglichen.

Viara Halatcheva
Modellierung und Implementierung eines Online-Beraters auf Basis eines hybriden Recommendersystems am Beispiel Mode
September 2006
Julia Peltason
Ein wissensbasierter Benutzermodellierungs-Service für Sprachdialogsysteme im Automobilbereich
Juli 2006
Silvia Richter
Learning Road Traffic Control: Towards Practical Traffic Control Using Policy Gradients
Juli 2006
Download: (PDF)
Martin Wehrle
Codierungen paralleler Pläne im Kontext erfüllbarkeitsbasierter Handlungsplanung
Mai 2006
Download: (PDF)
Robert Mattmüller
Erfüllbarkeitsbasierte Handlungsplanung mit temporal erweiterten Zielen
März 2006
Download: (PDF)
Sebastian Trüg
An integration of manipulation and action planning
Februar 2006
Download: (PDF)
Michael Drescher
Approximationseigenschaften von Transportproblemen in der Handlungsplanung
Januar 2006
Download: (PS.GZ)
Philipp Jarvers
Verkehrsflussoptimierung durch Abflugplanung von Kurzstreckenflügen
Januar 2006
Download: (PDF)
Uwe Zeisberger
Pfadplanung unter Unsicherheit
April 2005
Download: (PS.GZ)
Sebastian Kupferschmid
Entwicklung eines Double-Dummy Skat Solvers mit einer Anwendung für verdeckte Skatspiele
Juli 2003
Download: (PS.GZ)

In dieser Diplomarbeit werden Monte Carlo Simulation und Alpha-Beta-Suche auf das Skatspiel angewendet. Das entwickelte Skatprogramm integriert bekannte Techniken wie z. B. Zuganordnung (move ordering) mit zwei neuen Sucherweiterungen. Quasi-Symmetrie-Reduktion ist eine Generalisierung von M. Ginsbergs Partition Search, die es erlaubt ähnliche Zustände als symmetrisch anzusehen. Desweiteren wird eine Technik zur schnellen Vorwärtssuche vorgestellt, die Ideen aus dem Gebiet der heuristischen Suche in den Kontext von Zweipersonenspielen transferiert. Die Kombination dieser Techniken zusammen mit einem modernen Algorithmus zur Baumsuche ermöglicht es den spieltheoretischen Wert einer typischen Skathand (mit vollständigem Weltwissen) in 10 Millisekunden zu berechnen.

Moritz Tacke
MITRA: Aktionsauswahl im Tischfußball
Juni 2003
Download: (PS.GZ)
Erik Schulenburg
Selbstlokalisierung im Roboter-Fußball unter Verwendung einer omnidirektionalen Kamera
Februar 2003
Download: (PS.GZ)
Björn Fischer
Robuste Positionsschätzung mittels Monte-Carlo-Lokalisierung in der RoboCup-Umgebung
Juli 2002
Download: (PS.GZ)
Markus Dietl
Reinforcement-Lernen beim Roboterfußball
April 2002
Download: (PS.GZ)
Malte Helmert
On the Complexity of Planning in Transportation and Manipulation Domains
März 2001
Download: (PS.GZ)
Klaus Müller
Roboterfußball: Multiagentensystem CS Freiburg
Februar 2001
Download: (PS.GZ)
Alexander Scivos
Einführung in eine Theorie der ternären RST-Kalküle für qualitatives räumliches Schließen
Oktober 2000
Download: (PS.GZ)
Augustinus Topor
Roboter-Fußball: Pfadplanung in dynamischer Umgebung
April 2000
Download: (PS.GZ)
Maximilian Thiel
Roboter-Fußball: Zuverlässige Ballerkennung und Positionsschätzung
April 2000
Download: (PS.GZ)
Christian Reetz
Aktionsauswahl in dynamischen Umgebungen am Beispiel Roboter-Fußball
April 2000
Download: (PS.GZ)
Ronny Fehling
Effiziente Navigation im Lösungsraum eines graphischen Layout-Problems
April 2000
Bernhard Seckinger
Synthese von Aufzugssteuerungen mit Hilfe von constraintbasierten Suchververfahren
Dezember 1999
Download: (PS.GZ)
Jörg Hoffmann
Ein Überdeckungsproblem für beliebig dimensionierte Hyperquader
Juni 1999
Download: (PS.GZ)
Thilo Weigel
Roboter-Fußball: Selbstlokalisierung, Weltmodellierung, Pfadplanung und verhaltensbasierte Kontrolle
April 1999
Download: (PS.GZ)