Thesis projects

The following tags give a quick overview of the type of topic:

• #BSc suitable for a bachelor thesis
• #MSc suitable for a master thesis
• #Intership suitable for an internship
• #application writing a control program to solve a problem on hardware
• #hardware includes building new hardware
• #theory should extend the mathematical model or deliver proofs
• #simulation writing a control program to solve a problem in simulation

Monte-Carlo Tree Search (MCTS) is a best-first search technique that estimates game tree node values based on the results from simulated gameplay. It replaces exhaustive search through the game tree with well founded sampling techniques and has been quite successful in games difficult for computer AI’s like Go and Poker. However, MCTS can not deal with continuous action and state spaces and requires a priori discretization of both to be applicable. The recently developed idea of Tree Learning Search uses techniques from data stream mining to automatically discretize the environment. Although initial results in one-step optimization problems (such as function maximization) have been promising, it is still unclear how to make full use of collected samples in multi-step problems.
Focus: In this project you will investigate how Tree Learning Search can re-use experience in multi-step optimization problems. In a first step you will need to familiarize yourself with Tree Learning Search, its current issues with multi-step problems and some recently described but so far untested information re-use schemes. Any developed/implemented techniques will be evaluated in a combination of abstract and concrete simulated environments or a small robotic system: Squiggle Car and possibly a Texas Hold’em Poker Bot.

For more information, mail Karl Tuyls.

Swarm Intelligence mechanisms depend on environmental information. Since the e-pucks are not able to deposit pheromone (for example, like ants do), they have to depend on different environmental clues. For this project you will use the on-board e-puck camera to detect key environmental locations in order to store information (e.g., directional information).

Inter-robot position detection via IR can be inaccurate depending on many things, such as, light interference, robot positioning, sensor density. To improve position determination additional on-board sensors can be used such as, microphones and RF signals. It’s the student’s job to create a positioning library for the e-puck.

Database system for keeping track of e-puck robots for educational tasks. For more information mail Steven de Jong.

A single e-puck is not equipped to handle large objects. Moreover, even if it moves an object, it does so uncoordinated. The student’s task will be to think of ways (and implement them) to let multiple e-pucks coordinate and cooperate to complete such a task.

Autonomy of and interaction with Telepresence robots. Gesture recognition, navigation based on gestures, navigation based on kinect sensors (e.g., laser scanner).

It is common to assume in our analysis of learning that players have to play a game with each other. Let us turn that assumption upside down: How does the ability to choose your interaction partners influence what you learn from your interaction? This project can be performed empirically and analytically. The empirical approach requires implementing learning algorithms and running them in games with fixed and flexible interaction partners. For the analytical approach, both types of games need to be defined in terms of Game theory in order to establish a formal connection between them.

This project will give you the opportunity to work with the newest addition to our growing list of robots: Bob, the telepresence robot. A telepresence robot is essentially a tele-conferencing system – such as Skype – on wheels. The remote user is able to freely navigate the robot around and engage in conversations with people through a screen and webcam mounted at eye level on a pole. Naturally, in such a setting a consistent and reliable high speed WiFi connection is extremely important. That is why our robot is equipped with multiple high power WiFi cards. In order to keep up with the hardware part we need an intelligent Access Point (AP) handling agent that goes beyond your regular network manager. If – mapping WiFi signal-strengths throughout a building, – learning when to switch between Access Points and – open ended research in the area of wireless network performance sounds interesting to you, please contact Daniel Hennes or Karl Tuyls.

Markets like the New York Stock Exchange are exciting and complex environments for learning. The simulation platform JCAT allows to study different market schemes in competition to another. The grey-box model is perfectly suited for applying evolutionary optimization techniques to the market mechanisms. It promises key insights into market dynamics at the price of technical challenges in the implementation and computational complexity of the simulations.

Large collections of robots have the potential to perform tasks collectively using distributed control algorithms. These algorithms require communication between robots to allow the robots to coordinate their behavior and act as a collective. In this project you will implement an algorithm, i.e. the cardinality algorithm, which allows coordination between a swarm of e-puck robots, but does not require physical environment marks such as pheromones. Instead, this algorithm relies on simple, local, low–bandwidth, direct infrared communication between the e-pucks. The goal is to implement the cardinality algorithm on a physical system of robots and cope with real-life challenges like bandwidth restrictions and interference.

