Rendezvous of Distance-Aware Mobile Agents in Unknown Graphs

DOI10.1007/978-3-319-09620-9_23zbMATH Open1416.68190arXiv1406.2795OpenAlexW2915086378MaRDI QIDQ5496166FDOQ5496166

Przemysław Uznański, Adrian Kosowski, Shantanu Das, Dariusz Dereniowski

Publication date: 7 August 2014

Published in: Structural Information and Communication Complexity (Search for Journal in Brave)

Abstract: We study the problem of rendezvous of two mobile agents starting at distinct locations in an unknown graph. The agents have distinct labels and walk in synchronous steps. However the graph is unlabelled and the agents have no means of marking the nodes of the graph and cannot communicate with or see each other until they meet at a node. When the graph is very large we want the time to rendezvous to be independent of the graph size and to depend only on the initial distance between the agents and some local parameters such as the degree of the vertices, and the size of the agent's label. It is well known that even for simple graphs of degree $Delta$, the rendezvous time can be exponential in $Delta$ in the worst case. In this paper, we introduce a new version of the rendezvous problem where the agents are equipped with a device that measures its distance to the other agent after every step. We show that these emph{distance-aware} agents are able to rendezvous in any unknown graph, in time polynomial in all the local parameters such the degree of the nodes, the initial distance $D$ and the size of the smaller of the two agent labels $l=min(l_1,l_2)$. Our algorithm has a time complexity of $O(Delta(D+logl))$ and we show an almost matching lower bound of $Omega(Delta(D+logl/logDelta))$ on the time complexity of any rendezvous algorithm in our scenario. Further, this lower bound extends existing lower bounds for the general rendezvous problem without distance awareness.

Full work available at URL: https://arxiv.org/abs/1406.2795

zbMATH Keywords

lower boundssynchronousmobile agentrendezvousdistance oracleanonymous networks

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40) Artificial intelligence for robotics (68T40)

Cited In (9)

• Deterministic Meeting of Sniffing Agents in the Plane
• Two-agent tree evacuation
• Robust Rendezvous for Mobile Autonomous Agents via Proximity Graphs in Arbitrary Dimensions
• Byzantine gathering in networks
• Combination framework of rendezvous algorithm for multi-agent systems with limited sensing ranges
• Byzantine gathering in polynomial time
• Deterministic rendezvous with different maps
• Title not available (Why is that?)
• Asynchronous approach in the plane: a deterministic polynomial algorithm

This page was built for publication: Rendezvous of Distance-Aware Mobile Agents in Unknown Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5496166)