Summer Term 2015

Arne Kemper

September 23, 2015, 3:15 pm, F0.530

Convergence of synchronous, autonomous robots with limited visibility

The problem of gathering of synchronous and autonomous robots is studied well under various restrictions. But a lot of models make quite liberal assumptions about what information a robot can gain about the positions of other robots, so that a realization of robots with such a visibility model is potentially very expensive. Therefore it is interesting to examine whether robots can still gather on a single point even if their visibility model is further restricted. As an example, this talk deals with the model introduced by Ando, Suzuki and Yamashita with additional restictions on visibility and shows that convergence is still possible, while gathering is impossible to guarantee in the restricted model.

(Final presentation Bachelor’s thesis)

Menghsuan Sam Pan
Massachusetts Institute of Technology

August 26, 2015, 2:00 pm, F1.110

Reinforcement Learning for Service Composers in Static and Dynamic OTF markets

Our work attempts to understand the efficiency of composers in OTF markets which compose of simple service providers, complex service composer, and consumers. A composer bundles together a number of simple services as complex services, and receives an aggregated feedbacks from consumers just like in multi-arm bandit problems. The composer then uses reinforcement learning with various learning and choosing strategies to disaggregate the feedbacks and achieve better composer efficiency which is modeled as deviation from the ideal service bundle. Our result has allowed us to gain insights in markets with static and dynamic simple service provider behaviors.

Johannes Schaefer

August 12, 2015, 2:00 pm, F0.530

Prototypical Implementation of Disaster Management Support through Mobile Ad Hoc Networks on Android-based Smartphones

In disaster scenarios it is crucial for rescue forces to quickly gain an understanding of what is happening on site. People close to the disaster can provide information in the form of pictures, videos etc., but congestion or failure of the cell phone infrastructure can hinder this. An ad hoc network between participating phones, which would route the information to areas with functioning internet connectivity could help in such cases.
In this master thesis an Android app is to be implemented that provides this functionality. Since Android does not support WiFi ad hoc it has to be emulated using Wi-Fi Direct or temporary access points, which poses interesting questions to tackle.

(Introductory presentation Master’s thesis)

Georg Stilow

August 5, 2015, 2:00 pm, F0.530

Mobile agents in networks: Analysis of hotspots

Hotspots are situations where many agents visit one node of a network. These networks could for example represent street maps or computer networks, whereas the agents would be cars or messages. To get a better understanding of how and where those hotspots occur in a given network, the mobile agents can be simulated by using various movement methods. The movement method must be selected corresponding to the movement which is expected in reality because this creates the largest difference of where the hotspots will be. As a rough overview this talk will show the expected hotspot distribution of mobile agents with basic movement methods in a square network.

(Final presentation Bachelor’s thesis, talk in German)

Kacper Wardega
The Ohio State University

July 29, 2015, 2:00 pm, F0.530

A Simulation-Based Approach to Studying OTF Market Scenarios

In this talk we consider a simulation based approach to examine the behavior of simple service providers participating in an On-The-Fly market.  We will model the behavior of the simple service providers by treating them as players in a repeated game where the consumer of the composed service and the composer of services act in a predictable fashion.  Players are assigned ratings that are based on observed quality of previously composed services.  The change in popularity of interesting player strategies will be examined under varying market conditions.  We will then draw conclusions about the influence of market scenario on simple service provider behavior. Additionally, we will discuss a method for simulating the game in a time/memory efficient manner.

Björn Feldkord

July 15, 2015, 2:00 pm, F0.530

A Game of Online Algorithms

We introduce concepts to combine the game theoretical approach of analyzing selfish behavior with the competitive analysis applied in online scenarios.  We use our concept of online selfish agents to describe the behavior of agents who minimize their private costs over a period of time steps where they do not know parts of the input in advance. The performance of these online players are compared to players who are oblivious of the time aspect as well as to an offline algorithm which optimizes the social costs. The concepts are illustrated on a simplified variant of Multilevel Network Games and we show tight bounds for the performance measures introduced in this game.

Damian Kutzias

July 15, 2015, 2:30 pm, F0.530

The Impact of Friendship Graph Evolution on the Convergence of Network Creation Games

