Pattern Formation Problems for Mobile Robots
Pages 236 - 237
Abstract
The gathering over meeting nodes problem requires the mobile robots to gather at one of the pre-defined meeting nodes. The robots are deployed on the nodes of an anonymous two-dimensional infinite grid which has a subset of nodes marked as meeting nodes. This work addresses the solvability of the problem under different settings. The problem has been studied under the objective function that minimizes the total number of moves made by all the robots to finalize the gathering task. A variation of the problem considers two disjoint and finite groups of anonymous robots. The problem also comprises two finite and disjoint sets of heterogeneous meeting nodes. Each robot in the first (resp. second) group must gather at one of the meeting nodes belonging to the first (resp. second) set.
References
[1]
Subhash Bhagat, Abhinav Chakraborty, Bibhuti Das, and Krishnendu Mukhopadhyaya. 2020. Gathering over Meeting Nodes in Infinite Grid. In Algorithms and Discrete Applied Mathematics - 6th International Conference, CALDAM 2020, Hyderabad, India, February 13-15, 2020, Proceedings(Lecture Notes in Computer Science, Vol. 12016), Manoj Changat and Sandip Das (Eds.). Springer, 318–330. https://doi.org/10.1007/978-3-030-39219-2_26
[2]
Subhash Bhagat, Paola Flocchini, Krishnendu Mukhopadhyaya, and Nicola Santoro. 2020. Weak robots performing conflicting tasks without knowing who is in their team. In ICDCN 2020: 21st International Conference on Distributed Computing and Networking, Kolkata, India, January 4-7, 2020, Nandini Mukherjee and Sriram V. Pemmaraju (Eds.). ACM, 29:1–29:6. https://doi.org/10.1145/3369740.3369794
[3]
Serafino Cicerone, Gabriele Di Stefano, and Alfredo Navarra. 2018. Gathering of robots on meeting-points: feasibility and optimal resolution algorithms. Distributed Comput. 31, 1 (2018), 1–50. https://doi.org/10.1007/s00446-017-0293-3
[4]
Gianlorenzo D’Angelo, Gabriele Di Stefano, Ralf Klasing, and Alfredo Navarra. 2016. Gathering of robots on anonymous grids and trees without multiplicity detection. Theor. Comput. Sci. 610(2016), 158–168. https://doi.org/10.1016/j.tcs.2014.06.045
[5]
Ralf Klasing, Euripides Markou, and Andrzej Pelc. 2008. Gathering asynchronous oblivious mobile robots in a ring. Theor. Comput. Sci. 390, 1 (2008), 27–39. https://doi.org/10.1016/j.tcs.2007.09.032
[6]
Gabriele Di Stefano and Alfredo Navarra. 2017. Gathering of oblivious robots on infinite grids with minimum traveled distance. Inf. Comput. 254(2017), 377–391. https://doi.org/10.1016/j.ic.2016.09.004
[7]
Gabriele Di Stefano and Alfredo Navarra. 2017. Optimal gathering of oblivious robots in anonymous graphs and its application on trees and rings. Distributed Comput. 30, 2 (2017), 75–86. https://doi.org/10.1007/s00446-016-0278-7
Index Terms
- Pattern Formation Problems for Mobile Robots
Index terms have been assigned to the content through auto-classification.
Recommendations
Gathering over Meeting Nodes in Infinite Grid*
The gathering over meeting nodes problem asks the robots to gather at one of the pre-defined meeting nodes. The robots are deployed on the nodes of an anonymous two-dimensional infinite grid, which has a subset of nodes marked as meeting nodes. Robots are ...
Gathering over Meeting Nodes in Infinite Grid
Algorithms and Discrete Applied MathematicsAbstractThe gathering on meeting points problem requires the robots to gather at one of the pre-defined meeting points. This paper investigates a discrete version of the problem where the robots and meeting nodes are deployed on the nodes of an anonymous ...
Gathering of Opaque Robots in 3D Space
ICDCN '18: Proceedings of the 19th International Conference on Distributed Computing and NetworkingGathering is a fundamental coordination problem for multi-robot systems. This paper presents a study of the gathering problem for a set of oblivious, autonomous mobile robots in the three dimensional Euclidean space, under obstructed visibility model. ...
Comments
Information & Contributors
Information
Published In
January 2022
298 pages
ISBN:9781450395601
DOI:10.1145/3491003
Copyright © 2022 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 24 January 2022
Check for updates
Author Tags
Qualifiers
- Research-article
- Research
- Refereed limited
Conference
ICDCN '22
ICDCN '22: 23rd International Conference on Distributed Computing and Networking
January 4 - 7, 2022
AA, Delhi, India
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 56Total Downloads
- Downloads (Last 12 months)4
- Downloads (Last 6 weeks)1
Reflects downloads up to 09 Jan 2025
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign inFull Access
View options
View or Download as a PDF file.
PDFeReader
View online with eReader.
eReaderHTML Format
View this article in HTML Format.
HTML Format