Diplomarbeiten

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.