Imagine network creation games where either the peers of a fixed network can swap positions with neighbouring peers (Swap Game) or buy and maintain edges (Buy Game). The project group DynaSearch investigated several Swap Games with dynamic communication interests with respect to different aspects, e.g. convergence, convergence speed and the Price of Anarchy. Unfortunately it was shown, that many of the trivial upper bounds become tight for general network graphs.
This talk is about further approaches to extend the results of the project group, e.g. searching for special graph classes or characteristics. Furthermore, sequences of communication interest changes will be applied to Buy Games. Some new techniques like artificial communication interests will be introduced which may help to achieve good outcomes here.

(Introductory presentation Master’s thesis)

Max Drees

July 15, 2015, 3:00 pm, F0.530

Existence of Nash equilibria in restricted classes of bandwidth allocation games

Since bandwidth allocation games do not have pure Nash equilibria in general, we take a closer look at restricted classes of these games to determine how much we have to deviate from the general case in order to ensure the existence of stable states. Since bandwidth allocation games represent a generalization of weighted utility games with player-specific utility functions, we also consider existing results and how they relate to our model.

Christoph Robbert

July 8, 2015, 2:00 pm, F0.530

Error Correction for Swarm Segregation Using Checker Robots

In this talk I will show how to enhance the segregation of two swarms using gossip communication. Ding and Hamann already proposed a method but there exists situations unsolvable by their method. I will add a third swarm of checker robots to resolve these situations. The talk will show four different implementations of these checker robots. Later on the performance of these four checker robots is evaluated under different conditions. At the end we will have a look at the influence of unreliable communication to segregation process.

(Final presentation Master’s thesis)

Markus Benter

July 1, 2015, 2:00 pm, F0.530

Multi-Dimensional Range Queries on Dimension Independent Networks using Hilbert Curves and Shortcut Graphs

First, we introduce the definition of "Dimension Independent Networks". This property allows a Peer-to-Peer system to deal with multi-dimensional objects of arbitrary dimensions without any changes to the network topology. We argue that this property is desirable in practice if the maximal dimensionality of the objects to be added cannot be predicted prior to the deployment of the system. This means that an object of arbitrary dimension can be added to the system at any point of time. As queries, we consider multi-attribute range queries, i.e., an upper bound and a lower bound for each of the attributes (dimensions) is defined. The solution is the complete set of objects fulfilling the constraints. For this kind of queries, we show first results of the novel idea to combine the Hilbert space filling curve for dimension reduction with shortcut graphs to gain a speed-up.

Matthias Feldotto

June 24, 2015, 2:00 pm, F0.530

Approximation in the Model of Coevolutionary Opinion Formation Games

In this talk we study a game-theoretic model of opinion formation in social networks. Each player has an intrinsic and an expressed opinion. The objective function is the minimization of the own deviation between intrinsic and expressed value as well as the difference between the own expressed opinion compared to the ones of the friends. We look at different modifications of this model and present recent results from literature regarding the existence of equilibria and their quality given by the Price of Anarchy. Furthermore, we present our first results for approximate equilibria in this setting. We give first bounds on the approximation factor and show strategies to generate these states.

Pavel Podlipyan

June 17, 2015, 2:00 pm, F0.530

Almost collisionless gathering

In the following talk we are going to consider the gathering of the point like robots with limited viewing range on Euclidean plane in the continuous time model. We are going to consider modification of Go-To-The-Center algorithm due to Ando, Suzuki, and Yamashita. We will enhance the common unit disc graph model by the Gabriel graph.
In the first part of the talk we are going to present the model and runtime analysis results of our modified algorithm.  Then we are going to show the simulation results that will lead us to the second part of the talk.  The second part will be dedicated to current analysis of specific emergent properties of our algorithm that we obtained due to performed modifications. Namely, we will show our progress on the proof of the fact that the robot using modified algorithm gather without collisions from almost every initial configuration.

Sören Riechers

June 17, 2015, 2:30 pm, F0.530

Extensions for Scheduling Models

In my talk, I will present two interesting extensions to our scheduling models.
The first part of the talk will be about an extension to scheduling shared continuous resources. In the extension, a number of jobs with a certain resource requirement is given. They have to be scheduled on a number of m processors in order to minimize the makespan. Hence, in contrast to the original model, allocation of the jobs to the processors is not yet fixed. For the extended problem, I show NP-hardness and give a simple approximation algorithm. This model can further be extended by grouping the jobs into classes where we are interested in the sum of completion times of theses classes instead of the overall makespan.
The second part of my talk will consider speed scaling with speed limits. For the single processor case, we gave an exact polynomial algorithm for a quite huge class of natural continuous speed limit functions such as piecewise low-degree polynomials. It would be interesting to extend this to the problem setting with multiple processors and migration. I will give a short insight about prior work on speed scaling on multiple processors (without speed limits) which could be used as a starting point.

