Semester projects

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

Jens Witkowski
Eliciting honest reputation feedback in a Markov setting
August 2008
Download: (PDF)

Online reputation mechanisms need honest feedback to function effectively. Self-interested agents report the truth only when explicit rewards offset the potential gains obtained from lying. Feedback payment schemes (monetary rewards for submitted feedback) can make truth-telling a Nash equilibrium based on the correlation between the reports of different buyers.

Jurca and Faltings use Automated Mechanism Design to compute the budget-optimal adverse selection mechanism for a given setting. Up to this point, though, only settings in which the product's quality is fixed (i.e. does not change) have been considered.

This project extends the model to allow for the product's quality (its type) to change over time. To model the change, a Markov Process is introduced and as the type is observed with noise, the resulting structure is equivalent to a hidden Markov model (HMM) with selfish agents observing the signals. Eventually, the mechanism shall be evaluated both in theory and empirically.

Felix Steffenhagen
Development of a Semantic Interpreter for the SRM
May 2008
Download: (PDF)

The cognitive model SRM is based on so-called primitive relations such as right of, left of, in front of and behind. More complex relations of everyday language can often be decomposed into such primitive relations. The concept of definability of a relation over a language and a universe of discourse is essential in this context.

The objective of this work is to first analyze the decomposability of ordering relations over a discrete spatial structure and then extend the SRM by a processing unit called a Semantic Interpreter.

Pascal Bercher
Solving Reachability Games using the AO* algorithm
March 2008
Download: (PDF)

Reachability Games are two player games played on graphs where each node belongs to one of the two players who is to move in that node. The aim of player 1 is to force player 2 into one out of a set of designated goal states in any possible run of the game, the aim of player 2 is to prevent this. Both players have complete information about the current state.

The purpose of this work is to develop an AO* based algorithm for the solution of Reachability Games and strategy synthesis. Besides AO* search itself (graph search vs. tree search) the definition of the heuristic evaluation function used to guide the AO* search, in particular its automatic deduction from the game description, should be in the focus of this work. Initially, a monotonicity abstraction such as the one used in the FF planning system should be experimented with, which can later serve as a basis for comparison to other heuristics.

Finally, the algorithm should be implemented and compared to an existing implementation of the proof-number search algorithm on the basis of suitable benchmark problems.

Thomas Keller
Automatic Bidding for the Game of Skat
December 2007
Download: (PDF)

In recent years, researchers started to study the game of Skat. The strength of existing Skat playing programs is definitely the card play phase. The bidding phase, however, has been treated quite poorly so far. This is a severe drawback since bidding abilities influence the overall playing performance drastically.

In this semester project, a powerful bidding engine based on a k-nearest neighbor algorithm is presented.

Oliver Klug
Preferences in syllogistic reasoning
November 2007

Syllogisms are a kind of logical argument in which a conclusion is inferred from two premises of a certain form (quantified expressions). The syllogism are at the core of deductive reasoning, where facts are determined by combining existing statements, in contrast to inductive reasoning where facts are determined by repeated observations. Human reasoning differs significantly from formal approaches, w.r.t errors.

The objective of this work is to first analyze a result by Chater and Oaksford by means of Euler circles, to develop a computational model, and to explain the preference "rules" by a cognitive complexity measure.

Stefan Schleipen
Spatial Reasoning with Negation
November 2007
Download: (PDF)

In the past, psychological research on human deduction has mostly focused on positive expressions. However, stating what is not true constitutes a significant part of human communication. Over finite relational calculi, there is an equivalence between disjunctions of positive expressions and negated expressions.

The objective of this work is to first prove the existence of preferences in human processing of negative expressions, and then formalize and implement them within the SRM.

Tenda Okimoto
Endgame Databases in verification games
August 2007
Download: (PDF)

The automatic verification and analysis of complex systems serves the purpose of automatically detecting erros in safety critical systems such as cars, airplanes, and trains at an early stage of development. Several such verification tasks can be reduced to solving (i.e. determining the winner and a winning strategy) a certain kind of two-person zero-sum games. Such a solution can be achieved using appropriate AI game solving algorithms such as alpha beta search, AO* search, or proof number search.

The goal of this work is to investigate the applicability of endgame databases, which have proven helpful in solving games such as chess, to the class of games considered here. This investigation comprises the development of an algorithm for automatically generating endgame databases, its implementation, and its empirical evaluation.

Matthias Westphal
Goal orderings and landmarks for SAS+ planners
July 2007
Download: (PDF)

Many planning tasks exhibit dependencies between (implicit or explicit) subgoals. For example, towers in the classical Blocksworld domain should always be constructed from bottom to top, and packages in the classical Logistics domain must first be transported to an airport if they shall be delivered to a different city. Such dependencies can be formalized as (temporal) ordering relations called goal orderings (if they involve explicit subgoals) or ordered landmarks (if they involve implicit subgoals). This work applies existing techniques for the computation of landmarks in STRIPS problems to the multi-valued SAS+ formalism. The algorithms from the literature are extended and exploited within the Fast Downward planning system.

Andreas Knab
Implementation of a Congo Player
May 2007
Download: (PDF)

This semester project deals with the implementation of an algorithm for the chess-like game Congo. The basis of this algorithm forms an alpha-beta search, accelerated with some search enhancements like move ordering and transposition tables. The semester project also empirically investigates some evaluation functions for Congo positions.

Dali Sun
Pedestrian localization using acceleration sensors and RFID
May 2007
Download: (PDF)

When an area is struck by disaster, rescue operations must commence immediately. In such scenarios, localizing rescue personnel is of great importance. Because infrastructure in disaster areas is often unusable, rescue personnel must receive current information about the environment fast. Therefore, constructing a reasonable (not necessarily complete or fully correct) map of the environment is very useful. To achieve this objective, many people (or robots) can traverse the area to collect trajectory information. This semester project considers the problem of collecting and integrating such trajectory information, especially in situations where GPS signals or comparable data are unavailable.

Oliver Pier
An ontology-driven interface for constraint solving in qualitative calculi
April 2007
Sanja Jahnke
Development of a TD(λ)-based Skip-Bo player
February 2007
Download: (PDF)

This Semester project deals with Skip-Bo, a card game for two to six players and the implementation of different Skip-Bo agents. We implemented several rule based agents and used the temporal difference approach to implement two learning agents. This method adjusts the parameters of an evaluation function to approximate the expected long-time utility of a state. The developed agents can be evaluated online at http://www.td-skip-bo.de.vu.

Tomoko Kitamura
A visualization tool simulating mental processes with models in the Arrangement Calculus
December 2006
Zeno Gantner
A generic reasoner for qualitative calculi
October 2006
Andreas Maunz
Calculating strong answer sets of DL programs
August 2006
Download: (PDF)
Zu ADL gleichausdrucksstarke Basic-Action-Theorien im Situationskalkuel
June 2006
Micha Altmeyer
ATL model checking
November 2005