Skip to main content
SpringerLink
Log in

Computing on Rings by Oblivious Robots: A Unified Approach for Different Tasks

  • Published:
Algorithmica Aims and scope Submit manuscript

Abstract

A set of autonomous robots have to collaborate in order to accomplish a common task in a ring-topology where neither nodes nor edges are labeled (that is, the ring is anonymous). We present a unified approach to solve three important problems: the exclusive perpetual exploration, the exclusive perpetual clearing, and the gathering problems. In the first problem, each robot aims at visiting each node infinitely often while avoiding that two robots occupy a same node (exclusivity property); in exclusive perpetual clearing (also known as graph searching), the team of robots aims at clearing the whole ring infinitely often (an edge is cleared if it is traversed by a robot or if both its endpoints are occupied); and in the gathering problem, all robots must eventually occupy the same node. We investigate these tasks in the Look–Compute–Move model where the robots cannot communicate but can perceive the positions of other robots. Each robot is equipped with visibility sensors and motion actuators, and it operates in asynchronous cycles. In each cycle, a robot takes a snapshot of the current global configuration (Look), then, based on the perceived configuration, takes a decision to stay idle or to move to one of its adjacent nodes (Compute), and in the latter case it eventually moves to this neighbor (Move). Moreover, robots are endowed with very weak capabilities. Namely, they are anonymous, asynchronous, oblivious, uniform (execute the same algorithm) and have no common sense of orientation. In this setting, we devise algorithms that, starting from an exclusive and rigid (i.e. aperiodic and asymmetric) configuration, solve the three above problems in anonymous ring-topologies.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9
Fig. 10
Fig. 11
Fig. 12
Fig. 13
Fig. 14
Fig. 15

Similar content being viewed by others

