Note: This list is currently being revised and does not claim to be complete.
Diploma thesis
Truthful Feedback for Reputation Mechanisms
Author: Jens Witkowski (May 2009)
Download: (PDF)Reputation mechanisms such as those employed by Amazon and eBay offer an effective way to prevent market failure in online economies. However, most of these mechanisms assume that the privately monitored transaction outcomes are honestly reported. This clearly is a simplification since buyers may have incentives to misreport. While it has been shown that the truthful elicitation of these outcomes is feasible in settings with pure adverse selection, i.e. with a purely stochastic seller, we study whether honest feedback can be elicited in settings with moral hazard, i.e. with a strategic seller. For a pure moral hazard setting motivated by the one at eBay, we find that there is no feedback mechanism that makes honest reporting a best response to truthful play by all other players. For a combined setting with both adverse selection and moral hazard, however, we retrieve a positive result and construct a payment scheme that can be used as a "feedback plug-in" for reputation mechanisms.
Diploma thesis
Simplifying numerical planning problems
Author: Stefan Schleipen (April 2009)
Download: (PDF)Although international planning conferences, e.g. within the International Planning Competition (IPC), cover numerical as well as classical planning tasks, the number of numerical planners has remained low over recent years. This is different from the situation for classical planners, whose number has grown significantly. As a consequence, the quality of classical planners is considerably better than for numerical planners. The topic of this thesis is to modify numerical planning tasks in such a way that they can be solved with classical planners. For this purpose, the numerical parts of the problem must be extracted, converted, and reintegrated into the problem specification. In this context, the given problems are analyzed in order to recognize numerical variables and constants. We present methods for reducing the domains of numerical varables (optimally and approximatively) and to convert numerical problem into problems conforming to the STRIPS fragment of PDDL.
Diploma thesis
Application of Pattern Database Heuristics to the Solution of
Non-Deterministic Planning Problems
Author: Pascal Bercher (March 2009)
Download: (PDF)The present work is concerned with finding strong plans for non-deterministic planning problems by the approach of planning as heuristic search, more precisely, AO* search guided by domain-independent pattern database (PDB) heuristics. Strong plans guarantee that a goal state is reached in a finite number of steps independently of the non-deterministic outcomes. The focus of this work is on the PDB heuristics, which have already been successfully employed in classical planning and should now be generalized to non-deterministic planning. We show under which conditions patterns are additive and the corresponding PDB heuristics can be safely added in order to obtain an informative heuristic value while maintaining admissibility of the sum. The search algorithm and the heuristic are completely implemented. The performance of the heuristic is evaluated on three planning domains and the results are discussed. It turns out that PDB heuristics can yield very good results in non-deterministic planning as well, in particular if additivity is exploited.
Diploma thesis
Complexity and computation of the h+ heuristic
Author: Christoph Betz (February 2009)
Download: (PDF)In this thesis, Hoffmann's h+ heuristic for domain-independent planning systems is studied from a domain-dependent perspective. A theoretical study analyzes the complexity of computing the h+ heuristic in standard planning domains like Logistics or Blocksworld, and an empirical study implements the heuristic for a number of benchmark domains and empirically evaluates it in comparison to state-of-the-art domain-independent heuristics.
Diploma thesis
Implementation of a Procedure for Generating Büchi-Automata
from LTL Formulae in Isabelle
Author: Alexander Schimpf (December 2008)
Download: (PDF) (Code; ZIP)In this Diploma thesis, a procedure for generating Büchi-automata from LTL formulae is implemented and proved correct using the interactive theorem prover Isabelle/HOL. Subsequently, executable code is generated from this Isabelle spcification using the Isabelle/HOL code generator. Thus based on the original idea of the construction by Gerth, Peled, Vardi and Wolper, the correctness of the construction was proven.
Diploma thesis
Domain-Specific Optimal Transport- & Route Planning
Author: Thomas Keller (November 2008)
Download: (PDF)Nowadays, domain-independent planning is a scientific area dealt with by many people using very different methods. Even though important advances were achieved in the last couple of years it seems as if classical methods such as heuristic search or planning as satisfiability are about to reach their limitations.
One possibility to push that limit anyways might be the inclusion of domain-dependent knowledge. This thesis covers two topics relevant to that idea: On the one hand, methods to automatically detect already known subproblems in domains are discussed. On the other hand, two optimal planners for specific domains are described and taken as an example of how to analyze domains in general.
The performance of the implemented domain-specific planners clearly shows that the use of domain-dependent knowledge leads to better performing planners.
Diploma thesis
General Game Playing using Automatically Generated
Evaluation Functions
Author: Tenda Okimoto (September 2008)
A General Game Playing System is one that can accept a formal definition of a game and play the game effectively without human intervention. Unlike specialized game players, general game players do not rely on algorithms designed in advance for specific games, and they are able to play different kinds of games.
The purpose of this work is to develop a General Game Playing System based on the Java reference player Jocular that uses automatically generated evaluation functions to guide the exploration of the game tree. The inference of the evaluation function given the game description should be based on the fuzzy logic approach used in the Fluxplayer system. Experimenting with other distance heuristics would be interesting as well.
The resulting system should be evaluated against other General Game Playing Systems and possibly against human players on a number of benchmark games available online.
Diploma thesis
Default reasoning in multi-agent systems
Author: Andreas Knab (July 2008)
Diploma thesis
Generating Random Timed Automata in Uppaal Format
Author: Jan Rehm (January 2008)
Download: (PDF)Timed automata are a generalisation of finite automata having, apart from states and alphabet symbols, real-valued variables called clocks as well as integer variables. In contrast to usual automata, the transitions depend on conditions on these variables. Timed automata are a wide-spread formalism for modelling systems. For model checking timed automata, there is the tool Uppaal.
In the context of the AVACS project, the AI group explores heuristic search in the state spaces of timed automata. Therefore we are always interested in hard examples. Note that timed automata with a description of a few dozen lines can easily have state spaces of size 1000000 to 100000000.
The goal of the bachelor thesis is to generate such examples, either ad-hoc or even better, automatically, so that we can analyse systematically the relationship between certain parameters (number of clocks, out-degree of the states, etc.) and the hardness of the search problem and heuristic performance.
Diploma thesis
Terminologies, defaults, and probabilities:
an integrated approach for knowledge representation and reasoning
Author: Oliver Pier (November 2007)
Diploma thesis
An automata-theoretic heuristic for classical AI
planning
Author: Dennis Jung (July 2007)
Download: (PDF)Verification of invariants in model checking is a problem that is closely related to classical AI planning. It is thus often possible to successfully apply ideas from one of these areas to the other. In this thesis, an automata-theoretic heuristic from the model checking area is applied to classical AI planning tasks and compared to other well-known planning heuristics such as the FF heuristic.
Diploma thesis
Basic Action Theories with the same expressive power as ADL with arithmetic functions
Author: Mathias Exner (June 2007)
The integration of action formalisms like Golog and planning techniques, which usually use PDDL as description language, would provide great advantages. First endeavours have been made by identifying a subset of the situation calculus, which is the basis of Golog, with the same expressive power as the ADL fragment of PDDL.
In this thesis this framework shall be enlarged to include the arithmetic functions of PDDL. For this, requirements on the situation calculus must be identified that lead to the same expressivity. This property shall be proven by means of compilation techniques which also directly provide a method to translate problems of one formalism into the other. This translation shall be implemented. Furthermore, for some of the requirements shall be proven that they are necessary, or it shall be shown to what extent they can be eased.
Diploma thesis
Translating PLC Automata into Timed Automata
Author: Diana Dragojevic (May 2007)
Download: (PDF)This diploma thesis deals with the translation of PLC automata into timed automata. Such a translation is of interest, because currently there is no model checker which accepts PLC automata directly as input. The existing translation is part of Moby/RT, a CASE tool for PLC automata. Moby/RT verifies PLC automata by first translating them into Uppaal's input language and using Uppaal for verification afterwards. However, Moby/RT uses only a small fraction of Uppaal's input language; this leads to an unnecessary blow up of the resulting automata.
This thesis describes a translation which makes use of contemporary features of the input language. The resulting timed automata are more natural as the ones produced by Moby/RT. This is because one transition of the PLC automata is represented by one transition in the translation.
Diploma thesis
Multi-agent action planning by model checking in ATL
Author: Micha Altmeyer (May 2007)
Diploma thesis
Identification of phase transitions in AI Planning
benchmarks
Author: Paul Dischinger (May 2007)
Download: (PDF)In many NP-complete decision problems, one can observe so called phase transitions between regions of underconstrained positive and overconstrained negative instances. These transitions can usually be characterized by a problem dependent order parameter. Instances far away from the phase boundary can often be easily shown to be positive or negative instances, respectively. Many of the really hard instances are located near the phase boundary.
In this thesis, phase transitions in planning benchmark problems are investigated and described empirically, as knowledge about phase transitions potentially permits the automatic generation of particularly hard benchmark instances.
Diploma thesis
Planning and learning of autonomous robot behaviour
in difficult terrain
Author: Christian Dornhege (April 2007)
Download: (PDF)The goal of this diploma thesis is to develop an algorithm for exploration on rough terrain containing obstacles as pallets or ramps. In contrast to environments as gras or gravel, which already pose a challenge for a robot's mobility, very steep structures cannot be handled by just one behavior. Moreover it is necessary, that the robot knows about different obstacles and possesses specific skills to negotiate them.
To detect obstacles the robot uses a tilted 2d laser range scanner und builds classified elevation maps online. Based on those maps and a set of skill descriptions behavior maps are built automatically encoding skill routines directly into the map. This enables to plan using classical A* search handling specific obstacles implicitly. Experiments demonstrate a fully autonomous run in a test parcours, while the robot is traversing a pallet and a ramp.
Diploma thesis
Subsumption deterministischer Aktionsschemata
Author: Patrick Eyerich (April 2007)
Download: (PDF)Diploma thesis
Algorithms for partial satisfaction planning
Author: Benjamin Lempp (March 2007)
Download: (PDF)Partial satisfaction planning or over-subscription planning is an extension of the classical planning problem where the agent has the option of only partially satisfying a given goal. To estimate plan quality, the utility provided by the satisfied subgoals is compared to the cost of the plan.
In this thesis, algorithms for partial satisfaction planning are implemented, focusing on the problem of selecting an appropriate set of subgoals. For planning the actual sequence of actions for a given set of subgoals, a classical planner is used as a black box. Several new approaches to partial satisfaction planning are evaluated against each other and against techniques from the literature.
Diploma thesis
Modellierung und Implementierung eines Online-Beraters auf
Basis eines hybriden Recommendersystems am Beispiel Mode
Author: Viara Halatcheva (September 2006)
Diploma thesis
Ein wissensbasierter Benutzermodellierungs-Service für
Sprachdialogsysteme im Automobilbereich
Author: Julia Peltason (July 2006)
Diploma thesis
Learning Road Traffic Control: Towards Practical Traffic
Control Using Policy Gradients
Author: Silvia Richter (July 2006)
Download: (PDF)Diploma thesis
Codierungen paralleler Pläne im Kontext
erfüllbarkeitsbasierter Handlungsplanung
Author: Martin Wehrle (May 2006)
Download: (PDF)Diploma thesis
Erfüllbarkeitsbasierte Handlungsplanung mit temporal erweiterten Zielen
Author: Robert Mattmüller (March 2006)
Download: (PDF)Diploma thesis
An integration of manipulation and action planning
Author: Sebastian Trüg (February 2006)
Download: (PDF)Diploma thesis
Approximationseigenschaften von Transportproblemen in der
Handlungsplanung
Author: Michael Drescher (January 2006)
Download: (PS.GZ)Diploma thesis
Verkehrsflussoptimierung durch Abflugplanung von
Kurzstreckenflügen
Author: Philipp Jarvers (January 2006)
Download: (PDF)Diploma thesis
Pfadplanung unter Unsicherheit
Author: Uwe Zeisberger (April 2005)
Download: (PS.GZ)Diploma thesis
A Skat Player Based on Monte Carlo Simulation
Author: Sebastian Kupferschmid (July 2003)
Download: (PS.GZ)We apply Monte Carlo simulation and alpha-beta search to the game of Skat. The developed Skat-playing program integrates well-known techniques such as move ordering with two new search enhancements. Quasi-symmetry reduction generalizes symmetry reductions, popularized by Ginsberg's Partition Search algorithm, to search states which are "almost equivalent". Adversarial heuristics generalize ideas from single-agent search algorithms like A* to two-player games, leading to guaranteed lower and upper bounds for the score of a game position. Combining these techniques with state-of-the-art tree search algorithms, our program determines the game-theoretical value of a typical Skat hand (with perfect information) in 10 milliseconds.
Diploma thesis
MITRA: Aktionsauswahl im Tischfußball
Author: Moritz Tacke (June 2003)
Download: (PS.GZ)Diploma thesis
Selbstlokalisierung im Roboter-Fußball unter Verwendung
einer omnidirektionalen Kamera
Author: Erik Schulenburg (February 2003)
Download: (PS.GZ)Diploma thesis
Robuste Positionsschätzung mittels Monte-Carlo-Lokalisierung in der
RoboCup-Umgebung
Author: Björn Fischer (July 2002)
Download: (PS.GZ)Diploma thesis
Reinforcement-Lernen beim Roboterfußball
Author: Markus Dietl (April 2002)
Download: (PS.GZ)Diploma thesis
On the Complexity of Planning in Transportation and
Manipulation Domains
Author: Malte Helmert (March 2001)
Download: (PS.GZ)Diploma thesis
Roboterfußball: Multiagentensystem CS Freiburg
Author: Klaus Müller (February 2001)
Download: (PS.GZ)Diploma thesis
Einführung in eine Theorie der ternären RST-Kalküle für
qualitatives räumliches Schließen
Author: Alexander Scivos (October 2000)
Download: (PS.GZ)Diploma thesis
Roboter-Fußball: Pfadplanung in dynamischer Umgebung
Author: Augustinus Topor (April 2000)
Download: (PS.GZ)Diploma thesis
Roboter-Fußball: Zuverlässige Ballerkennung und
Positionsschätzung
Author: Maximilian Thiel (April 2000)
Download: (PS.GZ)Diploma thesis
Aktionsauswahl in dynamischen Umgebungen am Beispiel
Roboter-Fußball
Author: Christian Reetz (April 2000)
Download: (PS.GZ)Diploma thesis
Effiziente Navigation im Lösungsraum eines graphischen
Layout-Problems
Author: Ronny Fehling (April 2000)
Diploma thesis
Synthese von Aufzugssteuerungen mit Hilfe von
constraintbasierten Suchververfahren
Author: Bernhard Seckinger (December 1999)
Download: (PS.GZ)Diploma thesis
Ein Überdeckungsproblem für beliebig dimensionierte
Hyperquader
Author: Jörg Hoffmann (June 1999)
Download: (PS.GZ)Diploma thesis
Roboter-Fußball: Selbstlokalisierung, Weltmodellierung,
Pfadplanung und verhaltensbasierte Kontrolle
Author: Thilo Weigel (April 1999)
Download: (PS.GZ)
