TY - GEN

T1 - Almost optimal asynchronous rendezvous in infinite multidimensional grids

AU - Bampas, Evangelos

AU - Czyzowicz, Jurek

AU - Ga̧sieniec, Leszek

AU - Ilcinkas, David

AU - Labourel, Arnaud

PY - 2010

Y1 - 2010

N2 - Two anonymous mobile agents (robots) moving in an asynchronous manner have to meet in an infinite grid of dimension δ > 0, starting from two arbitrary positions at distance at most d. Since the problem is clearly infeasible in such general setting, we assume that the grid is embedded in a δ-dimensional Euclidean space and that each agent knows the Cartesian coordinates of its own initial position (but not the one of the other agent). We design an algorithm permitting the agents to meet after traversing a trajectory of length O(dδ polylogd). This bound for the case of 2d -grids subsumes the main result of [12]. The algorithm is almost optimal, since the Ω(dδ) lower bound is straightforward. Further, we apply our rendezvous method to the following network design problem. The ports of the δ-dimensional grid have to be set such that two anonymous agents starting at distance at most d from each other will always meet, moving in an asynchronous manner, after traversing a O(d δ polylogd) length trajectory. We can also apply our method to a version of the geometric rendezvous problem. Two anonymous agents move asynchronously in the δ-dimensional Euclidean space. The agents have the radii of visibility of r1 and r2, respectively. Each agent knows only its own initial position and its own radius of visibility. The agents meet when one agent is visible to the other one. We propose an algorithm designing the trajectory of each agent, so that they always meet after traveling a total distance of O((d/r)δ polylog (d/r)), where r = min (r 1, r2) and for r ≥ 1.

AB - Two anonymous mobile agents (robots) moving in an asynchronous manner have to meet in an infinite grid of dimension δ > 0, starting from two arbitrary positions at distance at most d. Since the problem is clearly infeasible in such general setting, we assume that the grid is embedded in a δ-dimensional Euclidean space and that each agent knows the Cartesian coordinates of its own initial position (but not the one of the other agent). We design an algorithm permitting the agents to meet after traversing a trajectory of length O(dδ polylogd). This bound for the case of 2d -grids subsumes the main result of [12]. The algorithm is almost optimal, since the Ω(dδ) lower bound is straightforward. Further, we apply our rendezvous method to the following network design problem. The ports of the δ-dimensional grid have to be set such that two anonymous agents starting at distance at most d from each other will always meet, moving in an asynchronous manner, after traversing a O(d δ polylogd) length trajectory. We can also apply our method to a version of the geometric rendezvous problem. Two anonymous agents move asynchronously in the δ-dimensional Euclidean space. The agents have the radii of visibility of r1 and r2, respectively. Each agent knows only its own initial position and its own radius of visibility. The agents meet when one agent is visible to the other one. We propose an algorithm designing the trajectory of each agent, so that they always meet after traveling a total distance of O((d/r)δ polylog (d/r)), where r = min (r 1, r2) and for r ≥ 1.

UR - http://www.scopus.com/inward/record.url?scp=78649810105&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=78649810105&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-15763-9_28

DO - 10.1007/978-3-642-15763-9_28

M3 - Conference contribution

AN - SCOPUS:78649810105

SN - 3642157629

SN - 9783642157622

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 297

EP - 311

BT - Distributed Computing - 24th International Symposium, DISC 2010, Proceedings

PB - Springer Verlag

ER -