Inspired by the Claytronics project, we adopt a modular robotics domain in order to test multi-agent approaches to programmable matter. In our abstract simulator each robot has a regular hexagon shape. If a robot is directly adjacent to another robot it can rotate around this robot (e.g. using a electromagnetic actuator), while isolated robots remain immobile. In this project you will use neural evolution to devise a distributed control mechanism to achieve the following goals – fully autonomous aggregation of robotic modules, – guiding a group of HEXBots towards a common goal location, and – use a group of HEXBots to resemble a given shape. For further information, please get in touch with Daniel Hennes or Karl Tuyls.

In this project you will investigate the phenomena of “signaling through queue lengths”. Consider the following example: Customers that are new in town and have no prior information about the service quality of restaurants are likely to join longer queues, inferring that the quality must be higher. An equally valid explanation for longer queues are slower service rates and thus an actual decrease in service quality. We are interested in the dynamics of such a multi-agent system where each agent uses reinforcement learning to maximize immediate and future profits. You will develop a simulation environment and analyze the resulting data using methods from dynamical systems theory and evolutionary game theory. For more information please get in touch with Daniel Hennes or Karl Tuyls.

In game theory, network congestion games (or potential games) are well studied but not so much in the multi-agent learning community. A network congestion game is a special case of the general congestion game in which resources are associated with edges or links of a graph or network, strategies are associated with simple paths, and players are associated with units of demand in a network. Players do not traverse along the graph, but rather allocate the entire path from source to destination in each one-shot game. On the one hand, network congestion games add some level of structure to the general congestion game, i.e. the graph/network. However, on the other hand, the problem remains tractable – we are not dealing with a traffic flow optimization problem where e.g. airplanes/cars are simulated to traverse the graph. Network congestion games (as all potential games) are proven to have at least one Nash equilibrium. Though, a stable solution, in many cases Nash equilibria are inefficient in terms of social or global performance. The margin between Nash equilibria performance and social optima in network congestion games has been studied analytically – related work often refer to the “cost of anarchy”. Social optimal solutions are hard or in some cases impossible to compute.
 The research goals for this project are: – Developing a decentralist, robust, multi-agent approach to find solutions to network congestion problems – Presenting a new perspective to network congestion games: the “dual problem”. In the original game, agents try to find minimum cost paths – the dual problem locates agents at the edges of the graph with the ability to disturb (e.g. artificially increase) the cost of a specific link. We can use this modified cost graph as an input for a standard approx. Nash algorithm to find a solution. – Theoretical analysis of the dual problem / proofing an upper bound for the cost of anarchy. If your are interested in hearing more about this project please get in touch with Daniel Hennes or Karl Tuyls.

Find an application for reinforcement learning that exposes the learning progress in an enjoyable way. Many think that reinforcement learning is an abstract concept that is hard to grasp, but it doesn’t need to be that way. There are applications like balancing that make it quite tangible, or projects like that try to visualize learning progress more technically. Consider an iPhone app or a audioization or get even more creative. For a bachelor topic, this project should culminate in a software that allows to playfully explore the dynamics of reinforcement learning (e.g., by comparing behaviors of varying parameters). A master student could additionally build a hardware system.

This project will give you the opportunity to work with the newest addition to our growing list of robots: Bob, the telepresence robot. A telepresence robot is essentially a tele-conferencing system – such as Skype – on wheels. Teleoperation allows the user to “do something from a distance”, while telepresence allows the user to “be present somewhere else”. Your task is to develop and evaluate an interface that gives the remote user the ability to freely navigate the robot around and engage in conversations with people through a screen and webcam mounted at eye level on a pole. Our robot is capable of building a map of its environment and localize itself – this information can be integrated into the teleoperation interface to assist in navigation and provide a more immersive experience to the user. Moreover, on-board distance sensors can be utilized for assisted driving, e.g. emergency stop in front of obstacles. If this is something you are interested in and like to learn more about, please contact Daniel Hennes or Karl Tuyls.

You will investigate the benefit of information in a large multi-agent single-commodity stock market driven by a double auction order matching mechanism. The population of trading agents is divided in groups of different information levels – reaching from uninformed investors to insiders. Uninformed traders have to rely on past and current information only; insiders hold information about the future development of the intrinsic value of a commodity, potentially even multiple trading days into the future. Previous studies have shown that more information does not necessarily lead to higher returns: uninformed traders may beat the market while average informed investors underperform. If your are interested in hearing more about this project please get in touch with Daniel Hennes or Karl Tuyls.