Angelo Fanelli
Centre national de la recherche scientifique (CNRS)

June 10, 2015, 2:00 pm, F0.530

Nash Stability in Fractional Hedonic Games

Coalition formation games are games in which coalitions are created as a result of the strategic interactions that occur among agents. We consider fractional hedonic games, that is, coalition formation games in which the happiness of each agent in a coalition is the average value she ascribes to its members. We adopt Nash stable outcomes, where no agent can improve her utility by unilaterally changing her own coalition, as the target solution concept and present their existence, complexity and performance for games played on general and specific graph topologies.

Andreas Cord-Landwehr

June 3, 2015, 2:00 pm, F0.530

Locality in Network Creation Games

We investigate a non-cooperative game-theoretic model for the formation of communication networks by selfish agents. Each agent aims for a central position at minimum cost for creating edges. In particular, the general model (Fabrikant et al., PODC'03) became popular for studying the structure of the Internet or social networks. Despite its significance, locality in this game was first studied only recently (Bilo et al., SPAA'14), where a worst case locality model was presented, which came with a high efficiency loss in terms of quality of equilibria. Our main contribution is a new and more optimistic view on locality: agents are limited in their knowledge and actions to their local view ranges, but can probe different strategies and finally choose the best. We study the influence of our locality notion on the hardness of computing best responses, convergence to equilibria, and quality of equilibria. Moreover, we compare the strength of local versus non-local strategy-changes. Our results address the gap between the original model and the worst case locality variant. On the bright side, our efficiency results are in line with observations from the original model, yet we have a non- constant lower bound on the price of anarchy.

Daniel Jung

June 3, 2015, 2:30 pm, F0.530

Gathering in Linear Time for Swarms of Robots Suffering Under a Limited Technical Infrastructure

We consider the following variant of the two dimensional gathering problem for swarms of robots: Initially, the robots form a closed chain on a two dimensional grid, where neighboring robots of the chain need to be positioned on neighboring cells of the grid. Each robot can only see its next left and right neighbors on the chain within a constant distance along the chain. Based on its state and relative positions of its chain-neighbors (no ids, no compass, no communication allowed), it decides where to move in the next step. We assume the fully synchronous FSYNC model. For this problem, we present a gathering algorithm which needs linear time. This result generalizes a result from Kutylowski et al., where an open chain with specified endpoints is considered. The endpoints are used as starting points of so called runs, performed by the algorithm.

Heiko Hamann

May 13, 2015, 2:00 pm, F0.530

Collective Patty-Cake or: "Backe, backe Kuchen"

What if programming would be as easy as baking a cake? In swarm robotics there is a chance to achieve that. In general, however, we are facing the fundamental challenge of how to find links between the so-called microscopic level (robot controller) and the macroscopic level (overall swarm behavior). For the example of binary collective decision-making systems, we can describe the robot controller as a minimalistic finite state machine (micro) and the swarm behavior with a simple population model (macro). A key idea is to give up the programmability of our robots which is anyway necessary in certain applications, such as nanorobotics. Now we can define a set of robot behaviors as basis functions ("ingredients of our cake") and formulate the swarm programming problem as a constraint least squares problem ("baking of the cake"). 

Manuel Malatyali

May 6, 2015, 2:00 pm, F0.530

Online Top-k-Position Monitoring of Distributed Data Streams

Consider n nodes connected to a single coordinator. Each node receives an individual online data stream of numbers and, at any point in time, the coordinator has to know the k nodes currently observing the largest values, for a given k between 1 and n. We design and analyze an algorithm that solves this problem while bounding the amount of messages exchanged between the nodes and the coordinator. Our algorithm employs the idea of using filters which, intuitively speaking, leads to few messages to be sent, if the new input is "similar" to the previous ones. The algorithm uses a number of messages that is on expectation by a factor of O((log Δ + k) log n) larger than that of an offline algorithm that sets filters in an optimal way, where Δ is upper bounded by the largest value observed by any node.

Nils Kothe

April 29, 2015, 2:00 pm, F0.530

