Rendezvous of heterogeneous mobile agents in edge-weighted networks

DOI10.1016/J.TCS.2015.05.055zbMATH Open1333.68247DBLPjournals/tcs/DereniowskiKKK15OpenAlexW51870591WikidataQ62048698 ScholiaQ62048698MaRDI QIDQ896142FDOQ896142

Authors Dariusz Dereniowski, Ralf Klasing, Adrian Kosowski, Łukasz Kuszner

Publication date 11 December 2015

Published in Theoretical Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

distributed algorithmrendezvousmobile agents

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Agent technology and artificial intelligence (68T42) Distributed algorithms (68W15) Distributed systems (68M14)

Abstract: We introduce a variant of the deterministic rendezvous problem for a pair of heterogeneous agents operating in an undirected graph, which differ in the time they require to traverse particular edges of the graph. Each agent knows the complete topology of the graph and the initial positions of both agents. The agent also knows its own traversal times for all of the edges of the graph, but is unaware of the corresponding traversal times for the other agent. The goal of the agents is to meet on an edge or a node of the graph. In this scenario, we study the time required by the agents to meet, compared to the meeting time $T_{OPT}$ in the offline scenario in which the agents have complete knowledge about each others speed characteristics. When no additional assumptions are made, we show that rendezvous in our model can be achieved after time $O(n{T}_{OPT})$ in a $n$-node graph, and that such time is essentially in some cases the best possible. However, we prove that the rendezvous time can be reduced to $Theta(T_{OPT})$ when the agents are allowed to exchange $Theta(n)$ bits of information at the start of the rendezvous process. We then show that under some natural assumption about the traversal times of edges, the hardness of the heterogeneous rendezvous problem can be substantially decreased, both in terms of time required for rendezvous without communication, and the communication complexity of achieving rendezvous in time $Theta(T_{OPT})$.

Recommendations

• Rendezvous of heterogeneous mobile agents in edge-weighted networks
• On deterministic rendezvous at a node of agents with arbitrary velocities
• Mathematical Foundations of Computer Science 2005
• Asynchronous deterministic rendezvous in graphs
• Time versus cost tradeoffs for deterministic rendezvous in networks

Cites work

• scientific article; zbMATH DE number 2102782 (Why is no real title available?)
• Almost optimal asynchronous rendezvous in infinite multidimensional grids
• Asynchronous deterministic rendezvous in graphs
• Boundary Patrolling by Mobile Agents with Distinct Maximal Speeds
• Data delivery by energy-constrained mobile agents
• Deterministic Rendezvous in Trees with Little Memory
• Deterministic rendezvous in graphs
• Deterministic rendezvous, treasure hunts and strongly universal exploration sequences
• Finding Your Kids When They Are Lost
• Gathering of asynchronous robots with limited visibility
• How to meet in anonymous network
• How to meet when you forget: log-space rendezvous in arbitrary graphs
• Localization for a system of colliding robots
• Minimax Rendezvous on the Line
• Rendezvous Search on the Line
• Rendezvous of heterogeneous mobile agents in edge-weighted networks
• Rendezvous on the Line when the Players' Initial Distance is Given by an Unknown Probability Distribution
• Rendezvous search when marks are left at the starting points
• Synchronous rendezvous for location-aware agents
• Tell Me Where I Am So I Can Meet You Sooner
• The beachcombers' problem: walking and searching with mobile robots
• The theory of search games and rendezvous.
• Two Dimensional Rendezvous Search

Cited in

(3)

• A new complex network model with multiweights and its synchronization control
• Deterministic rendezvous with different maps
• Rendezvous of heterogeneous mobile agents in edge-weighted networks

This page was built for publication: Rendezvous of heterogeneous mobile agents in edge-weighted networks

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