References

  1. Ambühl, C., Gąsieniec, L., Pelc, A., Radzik, T., Zhang, X.: Tree exploration with logarithmic memory. ACM Trans. Algorithms 7(2), 17:1–17:21 (2011)

    Article  Google Scholar 

  2. Baldoni, R., Bonnet, F., Milani, A., Raynal, M.: Anonymous graph exploration without collision by mobile robots. Inf. Process. Lett. 109(2), 98–103 (2008)

    Article  MathSciNet  Google Scholar 

  3. Baldoni, R., Bonnet, F., Milani, A., Raynal, M.: On the solvability of anonymous partial grids exploration by mobile robots. In: Proceedings of the 12th International Conference On Principles Of Distributed Systems (OPODIS). volume 5401 of Lecture Notes in Computer Science, pp. 428–445. Springer (2008)

  4. Bampas, E., Czyzowicz, J., Gąsieniec, L., Ilcinkas, D., Labourel, A.: Almost optimal asynchronous rendezvous in infinite multidimensional grids. In: Proceedings of the 24th International Symposium on Distributed Computing (DISC). volume 6343 of Lecture Notes in Computer Science, pp. 297–311 (2010)

  5. Bienstock, D., Seymour, P.D.: Monotonicity in graph searching. J. Algorithms 12(2), 239–245 (1991)

    Article  MATH  MathSciNet  Google Scholar 

  6. Blin, L., Milani, A., Potop-Butucaru, M., Tixeuil, S.: Exclusive perpetual ring exploration without chirality. In: Proceedings of the 24th International Symposium on Distributed Computing (DISC). volume 6343 of Lecture Notes in Computer Science, pp. 312–327 (2010)

  7. Blin, L., Burman, J., Nisse, N.: Exclusive graph searching. In: Proceedings of the 21st European Symposium on Algorithms (ESA). volume 8125 of Lecture Notes in Computer Science, pp. 181–192. Springer (2013)

  8. Bonnet, F., Milani, A., Potop-Butucaru, M., Tixeuil, S.: Asynchronous exclusive perpetual grid exploration without sense of direction. In: Proceedings of the 15th International Conference On Principles Of Distributed Systems (OPODIS). volume 7109 of Lecture Notes in Computer Science, pp. 251–265. Springer (2011)

  9. Brandes, P., Degener, B., Kempkes, B., Meyer auf der Heide, F.: Energy-efficient strategies for building short chains of mobile robots locally. Theor. Comput. Sci. 509, 97–112 (2013)

    Article  MATH  MathSciNet  Google Scholar 

  10. Clément, J., Défago, X., Potop-Butucaru, M.G., Izumi, T., Messika, S.: The cost of probabilistic agreement in oblivious robot networks. Inf. Process. Lett. 110(11), 431–438 (2010)

    Article  MATH  Google Scholar 

  11. Cohen, R., Fraigniaud, P., Ilcinkas, D., Korman, A., Peleg, D.: Label-guided graph exploration by a finite automaton. ACM Trans. Algorithms 4(4), 42:1–42:18 (2008)

    Article  MathSciNet  Google Scholar 

  12. Czyzowicz, J., Gąsieniec, L., Pelc, A.: Gathering few fat mobile robots in the plane. Theor. Comput. Sci. 410(6–7), 481–499 (2009)

    Article  MATH  Google Scholar 

  13. D’Angelo, G., Di Stefano, G., Navarra, A.: Gathering of six robots on anonymous symmetric rings. In: Proceedings of the 18th International Colloquium on Structural Information and Commnication Complexity (SIROCCO). volume 6796 of Lecture Notes in Computer Science, pp. 174–185 (2011)

  14. D’Angelo, G., Di Stefano, G., Klasing, R., Navarra, A.: Gathering of robots on anonymous grids without multiplicity detection. In: Proceedings of the 19th International Colloquium on Structural Information and Communication Complexity (SIROCCO). volume 7355 of Lecture Notes in Computer Science, pp. 327–338 (2012)

  15. D’Angelo, G., Di Stefano, G., Navarra, A.: How to gather asynchronous oblivious robots on anonymous rings. In: Proceedings of the 26th International Symposium on Distributed Computing (DISC). volume 7611 of Lecture Notes in Computer Science, pp. 330–344 (2012)

  16. D’Angelo, G., Di Stefano, G., Navarra, A.: Gathering asynchronous and oblivious robots on basic graph topologies under the look-compute-move model. In: Alpern, S., Fokkink, R., Gąsieniec, L., Lindelauf, R., Subrahmanian, V. (eds.) Search Theory: A Game Theoretic Perspective, pp. 197–222. Springer, Berlin (2013)

    Chapter  Google Scholar 

  17. D’Angelo, G., Di Stefano, G., Navarra, A., Nisse, N., Suchan, K.: A unified approach for different tasks on rings in robot-based computing systems. In: Proceedings of the 15th IEEE IPDPS Workshop on Advances in Parallel and Distributed Computing Models (APDCM), pp. 667–676 (2013)

  18. Devismes, S., Petit, F., Tixeuil, S.: Optimal probabilistic ring exploration by semi-synchronous oblivious robots. In: Proceedings of the 16th International Colloquium on Structural Information and Communication Complexity (SIROCCO). volume 5869 of Lecture Notes in Computer Science, pp. 195–208 (2009)

  19. Dieudonne, Y., Petit, F.: Scatter of robots. Parallel Process. Lett. 19(1), 175–184 (2009)

    Article  MathSciNet  Google Scholar 

  20. Flocchini, P., Ilcinkas, D., Pelc, A., Santoro, N.: Remembering without memory: tree exploration by asynchronous oblivious robots. Theor. Comput. Sci. 411(14–15), 1583–1598 (2010)

    Article  MATH  MathSciNet  Google Scholar 

  21. Flocchini, P., Prencipe, G., Santoro, N.: Distributed Computing by Oblivious Mobile Robots. Morgan and Claypool, San Rafael (2012)

    Google Scholar 

  22. Flocchini, P., Ilcinkas, D., Pelc, A., Santoro, N.: Computing without communicating: ring exploration by asynchronous oblivious robots. Algorithmica 65, 562–583 (2013)

    Article  MATH  MathSciNet  Google Scholar 

  23. Fomin, F.V., Thilikos, D.M.: An annotated bibliography on guaranteed graph searching. Theoret. Comput. Sci. 399(3), 236–245 (2008)

    Article  MATH  MathSciNet  Google Scholar 

  24. Ilcinkas, D., Nisse, N., Soguet, D.: The cost of monotonicity in distributed graph searching. Distrib. Comput. 22(2), 117–127 (2009)

    Article  MATH  Google Scholar 

  25. Izumi, T., Izumi, T., Kamei, S., Ooshita, F.: Mobile robots gathering algorithm with local weak multiplicity in rings. In: Proceedings of the 17th International Colloquium on Structural Information and Communication Complexity (SIROCCO). volume 6058 of Lecture Notes in Computer Science, pp. 101–113 (2010)

  26. Izumi, T., Izumi, T., Kamei, S., Ooshita, F.: Feasibility of polynomial-time randomized gathering for oblivious mobile robots. IEEE Trans. Parallel Distrib. Syst. 24(4), 716–723 (2013)

    Article  Google Scholar 

  27. Kamei, S., Lamani, A., Ooshita, F., Tixeuil, S.: Asynchronous mobile robot gathering from symmetric configurations. In: Proceedings of the 18th International Colloquium on Structural Information and Communication Complexity (SIROCCO). volume 6796 of Lecture Notes in Computer Science, pp. 150–161 (2011)

  28. Kamei, S., Lamani, A., Ooshita, F., Tixeuil, S.: Gathering an even number of robots in an odd ring without global multiplicity detection. In: Proceedings of the 37th International Symposium on Mathematical Foundations of Computer Science (MFCS). volume 7464 of Lecture Notes in Computer Science, pp. 542–553 (2012)

  29. Kempkes, B., Kling, P., Meyer auf der Heide, F.: Optimal and competitive runtime bounds for continuous, local gathering of mobile robots. In: Proceedings of the 24th Annual ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pp. 18–26. ACM (2012)

  30. Klasing, R., Markou, E., Pelc, A.: Gathering asynchronous oblivious mobile robots in a ring. Theor. Comput. Sci. 390, 27–39 (2008)

    Article  MATH  MathSciNet  Google Scholar 

  31. Klasing, R., Kosowski, A., Navarra, A.: Taking advantage of symmetries: gathering of many asynchronous oblivious robots on a ring. Theor. Comput. Sci. 411, 3235–3246 (2010)

    Article  MATH  MathSciNet  Google Scholar 

  32. Pelc, A.: Deterministic rendezvous in networks: a comprehensive survey. Networks 59(3), 331–347 (2012)

    Article  MathSciNet  Google Scholar 

  33. Prencipe, G.: Impossibility of gathering by a set of autonomous mobile robots. Theor. Comput. Sci. 384, 222–231 (2007)

    Article  MATH  MathSciNet  Google Scholar 

