article

Impossibility of gathering by a set of autonomous mobile robots

Author:

Giuseppe PrencipeAuthors Info & Claims

Theoretical Computer Science, Volume 384, Issue 2-3

Pages 222 - 231

https://doi.org/10.1016/j.tcs.2007.04.023

Published: 01 October 2007 Publication History

Abstract

Given a set of n autonomous mobile robots that can freely move on a two dimensional plane, they are required to gather in a position on the plane not fixed in advance (Gathering Problem). The main research question we address in this paper is: Under which conditions can this task be accomplished by the robots? The studied robots are quite simple: they are anonymous, totally asynchronous, they do not have any memory of past computations, they cannot explicitly communicate between each other. We show that this simple task cannot be in general accomplished by the considered system of robots.

References

[1]

N. Agmon, D. Peleg, Fault tolerant gathering algorithms for autonomous mobile robots, in: Proc. 15th Symposium on Discrete Algorithms, SODA 2004, 2004 pp. 1063-1071

Digital Library

Google Scholar

[2]

Ando, H., Oasa, Y., Suzuki, I. and Yamashita, M., A distributed memoryless point convergence algorithm for mobile robots with limited visibility. IEEE Transactions on Robotics and Automation. v15 i5. 818-828.

Google Scholar

[3]

Cieliebak, M., Gathering non-oblivious mobile robots. In: LNCS, vol. 2976. pp. 577-588.

Google Scholar

[4]

M. Cieliebak, P. Flocchini, G. Prencipe, N. Santoro, Solving the gathering problem, in: Proc. 30th International Colloquium on Automata, Languages and Programming, ICALP -03, 2003, pp. 1181-1196

Crossref

Google Scholar

[5]

R. Cohen, D. Peleg, Convergence properties of the gravitational algorithm in asynchronous robot systems, in: Proc. 12th Annual European Symposium on Algorithms, ESA -04, 2004, pp. 228-239

Google Scholar

[6]

R. Cohen, D. Peleg, Robot convergence via center-of-gravity algorithms, in: Proc. 11th International Colloquium On Structural Information And Communication Complexity, SIROCCO 11, 2004, pp. 79-88

Google Scholar

[7]

R. Cohen, D. Peleg, Convergence of autonomous mobile robots with inaccurate sensors and movements, in: Proc. 23rd Annual Symposium on Theoretical Aspects of Computer Science, STACS -06, 2006, pp. 549-560

Digital Library

Google Scholar

[8]

Flocchini, P., Prencipe, G., Santoro, N. and Widmayer, P., Hard tasks for weak robots: The role of common knowledge in pattern formation by autonomous mobile robots. In: LNCS, vol. 1741. pp. 93-102.

Digital Library

Google Scholar

[9]

Flocchini, P., Prencipe, G., Santoro, N. and Widmayer, P., Gathering of autonomous mobile robots with limited visibility. In: LNCS, vol. 2010. pp. 247-258.

Digital Library

Google Scholar

[10]

Prencipe, G., The effect of synchronicity on the behavior of autonomous mobile robots. Theory of Computing Systems. v38. 539-558.

Digital Library

Google Scholar

[11]

Suzuki, I. and Yamashita, M., Distributed anonymous mobile robots: Formation of geometric patterns. SIAM Journal of Computing. v28 i4. 1347-1363.

Digital Library

Google Scholar

Cited By

View all

Kirkpatrick DKostitsyna INavarra APrencipe GSantoro N(2024)On the power of bounded asynchrony: convergence by autonomous robots with limited visibilityDistributed Computing10.1007/s00446-024-00463-737:3(279-308)Online publication date: 9-Apr-2024
https://dl.acm.org/doi/10.1007/s00446-024-00463-7
Castenow JHarbig JMeyer auf der Heide F(2023)Unifying Gathering Protocols for Swarms of Mobile RobotsAlgorithms and Complexity10.1007/978-3-031-30448-4_1(5-16)Online publication date: 13-Jun-2023
https://dl.acm.org/doi/10.1007/978-3-031-30448-4_1
Pramanick SSpourgeon GRaj KMandal P(2022)Asynchronous Line Formation in Presence of Faulty RobotsProceedings of the 9th International Conference on Networking, Systems and Security10.1145/3569551.3569553(75-82)Online publication date: 20-Dec-2022
https://dl.acm.org/doi/10.1145/3569551.3569553
Show More Cited By

Index Terms

Impossibility of gathering by a set of autonomous mobile robots

Recommendations

On the feasibility of gathering by autonomous mobile robots
SIROCCO'05: Proceedings of the 12th international conference on Structural Information and Communication Complexity