Multilevel network games with constant distances in Highspeed Networks

A generalization of a multilevel network game was examined, in which nodes from an undirected graph can improve their distance to each other by individually deciding to connect to a high-speed network $S$, which forms a clique on another level of the graph. In the original multilevel network game, the weight of the edges within the clique was zero, but it was generalized to $\beta > 0$. Each node wants to minimize its private cost, which is either the sum of all shortest paths to each other node (Sum-Game) or the longest shortest path (Max-Game), while using the nodes in $S$ as shortcuts when appropriate. Additionaly, each node that is directly connected to the high-speed network $S$ has to pay a fee of  $\alpha > 0$. The ideas behind most proofs from the old model were taken to the new one, which resulted in various proofs concerning complexity, price of anarchy and the existence of equilibria for $\beta > 0$. These theoretical results were complemented with an experimental evaluation. 

(Final presentation Bachelor’s thesis, talk in German)

Alexander Weinhold

April 29, 2015, 2:30 pm, F0.530

Implementation of BEECLUST on Thymio II swarm robots: Towards
adaptiveness for different light conditions

Beeclust is an algorithm for aggregation of swarm robots in global
illuminance optima without communication, inspired by the behaviour of
honeybees in temperature gradient fields. This thesis implements the
algorithm on the educational robot "Thymio II" by the Aseba project. It
covers a hardware extension for the robots to achieve sensing of visible
light, building of a suitable arena and test environment and a practical
enhancement to decrease the need for manual adaption to the experiment

(Final presentation Master’s thesis)

Sascha Brandt

April 22, 2015, 2:00 pm, F0.530

Progressive Blue Surfels on the GPU

Progressive Blue Surfels is an algorithm for approximating complex parts of a virtual 3D scene using a set of points. These points are sorted in a way, that each prefix of the list of surfels provides a good visual representation of the approximated part. Although the Blue Surfels can be computed efficiently and independently of the underlying scene geometry, the algorithm still requires an obstructive amount of preprocessing time, especially for large scenes. In this talk I present my approach on computing Progressive Blue Surfel approximations for three-dimensional scenes in parallel on the GPU. Early experiments showed that the method is not only faster, it also produces a better quality of the blue noise distribution.

Alexander Mäcker

April 15, 2015, 2:00 pm, F0.530

Non-Preemptive Scheduling with Setup Times

The usage of reconfigurable machines (particularly FPGAs) is becoming common practice in modern compute centers. In order to provide the functionality to process a job, such machines require a configuration process to take place beforehand. We capture this fact in a theoretical model in which we assume that a set of $n$ jobs has to be processed non-preemptively on a set of $m$ parallel identical machines. The set of jobs is partitioned into $k$ disjoint classes and a machine requires a fixed setup time whenever switching from processing jobs of one class to jobs of another class.
In my talk, I will present an approximation algorithm that computes a schedule with a makespan that is by a factor of at most $3/2 + \epsilon$ worse than the optimal makespan and it runs in time polynomial in $n,m$ and $k$.

Shouwei Li

April 15, 2015, 2:30 pm, F0.530

Circuit Value Problem with bounded genus 1

We firstly introduce a data structure called PQ-tree, which can be used to the representations of a set $U$ in which various subsets of $U$ occur consecutively. Algorithms using PQ-trees are then given which test for the graph planarity problem. Finally we extend this algorithms for a more general problem, the circuit value problem with bounded genus 1.

Karlson Pfannschmidt

April 8, 2015, 3:30 pm, F0.530

Solving the aggregated bandits problem

In this thesis we introduce the aggregated bandits problem as a generalization of the multi-armed bandit problem. In this setting the player is only allowed to pick subsets of of bandits. Furthermore, only an aggregation of the rewards is revealed to the player. We show that for the deterministic aggregated bandits problem, determining the optimal order of subsets is NP-hard in general. For average aggregated rewards solving the optimal order and learning all of the bandits can be done in linear amount of steps. In the case of minimum aggregated rewards, we prove that learning all of the bandits needs exponentially many steps in the worst case. Finally, the MaxPeriodSolver algorithm is proposed which combines these techniques to solve the special case of randomly generated rewards. A series of experiments was conducted in which the MaxPeriodSolver is compared to benchmark policies and the results show a promising performance of the algorithm in this setting.

(Final presentation Master’s thesis)