Download references

Acknowledgments

This work has been partially supported by the Research Grant 2010N5K7EB ‘PRIN 2010’ ARS TechnoMedia (Algoritmica per le Reti Sociali Tecno-mediate) from the Italian Ministry of University and Research, Project ECOS-SUD Chile (Action ECOS C12E03), Inria Associated Team AlDyNet and Basal-CMM of Conicyt Chile.

Author information

Authors and Affiliations

  1. Gran Sasso Science Institute (GSSI), L’Aquila, Italy

    Gianlorenzo D’Angelo

  2. Dipartimento di Ingegneria e Scienze dell’Informazione e Matematica, Università degli Studi dell’Aquila, Coppito L’Aquila, Italy

    Gabriele Di Stefano

  3. Dipartimento di Matematica e Informatica, Università degli Studi di Perugia, Perugia, Italy

    Alfredo Navarra

  4. COATI Project, INRIA, Sophia Antipolis, France

    Nicolas Nisse

  5. University Nice Sophia Antipolis, CNRS, I3S, UMR 7271, Sophia Antipolis, France

    Nicolas Nisse

  6. Facultad de Ingeniería y Ciencias, Universidad Adolfo Ibáñez, Región Metropolitana, Chile

    Karol Suchan

  7. WMS - Faculty of Science and Engineering, AGH - University of Science and Technology, Kraków, Poland

    Karol Suchan

Authors
  1. Gianlorenzo D’Angelo
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Gabriele Di Stefano
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Alfredo Navarra
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Nicolas Nisse
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Karol Suchan
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Gianlorenzo D’Angelo.

Additional information

Preliminary results concerning this work have been presented in the 15th IEEE IPDPS Workshop on Advances in Parallel and Distributed Computing Models (APDCM) [17].

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

D’Angelo, G., Di Stefano, G., Navarra, A. et al. Computing on Rings by Oblivious Robots: A Unified Approach for Different Tasks. Algorithmica 72, 1055–1096 (2015). https://doi.org/10.1007/s00453-014-9892-6

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00453-014-9892-6

Keywords

Search

Navigation