Given a set of n autonomous mobile robots that can freely move on a two dimensional plane, they are required to gather in a position of the plane not fixed in advance (Gathering Problem). The main research question we address in this paper is: under ...
Gathering of Mobile Robots Tolerating Multiple Crash Faults
ICDCS '13: Proceedings of the 2013 IEEE 33rd International Conference on Distributed Computing Systems

We study distributed coordination among autonomous mobile robots, focusing on the problem of gathering the robots at a single location. The gathering problem has been solved previously using deterministic algorithms even for robots that are anonymous, ...
Design and Simulation of Autonomous Mobile Robots Obstacle Avoidance System
LNCS on Transactions on Edutainment XIII - Volume 10092

Autonomous mobile robot is a completely unknown or partially unknown, of its complex environment, which requires the ability to avoid obstacles in order to move safely and avoid the collisions while navigating. To solve this problem, it opted to propose ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Theoretical Computer Science

Theoretical Computer Science Volume 384, Issue 2-3

October, 2007

150 pages

ISSN:0304-3975

Issue’s Table of Contents

Publisher

Elsevier Science Publishers Ltd.

United Kingdom

Publication History

Published: 01 October 2007

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

55
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 20 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Kirkpatrick DKostitsyna INavarra APrencipe GSantoro N(2024)On the power of bounded asynchrony: convergence by autonomous robots with limited visibilityDistributed Computing10.1007/s00446-024-00463-737:3(279-308)Online publication date: 9-Apr-2024
https://dl.acm.org/doi/10.1007/s00446-024-00463-7
Castenow JHarbig JMeyer auf der Heide F(2023)Unifying Gathering Protocols for Swarms of Mobile RobotsAlgorithms and Complexity10.1007/978-3-031-30448-4_1(5-16)Online publication date: 13-Jun-2023
https://dl.acm.org/doi/10.1007/978-3-031-30448-4_1
Pramanick SSpourgeon GRaj KMandal P(2022)Asynchronous Line Formation in Presence of Faulty RobotsProceedings of the 9th International Conference on Networking, Systems and Security10.1145/3569551.3569553(75-82)Online publication date: 20-Dec-2022
https://dl.acm.org/doi/10.1145/3569551.3569553
Bhagat SMolla AAgrawal KAzar Y(2021)Min-Max Gathering of Oblivious RobotsProceedings of the 33rd ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3409964.3461829(420-422)Online publication date: 6-Jul-2021
https://dl.acm.org/doi/10.1145/3409964.3461829
Nakai RSudo YWada K(2021)Asynchronous Gathering Algorithms for Autonomous Mobile Robots with LightsStabilization, Safety, and Security of Distributed Systems10.1007/978-3-030-91081-5_27(410-424)Online publication date: 17-Nov-2021
https://dl.acm.org/doi/10.1007/978-3-030-91081-5_27
Bramas QLamani ATixeuil S(2021)Stand up Indulgent GatheringAlgorithms for Sensor Systems10.1007/978-3-030-89240-1_2(17-28)Online publication date: 9-Sep-2021
https://dl.acm.org/doi/10.1007/978-3-030-89240-1_2
Pattanayak DFoerster KMandal PSchmid S(2020)Conic Formation in Presence of Faulty RobotsAlgorithms for Sensor Systems10.1007/978-3-030-62401-9_12(170-185)Online publication date: 9-Sep-2020
https://dl.acm.org/doi/10.1007/978-3-030-62401-9_12
Molla AMondal KMoses W(2020)Efficient Dispersion on an Anonymous Ring in the Presence of Weak Byzantine RobotsAlgorithms for Sensor Systems10.1007/978-3-030-62401-9_11(154-169)Online publication date: 9-Sep-2020
https://dl.acm.org/doi/10.1007/978-3-030-62401-9_11
Alcántara MCastañeda AFlores-Peñaloza DRajsbaum S(2019)The topology of look-compute-move robot wait-free algorithms with hard terminationDistributed Computing10.1007/s00446-018-0345-332:3(235-255)Online publication date: 1-Jun-2019
https://dl.acm.org/doi/10.1007/s00446-018-0345-3
Balabonski TDelga ARieg LTixeuil SUrbain X(2019)Synchronous Gathering without Multiplicity DetectionTheory of Computing Systems10.1007/s00224-017-9828-z63:2(200-218)Online publication date: 1-Feb-2019
https://dl.acm.org/doi/10.1007/s00224-017-9828-z
Show More Cited By

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Abstract

References

Cited By

Index Terms

Recommendations

On the feasibility of gathering by autonomous mobile robots

Gathering of Mobile Robots Tolerating Multiple Crash Faults

Design and Simulation of Autonomous Mobile Robots Obstacle Avoidance System

Comments

Information

Published In

Publisher

Publication History

Author Tags

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations