article

Non-uniform circle formation algorithm for oblivious mobile robots with convergence toward uniformity

Authors:

Xavier Défago,

Samia SouissiAuthors Info & Claims

Theoretical Computer Science, Volume 396, Issue 1-3

Pages 97 - 112

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

Published: 01 May 2008 Publication History

Abstract

This paper presents a distributed algorithm whereby a group of mobile robots self-organize and position themselves into forming a circle in a loosely synchronized environment. In spite of its apparent simplicity, the difficulty of the problem comes from the weak assumptions made on the system. In particular, robots are anonymous, oblivious (i.e., stateless), unable to communicate directly, and disoriented in the sense that they share no knowledge of a common coordinate system. Furthermore, robots' activations are not synchronized. More specifically, the proposed algorithm ensures that robots deterministically form a non-uniform circle in a finite number of steps and converges to a situation in which all robots are located evenly on the boundary of the circle.

References

[1]

Aurenhammer, F., Voronoi Diagrams¿A survey of a fundamental geometric data structure. ACM Computing Surveys. v23 i3. 345-405.

Digital Library

[2]

Balch, T. and Arkin, R.C., Behavior-based Formation Control for Multi-robot Teams. IEEE Transactions on Robotics and Automation. v14 i6. 926-939.

[3]

I. Chatzigiannakis, M. Markou, S. Nikoletseas, Distributed circle formation for anonymous oblivious robots, in: Proc. 3rd Workshop on Efficient and Experimental Algorithms, WEA-04, 2004, pp. 159-174

[4]

I. Chatzigiannakis, S. Nikoletseas, P. Spirakis, On the average and worst-case efficiency of some new distributed communication and control algorithms for ad-hoc mobile networks, in: Proc. 1st ACM Intl. Workshop on Principles of Mobile Computing, POMC-01, 2001, pp. 1-19

[5]

Debest, X.A., Remark About Self-Stabilizing Systems. Communications of the ACM. v38 i2. 115-117.

[6]

X. Defago, A. Konagaya, Circle formation for oblivious anonymous mobile robots with no common sense of orientation, in: Proc. 2nd ACM Intl Workshop on Principles of Mobile Computing, POMC-02, 2002, pp. 97-104

Digital Library

[7]

M.B. Dias, A. Stentz, A free market architecture for distributed control of a multirobot system, in: Proc. 6th Intl. Conf. on Intelligent Autonomous Systems, IAS-00, 2000, pp. 115-122

[8]

Schneider, M., Self-Stabilization. ACM Computing Surveys. v25 i1. 45-67.

Digital Library

[9]

Berg, M., Krefeld, M., Overmars, M. and Schwarzkopf, O., Computational Geometry: Algorithms and Applications. 1998. Springer-Verlag.

Digital Library

[10]

Gervasi, V. and Prencipe, G., Coordination without communication: The case of the flocking problem. Discrete Applied Mathematics. v143 i1-3. 203-223.

Digital Library

[11]

B. Katreniak, Biangular circle formation by asynchronous mobile robots, in: Proc. 12th Intl. Colloquium on Structural Information and Communication Complexity, SIROCCO'05, vol. 3499, 2005, pp. 185-199

Digital Library

[12]

Krieger, M.J.B., Billeter, J.-B. and Keller, L., Ant-like task allocation and recruitment in cooperative robots. Nature. v406 i6799. 992-995.

[13]

S. Souissi, On distributed cooperative mobile robotics: Decomposition of basic problems and study of a self-stabilizing circle formation algorithm, Master Thesis, Japan Advanced Institute of Science and Technology, School of Information Science, 2004

[14]

Sugihara, K. and Suzuki, I., Distributed algorithms for formation of geometric patterns with many mobile robots. Journal of Robotics Systems. v3 i13. 127-139.

[15]

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

Digital Library

[16]

E.W. Weisstein, Reuleaux Triangle, From MathWorld'A Wolfram Web Resource. http://mathworld.wolfram.com/ReuleauxTriangle.html

[17]

Welzl, E., Smallest enclosing disks (balls and ellipsoids). New Results and New Trends in Computer Science. v555. 359-370.

[18]

Y. Dieudonne, O. Labbani-Igbida, F. Petit, Circle formation of weak mobile robots, in: Proc. 8th Intl. Symposium on Stabilization, Safety, and Security of Distributed Systems, SSS-06, vol. 4280, 2006, pp. 262-275

Digital Library

[19]

Dieudonne, Y. and Petit, F., Circle Formation of Weak Robots and Lyndon Words. Information Processing Letters. v104 i4. 156-162.

Digital Library

[20]

Y. Dieudonne, F. Petit, Swing words to make circle formation quiescent, in: Proc. Fourteenth Intl. Colloquium on Structural Information and Communication Complexity, SIROCCO -07, vol. 4474, 2007, pp. 166-179

Digital Library

[21]

Y. Dieudonne, F. Petit, A scatter of weak robots, Technical Report RR07-10, LARIA, CNRS, Amiens, France, 2007

[22]

P. Flocchini, G. Prencipe, N. Santoro, P. Widmayer, Hard tasks for weak robots: The role of common knowledge in pattern formation by autonomous mobile robots, in: Proc. 10th Intl. Symp. on Algorithms and Computation, ISAAC-99, vol. 1741, 1999, pp. 93-102

Digital Library

[23]

Uny Cao, Y., Fukunaga, A.S. and Kahng, A.B., Cooperative mobile robotics: Antecedents and directions. Autonomous Robots. v4. 1-23.

Digital Library

[24]

P. Flocchini, G. Prencipe, N. Santoro, P. Widmayer, Pattern formation by autonomous robots without chirality, in: Proc. 8th Intl. Colloquium on Structural Information and Communication Complexity, SIROCCO'01, 2001, pp. 147-162

[25]

Bonabeau, E., Dorigo, M. and Theraulaz, G., Swarm Intelligence: From Natural to Artificial Systems. 1999. Oxford University Press.

Digital Library

[26]

Flocchini, P., Prencipe, G., Santoro, N. and Widmayer, P., Gathering of asynchronous robots with limited visibility. Theoretical Computer Science. v337 i1-3. 147-168.

Digital Library

[27]

G. Prencipe, Instantaneous actions vs. full asynchronicity: Controlling and coordinating a set of autonomous mobile robots, in: Proc. 7th Italian Conference on Theoretical Computer Science, ICTCS-01, 2001, pp. 154-171

Digital Library

[28]

G. Prencipe, Corda: Distributed coordination of a set of autonomous mobile robots, in: Proc. 4th European Research Seminar on Advances in Distributed Systems, ERSADS-01, 2001, pp. 185-190

[29]

G. Prencipe, On the feasibility of gathering by autonomous mobile robots, in: Proc. 12th Colloquium on Structural Information and Communication Complexity, SIROCCO'05, vol. 3499, 2005, pp. 246-261

Digital Library

[30]

S. Souissi, X. Defago, M. Yamashita, Using eventually consistent compasses to gather oblivious mobile robots with limited visibility, in: Proc. 8th Intl. Symp. on Stabilization, Safety, and Security of Distributed Systems, SSS-06, vol. 4280, 2006, pp. 471-487

Digital Library

[31]

P. Flocchini, G. Prencipe, N. Santoro, Self-deployment algorithms for mobile sensors on a ring, in: Proc. 2nd Intl. Workshop on Algorithmic Aspects of Wireless Sensor Networks, Algosensors-06, vol. 4240, 2006, pp. 59-70

Digital Library

[32]

D. Peleg, Distributed coordination algorithms for mobile robot swarms: New directions and challenges, in: Proc. 7th Intl. Workshop on Distributed Computing, IWDC-05, 2005, pp. 1-12

Digital Library

[33]

Agmon, N. and Peleg, D., Fault-tolerant gathering algorithms for autonomous mobile robots. SIAM Journal on Computation. v36 i1. 56-82.

Digital Library

Cited By

Mondal MSingh SChaudhuri S(2024)K Circle Formation by Swarm Robots on a GridProceedings of the 25th International Conference on Distributed Computing and Networking10.1145/3631461.3632304(334-339)Online publication date: 4-Jan-2024
https://dl.acm.org/doi/10.1145/3631461.3632304
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
Mondal MGan Chaudhuri S(2022)Uniform Scattering of Robots on Alternate Nodes of a GridProceedings of the 23rd International Conference on Distributed Computing and Networking10.1145/3491003.3493231(254-259)Online publication date: 4-Jan-2022
https://dl.acm.org/doi/10.1145/3491003.3493231
Show More Cited By

