Optimal Gathering Over Weber Meeting Nodes in Infinite Grid

DOI10.1142/S0129054122500174MaRDI QIDQ6169957zbMATH OpenOpenAlexFDO

Authors Subhash Bhagat, Abhinav Chakraborty, Bibhuti Das, Krishnendu Mukhopadhyaya

Publication date 15 August 2023

Published in International Journal of Foundations of Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

asynchronousgatheringgridlook-compute-move cyclemeeting nodesWeber meeting nodes

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Abstract: The gathering over meeting nodes problem requires the robots to gather at one of the pre-defined meeting nodes. This paper investigates the problem with respect to the objective function that minimizes the total number of moves made by all the robots. In other words, the sum of the distances traveled by all the robots is minimized while accomplishing the gathering task. The robots are deployed on the nodes of an anonymous two-dimensional infinite grid which has a subset of nodes marked as meeting nodes. The robots do not agree on a global coordinate system and operate under an asynchronous scheduler. A deterministic distributed algorithm has been proposed to solve the problem for all those solvable configurations, and the initial configurations for which the problem is unsolvable have been characterized. The proposed gathering algorithm is optimal with respect to the total number of moves performed by all the robots in order to finalize the gathering.

Cites work

• k-circle formation by disoriented asynchronous robots
• An extension of the Fermat-Torricelli problem
• Computing by mobile robotic sensors
• Computing on rings by oblivious robots: a unified approach for different tasks
• Embedded pattern formation by asynchronous robots without chirality
• Euclidean Constructibility in Graph-Minimization Problems
• Fault-tolerant gathering of asynchronous oblivious mobile robots under one-axis agreement
• Gathering an even number of robots in an odd ring without global multiplicity detection
• Gathering asynchronous oblivious mobile robots in a ring
• Gathering of asynchronous robots with limited visibility
• Gathering of oblivious robots on infinite grids with minimum traveled distance
• Gathering of robots on anonymous grids and trees without multiplicity detection
• Gathering of robots on meeting-points: feasibility and optimal resolution algorithms
• Gathering on rings under the look-compute-move model
• Gathering over meeting nodes in infinite grid
• Gathering over Meeting Nodes in Infinite Grid*
• Gathering robots in graphs: the central role of synchronicity
• Gathering six oblivious robots on anonymous symmetric rings
• scientific article; zbMATH DE number 2038783 (Why is no real title available?)
• Mobile robots gathering algorithm with local weak multiplicity in rings
• Optimal gathering of oblivious robots in anonymous graphs and its application on trees and rings

Cited in

(1)

• Parking problem by oblivious mobile robots in infinite grids

This page was built for publication: Optimal Gathering Over Weber Meeting Nodes in Infinite Grid

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