Rendezvous of heterogeneous mobile agents in edge-weighted networks

DOI10.1016/J.TCS.2015.05.055zbMATH Open1333.68247DBLPjournals/tcs/DereniowskiKKK15arXiv1406.2008OpenAlexW51870591WikidataQ62048698 ScholiaQ62048698MaRDI QIDQ896142FDOQ896142

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

Publication date: 11 December 2015

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

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})$.

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)

Cites Work

• The theory of search games and rendezvous.
• How to meet when you forget: log-space rendezvous in arbitrary graphs
• Asynchronous deterministic rendezvous in graphs
• Deterministic rendezvous in graphs
• Deterministic Rendezvous in Trees with Little Memory
• Almost Optimal Asynchronous Rendezvous in Infinite Multidimensional Grids
• Two Dimensional Rendezvous Search
• Rendezvous search when marks are left at the starting points
• Rendezvous Search on the Line
• Minimax Rendezvous on the Line
• Title not available (Why is that?)
• How to meet asynchronously at polynomial cost
• Gathering of asynchronous robots with limited visibility
• How to meet in anonymous network
• Title not available (Why is that?)
• Boundary Patrolling by Mobile Agents with Distinct Maximal Speeds
• Data delivery by energy-constrained mobile agents
• Fence patrolling by mobile agents with distinct speeds
• Synchronous Rendezvous for Location-Aware Agents
• Tell Me Where I Am So I Can Meet You Sooner
• Finding Your Kids When They Are Lost
• Rendezvous on the Line when the Players' Initial Distance is Given by an Unknown Probability Distribution
• Localization for a System of Colliding Robots
• The Beachcombers’ Problem: Walking and Searching with Mobile Robots
• Rendezvous of Heterogeneous Mobile Agents in Edge-Weighted Networks

Cited In (3)

• Searching by heterogeneous agents
• A new complex network model with multiweights and its synchronization control
• Deterministic rendezvous with different maps

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)