Optimal Gathering Over Weber Meeting Nodes in Infinite Grid
From MaRDI portal
Publication:6169957
DOI10.1142/S0129054122500174arXiv2202.03350OpenAlexW4285800715MaRDI QIDQ6169957
Krishnendu Mukhopadhyaya, Subhash Bhagat, Abhinav Chakraborty, Bibhuti Das
Publication date: 15 August 2023
Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/2202.03350
Cites Work
- Unnamed Item
- Computing on rings by oblivious robots: a unified approach for different tasks
- Gathering of oblivious robots on infinite grids with minimum traveled distance
- Gathering of asynchronous robots with limited visibility
- An extension of the Fermat-Torricelli problem
- Gathering over meeting nodes in infinite grid
- Gathering of robots on anonymous grids and trees without multiplicity detection
- Gathering of robots on meeting-points: feasibility and optimal resolution algorithms
- \(k\)-circle formation by disoriented asynchronous robots
- Gathering robots in graphs: the central role of synchronicity
- Gathering on rings under the look-compute-move model
- Embedded pattern formation by asynchronous robots without chirality
- Optimal gathering of oblivious robots in anonymous graphs and its application on trees and rings
- Gathering six oblivious robots on anonymous symmetric rings
- Gathering asynchronous oblivious mobile robots in a ring
- 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
- Mobile Robots Gathering Algorithm with Local Weak Multiplicity in Rings
- Gathering over Meeting Nodes in Infinite Grid*
- Computing by Mobile Robotic Sensors
- Euclidean Constructibility in Graph-Minimization Problems
Related Items (1)
This page was built for publication: Optimal Gathering Over Weber Meeting Nodes in Infinite Grid
