# Diploma theses

Note: This list is currently being revised and does not claim to be complete.

Efficient Determination of Equilibrium Strategies for Extensive Two-Player General-Sum Games with Simultaneous Moves With an Application to General Game Playing
April 2011
Transformation of propositional formulae into linear pseudo-Boolean constraints
February 2011

A linear pseudo-Boolean constraint (LPB) is an expression of the form a_1 l_1+...+a_m l_m ≥ d, where each l_i is a literal (it assumes the value 1 or 0 depending on whether a propositional variable x_i is true or false) and the a_1,...,a_m,d are natural numbers. The formalism can be viewed as a generalisation of a propositional clause. LPBs can be used to represent Boolean functions more compactly than the well-known conjunctive or disjunctive normal forms. E.g., the LPB 2x_1+¯x_2+x_3+x_4≥2 corresponds to the DNF x_1\/(¬ x_2/\ x_3)\/(¬ x_2/\ x_4)\/(x_3/\ x_4). Therefore, in the literature one finds several approaches of generalising techniques from SAT solving to LPBs. All these approahes assume that the LPBs arise naturally from some problem domain.

However, one might ask if it is interesting to transform arbitrary propositional formulae into a set of LPBs, so that one can then benefit from the compact representation during the SAT solving. There is an algorithm solving this problem partially: given a propositional formula representable as a single LPB, the algorithm finds this LPB.

The goal of the project is to implement this algorithm and to conduct some experiments to judge how difficult the transformation is in practice.

Procedural domain control knowledge for temporal planning
October 2010

Domain control knowledge can be used to constrain the valid plans of a planning task in a certain domain. This reduces the search space and allows planning systems to solve tasks that would otherwise be too challenging. One way of defining domain control knowledge is to describe an abstract plan using a procedural (Golog-style) language. Baier proposed such a language for classical planning and showed how it can be exploited by compiling the constraint into the PDDL description of the task.

The aim of this diploma thesis is to carry this method over to temporal planning. The procedural description language should be extended with suitable temporal concepts with a clearly defined semantics. The temporal control programs should then be compiled into the temporal PDDL description of the planning task. This compilation should not only be defined theoretically but also be implemented for an experimental evaluation.

Truthful Feedback for Reputation Mechanisms
May 2009

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.

Simplifying numerical planning problems
April 2009

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.

Application of Pattern Database Heuristics to the Solution of Non-Deterministic Planning Problems
March 2009

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.

Complexity and computation of the h+ heuristic
February 2009

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.

Implementation of a Procedure for Generating Büchi-Automata from LTL Formulae in Isabelle
December 2008

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.

Domain-Specific Optimal Transport- & Route Planning
November 2008

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.

General Game Playing using Automatically Generated Evaluation Functions
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.

Default reasoning in multi-agent systems
July 2008
Generating Random Timed Automata in Uppaal Format
January 2008

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.

Terminologies, defaults, and probabilities: an integrated approach for knowledge representation and reasoning
November 2007
An automata-theoretic heuristic for classical AI planning
July 2007

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.

Basic Action Theories with the same expressive power as ADL with arithmetic functions
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.

Translating PLC Automata into Timed Automata
May 2007

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.

Multi-agent action planning by model checking in ATL
May 2007
Identification of phase transitions in AI Planning benchmarks
May 2007

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.

Planning and learning of autonomous robot behaviour in difficult terrain
April 2007

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.

Subsumption deterministischer Aktionsschemata
April 2007
Algorithms for partial satisfaction planning
March 2007

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.

Modellierung und Implementierung eines Online-Beraters auf Basis eines hybriden Recommendersystems am Beispiel Mode
September 2006
Ein wissensbasierter Benutzermodellierungs-Service für Sprachdialogsysteme im Automobilbereich
July 2006
July 2006
Codierungen paralleler Pläne im Kontext erfüllbarkeitsbasierter Handlungsplanung
May 2006
Erfüllbarkeitsbasierte Handlungsplanung mit temporal erweiterten Zielen
March 2006
An integration of manipulation and action planning
February 2006
Approximationseigenschaften von Transportproblemen in der Handlungsplanung
January 2006
Verkehrsflussoptimierung durch Abflugplanung von Kurzstreckenflügen
January 2006
April 2005
A Skat Player Based on Monte Carlo Simulation
July 2003

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.

MITRA: Aktionsauswahl im Tischfußball
June 2003
Selbstlokalisierung im Roboter-Fußball unter Verwendung einer omnidirektionalen Kamera
February 2003
Robuste Positionsschätzung mittels Monte-Carlo-Lokalisierung in der RoboCup-Umgebung
July 2002
Reinforcement-Lernen beim Roboterfußball
April 2002
On the Complexity of Planning in Transportation and Manipulation Domains
March 2001
Roboterfußball: Multiagentensystem CS Freiburg
February 2001
Einführung in eine Theorie der ternären RST-Kalküle für qualitatives räumliches Schließen
October 2000
April 2000
Roboter-Fußball: Zuverlässige Ballerkennung und Positionsschätzung
April 2000
Aktionsauswahl in dynamischen Umgebungen am Beispiel Roboter-Fußball
April 2000