TY - JOUR
AU - Degener, Bastian
AU - Kempkes, Barbara
AU - Kling, Peter
AU - Meyer auf der Heide, Friedhelm
ID - 16391
JF - ACM Transactions on Parallel Computing
SN - 2329-4949
TI - Linear and Competitive Strategies for Continuous Robot Formation Problems
ER -
TY - GEN
AU - Pfannschmidt, Karlson
ID - 251
TI - Solving the aggregated bandits problem
ER -
TY - CONF
AB - 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 (Bilò 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.
AU - Cord-Landwehr, Andreas
AU - Lenzner, Pascal
ID - 275
T2 - Proceedings of the 40th Conference on Mathematical Foundations of Computer Science (MFCS)
TI - Network Creation Games: Think Global - Act Local
ER -
TY - THES
AU - Abshoff, Sebastian
ID - 270
TI - On the Complexity of Fundamental Problems in Dynamic Ad-hoc Networks
ER -
TY - CONF
AB - Besides the life-as-it-could-be driver of artificial life research there is also the concept of extending natural life by creating hybrids or mixed societies that are built from natural and artificial components. In this paper we motivate and present the research program of the project flora robotica. Our objective is to develop and to investigate closely linked symbiotic relationships between robots and natural plants and to explore the potentials of a plant-robot society able to produce architectural artifacts and living spaces. These robot-plant bio-hybrids create synergies that allow for new functions of plants and robots. They also create novel design opportunities for an architecture that fuses the design and construction phase. The bio-hybrid is an example of mixed societies between 'hard' artificial and 'wet' natural life, which enables an interaction between natural and artificial ecologies. They form an embodied, self-organizing, and distributed cognitive system which is supposed to grow and develop over long periods of time resulting in the creation of meaningful architectural structures. A key idea is to assign equal roles to robots and plants in order to create a highly integrated, symbiotic system. Besides the gain of knowledge, this project has the objective to create a bio-hybrid system with a defined function and application -- growing architectural artifacts.
AU - Hamann, Heiko
AU - Wahby, Mostafa
AU - Schmickl, Thomas
AU - Zahadat, Payam
AU - Hofstadler, Daniel
AU - Stoy, Kasper
AU - Risi, Sebastian
AU - Faina, Andres
AU - Veenstra, Frank
AU - Kernbach, Serge
AU - Kuksin, Igor
AU - Kernbach, Olga
AU - Ayres, Phil
AU - Wojtaszek, Przemyslaw
ID - 19960
SN - 9781479975600
T2 - Proceedings of the 2015 IEEE Symposium on Artificial Life (IEEE ALIFE'15)
TI - Flora Robotica - Mixed Societies of Symbiotic Robot-Plant Bio-Hybrids
ER -
TY - CHAP
AU - Hamann, Heiko
AU - Correll, Nikolaus
AU - Kacprzyk, Janusz
AU - Pedrycz, Witold
ID - 19989
T2 - Springer Handbook of Computational Intelligence
TI - Probabilistic Modeling of Swarming Systems
ER -
TY - CONF
AU - Hamann, Heiko
AU - Schmickl, Thomas
AU - Kengyel, Daniela
AU - Zahadat, Payam
AU - Radspieler, Gerald
AU - Wotawa, Franz
ID - 19991
T2 - Principles and Practice of Multi-Agent Systems (PRIMA 2015)
TI - Potential of Heterogeneity in Collective Behaviors: A Case Study on Heterogeneous Swarms
ER -
TY - CONF
AU - Dorigo, Marco
AU - Hamann, Heiko
AU - Valentini, Gabriele
ID - 20006
T2 - AAAI-15 Video Proceedings
TI - Self-organized collective decisions in a robot swarm
ER -
TY - CONF
AB - We consider online leasing problems in which demands arrive over time and need to be served by leasing resources. We introduce a new model for these problems such that a resource can be leased for K different durations each incurring a different cost (longer leases cost less per time unit). Each demand i can be served anytime between its arrival ai and its deadline ai+di by a leased resource. The objective is to meet all deadlines while minimizing the total leasing costs. This model is a natural generalization of Meyerson’s ParkingPermitProblem (FOCS 2005) in which di=0 for all i. We propose an online algorithm that is Θ(K+dmaxlmin)-competitive where dmax and lmin denote the largest di and the shortest available lease length, respectively. We also extend the SetCoverLeasing problem by deadlines and give a competitive online algorithm which also improves on existing solutions for the original SetCoverLeasing problem.
AU - Li, Shouwei
AU - Mäcker, Alexander
AU - Markarian, Christine
AU - Meyer auf der Heide, Friedhelm
AU - Riechers, Sören
ID - 240
T2 - Proceedings of the 21st Annual International Computing and Combinatorics Conference (COCOON)
TI - Towards Flexible Demands in Online Leasing Problems
ER -
TY - CONF
AB - In \emph{bandwidth allocation games} (BAGs), the strategy of a player consists of various demands on different resources. The player's utility is at most the sum of these demands, provided they are fully satisfied. Every resource has a limited capacity and if it is exceeded by the total demand, it has to be split between the players. Since these games generally do not have pure Nash equilibria, we consider approximate pure Nash equilibria, in which no player can improve her utility by more than some fixed factor $\alpha$ through unilateral strategy changes. There is a threshold $\alpha_\delta$ (where $\delta$ is a parameter that limits the demand of each player on a specific resource) such that $\alpha$-approximate pure Nash equilibria always exist for $\alpha \geq \alpha_\delta$, but not for $\alpha < \alpha_\delta$. We give both upper and lower bounds on this threshold $\alpha_\delta$ and show that the corresponding decision problem is ${\sf NP}$-hard. We also show that the $\alpha$-approximate price of anarchy for BAGs is $\alpha+1$. For a restricted version of the game, where demands of players only differ slightly from each other (e.g. symmetric games), we show that approximate Nash equilibria can be reached (and thus also be computed) in polynomial time using the best-response dynamic. Finally, we show that a broader class of utility-maximization games (which includes BAGs) converges quickly towards states whose social welfare is close to the optimum.
AU - Drees, Maximilian
AU - Feldotto, Matthias
AU - Riechers, Sören
AU - Skopalik, Alexander
ID - 271
T2 - Proceedings of the 8th International Symposium on Algorithmic Game Theory (SAGT)
TI - On Existence and Properties of Approximate Pure Nash Equilibria in Bandwidth Allocation Games
ER -