@phdthesis{20262, author = {{Hamann, Heiko}}, isbn = {{9783642133763}}, issn = {{1867-4925}}, title = {{{Space-Time Continuous Models of Swarm Robotic Systems}}}, doi = {{10.1007/978-3-642-13377-0}}, year = {{2008}}, } @unpublished{26235, abstract = {{Kolmogorov Complexity constitutes an integral part of computability theory, information theory, and computational complexity theory -- in the discrete setting of bits and Turing machines. Over real numbers, on the other hand, the BSS-machine (aka real-RAM) has been established as a major model of computation. This real realm has turned out to exhibit natural counterparts to many notions and results in classical complexity and recursion theory; although usually with considerably different proofs. The present work investigates similarities and differences between discrete and real Kolmogorov Complexity as introduced by Montana and Pardo (1998).}}, author = {{Ziegler, Martin and Koolen, Wouter M.}}, booktitle = {{arXiv:0802.2027}}, title = {{{Kolmogorov Complexity Theory over the Reals}}}, year = {{2008}}, } @inproceedings{26243, abstract = {{Operations on univariate dense polynomials—multiplication, division with remainder, multipoint evaluation—constitute central primitives entering as build-up blocks into many higher applications and algorithms. Fast Fourier Transform permits to accelerate them from naive quadratic to running time O(n·polylogn), that is softly linear in the degree n of the input. This is routinely employed in complexity theoretic considerations and, over integers and finite fields, in practical number theoretic calculations. The present work explores the benefit of fast polynomial arithmetic over the field of real numbers where the precision of approximation becomes crucial. To this end, we study the computability of the above operations in the sense of Recursive Analysis as an effective refinement of continuity. This theo- retical worst-case stability analysis is then complemented by an empirical evaluation: We use GMP and the iRRAM to find the precision required for the intermediate calculations in order to achieve a desired output accuracy.}}, author = {{Köhler, Sven and Ziegler, Martin}}, booktitle = {{Proc. 8th Conference on Real Numbers and Computers}}, pages = {{147--156}}, title = {{{On the Stability of Fast Polynomial Arithmetic}}}, year = {{2008}}, } @article{26255, abstract = {{We turn the physical Church-Turing Hypothesis from an ambiguous source of sensational speculations into a (collection of) sound and well-defined scientific problem(s): Examining recent controversies and causes for misunderstanding concerning the state of the Church- Turing Hypothesis (CTH), it is suggested to study the CTH ‘sharpened’ relative to an arbitrary but specific physical theory—rather than vaguely referring to “nature” in general. For this purpose we combine physical structuralism with computational complexity theory. The benefits of this approach are illustrated by some exemplary results on computability and complexity in computational physics.}}, author = {{Ziegler, Martin}}, journal = {{Applied Mathematics and Computation}}, title = {{{Physically-Relativized Church-Turing Hypotheses}}}, year = {{2008}}, } @inbook{26262, author = {{Ziegler, Martin}}, booktitle = {{Verhandlungen der Deutschen Physikalischen Gesellschaft}}, pages = {{145}}, publisher = {{Deutsche Physikalische Gesellschaft (DPG)}}, title = {{{A Meta-Theory of Physics and Computation}}}, year = {{2008}}, } @article{26280, author = {{Meer, Klaus and Ziegler, Martin}}, issn = {{0885-064X}}, journal = {{Journal of Complexity}}, pages = {{3--15}}, title = {{{An explicit solution to Post's Problem over the reals}}}, doi = {{10.1016/j.jco.2006.09.004}}, year = {{2008}}, } @inproceedings{17416, abstract = {{In this paper we present a system for the simultaneous visualization of several parallel executed simulation replications. By aggregating the scenes of multiple similar simulations into one single scene it is possible to make a visual statistical analysis of a set of discrete event simulations as well as to easily compare different system parameterizations. The aim of our system is to enhance the model analysis, verification and validation process in terms of speed and ease. The parallel execution of several simulations of complex models and the visualization of these cannot be done on one computer, thus a parallel approach is necessary. Our system uses a thin-client and multiple processors on a PC-cluster. The rendering and the simulation execution are done on processors of the cluster. The client is used only for the visualization of the images transmitted by the cluster and for user interaction. }}, author = {{Suess, Tim and Huber, Daniel and Fischer, Matthias and Laroque, Christoph and Dangelmaier, Wilhelm}}, booktitle = {{IEEE International Symposium on Parallel and Distributed Processing with Applications}}, isbn = {{9780769534718}}, title = {{{A System for Aggregated Visualization of Multiple Parallel Discrete Event Simulations}}}, doi = {{10.1109/ispa.2008.30}}, year = {{2008}}, } @inproceedings{17868, abstract = {{The paper describes an approach for an aggregated animation of a simulation experiment in an interactive 3D environment, visualizing multiple, distributed simulation runs. Although the general approach of a 3-dimensional visualization of material flow simulation helps to understand the dynamic behavior of a system better as well as faster, it remains unclear, how typical the animated simulation represents the model, if there is a stochastic influence for even some parameters. By the integrated visualization of multiple distributed simulation runs, this uncertainty can be solved, which will be shown in this paper for a typical simulation study of a queuing system. }}, author = {{Dangelmaier, Wilhelm and Fischer, Matthias and Huber, Daniel and Laroque, Christoph and Suess, Tim}}, booktitle = {{2008 Winter Simulation Conference}}, isbn = {{9781424427079}}, pages = {{2012--2020}}, title = {{{Aggregated 3D-visualization of a distributed simulation experiment of a queuing system}}}, doi = {{10.1109/wsc.2008.4736296}}, year = {{2008}}, } @inproceedings{19003, author = {{Degener, Bastian and Gehweiler, Joachim and Lammersen, Christiane}}, booktitle = {{Proceedings of the 11th Scandinavian Workshop on Algorithm Theory (SWAT)}}, isbn = {{9783540699002}}, issn = {{0302-9743}}, pages = {{378--389}}, title = {{{The Kinetic Facility Location Problem}}}, doi = {{10.1007/978-3-540-69903-3_34}}, year = {{2008}}, } @inproceedings{19004, abstract = {{We present a deterministic kinetic data structure for the facility location problem that maintains a subset of the moving points as facilities such that, at any point of time, the sum of the maintenance cost for the facilities and the connection cost for the clients is at most a constant factor larger than the current optimal cost. In our scenario, each point can open a facility and moves continuously along a known trajectory in a d-dimensional Euclidean space where d is a constant. Our kinetic data structure has a storage requirement of O(n (log^d(n)+log(nR))), where n is the number of points and R is the ratio of the product of the maximum maintenance cost and demand to the product of their corresponding minimum values. In the case that each trajectory can be described by a bounded degree polynomial, the data structure processes O(n^2 log^2(nR)) events, each requiring only O(log(nR)) facility changes and O(log^(d+1)(n) log(nR)) time. This results in a total processing time of O(n^2 log^(d+1)(n) log^3(nR)). To the best of our knowledge, this is the first kinetic data structure for the facility location problem.}}, author = {{Gehweiler, Joachim and Lammersen, Christiane and Degener, Bastian}}, booktitle = {{Proceedings of the 24th European Workshop on Computational Geometry}}, pages = {{251--254}}, title = {{{The Kinetic Facility Location Problem}}}, year = {{2008}}, } @inproceedings{1940, author = {{Mense, Mario and Scheideler, Christian}}, booktitle = {{Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2008, San Francisco, California, USA, January 20-22, 2008}}, pages = {{1135----1144}}, publisher = {{SIAM}}, title = {{{SPREAD: an adaptive scheme for redundant and fair storage in dynamic heterogeneous storage systems}}}, year = {{2008}}, } @inproceedings{20367, author = {{Hamann, Heiko and Wörn, Heinz}}, booktitle = {{The tenth International Conference on Simulation of Adaptive Behavior (SAB'08)}}, isbn = {{9783540691334}}, issn = {{0302-9743}}, pages = {{447----456}}, title = {{{Aggregating Robots Compute: An Adaptive Heuristic for the Euclidean Steiner Tree Problem}}}, doi = {{10.1007/978-3-540-69134-1_44}}, volume = {{5040}}, year = {{2008}}, } @inproceedings{20368, abstract = {{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.}}, author = {{Hamann, Heiko and Schmickl, Thomas and Wörn, Heinz and Crailsheim, Karl}}, booktitle = {{IEEE/RSJ 2008 International Conference on Intelligent Robots and Systems (IROS'08)}}, pages = {{1415----1420}}, publisher = {{IEEE Press}}, title = {{{Spatial Macroscopic Models of a Bio-Inspired Robotic Swarm Algorithm}}}, doi = {{10.1109/IROS.2008.4651038}}, year = {{2008}}, } @article{20369, abstract = {{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.}}, author = {{Hamann, Heiko and Wörn, Heinz}}, issn = {{1935-3812}}, journal = {{Swarm Intelligence}}, number = {{2-4}}, pages = {{209--239}}, title = {{{A framework of space–time continuous models for algorithm design in swarm robotics}}}, doi = {{10.1007/s11721-008-0015-3}}, volume = {{2}}, year = {{2008}}, } @inbook{17978, author = {{Lürwer-Brüggemeier, Katharina and Ziegler, Martin}}, booktitle = {{Unconventional Computing}}, isbn = {{9783540851936}}, issn = {{0302-9743}}, title = {{{On Faster Integer Calculations Using Non-arithmetic Primitives}}}, doi = {{10.1007/978-3-540-85194-3_11}}, year = {{2008}}, } @inproceedings{18139, abstract = {{This paper describes a method for the animation of a large number of objects within a dynamic 3D visualization of a material flow simulation model. It uses key-frame based animation. The number of animated objects may grow constantly in complex simulation models, which might lead to an amount of animations that is too big to be computed in real-time. By the use of a dynamic adjustment, the presented algorithm prefers important animations. Less relevant animations are updated rarely, whereby the selection itself is taken by multiple indicators, e.g. the visible size of the animated object on the screen, in order to keep a good optical impression. Dependent on the computing power of the computer, the algorithm controls the animations in such a way, that the fluid visualization of a large number of objects is still possible. Though the algorithm is to be used within a material flow simulator, it is moreover implemented in a specific animation editor, which allows the design and control of animation schemes. It supports the use of grouping to allow the creation of hierarchical structures for complex animations in a fast and easy manner. The evaluation of the algorithm is proven by a test scene, consisting of tens of thousands animated objects. }}, author = {{Laroque, Christoph and Fischer, Matthias and Dangelmaier, Wilhelm and Eikel, Benjamin}}, booktitle = {{Industrial Simulation Conference (ISC 2008)}}, pages = {{306--310}}, publisher = {{EUROSIS-ETI}}, title = {{{Dynamic Control of Animation Schemes for the Efficient 3D-Visualization of Material Flow Simulations}}}, year = {{2008}}, } @inproceedings{18141, abstract = {{Dieser Artikel beschreibt eine Methode zur Animation einer großen Anzahl von Objekten zur dynamischen 3D-Visualisierung eines Simulationsmodells mittels der Materialflusssimulation auf Basis von Schlüsselbildern. Die Anzahl zu animierender Objekte ist in komplexen Modellen zu groß, um alle Animationen flüssig darzustellen. Dynamisch abgestuft wählt das entwickelte Verfahren gezielt wichtige Animationen aus, weniger relevante Animationen werden entsprechend seltener animiert. Die Selektion der Animationen erfolgt nach der projizierten Größe der Objekte auf das Ausgabegerät, um einen guten optischen Eindruck beizubehalten. Angepasst an die Leistungsfähigkeit des Rechners wird das Verfahren so geregelt, dass die Visualisierung einer hohen Anzahl von Objekten in Echtzeit möglich bleibt. Das Verfahren ist in einem Editor prototypisch implementiert, mit dem Schlüsselbilder für Objekte erzeugt werden können. Das Gruppieren von Objekten wird erlaubt, so dass eine Hierarchie von Bewegungspfaden definierbar ist. Die Evaluierung der Methode wird mittels Testszenen durchgeführt, die aus mehreren zehntausend animierten Objekten bestehen.}}, author = {{Laroque, Christoph and Fischer, Matthias and Eikel, Benjamin}}, booktitle = {{Augmented & Virtual Reality in der Produktentstehung}}, pages = {{193----206}}, publisher = {{Verlagsschriftenreihe des Heinz Nixdorf Instituts, Paderborn}}, title = {{{Regelung von Animationen in Simulationen von hochdynamischen Fabrikszenen }}}, volume = {{232}}, year = {{2008}}, } @article{18143, author = {{Le Roux, Stéphane and Ziegler, Martin}}, issn = {{1571-0661}}, journal = {{Electronic Notes in Theoretical Computer Science}}, pages = {{73--88}}, title = {{{Singular Coverings and Non-Uniform Notions of Closed Set Computability}}}, doi = {{10.1016/j.entcs.2008.03.009}}, year = {{2008}}, } @article{18570, abstract = {{We present a game theoretic study of hybrid communication networks in which mobile devices can connect in an ad hoc fashion to a base station, possibly via a few hops using other mobile devices as intermediate nodes. The maximal number of allowed hops might be bounded with the motivation to guarantee small latency. We introduce hybrid connectivity games to study the impact of selfishness on this kind of infrastructure. Mobile devices are represented by selfish players, each of which aims at establishing an uplink path to the base station minimizing its individual cost. Our model assumes that intermediate nodes on an uplink path are reimbursed for transmitting the packets of other devices. The reimbursements can be paid either by a benevolent network operator or by the senders of the packets using micropayments via a clearing agency that possibly collects a small percentage as commission. These different ways to implement the payments lead to different variants of the hybrid connectivity game. Our main findings are: (1) If there is no constraint on the number of allowed hops on the path to the base station, then the existence of equilibria is guaranteed regardless of whether the network operator or the senders pay for forwarding packets. (2) If the network operator pays, then the existence of equilibria is guaranteed only if at most one intermediate node is allowed, i.e., for at most two hops on the uplink path of a device, but not if the maximal number of allowed hops is three or larger. (3) In contrast, if the senders pay for forwarding their packets, then equilibria are guaranteed to exist given any bound on the number of allowed hops. The equilibrium analysis presented in this paper gives a first game theoretical motivation for the implementation of micropayment schemes in which senders pay for forwarding their packets. We further support this evidence by giving an upper bound on the Price of Anarchy for this kind of hybrid connectivity games that is independent of the number of nodes, but only depends on the number of hops and the power gradient.}}, author = {{Ackermann, Heiner and Briest, Patrick and Fanghänel, Alexander and Vöcking, Berthold}}, isbn = {{9783540771043}}, journal = {{Internet Mathematics}}, number = {{4}}, pages = {{459--475}}, publisher = {{Springer}}, title = {{{Who Should Pay for Forwarding Packets?}}}, doi = {{10.1007/978-3-540-77105-0_21}}, volume = {{5}}, year = {{2008}}, } @inbook{16463, author = {{Meyer auf der Heide, Friedhelm and Schneider, Barbara}}, booktitle = {{Biologically-Inspired Collaborative Computing}}, isbn = {{9780387096544}}, issn = {{1571-5736}}, title = {{{Local Strategies for Connecting Stations by Small Robotic Networks}}}, doi = {{10.1007/978-0-387-09655-1_9}}, year = {{2008}}, }