# Semester projects

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

**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.

**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.

**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.

**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.

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.

**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.

**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.

**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.

**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.

**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.

**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.