Article

Gathering of Asynchronous Oblivious Robots with Limited Visibility

Authors:

Paola Flocchini,

Giuseppe Prencipe,

Nicola Santoro,

Peter WidmayerAuthors Info & Claims

STACS '01: Proceedings of the 18th Annual Symposium on Theoretical Aspects of Computer Science

Pages 247 - 258

Published: 15 February 2001 Publication History

Abstract

We consider a collection of robots which are identical (anonymous), have limited visibility of the environment, and no memory of the past (oblivious); furthermore, they are totally asynchronous in their actions, computations, and movements. We show that, even in such a totally asynchronous setting, it is possible for the robots to gather in the same location in finite time, provided they have a compass.

References

[1]

H. Ando, Y. Oasa, I. Suzuki, and M. Yamashita. A Distributed Memoryless Point Convergence Algorithm for Mobile Robots with Limited Visibility. IEEE Trans. on Robotics and Autom., 15(5):818-828, 1999.

Google Scholar

[2]

G. Beni and S. Hackwood. Coherent Swarm Motion Under Distributed Control. In Proc. DARS'92, pages 39-52, 1992.

Google Scholar

[3]

E. H. Durfee. Blissful Ignorance: Knowing Just Enough to Coordinate Well. In ICMAS, pages 406-413, 1995.

Google Scholar

[4]

P. Flocchini, G. Prencipe, N. Santoro, and P. Widmayer. Hard Tasks for Weak Robots: The Role of Common Knowledge in Pattern Formation by Autonomous Mobile Robots. In ISAAC '99, pages 93-102.

Crossref

Google Scholar

[5]

P. Flocchini, G. Prencipe, N. Santoro, and P. Widmayer. Limited Visibility Gathering by a Set of Autonomous Mobile Robots. Technical Report TR-00-09, Carleton University, 2000.

Google Scholar

[6]

D. Jung, G. Cheng, and A. Zelinsky. Experiments in Realising Cooperation between Autonomous Mobile Robots. In 5th International Symposium on Experimental Robotics (ISER), June 1997.

Crossref

Google Scholar

[7]

Y. Kawauchi and M. Inaba and. T. Fukuda. A Principle of Decision Making of Cellular Robotic System (CEBOT). In Proc. IEEE Conf. on Robotics and Automation, pages 833-838, 1993.

Google Scholar

[8]

M. J Matarić. Interaction and Intelligent Behavior. PhD thesis, MIT, May 1994.

Crossref

Google Scholar

[9]

S. Murata, H. Kurokawa, and S. Kokaji. Self-Assembling Machine. In Proc. IEEE Conf. on Robotics and Autom., pages 441-448, 1994.

Google Scholar

[10]

K. Sugihara and I. Suzuki. Distributed Algorithms for Formation of Geometric Patterns with Many Mobile Robots. J. of Robotics Systems, 13:127-139, 1996.

Google Scholar

[11]

I. Suzuki and M. Yamashita. Distributed anonymous mobile robots. In Proc. of 3rd International Colloquium on Structural Information and Communication Complexity, pages 313-330, Siena, 1996.

Google Scholar

[12]

I. Suzuki and M. Yamashita. Distributed Anonymous Mobile Robots: Formation of Geometric Patterns. SIAM J. Comput., 28(4):1347-1363, 1999.

Crossref

Google Scholar

Cited By

View all

Eftekhari MKranakis EKrizanc DMorales-Ponce ONarayanan LOpatrny JShende S(2016)Distributed algorithms for barrier coverage using relocatable sensorsDistributed Computing10.1007/s00446-016-0267-x29:5(361-376)Online publication date: 1-Oct-2016
https://dl.acm.org/doi/10.1007/s00446-016-0267-x
Dieudonné YPelc A(2015)Deterministic polynomial approach in the planeDistributed Computing10.1007/s00446-014-0216-528:2(111-129)Online publication date: 1-Apr-2015
https://dl.acm.org/doi/10.1007/s00446-014-0216-5
Czyzowicz JKranakis EPacheco EPająk D(2015)Information Spreading by Mobile Particles on a LinePost-Proceedings of the 22nd International Colloquium on Structural Information and Communication Complexity - Volume 943910.1007/978-3-319-25258-2_20(285-298)Online publication date: 14-Jul-2015
https://dl.acm.org/doi/10.1007/978-3-319-25258-2_20
Show More Cited By

Gathering of Asynchronous Oblivious Robots with Limited Visibility
1. Human-centered computing
  1. Collaborative and social computing
    1. Collaborative and social computing systems and tools
2. Software and its engineering
  1. Software organization and properties
    1. Software system structures

Recommendations

Gathering of asynchronous robots with limited visibility