A great deal of research has been performed in the area of finding reinforcement learning algorithms that converge to guaranteed (local) optima. An example algorithm is Counter-Factual Regret Minimization (CFR), which can compute a Nash equilibrium in a 2-player, zero-sum, imperfect information game. The most notable result of CFR has been the development of very strong 2-player Limit Texas Hold’em Poker bots by the University of Alberta. Another interesting algorithm is the Continuous-Action Learning Automaton (CALA), which can optimize a continuous reward function in a stateless game, e.g. games such as the Public Goods Game. The aim of this project is to combine these two approaches such that we arrive at a convergent algorithm for continuous actions. Ideally, the convergence of the algorithm should be empirically shown (an application could be a smaller version of 2-player No-Limit Poker, e.g. No-Limit Kuhn Poker) as well as analytically proven. For more information, contact Steven de Jong (see above). The project will be guided by him and by Kurt Driessens.

Interaction networks are a hot topic nowadays. Many interesting phenomena, such as the emergence of cooperation and the spreading of opinions or infections, have been shown to be heavily influenced by the manner in which individuals interact. Most research has been performed in virtual networks (e.g. scale-free networks). In this project, which may partially be implemented on the e-puck robots, we will investigate how being embodied (i.e. able to move in physical space) influences the spreading of infectious diseases. For example, infected people generally stay at home, which may slow down the spreading of their infection. For more information, contact Steven de Jong (see above).

Predator-prey interactions are a driving force behind many intelligent behaviors found in nature, such as flocking and teamwork. Researchers motivate the emergence of human cooperation by pointing to our recent past, i.e. we started to hunt larger prey animals, which was only possible if we had some sort of social awareness in addition to being cautious (after all, hunting a mammoth is dangerous). Models have been proposed that can explain why humans cooperate. In this project, we will apply these models to the scenario they are originally said to come from. Multiple independent predators with limited capabilities (i.e. e-pucks or simulated agents) need to track down, disable, and transport a large prey. Does including models of human social awareness help them? For more information, contact Steven de Jong (see above).

Context: A problem of significant practical relevance is the so-called task assignment problem (TAP), that is, the problem of assigning tasks to executing agents so that certain performance criteria are fulfilled such as minimization of overall execution time, minimization of overall costs and maximization of the average execution quality. The TAP is non-trivial (actually, it is NP-hard in general), and challenging instantiations of the TAP can be found in numerous application domains, ranging from industrial manufacturing to networked computing.
Focus:This project deals with the question how task assignment can be automated in applications where the executing agents are computational entities such as software programs or robots. Thereby the project focuses on TAP scenarios which show the following basic characteristics: the tasks can be divided into sub-tasks; the (sub-)tasks differ in the demands their completion raises; and the agents differ in their abilities to complete (sub-)tasks. The goal is to develop, implement and experimentally investigate a flexible and robust solution for this type of TAP scenarios which follows the idea that the executing agents autonomously decide and agree on the assignment of the (sub-)tasks on the basis bilateral negotiations and contracts. The project has available approaches to automated task assignment as its starting point and builds on related state-of-the-art work from the fields of artificial intelligence and multi-agent systems.
Further Information: Please get in touch with Gerhard Weiss.

Context: The progressive establishment of e-commerce, e-business, e-trading and e-markets has led to a great practical interest in automated price negotiations, that is, in the automated negotiation of prices for goods among electronic buyers (being interested in low prices) and electronic sellers (being interested in high prices). This, in turn, has led to various theoretical and empirical research efforts worldwide, all aiming at a better understanding of automated price negotiation.
Focus:: A still unanswered question is what the best strategy is for a buyer or seller to change his price offer during the negotiation process. For instance, a possible strategy for a buyer (seller) is to increase (decrease) his offer proportional to the remaining negotiation time. Several basic strategies have been proposed in the literature. However, most of them were only investigated in simplified scenarios (e.g., in scenarios where there is only one buyer and one seller). This project aims at systematically exploring through simulation studies how these strategies perform in more complex and realistic scenarios.
Basic requirements:: Good programming skills; interest in experimental research (simulation studies).
Further Information: Please get in touch with Gerhard Weiss.

Context: While standard artificial intelligent opponents in games “reason” about the game and the goals they want to obtain, the research community has started to recognize the information treasure as left by humans on the internet in their free time.  This project will not go as far as Amazon’s Mechanical Turk, that asks people to solve problems left by other people, it will aim at using logs generated by human expertise to imitate the human decision process.
Focus: In this project you will investigate if it is possible to construct conceptually simple game-playing bots that make use of freely available logs of human games to generate reasonable behavior. This project will consist of building a knowledge base from existing game-logs and constructing a system that uses nearest neighbor techniques and relational distances to select amongst those decisions that are most appropriate for the encountered game state.
Basic requirements: Good programming skills; familiarity with data-base systems is a plus
Further Information: Please get in touch with Kurt Driessens.