Article

Using eventually consistent compasses to gather oblivious mobile robots with limited visibility

Authors:

Samia Souissi,

Xavier Défago,

Masafumi YamashitaAuthors Info & Claims

SSS'06: Proceedings of the 8th international conference on Stabilization, safety, and security of distributed systems

Pages 484 - 500

Published: 17 November 2006 Publication History

Abstract

Reaching agreement between a set of mobile robots is one of the most fundamental issues in distributed robotic systems. This problem is often illustrated by the gathering problem, where the robots must self-organize and meet at some (not predetermined) location, without a global coordinate system. While being very simple to express, this problem has the advantage of retaining the inherent difficulty of agreement, namely the question of breaking symmetry between robots. In previous works, it was proved that gathering is solvable in asynchronous model with oblivious robots and limited visibility, as long as the robots share the knowledge of some direction, as provided by a compass. However, the problem has no solution in the semi-synchronous model when robots do not share a compass and cannot detect multiplicity.

In this paper, we define a model in which compasses may be unreliable, and study the solvability of gathering oblivious mobile robots with limited visibility in a semi-synchronous model. In particular, we give an algorithm that solves the problem in finite time in a system where compasses are unstable for some arbitrary long periods, provided that they stabilize eventually. In addition, our algorithm is self-stabilizing.

References

[1]

Suzuki, I., Yamashita, M.: Distributed anonymous mobile robots: Formation of geometric patterns. SIAM Journal of Computing 28(4) (1999) 1347-1363.

Digital Library

Google Scholar

[2]

Dolev, S.: Self-Stabilization. MIT Press (2000).

Digital Library

Google Scholar

[3]

Schneider, M.: Self-stabilization. ACM Computing Surveys 25(1) (1993) 45-67.

Digital Library

Google Scholar

[4]

