TuringMobile: A Turing Machine of Oblivious Mobile Robots with Limited Visibility and Its Applications

Authors Giuseppe A. Di Luna, Paola Flocchini, Nicola Santoro, Giovanni Viglietta



PDF
Thumbnail PDF

File

LIPIcs.DISC.2018.19.pdf
  • Filesize: 0.51 MB
  • 18 pages

Document Identifiers

Author Details

Giuseppe A. Di Luna
  • Aix-Marseille University and LiS Laboratory, Marseille, France
Paola Flocchini
  • University of Ottawa, Ottawa, Canada
Nicola Santoro
  • Carleton University, Ottawa, Canada
Giovanni Viglietta
  • JAIST, Nomi City, Japan

Cite AsGet BibTex

Giuseppe A. Di Luna, Paola Flocchini, Nicola Santoro, and Giovanni Viglietta. TuringMobile: A Turing Machine of Oblivious Mobile Robots with Limited Visibility and Its Applications. In 32nd International Symposium on Distributed Computing (DISC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 121, pp. 19:1-19:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.DISC.2018.19

Abstract

In this paper we investigate the computational power of a set of mobile robots with limited visibility. At each iteration, a robot takes a snapshot of its surroundings, uses the snapshot to compute a destination point, and it moves toward its destination. Each robot is punctiform and memoryless, it operates in R^m, it has a local reference system independent of the other robots' ones, and is activated asynchronously by an adversarial scheduler. Moreover, the robots are non-rigid, in that they may be stopped by the scheduler at each move before reaching their destination (but are guaranteed to travel at least a fixed unknown distance before being stopped). We show that despite these strong limitations, it is possible to arrange 3m+3k of these weak entities in R^m to simulate the behavior of a stronger robot that is rigid (i.e., it always reaches its destination) and is endowed with k registers of persistent memory, each of which can store a real number. We call this arrangement a TuringMobile. In its simplest form, a TuringMobile consisting of only three robots can travel in the plane and store and update a single real number. We also prove that this task is impossible with fewer than three robots. Among the applications of the TuringMobile, we focused on Near-Gathering (all robots have to gather in a small-enough disk) and Pattern Formation (of which Gathering is a special case) with limited visibility. Interestingly, our investigation implies that both problems are solvable in Euclidean spaces of any dimension, even if the visibility graph of the robots is initially disconnected, provided that a small amount of these robots are arranged to form a TuringMobile. In the special case of the plane, a basic TuringMobile of only three robots is sufficient.

Subject Classification

ACM Subject Classification
  • Computing methodologies → Multi-agent planning
Keywords
  • Mobile Robots
  • Turing Machine
  • Real RAM

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. C. Agathangelou, C. Georgiou, and M. Mavronicolas. A distributed algorithm for gathering many fat mobile robots in the plane. In 32nd ACM Symposium on Principles of Distributed Computing (PODC), pages 250-259, 2013. Google Scholar
  2. N. Agmon and D. Peleg. Fault-tolerant gathering algorithms for autonomous mobile robots. SIAM Journal on Computing, 36(1):56-82, 2006. Google Scholar
  3. A. V. Aho, J. E. Hopcroft, and J. D. Ullman. The Design and Analysis of Computer Algorithms. Addison-Wesley, Reading, Massachusetts, 1974. Google Scholar
  4. H. Ando, Y. Oasa, I. Suzuki, and M. Yamashita. Distributed memoryless point convergence algorithm for mobile robots with limited visibility. IEEE Transactions on Robotics and Automation, 15(5):818-838, 1999. Google Scholar
  5. Q. Bramas and S. Tixeuil. The random bit complexity of mobile robots scattering. International Journal of Foundations of Computer Science, 28(2):111-134, 2017. Google Scholar
  6. D. Canepa, X. Défago, T. Izumi, and M. Potop-Butucaru. Flocking with oblivious robots. In 18th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS), pages 94-108, 2016. Google Scholar
  7. S. Cicerone, G. Di Stefano, and A. Navarra. Minimum-traveled-distance gathering of oblivious robots over given meeting points. In 10th International Symposium on Algorithms and Experiments for Sensor Systems (Algosensors), pages 57-72, 2014. Google Scholar
  8. S. Cicerone, G. Di Stefano, and A. Navarra. Asynchronous pattern formation: The effects of a rigorous approach. In arXiv:1706.02474, 2017. Google Scholar
  9. M. Cieliebak, P. Flocchini, G. Prencipe, and N. Santoro. Distributed computing by mobile robots: Gathering. SIAM Journal on Computing, 41(2):829-879, 2012. Google Scholar
  10. R. Cohen and D. Peleg. Convergence properties of the gravitational algorithm in asynchronous robot systems. SIAM Journal on Computing, 36(6):1516-1528, 2005. Google Scholar
  11. P. Courtieu, L. Rieg, S. Tixeuil, and X. Urbain. Impossibility of gathering, a certification. Information Processing Letters, 115(3):447-452, 2015. Google Scholar
  12. P. Courtieu, L. Rieg, S. Tixeuil, and X. Urbain. Certified universal gathering in ℝ² for oblivious mobile robots. In 30th International Symposium on Distributed Computing (DISC), pages 187-200, 2016. Google Scholar
  13. S. Das, P. Flocchini, N. Santoro, and M. Yamashita. Forming sequences of geometric patterns with oblivious mobile robots. Information Processing Letters, 28(2):131-145, 2015. Google Scholar
  14. X. Défago, M. Gradinariu, S. Messika, P. Raipin-Parvédy, and S. Dolev. Fault-tolerant and self-stabilizing mobile robots gathering. In 20th International Symposium on Distributed Computing (DISC), pages 46-60, 2006. Google Scholar
  15. B. Degener, B. Kempkes, P. Kling, and F. Meyer auf der Heide. Linear and competitive strategies for continuous robot formation problems. ACM Transactions on Parallel Computing, 2(1):2:1-2:8, 2015. Google Scholar
  16. B. Degener, B. Kempkes, P. Kling, F. Meyer auf der Heide, P. Pietrzyk, and R. Wattenhofer. A tight runtime bound for synchronous gathering of autonomous robots with limited visibility. In 23rd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 139-148, 2011. Google Scholar
  17. G. Di Luna, P. Flocchini, N. Santoro, and G. Viglietta. Turingmobile: A turing machine of oblivious mobile robots with limited visibility and its applications. In arXiv:1709.08800, 2017. Google Scholar
  18. P. Flocchini, G. Prencipe, and N. Santoro. Distributed Computing by Oblivious Mobile Robots. Morgan &Claypool, 2012. Google Scholar
  19. P. Flocchini, G. Prencipe, N. Santoro, and G. Viglietta. Distributed computing by mobile robots: Uniform circle formation. Distributed Computing, 30(6):413-457, 2017. Google Scholar
  20. P. Flocchini, G. Prencipe, N. Santoro, and P. Widmayer. Gathering of asynchronous robots with limited visibility. Theoretical Computer Science, 337(1-3):147-168, 2005. Google Scholar
  21. P. Flocchini, G. Prencipe, N. Santoro, and P. Widmayer. Arbitrary pattern formation by asynchronous, anonymous, oblivious robots. Theoretical Computer Science, 407(1-3):412-447, 2008. Google Scholar
  22. N. Fujinaga, Y. Yamauchi, S. Kijima, and M. Yamahista. Pattern formation by oblivious asynchronous mobile robots. SIAM Journal on Computing, 44(3):740-785, 2015. Google Scholar
  23. T. Izumi, M. Gradinariu, and S. Tixeuil. Connectivity-preserving scattering of mobile robots with limited visibility. In 12th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS), pages 319-331, 2010. Google Scholar
  24. P. Linda, G. Prencipe, and G. Viglietta. Getting close without touching: Near-gathering for autonomous mobile robots. Distributed Computing, 28(5):333-349, 2015. Google Scholar
  25. F.P. Preparata and M.I. Shamos. Computational Geometry. Springer-Verlag, Berlin and New York, 1985. Google Scholar
  26. M.I. Shamos. Computational Geometry. Ph.D. thesis, Department of Computer Science, Yale University, 1978. Google Scholar
  27. I. Suzuki and M. Yamashita. Distributed anonymous mobile robots: Formation of geometric patterns. SIAM Journal on Computing, 28(4):1347-1363, 1999. Google Scholar
  28. M. Yamashita and I. Suzuki. Characterizing geometric patterns formable by oblivious anonymous mobile robots. Theoretical Computer Science, 411(26-28):2433-2453, 2010. Google Scholar
  29. Y. Yamauchi, T. Uehara, S. Kijima, and M. Yamashita. Plane formation by synchronous mobile robots in the three-dimensional euclidean space. Journal of the ACM, 64(3):16:1-16:43, 2017. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail