Proposed topics
Master's thesis
Preferences in spatial planning
A number of board or computer games (like Go, Dame or even Tetris) require the capability for spatial planning. There are, however, fundamental differences between cognitive strategies of human players and computer programs. For instance human players prefer some operations and neglect others. These differences are, however, very important for an understanding of the human planning process.
The objective is to develop, implement, and formally found a cognitively adequate theory of spatial planning and to compare formal approaches with it. The student is expected to have a certain level of expertise in programming and logic as well as an openness to cognitive research questions.
Further information and contact: Marco Ragni
Master's thesis
Reasoning with spatial analogies
The capability to identify similar circumstances and to make conclusions is basically a purely human ability. The degree of this capability (to form analogies) can be measured with intelligence test. A typical task is for instance "Hand is to palm as foot is to ____?"
The objective is to analyze a certain class of mathematical analogies and to develop a computer program to solve tasks of an intelligence test (cf. HAWIE, IST-70, Ravens Advanced Matrices). The student is expected to have a certain level of expertise in programming and logic and an openness to cognitive research questions.
Further information and contact: Marco Ragni
Semester project
Virtual Reality
The objective of this semester project is to extend existing implementations of virtual supermarkets (consisting of shelves with placements in 3D) and to compare human strategies with formal search approaches. This implementation and modeling will be done in Python by using the Vizard Virtual Reality Toolkit (cf. http://worldviz.com/) and be based on sample implementations. Since background knowledge has a significant effect while shopping it should be modeled as well. Your model and implementation will be directly used for psychological investigations and market research.
Prerequisites:
- Good skills in Python programming and sufficient knowledge in C++
- Knowledge about constraint satisfaction problems (as taught in the course Foundation of Artificial Intelligence)
Further information and contact: Marco Ragni
Bachelor's thesis or Master's thesis
Playing Tetris using learning by imitation
Tetris is a famous block game to which many people are addicted. A sequence of blocks falls down unto a playing field. A player has to move the falling block in order to create horizontal lines without gaps as many as possible. Two players can compete against each other by removing N lines at a time and creating N-1 lines of attack for the opponent.
The topic for the paper is about how to make an intelligent agent play Tetris against human players. We want to imitate the strategies of different players and using these when playing against human players.
This topic can be organized as a Bachelor's thesis or a Master's thesis. The prerequisites are
- C++ programming under Linux
- Motivation to invest time and effort
Further information and contact: Dapeng Zhang
Bachelor's thesis, Master's thesis or semester project
Learning with table soccer
Table Soccer Robot KiRo can already win about 90% of games against human players. Challenging real opponents, such as the world-champion, requires extensive study of games played by humans. Therefore, a game recorder KiRe was constructed to record these games. Based on the recorded data, a series of machine learning approaches can be implemented to achieve the following tasks:
- Classifying the actions.
- Calculating the technical statistics of a game.
- Classifying the players.
- Evaluating the quality of the actions.
- Evaluating the skill of a player.
Each topic can be organized as a Bachelor's thesis, Master's thesis, or semester project. The prerequisites for these topics are
- C++ programming under Linux
- Motivation to invest time and effort
Further information and contact: Dapeng Zhang
Bachelor's thesis or semester project
Solving spatio-temporal planning problems
for the temporalized Cardinal Directions calculus
There are several recent approaches to the temporalization of qualitative spatial calculi. The resulting satisfiability problems and solution approaches are related to classical planning problems and can often be encoded in propositional logic. A special property of these problems is that dense and discrete structures play a role in the encoding.
The objective of this work is to encode the temporalized version of the Cardinal Direction calculus as a classical planning problem and either develop a solver or evaluate different heuristic methods such as local search on the resulting problem.
Further information and contact: Marco Ragni
Semester project
SAT based LTL model checking in NuSMV
Model checking is a method to automatically check whether a given system satisfies a given specification. If this is not the case, a counterexample is generated indicating how and why the specification is violated. NuSMV is a symbolic model checking tool for specifications in the logics CTL and LTL. It implements SAT and BDD based algorithms for LTL model checking. Experiments show that the SAT based algorithm is often less efficient than the BDD based one.
The goal of this work is to implement a given modification of the SAT based algorithm in NuSMV (parallel instead of only sequential transitions), possibly gaining an increase in efficiency. The work should be concluded by an empirical evaluation of the implementation in comparison to other approaches.
Prerequisites:
- Good skills in C programming
- Helpful: basic knowledge about planning as satisfiability and about temporal (modal) logics
Further information and contact: Robert Mattmüller
Bachelor's thesis
Generating random Timed Automata
Timed automata are a generalisation of finite automata having, apart from states and alphabet symbols, real-valued variables called clocks as well as integer variables. In contrast to usual automata, the transitions depend on conditions on these variables. Timed automata are a wide-spread formalism for modelling systems. For model checking timed automata, there is the tool Uppaal.
In the context of the AVACS project, the AI group explores heuristic search in the state spaces of timed automata. Therefore we are always interested in hard examples. Note that timed automata with a description of a few dozen lines can easily have state spaces of size 1000000 to 100000000.
The goal of the bachelor thesis is to generate such examples, either ad-hoc or even better, automatically, so that we can analyse systematically the relationship between certain parameters (number of clocks, out-degree of the states, etc.) and the hardness of the search problem and heuristic performance.
Further information and contact: Jan-Georg Smaus
Bachelor's thesis
Transformation of propositional formulae
into linear pseudo-Boolean constraints
A linear pseudo-Boolean constraint (LPB) is an expression of the form a_1 l_1+...+a_m l_m ≥ d, where each l_i is a literal (it assumes the value 1 or 0 depending on whether a propositional variable x_i is true or false) and the a_1,...,a_m,d are natural numbers. The formalism can be viewed as a generalisation of a propositional clause. LPBs can be used to represent Boolean functions more compactly than the well-known conjunctive or disjunctive normal forms. E.g., the LPB 2x_1+¯x_2+x_3+x_4≥2 corresponds to the DNF x_1\/(¬ x_2/\ x_3)\/(¬ x_2/\ x_4)\/(x_3/\ x_4). Therefore, in the literature one finds several approaches of generalising techniques from SAT solving to LPBs. All these approahes assume that the LPBs arise naturally from some problem domain.
However, one might ask if it is interesting to transform arbitrary propositional formulae into a set of LPBs, so that one can then benefit from the compact representation during the SAT solving. There is an algorithm solving this problem partially: given a propositional formula representable as a single LPB, the algorithm finds this LPB.
The goal of the project is to implement this algorithm and to conduct some experiments to judge how difficult the transformation is in practice.
Further information and contact: Jan-Georg Smaus
Ongoing topics
Diploma thesis
Domain-Specific Optimal Planners for Selected
Benchmark Domains from the International Planning Competition
Assigned to: Thomas Keller (since April 2008)
At the biennial International Planning Competition (IPC), domain independent planning systems are compared based on their performance on planning problems from given planning domains. The hardness of the problems often prohibits domain-independent planners from solving all problems from a given domain optimally.
The purpose of this thesis is to investigate optimal plans and plan lengths for some of these problems in order to obtain a basis of comparison for domain-independent planners. Optimal plans should be computed using domain-specific planners for a selection of domains. This will often involve identifying underlying combinatorial optimization problems and solving them using standard combinatorial optimization techniques.
Over the course of this thesis, domains with increasingly complex features, from classical planning to planning with time and resources, should be solved.
Diploma thesis
General Game Playing using Automatically Generated
Evaluation Functions
Assigned to: Tenda Okimoto (since April 2008)
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.
The purpose of this work is to develop a General Game Playing System based on the Java reference player Jocular that uses automatically generated evaluation functions to guide the exploration of the game tree. The inference of the evaluation function given the game description should be based on the fuzzy logic approach used in the Fluxplayer system. Experimenting with other distance heuristics would be interesting as well.
The resulting system should be evaluated against other General Game Playing Systems and possibly against human players on a number of benchmark games available online.
Semester project
Online reputation mechanisms without monetary
rewards
Assigned to: Jens Witkowski (since November 2007)
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 mechanism for a given setting. Up to this point, only monetary rewards have been considered, leading to high costs for the mechanism. In addition -- when lacking altruistic agents or so-called "trusted reports" (reports that are true with high probability) -- multiple lying equilibria exist with some of them having higher payoffs than the honest equilibrium.
This project considers the question whether one can circumvent these drawbacks by paying agents with the reputation information given by other agents for other products or services.
Diploma thesis
Default reasoning in multi-agent systems
Assigned to: Andreas Knab (since November 2007)
Semester project
Preferences in syllogistic reasoning
Assigned to: Oliver Klug (since June 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.
Semester project
Pedestrian localization using acceleration sensors
and RFID
Assigned to: Dali Sun (since January 2007)
Semester project
Development of a Semantic Interpreter for the SRM
Assigned to: Felix Steffenhagen (since November 2006)
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
Are there preferences in relational reasoning
with negated premises? An empirical and computational study
Assigned to: Stefan Schleipen (since August 2006)
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.
