Sommersemester 2016

Anastasios Getsopulos

September 30, 2016, 2:30 pm, F1.110

Modular and distributed robotic systems for autonomous shaping of plants

In this thesis we influenced the architectural of a plant by creating a symbiotic relationship between robotic nodes and plants. In the first part, the existing robotic node was improved. Eight instances of the smarter and more stable iteration of previously existing robotic node was used to build a decision wall for stimulating the direction of growth of the plant. A decentralized calibration algorithm was designed for the behavior of the robotic nodes. The algorithm works based on information provided by Wi-Fi and the light sensors mounted on the nodes. Results of our experiments show that we successfully laid a solid foundation for future works considering collaboration between robots and plants.

(Final Presentation Master's Thesis)

Stanislaw Eppinger

September 28, 2016, 2:00 pm, FU.511 (Mozart)

Approximated Photon Mapping for real-time Global Illumination

Indirect lighting plays a significant part in rendering photo realistic images. It is mostly computed offline because its computation is expensive. While this is acceptable for cases like movies, real-time applications like modern computer games need a fast computation of indirect lighting. It is often only allowed to take a few milliseconds. This calls for potent hardware as well as sophisticated real-time algorithms.
This work introduces a novel algorithm which outsources the computation of diffuse indirect lighting to an approximation of the original scene and evaluates it only locally for the visible part of the scene. The camera shoots photons into the approximated scene which in turn gather incoming indirect light. These photons are sampled in screen space and are incorporated in the final rendering step to simulate a one bounce diffuse indirect lighting effect. No further data structures nor texture atlases are needed. The idea is that an approximation of the original scene suffices to compute an approximation of indirect light which is still believable for the user.

(Final Presentation Master's Thesis)

Hassan Elsharkawi

September 28, 2016, 2:30 pm, FU.511 (Mozart)

Florabot: a prototype of smart rods system for building self-organized structures

Self-organized structures are one of the members of the flora-robotica society. One way to realize such structures is using robotics rods and nodes, where the nodes are used to mechanically connect the rods together. In this context, self-organized (self-assembly and self-repairing) means that the rods themselves know the desired structure and accordingly signal the user about the need to connect/disconnect other rods at specific positions to build that structure. Additionally, they can detect any faults while or after building (e.g., incorrectly-inserted or missing rods), and ask the user to correct those faults.
In the last couple of months, I worked on realizing the first prototype of such robotic rods. Taking into consideration the potential use-cases for the system with scalability and user-friendliness in mind. This included the selection of the processing unit, the required sensors, the communication between the rods, and how they communicate with the user. On top of that, a hardware abstraction layer was implemented to enable the users of the system to experiment different behaviors and algorithms without caring about the hardware details.
Furthermore, the more complex the structure is, the more the rods we need and vice versa. Since it is a swarm-robotics system, all of them run an identical program. Programming them one by one is impractical at all for the user, specially for large swarm systems. An alternative approach that saves the required time and effort independently of the number of rods to be programmed was adopted.
In my final talk, I am going to present the first prototype of those smart rods, introduce my vision for the future work, and show a video demonstration of a self-organized square out of those rods.

(Final Presentation Master's Thesis)

Henrik Heine

September 28, 2016, 3:00 pm, FU.511 (Mozart)

On demand terrain generation for predefined street networks

Virtual terrains are an important factor of many modern 3D applications. Their size increases constantly and therefore the development time for such a terrain increases also. In order to reduce the needed time, several different algorithms have been developed.
This thesis proposes a new algorithm, which is able to create a detailed terrain solely based on a predefined street network. The idea behind this approach is that the street layout already tells a lot about the surrounding terrain. Therefore it is possible to derive natural features, like rivers and mountains, from the curvature of a given network. Furthermore the absence of a street is also a good hint for certain features. In order to increase the performance of such a system, the final terrain is not generated all at once, but parts of it are generated on demand, for example when the user comes closer to a certain region.
Terrain generation based on a given street network is especially useful for the simulation of advanced driver assistance systems and for racing games. Those fields require a realistic terrain, which focuses on the street layout.

(Final Presentation Master's Thesis)

Project Group: DisDaS

September 21, 2016, 2:00 pm, F1.110

Results of the Project Group DisDas

We consider a setting in which there are $n$ distributed sensors observing data streams, a server computing aggregation functions over the streams and clients requesting information about sensors' data from the server. Sensors can communicate to the server by single cast messages while the server is allowed to send broadcast messages to clients and sensors. Concerning this scenario, we present our results regarding 1) the aggregation and 2) the scheduling of answers to requests.

For 1) we consider a model in which sensors are partitioned into two sets.  The data streams define the membership of a sensor to one of the sets so that the partition may change over time. The server is asked to continuosly maintain an $\epsilon$-approximation of the size of the sets with probability $1-\delta$.

We propose an algorithm and analyze its communication complexity, with our main results: 1. If nodes can switch sets in both directions, an algorithm is proposed using $\mathcal{O} \left (w \cdot \frac{\ln\left ( w/(1-\sqrt{1-\delta})\right )}{\varepsilon^2}\right )$ messages under a certain  restriction. 2. If nodes only switch in one common direction, we can drop the restriction.

Concerning 2) we consider a scheduling problem in which the server has static information about each sensor. Clients request subsets of these information by specifying intervals of the associated sensors. In each step, the server can broadcast one answer consisting of an interval of sensors. The goal is to maximize the number of requests satisfied before their respective deadlines, where a request is satisfied if answered and requested interval are ''similar enough'' according to the Jaccard measure.

Our results are: 1. Many results for broadcast scheduling are applicable if the decision is based on comparing all possible candidate intervals. 2. In simulations, we studied alternatives to 1. and show that they perform better in terms of runtime or quality. 3. For intervals containing only one item, we look at speed augmented deterministic online algorithms for minimizing the maximum tardiness.  Our main results are that no $2$-speed algorithm can be $1$-competitive and $\Theta(\sqrt{n})$ speed (alternatively $\Theta(\sqrt{\sigma})$, where $\sigma$ denotes the largest slack) is necessary and sufficient for Earliest Deadline First to be $1$-competitive.

Peter Kling
Simon Fraser University

September 14, 2016, 10:00 am, F1.110

Fast Distributed Consensus – Recent & Future Results

Consider a system of $n$ nodes in a distributed system, each having one of $k$ opinions. A fundamental problem is to find a fast, simple, and robust distributed protocol that reaches *consensus*, a state where all nodes have the same opinion. Bonus points are granted if the protocol preserves the initial *plurality*, the opinion with the highest support among the nodes. In this talk, I survey recent results for this problem and highlight some ongoing work and open problems.
We will see simple yet highly efficient plurality consensus protocols inspired from biological settings that achieve plurality consensus on the complete graph in time $O(k \log n)$ [Becchetti et al.; SODA'15]. Our own work [ICALP'16] improves this to $O(\log k \log\log n)$. For arbitrary graphs, we have a protocol based on ideas from load balancing and rapid mixing [ESA'16], which improves upon a related result by Alistarh et al. [PODC'15]. A large part of the talk will focus on ongoing work and open problems in this research area.

Martin Ziegler
KAIST School of Computing

September 14, 2016, 11:00 am, F1.110

Computational Complexity of (Functions on) Compact Metric Spaces

We promote the theory of computational complexity on metric spaces: as natural common generalization of (i) the classical discrete setting of integers, binary strings, graphs etc. as well as of (ii) the bit-complexity theory on real numbers and functions according to Friedman, Ko (1982ff), Cook, Braverman et al.; as (iii) resource-bounded refinement of the theories of computability on, and representations of, continuous universes by Pour-El&Richards (1989) and Weihrauch (1993ff); and as (iv) computational perspective on quantitative concepts from classical Analysis: Our main results relate (i.e. upper and lower bound) Kolmogorov's entropy of a compact metric space $X$ polynomially to the uniform relativized complexity of approximating various families of continuous functions on $X$. The upper bounds are attained by carefully crafted oracles and bit-cost analyses of algorithms perusing them. They all employ the same representation (i.e. encoding, as infinite binary sequences, of the elements) of such spaces, which thus may be of own interest. The lower bounds adapt adversary arguments from unit-cost Information-Based Complexity to the bit model. They extend to, and indicate perhaps surprising limitations even of, encodings via binary string functions (rather than sequences) as introduced by Kawamura&Cook (SToC'2010,\S3.4). These insights offer some guidance towards suitable notions of complexity for higher types.

(joint work with Akitoshi Kawamura and Florian Steinberg)

Jörn Koepe

September 8, 2016, 2:00 pm, F1.110

Price-Based Allocation Games

We proposed price based allocation games. Price based allocation games are a new kind of congestion games, in which every player has to buy resources in order to use them. Besides using the resource, the delay a player is receiving by a resources also is depending on the money spend on them. The more money is spent on one resource by one player, the less delay this player receives. Furthermore, the delay is not only dependent on the own money, but also on the money which was spent by the other players. Furthermore, we looked at strategy classes. A strategy class is a union of every strategy which uses the same resources. Strategy classes are independent, if they do not share any resources. We proved, that games with independent strategy classes always possesses a pure Nash equilibrium and analyze this equilibrium.

Marcin Bienkowski
University of Wroclaw

August 10, 2016, 2:00 pm, F1.110

Online Algorithms for Multi-Level Aggregation

In the Multi-Level Aggregation Problem (MLAP), requests arrive at the nodes of an edge-weighted tree T, and have to be served eventually.  A service is defined as a subtree X of T that contains its root. This subtree X serves all requests that are pending in the nodes of X, and the cost of this service is equal to the total weight of X. Each request also incurs waiting cost between its arrival and service times. The objective is to minimize the total waiting cost of all requests plus the total cost of all service subtrees.  Aggregation problem for trees of arbitrary depth arise in multicasting, sensor networks, communication in organization hierarchies, and in supply-chain management. The instances of MLAP associated with these applications are naturally online, in the sense that aggregation decisions need to be made without information about future requests.
Constant-competitive online algorithms are known for MLAP with one or two levels. However, it has been open whether there exist constant competitive online algorithms for trees of depth more than 2. Addressing this open problem, we give the first constant competitive online algorithm for networks of arbitrary (fixed) number of levels. The competitive ratio is O(D^4 2^D), where D is the depth of T. The algorithm works for arbitrary waiting cost functions, including the variant with deadlines.
Joint work with Martin Böhm, Jarosław Byrka, Marek Chrobak, Christoph Dürr, Lukáš Folwarczný, Łukasz Jeż, Jiří Sgall, Nguyen Kim Thang and Pavel Veselý, to appear at ESA 2016.

Johnny Jacobs
University of Rochester

August 3, 2016, 2:00 pm, F1.110

Aggregate Multi-Armed Bandits

The Multi-Armed Bandit (MAB) is a class of problems in machine learning in which every round the player must choose one of several bandits to recieve a reward from, with the goal of maximizing total reward over a number of rounds. The process which each bandit uses to generate rewards is unknown to the player, and can only be approximated through experimentation. The difficulty of the task is further increased in the aggregate MAB scenario, where a group of bandits is chosen, but only a single reward, some function of the group's rewards, is oberserved. In this talk, classic MAB algorithms are empirically evaluated for the aggregate MAB scenario and the results and implications discussed.

Zahra Nouri

July 27, 2016, 2:00 pm, F1.110

Collective Decision Making on Braided Compounds with Long-term Adaptation

Investigation of interaction between artificial and real life is one of the interesting aspects of artificial life research. The bio-hybrid system in the flora robotica project develops a high level integration between robots and natural plants in order to boost the effectiveness in their collaboration. This system aims to influence the natural growth process of the plant to produce desired architectural artifacts as a result. The artificial life in this project is a braid of intelligent strips containing sensors, actuators, processors, and communication units. The strips have local communication with their neighbors, thus there exists a decentralized communication in the swarm. It is necessary to develop a collective decision-making mechanism whereby the swarm reaches a consensus on the most reasonable decision among various options in the swarm. While the collective decision-making process iterates, the swarm learns how to make more accurate and faster decisions based on long-term adaptation. In this thesis, we simulate the strips equipped with ambient light sensors to measure the distribution of light on the structure. Afterwards, a binary decision making mechanism will be adapted.

(Introductory presentation Master's thesis)

Dennis Komm
ETH Zürich

July 13, 2016, 2:00 pm, F1.110

Information Content of Online Problems

In online computation, the input of a computational problem is revealed gradually such that parts of the definite output need to be given with incomplete information.  Using competitive analysis, one usually studies the resulting loss in solution quality.  In this talk, another aspect is investigated, namely how a potentially critical part of the input can be both identified and quantified.  Therefore, we study so called online algorithms with advice, i.e., online algorithms that obtain additional information about the input at hand, which allows them to increase their solution quality.  Our goal is to give bounds on the information both necessary and sufficient in order to obtain a given competitive ratio.  Our results have also impact on randomized online computation.

Subhashree Radhakrishnan
Amrita University

July 13, 2016, 3:00 pm, F1.110

Developing Intelligent Control and Automated Applications in Bio-hybrid Systems

The main objective of the project is to build automated bio-hybrid systems with plants and robotic nodes and implement some intelligent control algorithms to extrapolate some data of plant motion and its characteristics. My talk would be broadly spread out on 4 major topics namely the automatic garden, plant automation, the minibox setup and image processing. Automatic Garden would deal with experiment to automate the various processes required to nurture the growth of plants such as light, water and soil temperature remotely. This is implemented with the help of raspberry pi and RF based wireless power outlets. The Plant automation experiment would deal with the simulation of  the phenomenon of phototropism using mechanical artifacts and embedded processors. The minibox setup will give an overview of two important experiments that were conducted with climber plants, hanging rods and robotic node. The important findings and the processes used in these experiments would be analyzed. Finally the Image Processing section would give insights into developing intelligent algorithms for processing the images obtained in the minibox bio-hybrid experiments, in order to make interpretations of plant growth and influence the decision making of plants. An algorithm is proposed for tip detection and motion tracking of the tip.

Daniel Jung

June 29, 2016, 1:30 pm, F1.310

Local gathering of a swarm of point-shaped robots on a two-dimensional grid

In our paper, we solve the local gathering problem of a swarm of n indistinguishable, point-shaped robots on a two- dimensional grid in asymptotically optimal time O(n) in the fully synchronous FSYNC time model. Given an arbitrarily distributed (yet connected) swarm of robots, the gathering problem on the grid is to locate all robots within a 2x2-sized area that is not known beforehand. Two robots are connected if they are vertical or horizontal neighbors on the grid. The locality constraint means that no global control, no compass, no global communication and only local vision is available; hence, a robot can see its grid neighbors only up to a constant L_1-distance, which also limits its movements. A robot can move to one of its eight neighboring grid cells and if two or more robots move to the same location they are merged to be only one robot. The locality constraint is the significant challenging issue here, since robot movements must not harm the (only globally checkable) swarm connectivity. For solving the gathering problem, we provide a synchronous algorithm -- executed by every robot -- which ensures that robots merge without breaking the swarm connectivity. In our model, robots can obtain a special state, which marks such a robot to be performing specfic connectivity preserving movements in order to allow later merge operations of the swarm. Compared to the grid, for gathering in the Euclidean plane for the same robot and time model the best known upper bound is O(n^2).

André Graute

June 29, 2016, 2:00 pm, F1.110

Gathering a Closed Chain of Robots on a Grid

In this Bachelor thesis, we will implement the algorithm, which is known from "Gathering of a Closed Chain of Robots on a Grid" by Sebastian Abshoff, Andreas Cord-Landwehr, Matthias Fischer, Daniel Jung und Friedhelm Meyer auf der Heide (19. October 2015, arxiv.org/abs/1510.05454). Some of the found inaccuracies in the description of the algorithm will be improved and corrected. Afterwards we will analyze the algorithm with the goal to find a new measure of progress for the gathering process. Therefore, we are going to measure and investigate the inner area, the length of the border, the diameter, the height and the width of the robot chain. We will see that the inner area and the length of the border of the robot chain are no appropriate measurement of the gathering progress because both can sink and climb even above the initial value during the gathering process. In contrast to this the height, the width and the diameter are appropriate measurements of the gathering process. All three cannot been increased during the gathering process and we can show that the height and the width will decrease after at least $15+n/2$ rounds of the gathering process. We can show also that the diameter will be decreased after at least $n*15+n/2$ rounds of the gathering process. We will also show that a robot chain containing $n$ robots, with a square or rectangular arrangement and a maximum difference in height and width of one numerator, will have a higher duration of the gathering process, than any other robot chain containing $n$ robots. So this chains will form the upper bound of the gathering process. We will also investigate certain aspects of the gathering algorithm such as runs and merge operations. In this we can improve the upper bound of rounds during the gathering process to $15*(n/2+\lceil n/8\rceil )+n$ rounds. According to this we will show that we are able to start at least four progress pairs along a mergeless chain in each interval. We will also look at the parameter we measured and investigate which aspects of the algorithm are influencing these parameters. We will see that merge operations can influence all of the measured parameters where runs are not able to make any changes to the height or width of the robot chain. Runs can only make changes to the inner area, the length of the border or the diameter.

Matthias Feldotto

June 29, 2016, 2:30 pm, F1.110

Properties of Cost Sharing Games with Shapley Cost Sharing

In this talk, we further investigate the computation of approximate pure Nash equilibria in cost sharing games. We consider weighted congestion games with polynomial cost functions for the resources. Compared to standard (weighted) congestion games, the cost functions are only given for the whole resource, but not for each player. A cost sharing method is then used to determine the costs of each player. Next to the trivial proportional cost sharing where each player has to pay a share proportional to her weight, the Shapley cost sharing method is the most accepted one since each player has to pay her marginal contribution to the overall costs.
Here, we discuss different properties of this game class for the Shapley cost sharing method which are needed for the computation of approximate equilibria. Namely, we look at sub games and the partial potential function in these games as well as at the stretch of the potential function. Both properties are required in the analyis of the computation.

Björn Feldkord

June 22, 2016, 1:30 pm, F1.310

Strategic Online Facility Location

We consider a strategic variant of the online facility location problem. Given is a graph in which each node serves two roles: it is a strategic client stating requests as well as a potential location for a facility. In each time step one client has to state a request which induces private costs equal to the distance to the closest facility. Before serving, the clients may collectively decide to open new facilities, sharing the corresponding price. Instead of optimizing the global costs, each client acts selfishly. The prices of new facilities vary between nodes and also change over time, but are always bounded by some fixed value α . Both the requests as well as the facility prices are given by an online sequence and are not known in advance.

Shouwei Li

June 22, 2016, 2:00 pm, F1.110

Parameterised Maximum Matching Problem

Whether an NC algorithm exists for Maximum Matching Problem is still open. In this talk, we will evaluate this problem from another perspective: we show that if the cardinality of a maximum matching for an undirected graph bounded to a constant number $k$, then the problem can be solved in {$\mathcal{O}(f(k)\cdot(\log^c n))$} time with polynomial number of processors, where $<n,k>$ is the instance of the problem, $k$ is the parameter. $f$ is an arbitrary computable function, and $c$ is a constant independent of $n$ and $k$.

Pavel Podlipyan

June 22, 2016, 2:30 pm, F1.110

Towards almost collisionless gathering

We consider the gathering problem and some other coordination problems of a swarm of robots. The robots are assumed to have no extent, live in the one or two dimensional Euclidean space, and have bounded viewing range.  In contrast to many related results, we assume a continuous time model: robots continuously adapt their speed (assuming a fixed speed limit) and direction, dependent on their continuously observed neighborhood. We first analyze a continuous version of the Go-To-The-Center algorithm due to Ando, Suzuki, and Yamashita. Then we present and evaluate a variant which performs Go-To-The-Center considering only the neighbors of a robots w.r.t. the Gabriel subgraph of the visibility graph.
Long time ago we have shown that in 2D modification still correctly executes gathering in time $O(n^2)$, but has severe impact on the behavior of the algorithm. Lately we have shown that in 1D the modification still correctly executes gathering in time $\Theta(n)$. We also have shown  that in 1D the gathering is collisionless from any initial configuration. In 2D we conjecture that, for almost every initial configuration, no early collisions happen. Our conjecture is supported with simulations results. After that we formalize the problems that stand on our way towards collisionless gathering in 2D and consider possible solutions.

Sascha Brandt

June 15, 2016, 1:30 pm, F1.310

Kinetic Visibility Sampling

In my talk, I will present my first approaches to a datastructure to be used int the rendering of highly dynamic high-speed drive-throughs. The basic idea is to have kinetic datastructure that can uphold visibility information in a ever changing environment. After a short recap of the research context of on-the-fly rendering for driver assistance systems and a short introduction to kinetic datastructures, I will present my model for the idea of kinetic visibility sampling and discuss the inherent challenges that need to be solved.

Manuel Malatyali

June 15, 2016, 2:00 pm, F1.110

Smoothed Competitive Analysis for Dynamic Distributed Streams

Smoothed Analysis was introduced by Spielman and Teng as a generalization of worst-case and average-case analysis. The idea is to randomly perturb the input instance and analyze the (expected) costs of the perturbed instances. Becchetti et al. proposed smoothed competitive analysis, i.e. the input sequence generated by an adversary is perturbed. The cost of an algorithm is compared instance-wise to an optimal algorithm which knows the whole input sequence in advance. In this talk we propose a technique to upper bound the smoothed ratio under certain conditions. We observed that our technique can be applied to a variety of algorithms in the area of dynamic distributed streams.

Sören Riechers

June 15, 2016, 2:30 pm, F1.110

New insights on scheduling on shared continuous resources

In my talk, I consider a variant of scheduling on shared continuous resources. Here, 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. For the extended problem, I present hardness results and give a simple approximation algorithm with approximation factor 1+1/(m-1)+o(1). Afterwards, I focus on two different extensions of the model, where my goal is to merge these two extensions in the future.
(1) In the first extension, the jobs are grouped into classes where we are interested in the average flow time of theses classes instead of the overall makespan. If release times are individual, one can show a lower bound of O(1/n^(1/3)) on the approximation factor unless P=NP. It seems simple to achieve an optimal solution if we allow our algorithm to use twice the resource and 2m+1 instead of m processors. For the case where all release times are 0, I present how to achieve a [2*(1+2/(m-2))+o(1)]-approximation algorithm.
(2) In the second extension, we allow jobs to have a length additionally to the resource requirement interpreted as size or height. Hence, if a job has length 3 and resource requirement 0.7, this implies that the job can never use more than a resource of 0.7. However, it can be split into more than 3 time steps summing up to an overall resource usage of 3*0.7=2.1, where each time step is allowed to use a resource of at most 0.7. I present insights on where this modification makes our problem more difficult and how to cope with these problems.

Mostafa Wahby

June 8, 2016, 2:00 pm, F1.110

Self-organizing bio-hybrid collaboration of robots and natural plants

The self-organizing bio-hybrid collaboration of robots and natural plants allows for a variety of interesting applications. As an example we investigate how robots can be used to control the growth and motion of a natural plant, using LEDs to provide stimuli. We follow an evolutionary robotics approach where task performance is determined by monitoring the plant's reaction. First, we do initial plant experiments with simple, predetermined controllers. Then we use image sampling data as a model of the dynamics of the plant tip xy position. Second, we use this approach to evolve robot controllers in simulation. The task is to make the plant approach three predetermined, distinct points in an xy-plane. Finally, we test the evolved controllers in real plant experiments and find that we cross the reality gap successfully. We shortly describe how we have extended from plant tip to many points on the plant, for a model of the plant stem dynamics. Future work will extend to two-axes image sampling for a 3-d approach.

Mohammad Divband Soorati

June 8, 2016, 2:30 pm, F1.110

Robot Self-Assembly as Adaptive Growth Process: Collective Selection of Seed Position and Self-Organizing Tree-Structures

Autonomous self-assembly allows to create structures and scaffolds on demand and automatically. The desired structure may be predetermined or alternatively it is the result of an artificial growth process that adapts to environmental features and to the intermediate structure itself. In a self-organizing and decentralized control approach the robots interact only locally and form the structure collectively. Designing a complete approach that allows the robot group to collectively decide on where to start the self-assembly, that adapts at runtime to environmental conditions, and that guarantees the structural stability is challenging and does not yet exist. We present an approach to self-assembly inspired by diffusion-limited aggregation that generates an adaptive structure reacting to environmental conditions in an artificial growth process. During a preparatory stage the robots collectively decide where to start the self-assembly also depending on environmental conditions. In the actual self-assembly stage, the robots create tree-like structures that grow towards light. We report the results of robot self-assembly experiments with 50 Kilobots. Our results demonstrate how an adaptive growth process can be implemented in robots. We explain how our approach will be extended to a 3-d growth process and how robot self-assembly as an open-ended adaptive growth process opens up a multiplicity of future opportunities.

Syam Gullipalli

June 1, 2016, 2:00 pm, F1.110

Decision Making in a Bio-hybrid Autonomous Robotic System (Cyborg Plant)

"Someone's sitting in the shade today because someone planted a tree a long time ago." - Warren Buffet
Plants play vital role in preserving earth's ecology. We consume plants in our daily life in many forms; from basic needs like food, shelter, medicines, clothing to industrial needs like construction, furniture, fuel, and many more. Shaping plants as artifacts while they live, instead of cutting large trees for timber can improve the earth's ecology. Making artifacts from plants has been in practice by forcing and pruning the plants. The existing methods do not save the plants as they require the plants to be cut and smoothed at the end to make the final artifact. The focus of this thesis is to make a prototype of robotic nodes that stimulate and sense plants, and experiment to make simple shapes ('S' shape for example) out of living plants to achieve consensus between plants.
The physiological responses of plants to different stimuli like light, touch, etc., could be used to shape plants as artifacts. The robotic nodes that stimulate and sense plants could help building synergies of plant robot society. The results of this thesis are testbeds for the vision of florarobotica. Florarobotica is an EU funded research project, aims at investigating symbiotic relationship between robots and plants, and exploring the potentials of plant-robot hybrids to produce architectural artifacts.

(Final presentation Master's thesis)

Henrik Heine

Mai 25, 2016, 2:00 pm, F1.110

On demand terrain generation for predefined street networks

Procedural terrain generation has become an important part in virtual worlds. The size of those worlds has become so huge, that it is no longer possible to create them by hand. Therefor developers had to come up with algorithms to automatically generate huge worlds.
The objective of the proposed thesis is to generate terrain, based on already defined street networks.
Therefor the main task of this thesis is the development of different data structures and algorithms, which will be used to analyze a given street network in order to generate a suitable terrain around it. The generated environment is only indirectly defined by the given network and should look as realistic as possible. Furthermore it is not generated in all detail, but instead more details will be generated if the camera comes closer. In order to achieve such a natural looking terrain it is not sufficient to interpolate the terrain between the given streets. As a result a more complex approach is needed, which will take more information of the street into account.

(Introductory presentation Master's thesis)

Alexander Mäcker

Mai 25, 2016, 2:30 pm, F1.110

Cost-efficient Scheduling with Bounded Tardiness on Machines from the Cloud

We consider a scheduling problem where machines need to be rented from the cloud in order to process jobs. There are two types of machines available which can be rented for machine-type dependent prices and for arbitrary durations. However, a machine-type dependent setup time is required before a machine is available for processing. Jobs arrive online over time, have machine-type dependent sizes and have individual deadlines. The objective is to rent machines and schedule jobs so as to minimize the rental cost without violating a given bound on the maximal allowed tardiness of jobs. In the talk, we consider lower and upper bounds on the competitiveness of online algorithms for this problem.

Kuai Shen
Köln

Mai 18, 2016, 2:00 pm, F1.110

Myrmecophilia: ant mimicry as a post-biological model for resilient technology

“Nature creates similarities. One need only think of mimicry. The highest capacity for producing similarities, however, is man’s. His gift of seeing resemblances is nothing other than a rudiment of the powerful compulsion in former times to become and behave like something else. Perhaps there is none of his higher functions in which his mimetic faculty does not play a decisive role.” – Walter Benjamin

Ant mimicry seems to be a recurrent phenomenon in the nature of insects, particularly in certain species of insect individuals, which mimic the appearance, behaviour and chemical communication of ants. From an artistic perspective, this evolutionary system of mimicry suggests that imitation as well as deceit could be considered an immanent social force more than a strategy for survival. Can we interconnect such recurrences of mimicry in nature to technologically-driven experiences as well as to human interactions?
The relationship between human technology and biological organisms plays an important role in the creation of new ecosystems and the transformation of old ones. It is essential to investigate these multi-scalar relationships between organisms and artefacts, which reverberate and have the power to affect not only natural and technological environments, but virtual social encounters where human and nonhuman can mutually coexist. Moreover, the relations between the imposing artificial will of humans and the unforeseeable morphogenesis of nature should be rather approached from the immanent naturalist perspective of the doctrine of the similar, that is, forces of imitation which recover the importance of relationships in the creation of the resilient networks.
Ant mimicry has indeed a strong influence in the materialization of media art practices and in the development of artificial intelligence, too. Deceiving and acting as something or someone else is an experience we humans can enact with the aid of technology in the age of networks: a transformative phenomena which breaks the boundaries delimiting the autopoiesis of the artificial and the organic and creates opportunities of inclusion, hybridization and collaboration.

Mouns R. Husan Almarrani

Mai 11, 2016, 2:00 pm, F1.110

2D shapes to increase the image quality in point-based rendering systems

One of the big challenges in the 3-D computer graphics is the rendering of highly complex scenes. To make the rendering of such scenes more efficient its complexity must be reduced. For this purpose approximation techniques are used. One of these techniques is the point-based technique, that simplifies the complex geometry by replacing it with sample points.
In this thesis a new approximation process was developed, implemented and evaluated. It is based on a point-based technique (PBS: Progressive-Blue-Surfels by Claudius Jaehn). The main goal was to improve the image quality compare to PBS with respect to the runtime and rendering time.
The basic idea is to render 2-D shapes instead of surfels. First the surfels (points) is determined by PBS. Then each region of surfel is clustered in 2-D space based color and depth values. The clusters are described in 2-D shape features with the help of the image-Moments. The described clusters are compared with predefined 2-D shapes to match the best fitted shape and to render it. Each 2D shape is rendered as a textured quad in, the 3D space. The whole rendered 2D shapes visualize the approximated geometry.
The  new process provides in most cases better image quality than PBS especially with low amount  of primitivs. It is also suitable for real-time rendering systems for highly complex 3D scenes.

(Final presentation Master's thesis)

Stanislaw Eppinger

Mai 11, 2016, 2:30 pm, F1.110

Approximated Photon Mapping for Real-Time Global Illumination

Indirect Illumination or Global Illumination is an important aspect of realistic image synthesis. It has been mainly computed offline in raytracing or radiosity based approcheas for a long time. The reason is its high computational demand. Only in the last recent years real-time approaches like Reflective Shadow Maps, Imperfect Shadow Maps, Virtual Point Lights or Voxel Cone Tracing have emerged. But even with increasing computational power not every technique is applicable in every scenario. Everyone has its particular drawbacks, be it high computational demand, high memory consumption or low precision.
In this thesis a new approach for real-time global illumination will be developed which should be low in memory consumption and less computational demanding. The main idea is a second representation of the original scene which approximates the original scene with far less complexity. Light sources render the approximated scene and mark every polygon which they illuminate. We then shoot photons from the camera's point of view into the scene. Every of these photons render again the approximated scene. In this process every marked polygon which is seen from one photon contributes to its irradiance value. These photons will then be sampled in the screen space in order to contribute their irradiance value to the final lighting computation of a pixel.

(Introductory presentation Master's thesis)

Lennart Leder

Mai 11, 2016, 3:00 pm, F1.110

Congestion Games with Mixed Objectives

Congestion games are a useful tool to model situations in which selfish actors (called players) allocate shared resources. The cost of a resource may increase if it is used by more players. In the standard definition, the cost of a player is defined as the sum of the costs of the resources that she allocates. In a bottleneck congestion game the cost of a player corresponds to her most expensive resource. This thesis regards congestion games with more general aggregation functions for the costs of the players. In particular, it introduces the model of congestion games with mixed objectives, which is a combination of standard and bottleneck congestion games. Moreover, it examines congestion games in which the costs are aggregated using Lp-norms. For both these models, the thesis derives results on the existence and computability of exact and approximate pure Nash equilibria.

(Final presentation Master's thesis)

Damian Kutzias

Mai 4, 2016, 2:00 pm, F1.110

Friendship Processes in Network Creation Games

Modern large-scale networks need self-organising concepts for the purpose of efficient service offering. Such self-organisation can for example show up as routing decisions, local structure changes to the network topology or the use of other network layers. Due to the complexity of many of these dynamic systems, theoretical means of investigation are very important. Network creation games are well-established for the investigation of self-organising networks, considering participants as selfish agents performing changes following a certain rule set to improve a cost- or utility function.
Most existing models consider uniform communication interests (also called friendships) where every participant wants to exchange data with every other participant of the network. This thesis focusses on a multilevel network creation game where agents can decide to pay for being a gateway allowing access to a high-speed layer with non-uniform friendships. Theoretical results about the quality of such networks are given and discusses. While many of the theoretical results indicate bad quality at least for the worst-cases, simulations were performed showing that most of these worst-cases do not happen in practice.

(Final presentation Master's thesis)

Daniel Jung

Mai 4, 2016, 2:30 pm, F1.110

Gathering a Closed Chain of Robots on a Grid

We consider the following variant of the twodimensional gathering problem for swarms of robots: Given a swarm of n indistinguishable, point-shaped robots on a twodimensional grid. Initially, the robots form a closed chain on the grid and must keep this connectivity during the whole process of their gathering. Connectivity means, that neighboring robots of the chain need to be positioned at the same or neighboring points of the grid. In our model, gathering means to keep shortening the chain until the robots are located inside a 2x2 subgrid. Our model is completely local (no global control, no global coordinates, no compass, no global communication or vision, ...). Each robot can only see its next constant number of left and right neighbors on the chain. This fixed constant is called the viewing path length. All its operations and detections are restricted to this constant number of robots. Other robots, even if located at neighboring or the same grid point, cannot be detected. Only based on the relative positions of its detectable chain neighbors, can a robot decide to obtain a certain state. Based on this state and their local knowledge, the robots do local modifications to the chain by moving to neighboring grid points without breaking the chain. These modifications are performed without the knowledge whether they lead to a global progress or not. We assume the fully synchronous FSYNC model. For this problem, we present a gathering algorithm which needs linear time. This result generalizes other results, where an open chain with specified distinguishable (and fixed) endpoints is considered.

Florian Pieper

April 20, 2016, 2:00 pm, F1.110

Graph based real time global illumination for wide area scenes

Global illumination is a key element to increase realism in virtual scenes. There are a lot of global illumination techniques, but most of them having the drawback of being very computational expensive. In praxis this means, that they can either only be applied to small scenes or do not guarantee real-time frame rates.
In this thesis a new global illumination algorithm was developed. To reach real-time frame rates, the algorithm relies on reusing visibility information. Once the visibility relations of a scene is calculated, the algorithm reuses it as long as there are no scene changes. Therefore a light graph stores the approximated surface to surface visibilities. To reduce the number of nodes and edges, the graph is distributed over spatial levels. Nodes that are located on higher levels are used to illuminate larger parts of the scene than nodes that are located on lower levels. The graph's edges are built by an approximated cone tracing, which also divides the node into the different levels.
The algorithm is also capable of handling interactive dynamic scene changes. To allow for fast scene changes, the graph is again reused. Only parts of the graph that are affected by the scene change get updated.

(Final presentation Master's thesis)

Vihar Bozadzhiev

April 20, 2016, 2:30 pm, F1.110

Highly scalable procedural road generation on 3D terrains

With the increasing computational power of modern computers, procedural generation of content has been steadily gaining popularity. Creating vast open worlds in computer games has forced creators to develop efficient generation algorithms that can provide realistic results under real-time constraints.
The objective of the proposed thesis is to focus on one aspect of this generation process, namely procedural road generation.
The main task of this thesis is the development and evaluation of a method for the procedural generation of roads on a given 3D terrain. The developed algorithm should take a start point and an end point as input for the path calculation and minimize a predefined cost function in order to find the shortest possible weighted path between the two points. The weight function is dependent on different parameters like the terrain slope, path curvature or user-defined restrictions on the obstacles in the scene. The goal is to generate a road along the landscape by deforming the terrain, avoiding certain regions or removing objects which lay on the path. In certain cases additional structures such as bridges and tunnels need to be generated in order to bring realism to the scene.

(Introductory presentation Master's thesis)

Hassan Elsharkawi

April 14, 2016, 2:00 pm, F0.530

Florabot: a prototype of modular robots system for flora-robotica project

Flora-robotica is a research project with the objective of creating mixed societies of natural plants and artificial robots. The artificial part takes the form of a scaffold built out of robotic rods and nodes. The nodes are used to mechanically connect the robotic rods together.
These robots will form a smart structure that provides self-assembly and self-repairing features. To achieve this goal, we should start by realizing the building blocks of such a structure (i.e. the robots).
The objective of the proposed thesis is to build a prototype of a scalable and easily-programmable system of modular robots that form the scaffold structure (i.e. the artificial part of the flora-robotica bio-hybrid system). Basic collective behavior of a swarm of
robots would be a nice demonstration for the different features of the system and a guarantee that the objective is met.

(Introductory presentation Master's thesis)

Jürgen König

April 13, 2016, 2:00 pm, F1.110

Shared Resource Scheduling with Interconnected Services

Consider a system in which different services are offered. Jobs composed of these services have to be processed. Communication between those services is necessary. The main performance limiting factors are the number of services active at a time and the required communication bandwidth between them. This master's thesis explored a new NP hard scheduling model for such a setting. In the thesis the proof of the NP hardness was formalized. Also two approximation algorithms using different approaches were obtained. In this talk both approximation algorithms and their practical evaluation will be presented.

(Final presentation Master's thesis)

Johannes Schaefer

April 6, 2016, 2:00 pm, F0.530

Routing Algorithms on Delayed Networks for Disaster Management Support

In large catastrophes such as earthquakes or floodings communication infrastructure may be broken. To allow people to communicate to the authorities smart phones can be used to create a network that can forward messages. In my thesis I develop a model for such networks and extend a simulator with it. On top of this model works the newly developed potential algorithm, of which I experimentally show that it routes messages efficiently from random phones to such with an internet connection.

(Final presentation Master's thesis)

Vihar Vasilev Bozadzhiev, Niladri Das, Srijani Ghosh, Henrik Werner Heine, Vishwak Narasimhan, Sayan Pal, Shivdeep Ganesh Rao, Felix Ruddat

April 6, 2016, 2:30 pm, F0.530

Project Group TestDrive3D

In this project we developed a virtual driving simulation in a dynamic 3D world. In contrast to existing driving simulations, like e.g. 3D street racing games, the track and the surrounding scenery is not completely defined before the simulation starts, but is generated while driving through the scene. Additionally, a test leader can modify the scene by issuing commands for street, forest and city generation, while a driver continuously explores the virtual world which emerges ahead of him.

(Final presentation)