<p>We investigate gathering algorithms for asynchronous autonomous mobile robots moving in uniform ring-shaped networks. Different from most work using the Look-Compute-Move (LCM) model, we assume that robots have limited visibility and lights. That is, robots can observe nodes only within a certain fixed distance, and emit a color from a set of constant number of colors. We consider gathering algorithms depending on two parameters related to the initial configuration: <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="224_2024_10199_Article_IEq1.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="39" /> </InlineMediaObject> <EquationSource Format="TEX">$M_{init}$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>M</mi> <mrow> <mi mathvariant="italic">init</mi> </mrow> </msub> </math></EquationSource> </InlineEquation>, which denotes the number of nodes between two border nodes, and <InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="224_2024_10199_Article_IEq2.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="36" /> </InlineMediaObject> <EquationSource Format="TEX">$N_{init}$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>N</mi> <mrow> <mi mathvariant="italic">init</mi> </mrow> </msub> </math></EquationSource> </InlineEquation>, which denotes the number of nodes hosting robots between two border nodes. In both cases, a border node is a node hosting one or more robots that may see other robots on exactly one side. Our main contribution is to prove that, if <InlineEquation ID="IEq3"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="224_2024_10199_Article_IEq3.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="39" /> </InlineMediaObject> <EquationSource Format="TEX">$M_{init}$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>M</mi> <mrow> <mi mathvariant="italic">init</mi> </mrow> </msub> </math></EquationSource> </InlineEquation> or <InlineEquation ID="IEq4"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="224_2024_10199_Article_IEq4.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="36" /> </InlineMediaObject> <EquationSource Format="TEX">$N_{init}$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>N</mi> <mrow> <mi mathvariant="italic">init</mi> </mrow> </msub> </math></EquationSource> </InlineEquation> is odd, gathering is always feasible with three or four colors. The proposed algorithms do not require additional assumptions, such as knowledge of the number of robots, multiplicity detection capabilities, or the assumption of towerless initial configurations. These results demonstrate the power of lights to achieve gathering of robots with limited visibility.</p>

Gathering on Rings for Myopic Asynchronous Robots with Lights

期刊论文
发表日期：

2025年1月24日

查看全文

Sayaka Kamei,
Anissa Lamani,
Fukuhito Ooshita,
Sébastien Tixeuil,
Koichi Wada

摘要

We investigate gathering algorithms for asynchronous autonomous mobile robots moving in uniform ring-shaped networks. Different from most work using the Look-Compute-Move (LCM) model, we assume that robots have limited visibility and lights. That is, robots can observe nodes only within a certain fixed distance, and emit a color from a set of constant number of colors. We consider gathering algorithms depending on two parameters related to the initial configuration: $M_{init}$ $M_{init}$ , which denotes the number of nodes between two border nodes, and $N_{init}$ $N_{init}$ , which denotes the number of nodes hosting robots between two border nodes. In both cases, a border node is a node hosting one or more robots that may see other robots on exactly one side. Our main contribution is to prove that, if $M_{init}$ $M_{init}$ or $N_{init}$ $N_{init}$ is odd, gathering is always feasible with three or four colors. The proposed algorithms do not require additional assumptions, such as knowledge of the number of robots, multiplicity detection capabilities, or the assumption of towerless initial configurations. These results demonstrate the power of lights to achieve gathering of robots with limited visibility.