A New Approach for Analyzing Convergence Algorithms for Mobile Robots
Cord-Landwehr, Andreas
Degener, Bastian
Fischer, Matthias
Hüllmann, Martina
Kempkes, Barbara
Klaas, Alexander
Kling, Peter
Kurras, Sven
Märtens, Marcus
Meyer auf der Heide, Friedhelm
Raupach, Christoph
Swierkot, Kamil
Warner, Daniel
Weddemann, Christoph
Wonisch, Daniel
Given a set of n mobile robots in the d-dimensional Euclidean space, the goal is to let them converge to a single not predefined point. The challenge is that the robots are limited in their capabilities. Robots can, upon activation, compute the positions of all other robots using an individual affine coordinate system. The robots are indistinguishable, oblivious and may have different affine coordinate systems. A very general discrete time model assumes that robots are activated in arbitrary order. Further, the computation of a new target point may happen much earlier than the movement, so that the movement is based on outdated information about other robot's positions. Time is measured as the number of rounds, where a round ends as soon as each robot has moved at least once. In [Cohen, Peleg: Convergence properties of gravitational algorithms in asynchronous robot systems], the Center of Gravity is considered as target function, convergence was proven, and the number of rounds needed for halving the diameter of the convex hull of the robot's positions was shown to be O(n^2) and Omega(n). We present an easy-to-check property of target functions that guarantee convergence and yields upper time bounds. This property intuitively says that when a robot computes a new target point, this point is significantly within the current axes aligned minimal box containing all robots. This property holds, e.g., for the above-mentioned target function, and improves the above O(n^2) to an asymptotically optimal O(n) upper bound. Our technique also yields a constant time bound for a target function that requires all robots having identical coordinate axes.
2011
info:eu-repo/semantics/bookPart
doc-type:bookPart
text
http://purl.org/coar/resource_type/c_3248
https://ris.uni-paderborn.de/record/16409
Cord-Landwehr A, Degener B, Fischer M, et al. A New Approach for Analyzing Convergence Algorithms for Mobile Robots. In: <i>Automata, Languages and Programming</i>. Berlin, Heidelberg; 2011. doi:<a href="https://doi.org/10.1007/978-3-642-22012-8_52">10.1007/978-3-642-22012-8_52</a>
eng
info:eu-repo/semantics/altIdentifier/doi/10.1007/978-3-642-22012-8_52
info:eu-repo/semantics/altIdentifier/issn/0302-9743
info:eu-repo/semantics/altIdentifier/issn/1611-3349
info:eu-repo/semantics/altIdentifier/isbn/9783642220111
info:eu-repo/semantics/altIdentifier/isbn/9783642220128
info:eu-repo/semantics/closedAccess