Collaborative dispersion by silent robots

DOI10.1007/978-3-031-21017-4_17MaRDI QIDQ6155249zbMATH OpenOpenAlexFDO

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)

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

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)

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.

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

Cites work

• scientific article; zbMATH DE number 1263231 (Why is no real title available?)
• A note on the token distribution problem
• Dispersion of mobile robots on grids
• Dispersion of mobile robots: the power of randomness
• Efficient Dispersion of Mobile Agents without Global Knowledge
• Efficient dispersion on an anonymous ring in the presence of weak Byzantine robots
• Fast collaborative graph exploration
• Memory optimal dispersion by anonymous mobile robots
• Near-perfect token distribution
• Strongly adaptive token distribution
• The theory of search games and rendezvous.
• Uniform Deployment of Mobile Agents in Asynchronous Rings
• Uniform multi-agent deployment on a ring
• 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)