Collaborative dispersion by silent robots

DOI10.1007/978-3-031-21017-4_17zbMATH Open1522.68403arXiv2202.05710OpenAlexW4312392439MaRDI QIDQ6155249FDOQ6155249

Authors: Barun Gorain, P. S. Mandal, Kaushik Mondal, Supantha Pandit 

Publication date: 12 June 2023

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Abstract: In the dispersion problem, a set of $k$ co-located mobile robots must relocate themselves in distinct nodes of an unknown network. The network is modeled as an anonymous graph $G=(V,E)$, where the nodes of the graph are not labeled. The edges incident to a node $v$ with degree $d$ are labeled with port numbers in the range $0,1,cdots,d-1$ at $v$. The robots have unique ids in the range $[0,L]$, where $Lgek$, and are initially placed at a source node $s$. Each robot knows only its own id but does not know the ids of the other robots or the values of $L,k$. The task of dispersion was traditionally achieved with the assumption of two types of communication abilities: (a) when some robots are at the same node, they can communicate by exchanging messages between them (b) any two robots in the network can exchange messages between them. In this paper, we ask whether this ability of communication among co-located robots is necessary to achieve dispersion. We show that even if the ability of communication is not available, the task of dispersion by a set of mobile robots can be achieved in a much weaker model where a robot at a node $v$ has the access of following very restricted information at the beginning of any round: (1) am I alone at $v$? (2) the number of robots at $v$ increased or decreased compare to the previous round? We propose a deterministic algorithm that achieves dispersion on any given graph $G=(V,E)$ in time $Oleft(klogL+k^{2}logDeltaight)$, where $Delta$ is the maximum degree of a node in $G$. Each robot uses $O(logL+logDelta)$ additional memory. We also prove that the task of dispersion cannot be achieved by a set of mobile robots with $o(logL+logDelta)$ additional memory.

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

Recommendations

• Optimal dispersion on an anonymous ring in the presence of weak Byzantine robots
• Efficient dispersion on an anonymous ring in the presence of weak Byzantine robots
• Efficient Dispersion of Mobile Agents without Global Knowledge
• Uniform dispersal of asynchronous finite-state mobile robots in presence of holes
• Filling arbitrary connected areas by silent robots with minimum visibility range

zbMATH Keywords

dispersiondeterministic algorithmautonomous mobile robotsanonymous graphstime and memory complexity

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Artificial intelligence for robotics (68T40) Distributed algorithms (68W15)

Cites Work

• The theory of search games and rendezvous.
• Uniform multi-agent deployment on a ring
• Strongly adaptive token distribution
• Fast collaborative graph exploration
• Dispersion of mobile robots on grids
• Efficient dispersion on an anonymous ring in the presence of weak Byzantine robots
• Dispersion of mobile robots: the power of randomness
• Uniform Deployment of Mobile Agents in Asynchronous Rings
• Efficient Dispersion of Mobile Agents without Global Knowledge
• Memory optimal dispersion by anonymous mobile robots
• Near-perfect token distribution
• A note on the token distribution problem
• Title not available (Why is that?)
• Uniform scattering of autonomous mobile robots in a grid
• Want to Gather? No Need to Chatter!

Cited In (10)

• Optimal dispersion on an anonymous ring in the presence of weak Byzantine robots
• Observe and remain silent (communication-less agent location discovery)
• Efficient Dispersion of Mobile Agents without Global Knowledge
• Near-optimal dispersion on arbitrary anonymous graphs
• Efficient dispersion on an anonymous ring in the presence of weak Byzantine robots
• A note on dispersing particles on a line
• Robotic swarm dispersion using wireless intensity signals
• Filling arbitrary connected areas by silent robots with minimum visibility range
• Uniform dispersal of asynchronous finite-state mobile robots in presence of holes
• Uniform Dispersal of Robots with Minimum Visibility Range

This page was built for publication: Collaborative dispersion by silent robots

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