Note: This list is currently being revised and does not claim to be complete.
Semester project
Eliciting honest reputation feedback in a
Markov setting
Author: Jens Witkowski (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.
Semester project
Development of a Semantic Interpreter for the SRM
Author: Felix Steffenhagen (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.
Semester project
Solving Reachability Games using the AO* algorithm
Author: Pascal Bercher (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.
Semester project
Automatic Bidding for the Game of Skat
Author: Thomas Keller (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.
Semester project
Are there preferences in relational reasoning
with negated premises? An empirical and computational study
Author: Stefan Schleipen (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.
Semester project
Endgame Databases in verification games
Author: Tenda Okimoto (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.
Semester project
Goal orderings and landmarks for SAS+ planners
Author: Matthias Westphal (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.
Semester project
Implementation of a Congo Player
Author: Andreas Knab (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.
Semester project
Pedestrian localization using acceleration sensors
and RFID
Author: Dali Sun (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.
Semester project
An ontology-driven interface for constraint solving in qualitative calculi
Author: Oliver Pier (April 2007)
Semester project
Development of a TD(λ)-based Skip-Bo player
Author: Sanja Jahnke (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.
Semester project
A visualization tool simulating mental processes with models in the Arrangement Calculus
Author: Tomoko Kitamura (December 2006)
Semester project
A generic reasoner for qualitative calculi
Author: Zeno Gantner (October 2006)
Semester project
Calculating strong answer sets of DL programs
Author: Andreas Maunz (August 2006)
Download: (PDF)Semester project
Zu ADL gleichausdrucksstarke Basic-Action-Theorien im Situationskalkuel
Author: Patrick Eyerich (June 2006)
Semester project
ATL model checking
Author: Micha Altmeyer (November 2005)