In this paper we study the problem of gathering a collection of identical oblivious mobile robots in the same location of the plane. Previous investigations have focused mostly on the unlimited visibility setting, where each robot can always see all the ...
Gathering Asynchronous Swarm Robots under Nonuniform Limited Visibility
ICDCIT 2015: Proceedings of the 11th International Conference on Distributed Computing and Internet Technology - Volume 8956

This paper proposes a distributed algorithm for gathering a group of autonomous, homogeneous, oblivious, asynchronous mobile robots having limited visibility sensing ranges. To the best of our knowledge, all reported results have assumed that the ...
Asynchronous Ring Gathering by Oblivious Robots with Limited Vision
SRDSW '14: Proceedings of the 2014 IEEE 33rd International Symposium on Reliable Distributed Systems Workshops

We investigate in this paper the gathering problem on ring shaped networks where the aim is to ensure that a collection of identical, oblivious and asynchronous mobile robots meet (gather) in one location not known in advance. Robots operate in cycles ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

STACS '01: Proceedings of the 18th Annual Symposium on Theoretical Aspects of Computer Science

February 2001

574 pages

ISBN:3540416951

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 15 February 2001

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

41
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 20 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Eftekhari MKranakis EKrizanc DMorales-Ponce ONarayanan LOpatrny JShende S(2016)Distributed algorithms for barrier coverage using relocatable sensorsDistributed Computing10.1007/s00446-016-0267-x29:5(361-376)Online publication date: 1-Oct-2016
https://dl.acm.org/doi/10.1007/s00446-016-0267-x
Dieudonné YPelc A(2015)Deterministic polynomial approach in the planeDistributed Computing10.1007/s00446-014-0216-528:2(111-129)Online publication date: 1-Apr-2015
https://dl.acm.org/doi/10.1007/s00446-014-0216-5
Czyzowicz JKranakis EPacheco EPająk D(2015)Information Spreading by Mobile Particles on a LinePost-Proceedings of the 22nd International Colloquium on Structural Information and Communication Complexity - Volume 943910.1007/978-3-319-25258-2_20(285-298)Online publication date: 14-Jul-2015
https://dl.acm.org/doi/10.1007/978-3-319-25258-2_20
Dieudonné YPelc AKhanna S(2013)Anonymous meeting in networksProceedings of the twenty-fourth annual ACM-SIAM symposium on Discrete algorithms10.5555/2627817.2627870(737-747)Online publication date: 6-Jan-2013
https://dl.acm.org/doi/10.5555/2627817.2627870
Eftekhari MKranakis EKrizanc DMorales-Ponce ONarayanan LOpatrny JShende SFatourou PTaubenfeld G(2013)Distributed algorithms for barrier coverage using relocatable sensorsProceedings of the 2013 ACM symposium on Principles of distributed computing10.1145/2484239.2484258(383-392)Online publication date: 22-Jul-2013
https://dl.acm.org/doi/10.1145/2484239.2484258
Dieudonné YPelc AVillain VFatourou PTaubenfeld G(2013)How to meet asynchronously at polynomial costProceedings of the 2013 ACM symposium on Principles of distributed computing10.1145/2484239.2484245(92-99)Online publication date: 22-Jul-2013
https://dl.acm.org/doi/10.1145/2484239.2484245
Fraigniaud PPelc A(2013)Delays Induce an Exponential Memory Gap for Rendezvous in TreesACM Transactions on Algorithms10.1145/2438645.24386499:2(1-24)Online publication date: 1-Mar-2013
https://dl.acm.org/doi/10.1145/2438645.2438649
Dieudonné YPelc APeleg D(2012)Gathering despite mischiefProceedings of the twenty-third annual ACM-SIAM symposium on Discrete algorithms10.5555/2095116.2095161(527-540)Online publication date: 17-Jan-2012
https://dl.acm.org/doi/10.5555/2095116.2095161
Czyzowicz JPelc ALabourel A(2012)How to meet asynchronously (almost) everywhereACM Transactions on Algorithms10.1145/2344422.23444278:4(1-14)Online publication date: 4-Oct-2012
https://dl.acm.org/doi/10.1145/2344422.2344427
Czyzowicz JKosowski APelc ABlelloch GHerlihy M(2012)Time vs. space trade-offs for rendezvous in treesProceedings of the twenty-fourth annual ACM symposium on Parallelism in algorithms and architectures10.1145/2312005.2312007(1-10)Online publication date: 25-Jun-2012
https://dl.acm.org/doi/10.1145/2312005.2312007
Show More Cited By

Abstract

References

Cited By

Recommendations

Gathering of asynchronous robots with limited visibility

Gathering Asynchronous Swarm Robots under Nonuniform Limited Visibility

Asynchronous Ring Gathering by Oblivious Robots with Limited Vision

Comments

Information

Published In

Publisher

Publication History

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations