TY - GEN
AB - We study the problem of computing approximate Nash equilibria (epsilon-Nash
equilibria) in normal form games, where the number of players is a small
constant. We consider the approach of looking for solutions with constant
support size. It is known from recent work that in the 2-player case, a
1/2-Nash equilibrium can be easily found, but in general one cannot achieve a
smaller value of epsilon than 1/2. In this paper we extend those results to the
k-player case, and find that epsilon = 1-1/k is feasible, but cannot be
improved upon. We show how stronger results for the 2-player case may be used
in order to slightly improve upon the epsilon = 1-1/k obtained in the k-player
case.
AU - Briest, Patrick
AU - Goldberg, Paul W.
AU - Roeglin, Heiko
ID - 19688
TI - Approximate Equilibria in Games with Few Players
ER -
TY - GEN
AU - Pietrzyk, Peter
ID - 19950
TI - Lokale Strategien zur Optimierung von Kommunikationsketten
ER -
TY - THES
AU - Hamann, Heiko
ID - 20262
SN - 1867-4925
TI - Space-Time Continuous Models of Swarm Robotic Systems
ER -
TY - CONF
AB - We present a comparative study of two spatially resolved macroscopic models of an autonomous robotic swarm. In previous experiments, the collective behavior of 15 autonomous swarm robots, driven by a simple bio-inspired control algorithm, was investigated: in two different environmental conditions, the ability of the robots to aggregate below a light source was tested. Distinct approaches to predict the dynamics of the spatial distribution were made by two different modeling approaches: one model was constructed in a compartmental manner (ODEs). In parallel, a space-continuous model (PDEs) was constructed. Both models show a high degree of similarity concerning the modeling of concrete environmental factors (light), but due to their different basic approaches, show also significant differences in their implementation. However, the predictions of both models compare well to the observed behavior of the robotic swarm, thus both models can be used to develop further extensions of the algorithm as well as different experimental setups without the need to run extensive real robotic preliminary experiments.
AU - Hamann, Heiko
AU - Schmickl, Thomas
AU - Wörn, Heinz
AU - Crailsheim, Karl
ID - 20368
T2 - IEEE/RSJ 2008 International Conference on Intelligent Robots and Systems (IROS'08)
TI - Spatial Macroscopic Models of a Bio-Inspired Robotic Swarm Algorithm
ER -
TY - CHAP
AU - Gehweiler, Joachim
AU - Meyer auf der Heide, Friedhelm
ID - 16464
SN - 9783540763932
T2 - Taschenbuch der Algorithmen
TI - Bin Packing oder „Wie bekomme ich die Klamotten in die Kisten?“
ER -
TY - THES
AU - Schomaker, Gunnar
ID - 19615
SN - 978-3-939350-78-1
TI - Distributed Resource Allocation and Management in Heterogeneous Networks
ER -
TY - CONF
AB - Modern peer-to-peer networks consist of several network layers and distributed algorithms providing features like indexing, resource balancing, entry protocols, security, anonymity, and cryptography. Since peer-to-peer networks are highly dynamic, a fundamental task in the design of these networks is to provide high connectivity. We propose a solution by distributed random link exchange algorithms such that the overlay network can be a connected random graph or use a random graph as backbone. Random graphs are expander graphs have logarithmic diameter, high node connectivity, excellent communication properties, and are expander graphs with high probability. In summary: they are an excellent choice to improve the stability and robustness of a dynamic network.
AU - Schindelhauer, Christian
AU - Mahlmann, Peter
ID - 19812
IS - 222
T2 - The European Integrated Project "Dynamically Evolving, Large Scale Information Systems (DELIS), Proceedings of the Final Workshop
TI - Random Graphs for Peer-to-Peer Overlays
ER -
TY - JOUR
AB - Designing and analyzing self-organizing systems such as robotic swarms is a challenging task even though we have complete knowledge about the robot’s interior. It is difficult to determine the individual robot’s behavior based on the swarm behavior and vice versa due to the high number of agent–agent interactions. A step towards a solution of this problem is the development of appropriate models which accurately predict the swarm behavior based on a specified control algorithm. Such models would reduce the necessary number of time-consuming simulations and experiments during the design process of an algorithm. In this paper we propose a model with focus on an explicit representation of space because the effectiveness of many swarm robotic scenarios depends on spatial inhomogeneity. We use methods of statistical physics to address spatiality. Starting from a description of a single robot we derive an abstract model of swarm motion. The model is then extended to a generic model framework of communicating robots. In two examples we validate models against simulation results. Our experience shows that qualitative correctness is easily achieved, while quantitative correctness is disproportionately more difficult but still possible.
AU - Hamann, Heiko
AU - Wörn, Heinz
ID - 20369
IS - 2-4
JF - Swarm Intelligence
SN - 1935-3812
TI - A framework of space–time continuous models for algorithm design in swarm robotics
VL - 2
ER -
TY - GEN
AB - For a fixed virtual scene (=collection of simplices) S and given observer
position p, how many elements of S are weakly visible (i.e. not fully occluded
by others) from p? The present work explores the trade-off between query time
and preprocessing space for these quantities in 2D: exactly, in the approximate
deterministic, and in the probabilistic sense. We deduce the EXISTENCE of an
O(m^2/n^2) space data structure for S that, given p and time O(log n), allows
to approximate the ratio of occluded segments up to arbitrary constant absolute
error; here m denotes the size of the Visibility Graph--which may be quadratic,
but typically is just linear in the size n of the scene S. On the other hand,
we present a data structure CONSTRUCTIBLE in O(n*log(n)+m^2*polylog(n)/k)
preprocessing time and space with similar approximation properties and query
time O(k*polylog n), where k