Uni-Logo

Bachelor's theses

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

Ilia Dobrusin
Implementation of a Domain-Specific Language for Controlling an Athropomorphic Robot Head
October 2016
Jens Schindler
Design und Entwurf einer Roboters zur Manipulation von Objekten in einer kompetitiven Umgebung
March 2016
Herrmann Ritzenthaler
Multi-robot simulation for decision making and strategy for Sick Robot Day 2016
March 2016
The Sick Robot Day competition poses many interesting challenges for an autonomous robot, especially in the fields of navigation, perception and manipulation. In this project various strategies for placing cubes in the competition arena are to be evaluated. The robot can place cubes anywhere on the field. Placing cubes in empty goal fields increase the score. Furthermore cubes can block paths and hinder naviagation for robots of both teams. The simulation of the competition is expected to discover good strategies for the competition.
Janosch Deurer
Applied Implicitly Coordinated Epistemic Plans
July 2015
Jonas Thiem
Counter-Example Guided Abstraction Refinement for POND Task Unsolvability
March 2015
Julian Schwarz
Implementing and Testing the LUG Heuristic in a Nondeterministic Planner
February 2015
David Speck
Observation Landmarks in Partially Observable Nondeterministic Planning
February 2015
Dominik Winterer
Partial Order Reduction for Fully Observable Nondeterministic Planning
January 2015
Sascha Oßwald
Symmetry Reduction in Nondeterministic Planning
July 2014
Erik Wacker
Determining Minimal Information Necessary for POND Plan Existence
March 2014
Jochen Kempfle
Implementing robot capability maps
March 2014

In robotics the workspace for a manipulator is a subset of 6-DoF space. It is implicitly given by the robot's kinematics. Knowledge about the workspace is necessary when reasoning about a robot's actions as in planning. Usually it can be queried by computing inverse kinematics. Alternatively capability maps precompute a manipulator's workspace and store the 6-Dof structure efficiently.

The goal of this work is to implement such capability maps. This consists of the algorithm for computing the space efficient 6-Dof representation and the querying of capability maps. Extensions like combining different capability maps can be added. The implementation will be done in C++.

Patrick Ebner
Implementation of the Labelled Uncertainty Graph for Nondeterministic Planning under Partial Observability
August 2013
Josua Scherzinger
The Landmark-Cut Heuristic for Nondeterministic Planning
August 2013
Andreas Kuhner
Influence of the Sample Size of Approximate Belief States on the Performance of a General Game Player under Imperfect Information
October 2012
Martin Goth
Implementation of the NDP Algorithm for Strong Cyclic Planning in Fast Downward
September 2012
Daniel Brand
General Game Playing with PROST
April 2012
Download: (PDF)

This work gives the probabilistic planning system PROST the functionality to solve single player games in general game playing. Therefore, a communication with the game master, i.e., the server managing the game flow, must be established. Initially, the game master sends the rules to every player encoded in the game description language (GDL). As PROST was developed as a probablistic planning system, it supports only RDDL. For this reason, the rules must be converted from GDL to RDDL, which is the main focus of this work. The aim of this conversion is to create valid RDDL files which can be used with existing PROST-functionality. As PROST only supports a fragment of RDDL, it is necessary to also enhance the PROST planner in order to be able to make reasonable plans for single player games. Finally, the results of this work are analysed empirically and problems and limitations of PROST and RDDL are presented.

Tilman Thiry
Application of the Merge-and-Shrink-Heuristic to Nondeterministic Planning
December 2011

This work is concerned with a subproblem of the problem of finding strong and strong cyclic plans for non-deterministic planning problems via the approach of planning as heuristic search, more precisely, (L)AO* search guided by domain-independent merge-and-shrink (M&S) heuristics. Strong and strong cyclic plans guarantee that a goal state is reached in a finite number of steps and that dead-ends are avoided, respectively, independently of the nondeterministic outcomes. The focus of this work is on the automatic generation of suitable heuristics to guide the search. To that end, we adapt the merge-and-shrink approach by Helmert, Haslum, and Hoffmann (2007).

