Time optimal gathering of myopic robots on an infinite triangular grid

DOI10.1007/978-3-031-21017-4_18zbMATH Open1522.68601arXiv2204.14042OpenAlexW4312713142MaRDI QIDQ6155253FDOQ6155253

Authors: Pritam Goswami, Avisek Sharma, Satakshi Ghosh, Buddhadeb Sau 

Publication date: 12 June 2023

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

Abstract: This work deals with the problem of gathering $n$ oblivious mobile entities, called robots, at a point (not known beforehand) placed on an infinite triangular grid. The robots are considered to be myopic, i.e., robots have limited visibility. Earlier works of gathering mostly considered the robots either on a plane or on a circle or on a rectangular grid under both full and limited visibility. In the triangular grid, there are two works to the best of our knowledge. The first one is by Cicerone et al. on arbitrary pattern formation where full visibility is considered. The other one by Shibata et al. which considers seven robots with 2- hop visibility that form a hexagon with one robot in the center of the hexagon in a collision-less environment under a fully synchronous scheduler . In this work, we first show that gathering on a triangular grid with 1-hop vision of robots is not possible even under a fully synchronous scheduler if the robots do not agree on any axis. So one axis agreement has been considered in this work (i.e., the robots agree on a direction and its orientation). We have also shown that the lower bound for time is $Omega(n)$ epochs when $n$ number of robots are gathering on an infinite triangular grid. An algorithm is then presented where a swarm of $n$ number of robots with 1-hop visibility can gather within $O(n)$ epochs under a semi-synchronous scheduler. So the algorithm presented here is time optimal.

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

Recommendations

• Gathering Anonymous, Oblivious Robots on a Grid
• Universally optimal gathering under limited visibility
• Gathering of oblivious robots on infinite grids with minimum traveled distance
• Gathering anonymous, oblivious robots on a grid
• Gathering of asynchronous robots with limited visibility

zbMATH Keywords

gatheringtriangular gridlimited visibilityswarm robot

Mathematics Subject Classification ID

Artificial intelligence for robotics (68T40) Distributed algorithms (68W15) Distributed systems (68M14)

Cites Work

• Gathering asynchronous oblivious mobile robots in a ring
• Fault-Tolerant Gathering Algorithms for Autonomous Mobile Robots
• Gathering of asynchronous robots with limited visibility
• Taking advantage of symmetries: Gathering of many asynchronous oblivious robots on a ring
• Title not available (Why is that?)
• Gathering six oblivious robots on anonymous symmetric rings
• Gathering of robots on anonymous grids and trees without multiplicity detection
• Gathering of robots on meeting-points: feasibility and optimal resolution algorithms
• Arbitrary pattern formation on infinite regular tessellation graphs
• Gathering synchronous robots in graphs: from general properties to dense and symmetric topologies
• Fault-tolerant gathering of asynchronous oblivious mobile robots under one-axis agreement

Cited In (4)

• Gathering a Euclidean closed chain of robots in linear time
• Gathering Anonymous, Oblivious Robots on a Grid
• Time optimal gathering of myopic robots on an infinite triangular grid
• Universally optimal gathering under limited visibility

This page was built for publication: Time optimal gathering of myopic robots on an infinite triangular grid

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