Name
Abstract | ||
|---|---|---|
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 [6], 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(n2) and Ω(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(n2) 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. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1007/978-3-642-22012-8_52 | ICALP (2) |
Keywords | Field | DocType |
predefined point,n mobile robot,target function,easy-to-check property,new target point,constant time,convergence algorithm,yields upper time bound,new approach,general discrete time model,above-mentioned target function,property intuitively | Coordinate system,Affine transformation,Combinatorics,Computer science,Affine coordinate system,Upper and lower bounds,Convex hull,Algorithm,Euclidean space,Robot,Mobile robot | Conference |
Volume | ISSN | Citations |
6756 | 0302-9743 | 22 |
PageRank | References | Authors |
0.91 | 15 | 15 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Andreas Cord-Landwehr | 1 | 56 | 4.97 |
| Bastian Degener | 2 | 130 | 10.55 |
| Matthias Fischer | 3 | 22 | 0.91 |
| Martina Hüllmann | 4 | 42 | 2.28 |
| Barbara Kempkes | 5 | 127 | 9.43 |
| Alexander Klaas | 6 | 41 | 2.93 |
| Peter Kling | 7 | 81 | 11.56 |
| Sven Kurras | 8 | 38 | 1.76 |
| Marcus Märtens | 9 | 161 | 9.05 |
| Friedhelm Meyer auf der Heide | 10 | 1744 | 238.01 |
| Christoph Raupach | 11 | 130 | 4.43 |
| Kamil Swierkot | 12 | 129 | 4.40 |
| Daniel Warner | 13 | 38 | 1.76 |
| Christoph Weddemann | 14 | 38 | 1.76 |
| Daniel Wonisch | 15 | 68 | 5.56 |