Florian Geißer
Tableaux-Verfahren zur Lösung qualitativer CSP
April 2011
André Doser
Revisionsoperationen auf qualitativen Constraintnetzen
April 2011
Philipp Lerche
Kompakte Routenbeschreibungen: Eine Evaluation verschiedener Algorithmen
April 2011
Tim Schulte
Berechnung handhabbarer Klassen für qualitative räumliche Formalismen
April 2011
Silvan Sievers
Extension of a Planning System for the Solution of Single Person Games
October 2009
Download: (PDF)

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.

Besides two-player and multi-player games, the games that have to played successfully at the AAAI General Game Playing Competition also include single-player games. Due to algorithmic reasons, it is preferable to develop different modules handling the different kinds of games. Since single-player games described in the Game Description Language (GDL), in which the competition games are encoded, are essentially classical planning problems, it is possible to solve them using according algorithms.

The goal of this thesis was to integrate state-of-the-art algorithms and heuristics used in classical planning into a General Game Playing system currently under development. The resulting system should be evaluated using some of the benchmark games available online.

Diana Hille
An analysis of SGPlan
September 2009
Download: (PDF)

The purpose of this work is to give a detailed analysis of SGPlan. SGPlan achieved good results in the last international planning competitions (in particular at the 4th and 5th IPC). The source code of the planner wasn't accessible until now, but was made available for free use within the 6th IPC. Using this code, the achievement of the results and the algorithmic background of SGPlan shall be examined, because up until now the code was not sufficiently explained through the publicly available descriptions.

Jendrik Seipp
Fluent Merging for classical planning problems
September 2009
Download: (PDF)

Fluent merging is a reformulation technique for classical planning problems that can be applied automatically or semi-automatically. The reformulation strives to transform a planning task into a representation that allows a planning algorithm to find solutions more efficiently or to find solutions of better quality. This work introduces different approaches for fluent merging and evaluates them within state-of-the-art planning systems.

Jonas Sternisko
Influence of the Finite Domain Representation on the performance of planning systems
September 2009
Download: (PDF)

In contrast to the common propositional representation of planning tasks, where each state variable can only take the values true and false, the Finite Domain Representation allows arbitrary finite domains. This permits a much more natural formalization of the planning tasks. In addition, it explicitly states certain mutexes, which can be exploited by planning systems to solve the task more efficiently. The objective of this thesis is to examine the influence of the representation on the performance of several planning systems empirically.

Manuela Ortlieb
Automatic Pattern Selection for Pattern Database Heuristics in Non-deterministic Planning
September 2009
Download: (PDF)

This work is concerned with a subproblem of the problem of finding strong plans for non-deterministic planning problems via 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 automatic selection of approproate patterns through heuristic search in the space of pattern collections, alalogous to the work by Haslum et al. in the context of deterministic planning. The aim of this work is the implementation and evaluation of a pattern selection algorithm.

Johannes Aldinger
Solving General Games by Heuristic Search
April 2009
Download: (PDF)

A General Game Playing System is a system 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.

In this work, a player based on the General Game Playing System Jocular was developed that uses an automatically generated evaluation function derived from the FF heuristic known from research in action planning. The evaluation function generalizes the FF heuristic in that it is designed for two-player games with numeric preferences over terminal states.

Florian Pommerening
Norms and space: Integrating qualitative rules in the situation calculus
November 2008
David Goergen
Compact encodings of monotonic Boolean functions
May 2008

A Boolean function is monotonic if it can be represented by a combinatorial circuit of AND- and OR-gates. Monotonic Boolean functions play an important role in complexity theory and naturally occur in a number of applications.

The goal of this project is to compute a compact representation for monotonic Boolean functions given as circuits or propositional logic programs, i.e., to find a circuit with a small number of gates which computes the given function. The resulting algorithm shall then be applied to the problem of computing relaxation heuristics for AI planning tasks, and to the problem of line of sight computation in discrete 2D worlds.