Cieliebak, M.: Gathering non-oblivious mobile robots. In: Proc. 6th Latin American Symp. on Theoretical Informatics (LATIN'04). (2004) 577-588.

Crossref

Google Scholar

[5]

Cieliebak, M., Flocchini, P., Prencipe, G., Santoro, N.: Solving the robots gathering problem. In: Proc. Intl. Colloquium on Automata, Languages and Programming (ICALP'03). (2003) 1181-1196.

Digital Library

Google Scholar

[6]

Flocchini, P., Prencipe, G., Santoro, N., Widmayer, P.: Gathering of asynchronous robots with limited visibility. Theor. Comput. Sci. 337(1-3) (2005) 147-168.

Digital Library

Google Scholar

[7]

Prencipe, G.: On the feasibility of gathering by autonomous mobile robots. In: Proc. Colloquium on Structural Information and Communication Complexity (SIROCCO'05). (2005) 246-261.

Digital Library

Google Scholar

[8]

Ando, H., Oasa, Y., Suzuki, I., Yamashita, M.: Distributed memoryless point convergence algorithm for mobile robots with limited visibility. IEEE Trans. on Robotics and Automation 15(5) (1999) 818-828.

Crossref

Google Scholar

[9]

Prencipe, G.: Corda: Distributed coordination of a set of autonomous mobile robots. In: Proc. ERSADS'01, Bertinoro, Italy (2001) 185-190.

Google Scholar

[10]

Cohen, R., Peleg, D.: Robot convergence via center-of-gravity algorithms. In: Proc. Colloquium on Structural Information and Communication Complexity (SIROCCO'04). Number 3104 in LNCS (2004) 79-88.

Crossref

Google Scholar

[11]

Agmon, N., Peleg, D.: Fault-tolerant gathering algorithms for autonomous mobile robots. In: Proc. 15th Annual ACM-SIAM Symp. on Discrete Algorithms (SODA'04), Philadelphia, PA, USA (2004) 1070-1078.

Digital Library

Google Scholar

[12]

Défago, X., Gradinariu, M., Messika, S., Raipin-Parvédy, P.: Fault-tolerant and self-stabilizing mobile robots gathering. In Dolev, S., ed.: Proc. 20th Intl. Symp. on Distributed Computing (DISC'06). LNCS (2006).

Digital Library

Google Scholar

Cited By

View all

Bolla KKovacs TFazekas G(2012)Gathering of fat robots with limited visibility and without global navigationProceedings of the 2012 international conference on Swarm and Evolutionary Computation10.1007/978-3-642-29353-5_4(30-38)Online publication date: 29-Apr-2012
https://dl.acm.org/doi/10.1007/978-3-642-29353-5_4
Défago XSouissi S(2008)Non-uniform circle formation algorithm for oblivious mobile robots with convergence toward uniformityTheoretical Computer Science10.1016/j.tcs.2008.01.050396:1-3(97-112)Online publication date: 1-May-2008
https://dl.acm.org/doi/10.1016/j.tcs.2008.01.050
Inuzuka NTomida YIzumi TKatayama YWada K(2008)Gathering Problem of Two Asynchronous Mobile Robots with Semi-dynamic CompassesProceedings of the 15th international colloquium on Structural Information and Communication Complexity10.1007/978-3-540-69355-0_3(5-19)Online publication date: 17-Jun-2008
https://dl.acm.org/doi/10.1007/978-3-540-69355-0_3
Show More Cited By

Index Terms

Using eventually consistent compasses to gather oblivious mobile robots with limited visibility
1. Computer systems organization
  1. Embedded and cyber-physical systems
    1. Robotics
2. Computing methodologies
  1. Artificial intelligence
    1. Control methods
      1. Robotic planning
    2. Planning and scheduling
      1. Robotic planning

Recommendations

Using eventually consistent compasses to gather memory-less mobile robots with limited visibility

Reaching agreement among a set of mobile robots is one of the most fundamental issues in distributed robotic systems. This problem is often illustrated by the gathering problem, where the robots must self-organize and meet at some location not ...
The Gathering Problem for Two Oblivious Robots with Unreliable Compasses

Anonymous mobile robots are often classified into synchronous, semi-synchronous, and asynchronous robots when discussing the pattern formation problem. For semi-synchronous robots, all patterns formable with memory are also formable without memory, with ...
Decentralized navigation of groups of wheeled mobile robots with limited communication

In this paper, we consider a group of wheeled mobile robots, where each robot has very limited information on other robots in the group. We propose a simple bio-inspired decentralized navigation law, which guarantees that all robots will eventually move ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

SSS'06: Proceedings of the 8th international conference on Stabilization, safety, and security of distributed systems

November 2006

589 pages

ISBN:9783540490180

Editors:
Ajoy K. Datta
School of Computer Science, University of Nevada Las Vegas, Las Vegas
,
Maria Gradinariu
Universite Paris 6, LIP6, Paris, France

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 17 November 2006

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 24 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Bolla KKovacs TFazekas G(2012)Gathering of fat robots with limited visibility and without global navigationProceedings of the 2012 international conference on Swarm and Evolutionary Computation10.1007/978-3-642-29353-5_4(30-38)Online publication date: 29-Apr-2012
https://dl.acm.org/doi/10.1007/978-3-642-29353-5_4
Défago XSouissi S(2008)Non-uniform circle formation algorithm for oblivious mobile robots with convergence toward uniformityTheoretical Computer Science10.1016/j.tcs.2008.01.050396:1-3(97-112)Online publication date: 1-May-2008
https://dl.acm.org/doi/10.1016/j.tcs.2008.01.050
Inuzuka NTomida YIzumi TKatayama YWada K(2008)Gathering Problem of Two Asynchronous Mobile Robots with Semi-dynamic CompassesProceedings of the 15th international colloquium on Structural Information and Communication Complexity10.1007/978-3-540-69355-0_3(5-19)Online publication date: 17-Jun-2008
https://dl.acm.org/doi/10.1007/978-3-540-69355-0_3
Studer GHarvey I(2007)A distributed formation algorithm to organize agents with no coordinate agreementProceedings of the 9th European conference on Advances in artificial life10.5555/1771390.1771452(515-524)Online publication date: 10-Sep-2007
https://dl.acm.org/doi/10.5555/1771390.1771452
Katayama YTomida YImazu HInuzuka NWada K(2007)Dynamic compass models and gathering algorithms for autonomous mobile robotsProceedings of the 14th international conference on Structural information and communication complexity10.5555/1760631.1760661(274-288)Online publication date: 5-Jun-2007
https://dl.acm.org/doi/10.5555/1760631.1760661
Souissi SDéfago XYamashita M(2006)Gathering asynchronous mobile robots with inaccurate compassesProceedings of the 10th international conference on Principles of Distributed Systems10.1007/11945529_24(333-349)Online publication date: 12-Dec-2006
https://dl.acm.org/doi/10.1007/11945529_24

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

Using eventually consistent compasses to gather memory-less mobile robots with limited visibility

The Gathering Problem for Two Oblivious Robots with Unreliable Compasses

Decentralized navigation of groups of wheeled mobile robots with limited communication

Comments

Information

Published In

Publisher

Publication History

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