Index Terms

Recommendations

Circle formation by asynchronous fat robots with limited visibility
ICDCIT'12: Proceedings of the 8th international conference on Distributed Computing and Internet Technology

This paper proposes a distributed algorithm for circle formation by multiple autonomous mobile robots. The vision of each robot is limited to a maximum distance. The robots do not store past actions or records of past data. They are anonymous and cannot ...
Arbitrary pattern formation by asynchronous, anonymous, oblivious robots

From an engineering point of view, the problem of coordinating a set of autonomous, mobile robots for the purpose of cooperatively performing a task has been studied extensively over the past decade. In contrast, in this paper we aim to understand the ...
Circle formation of weak mobile robots

We consider distributed systems made of weak mobile robots, that is, mobile devices, equipped with sensors, that are anonymous, autonomous, disoriented, and oblivious. The Circle Formation Problem (CFP) consists of the design of a protocol insuring that,...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Theoretical Computer Science

Theoretical Computer Science Volume 396, Issue 1-3

May, 2008

305 pages

ISSN:0304-3975

Issue’s Table of Contents

Copyright © Elsevier Ltd © 2008.

Publisher

Elsevier Science Publishers Ltd.

United Kingdom

Publication History

Published: 01 May 2008

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

22
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

Mondal MSingh SChaudhuri S(2024)K Circle Formation by Swarm Robots on a GridProceedings of the 25th International Conference on Distributed Computing and Networking10.1145/3631461.3632304(334-339)Online publication date: 4-Jan-2024
https://dl.acm.org/doi/10.1145/3631461.3632304
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
Mondal MGan Chaudhuri S(2022)Uniform Scattering of Robots on Alternate Nodes of a GridProceedings of the 23rd International Conference on Distributed Computing and Networking10.1145/3491003.3493231(254-259)Online publication date: 4-Jan-2022
https://dl.acm.org/doi/10.1145/3491003.3493231
Das BMukhopadhyaya K(2022)k-Circle Formation by Oblivious Mobile RobotsProceedings of the 23rd International Conference on Distributed Computing and Networking10.1145/3491003.3491299(238-239)Online publication date: 4-Jan-2022
https://dl.acm.org/doi/10.1145/3491003.3491299
Mondal MChaudhuri S(2020)Uniform Circle Formation by Fat Robots Under Non-Uniform Visibility RangesProceedings of the 21st International Conference on Distributed Computing and Networking10.1145/3369740.3372779(1-5)Online publication date: 4-Jan-2020
https://dl.acm.org/doi/10.1145/3369740.3372779
Poudel PSharma G(2020)Fast Uniform Scattering on a Grid for Asynchronous Oblivious RobotsStabilization, Safety, and Security of Distributed Systems10.1007/978-3-030-64348-5_17(211-228)Online publication date: 18-Nov-2020
https://dl.acm.org/doi/10.1007/978-3-030-64348-5_17
Poudel PSharma GHansdah RKrishnaswamy DVaidya N(2019)Time-optimal uniform scattering in a gridProceedings of the 20th International Conference on Distributed Computing and Networking10.1145/3288599.3288622(228-237)Online publication date: 4-Jan-2019
https://dl.acm.org/doi/10.1145/3288599.3288622
Yu MWang HXie GJin K(2018)Event-triggered circle formation control for second-order-agent systemNeurocomputing10.1016/j.neucom.2017.08.061275:C(462-469)Online publication date: 31-Jan-2018
https://dl.acm.org/doi/10.1016/j.neucom.2017.08.061
Di Luna GFlocchini PGan Chaudhuri SPoloni FSantoro NViglietta G(2017)Mutual visibility by luminous robots without collisionsInformation and Computation10.1016/j.ic.2016.09.005254:P3(392-418)Online publication date: 1-Jun-2017
https://dl.acm.org/doi/10.1016/j.ic.2016.09.005
Flocchini PPrencipe GSantoro NViglietta G(2017)Distributed computing by mobile robotsDistributed Computing10.1007/s00446-016-0291-x30:6(413-457)Online publication date: 1-Dec-2017
https://dl.acm.org/doi/10.1007/s00446-016-0291-x
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.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents