Master's theses

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

Daniel Saier
Symmetries and Symmetry Detection in Constraint Satisfaction
September 2016

Many constraint satisfaction problems exhibit symmetries, which provide an op- portunity to make the search for solutions more efficient. Existing techniques for symmetry breaking all have a common drawback, though. They require a manual specification of the symmetries. In this thesis, we present a novel approach for detecting symmetries automatically. The basis for our algorithm is a database of commonly used constraints and their properties. This allows us to efficiently find symmetries of the problem by analyzing the structure of its constraints. In particular, we use this information to construct a graph whose automorphisms correspond to symmetries of the problem’s variables. The same information also enables us to deduce symmetries of the problem’s values. Our implementation simplifies the practical application of symmetry breaking sig- nificantly. We evaluated it on a number of different problems and found that it can reliably find symmetries — often even more than a human modeller would specify. Furthermore, it is fast enough that investing time into symmetry detection actually pays off.

Jan Metzger
Automatische Generierung vom optimierten Klassifikationsdialogen aus Ontologien
February 2016
Matthias Frorath
Identification and Modeling of Human Strategies in the Spatial Planning Task Rush Hour
October 2015
Matthias Hengel
Räumliche und zeitliche Constraints in beschreibungslogischen Wissensbasen
December 2014

For the meaningful usage of temporal or spatial knowledge in a description logic knowledge base, properties of spatial and temporal relations like disjointness of relations must be considered. One way to achieve this is by using a concrete domain for the representation of spatial or temporal knowledge. This approach requires adapted reasoning algorithms, as the knowledge about the concrete domain is not represented in the knowledge base itself. Possible concrete domains also have to fulfil some requirements, especially for reasoning with general TBoxes.

In this thesis, we analyse the practicability of reasoning with general TBoxes in ALC(D) knowledge bases containing constraint-based temporal or spatial knowledge integrated using concrete domains. Similar to the case of pure description logics, optimizations of the tableau algorithm used for reasoning are inevitable to achieve a behaviour which allows the use in practice. Therefore, we adapt optimization techniques for tableau-based reasoners to our case. To evaluate this approach, we analyse reasoning in such knowledge bases empirically using randomly generated knowledge bases and concepts.

Serdar Oguz Ata
Partial Order Reduction for Timed Systems
August 2014
Thorsten Engesser
An Implementation of an Epistemic Planning System
April 2014
Philipp Lerche
Fast Incremental Planning under Partial Observability
March 2014
André Doser
Extending UCT with Game-Theoretic Concepts
December 2013
Florian Geißer
General Game Playing under Uncertainty
November 2013
Manuela Ortlieb
Pattern Database Heuristics for Nondeterministic Planning Problems under Partial Observability
November 2012
Yusra Alkhazraji
Partial Order Reduction for Automated Planning
April 2012
Andreas Hertle
Design and Implementation of an Object-Oriented Planning Language
November 2011
Download: (PDF)

Semantic attachments improve the applicability of symbolic planning systems to real world problems, by incorporation low-level algorithms directly into the high-level reasoning process. The Temporal Fast Downward (TFD) planning system implements this concept by providing a generic interface for data exchange between its internal state and external modules. However, due to its generic nature, the interface is inefficient and cumbersome to use. In this Thesis we present the Object-oriented Planning Language. We demonstrate how a domain-specific module interface can be generated from a planning task described in OPL. We show, how the domain-specific interface is integrated into the planning system, without compromising the domain-independence of the TFD. We conduct experiments to show compare the efficiency of our novel approach to the current TFD module interface.

Dapeng Zhang
Action Selection and Action Control for Playing Table Soccer Using Markov Decision Processes
April 2005
Download: (PS.GZ)