World Scientific
  • Search
Skip main navigation

Cookies Notification

We use cookies on this site to enhance your user experience. By continuing to browse the site, you consent to the use of our cookies. Learn More
Our website is made possible by displaying certain online content using javascript.
In order to view the full content, please disable your ad blocker or whitelist our website

System Upgrade on Tue, Oct 25th, 2022 at 2am (EDT)

Existing users will be able to log into the site and access content. However, E-commerce and registration of new users may not be available for up to 12 hours.
For online purchase, please visit us again. Contact us at [email protected] for any enquiries.

Explicit Communication Among Stigmergic Robots

    In this paper, we investigate avenues for the exchange of information (explicit communication) among deaf and mute mobile robots scattered in the plane. We introduce the use of movement-signals (analogously to flight signals and bees waggle) as a mean to transfer messages, enabling the use of distributed algorithms among robots. We propose one-to-one deterministic movement protocols that implement explicit communication among semi-synchronous robots. We first show how the movements of robots can provide implicit acknowledgment in semi-synchronous systems. We use this result to design one-to-one communication among a pair of robots. Then, we propose two one-to-one communication protocols for any system of n2 robots. The former works for robots equipped with observable IDs that agree on a common direction (sense of direction). The latter enables one-to-one communication assuming robots devoid of any observable IDs or sense of direction. All protocols (for either two or any number of robots) assume that no robot remains inactive forever. However, they cannot avoid that the robots move either away or closer to each others, by the way requiring robots with an infinite visibility. In this paper, we also present how to overcome these two disadvantages (some activity of every robot and infinite visibility).

    Our protocols enable the use of distributing algorithms based on message exchanges among swarms of stigmergic robots. They also allow robots to be equipped with the means of communication to tolerate faults in their communication devices.

    Communicated by Oscar Ibarra


    • 1. A. Aljohani and G. Sharma, Complete visibility for mobile robots with lights tolerating faults, IJNC 8(1) (2018) 32–52. CrossrefGoogle Scholar
    • 2. H. Ando, Y. Oasa, I. Suzuki and M. Yamashita, A distributed memoryless point convergence algorithm for mobile robots with limited visibility, IEEE Transaction on Robotics and Automation 15(5) (1999) 818–828. CrossrefGoogle Scholar
    • 3. F. Aurenhammer, Voronoi diagrams — A survey of a fundamental geometric data structure, ACM Comput. Surv. 23(3) (1991) 345–405. Crossref, ISIGoogle Scholar
    • 4. R. Beckers, O. Holland and J. Deneubourg, From local actions to global tasks: Stigmergy and collective robotics., Artificial Life, 4th Int. Worksh. on the Synth. and Simul. of Living Syst. 4 (1994) 173–202. Google Scholar
    • 5. Z. Bouzid, S. Dolev, M. Potop-Butucaru and S. Tixeuil, Robocast: Asynchronous communication in robot networks, 14th International Conference On Principles of Distributed Systems (OPODIS 2010) (2010), pp. 16–31. Google Scholar
    • 6. M. Cieliebak, P. Flocchini, G. Prencipe and N. Santoro, Distributed computing by mobile robots: Gathering, SIAM J. Comput. 41(4) (2012) 829–879. Crossref, ISIGoogle Scholar
    • 7. R. Cohen and D. Peleg, Local spreading algorithms for autonomous robot systems, Theor. Comput. Sci. 399(1–2) (2008) 71–82. Crossref, ISIGoogle Scholar
    • 8. C. R. Kube, Task modelling in collective robotics, Auton. Robots 4(1) (1997) 53–72. Crossref, ISIGoogle Scholar
    • 9. G. D’Angelo, X. Défago and N. Nisse, Understanding the power of stigmergy of anonymous agents in discrete environments, Second International Symposium on Computing and Networking, CANDAR 2014, Shizuoka, Japan (2014), pp. 50–59. Google Scholar
    • 10. S. Das, P. Flocchini, G. Prencipe, N. Santoro and M. Yamashita, Autonomous mobile robots with lights, Theor. Comput. Sci. 609 (2016) 171–184. Crossref, ISIGoogle Scholar
    • 11. S. Das, P. Flocchini, N. Santoro and M. Yamashita, Forming sequences of geometric patterns with oblivious mobile robots, Distributed Computing 28(2) (2015) 131–145. Crossref, ISIGoogle Scholar
    • 12. X. Defago and A. Konagaya, Circle formation for oblivious anonymous mobile robots with no common sense of orientation, 2nd ACM International Annual Workshop on Principles of Mobile Computing (POMC 2002) (2002), pp. 97–104. Google Scholar
    • 13. S. Devismes, A. Lamani, F. Petit and S. Tixeuil, Optimal torus exploration by oblivious robots, Third International Conference on Networked Systems (NETYS 2015), Lecture Notes in Computer Science (LNCS), Vol. 9466 (Springer, Berlin/Heidelberg, Agadir, Morocco, 2015), pp. 183–199. Google Scholar
    • 14. S. Devismes, F. Petit and S. Tixeuil, Optimal probabilistic ring exploration by semi-synchronous oblivious robots, Theoretical Computer Science 498 (2013) 10–27. Crossref, ISIGoogle Scholar
    • 15. Y. Dieudonné, O. Labbani-Igbida and F. Petit, Circle formation of weak mobile robots, ACM Transactions on Autonomous and Adaptive Systems 3(4) (2008). Crossref, ISIGoogle Scholar
    • 16. Y. Dieudonné and F. Petit, Deterministic leader election in anonymous sensor networks without common coodinated system, 11th International Conference On Principles of Distributed Systems (OPODIS 2007), Lecture Notes in Computer Science, Vol. 4878 (Springer, 2007), pp. 132–142. Google Scholar
    • 17. Y. Dieudonné, S. Dolev, F. Petit and M. Segal, Deaf, dumb, and chatting asynchronous robots, 13th International Conference On Principles of Distributed Systems (OPODIS 2009) (2009), pp. 71–85. Google Scholar
    • 18. Y. Dieudonné, F. Levé, F. Petit and V. Villain, Deterministic geoleader election in disoriented anonymous systems, Theoretical Computer Science (2013) 43–54. Crossref, ISIGoogle Scholar
    • 19. Y. Dieudonné and F. Petit, Self-stabilizing gathering with strong multiplicity detection, Theoretical Computer Science 428 (2012) 47–57. Crossref, ISIGoogle Scholar
    • 20. S. Dolev, Self-Stabilization (The MIT Press, 2000). CrossrefGoogle Scholar
    • 21. A. P. Engelbrecht, Fundamentals of Computational Swarm Intelligence (John Wiley & Sons, 2006). Google Scholar
    • 22. E. O. Wilson, Sociobiology (Belknap Press of Harward University Press, 1975). Google Scholar
    • 23. 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, 10th Annual International Symposium on Algorithms and Computation (ISAAC 99) (1999), pp. 93–102. Google Scholar
    • 24. P. Flocchini, G. Prencipe, N. Santoro and P. Widmayer, Gathering of asynchronous robots with limited visibility, Theor. Comput. Sci. 337(1–3) (2005) 147–168. Crossref, ISIGoogle Scholar
    • 25. P. Flocchini, Computations by luminous robots, Ad-hoc, Mobile, and Wireless Networks — 14th International Conference, ADHOC-NOW 2015, Athens, Greece, Proceedings (2015), pp. 238–252. Google Scholar
    • 26. P. Flocchini, G. Prencipe, N. Santoro and P. Widmayer, Arbitrary pattern formation by asynchronous, anonymous, oblivious robots, Theor. Comput. Sci. 407(1–3) (2008) 412–447. Crossref, ISIGoogle Scholar
    • 27. T. Fukuda and S. Nakagawa, Approach to the dynamically reconfigurable robotic sytem, Journal of Intelligent and Robotic System 1 (1988) 55–72. CrossrefGoogle Scholar
    • 28. N. Gordon, I. A. Wagner and A. M. Brucks, Discrete bee dance algorithms for pattern formation on a grid, IAT’ 03: Proceedings of the IEEE/WIC International Conference on Intelligent Agent Technology (IEEE Computer Society, 2003), pp. 545–549. Google Scholar
    • 29. P.-P. Grassé, La reconstruction du nid et les coordinations inter-individuelles chez bellicosi-termes natalensis et cubitermes sp. la theorie de la stigmergie: Essai dinterpretation des termites constructeurs, Insectes Sociaux 6 (1959) 41–83. CrossrefGoogle Scholar
    • 30. G. A. D. Luna, P. Flocchini, S. G. Chaudhuri, F. Poloni, N. Santoro and G. Viglietta, Mutual visibility by luminous robots without collisions, Inf. Comput. 254 (2017) 392–418. Crossref, ISIGoogle Scholar
    • 31. M. Matarić, Issues and approaches in the design of collective autonomous agents, Robotics and Autonomous Systems 16(2–4) (1995) 321–331. Crossref, ISIGoogle Scholar
    • 32. N. Megiddo, Linear-time algorithms for linear programming in R3 and related problems, SIAM Journal on Computing 12(4) (1983) 759–776. Crossref, ISIGoogle Scholar
    • 33. F. Noreils, An architecture for cooperative and autonomous mobile robots, IEEE International Conference on Robotics and Automation (1992), pp. 2703–2710. Google Scholar
    • 34. G. Prencipe, Distributed coordination of a set of autonomous mobile robots, PhD thesis, Dipartimento di Informatica, University of Pisa (2002). Google Scholar
    • 35. N. Santoro, Design and Analysis of Distributed Algorithms (John Wiley & Sons, Inc., 2007). Google Scholar
    • 36. G. Sharma, C. Busch and S. Mukhopadhyay, Mutual visibility with an optimal number of colors, Algorithms for Sensor Systems — 11th International Symposium on Algorithms and Experiments for Wireless Sensor Networks, ALGOSENSORS 2015, Patras, Greece, Revised Selected Papers (2015), pp. 196–210. Google Scholar
    • 37. G. Sharma, R. Vaidyanathan and J. L. Trahan, Constant-time complete visibility for asynchronous robots with lights, Stabilization, Safety, and Security of Distributed Systems — 19th International Symposium, SSS 2017, Boston, MA, USA, Proceedings (2017), pp. 265–281. Google Scholar
    • 38. G. Sharma, R. Vaidyanathan, J. L. Trahan, C. Busch and S. Rai, O(logn)-time complete visibility for asynchronous robots with lights, 2017 IEEE International Parallel and Distributed Processing Symposium, IPDPS 2017, Orlando, FL, USA (2017), pp. 513–522. Google Scholar
    • 39. I. Suzuki and M. Yamashita, Distributed anonymous mobile robots — formation of geometric patterns, SIAM Journal of Computing 28(4) (1999) 1347–1363. Crossref, ISIGoogle Scholar
    • 40. C. Tovey, The honey bee algorithm: A biological inspired approach to internet server optimization, Engineering Enterprise, the Alumni Magazine for ISyE at Georgia Institute of Technology Spring 2004 (2004) 13–15. Google Scholar
    • 41. G. Viglietta, Rendezvous of two robots with visible bits, Algorithms for Sensor Systems — 9th International Symposium on Algorithms and Experiments for Sensor Systems, Wireless Networks and Distributed Robotics, ALGOSENSORS 2013, Sophia Antipolis, France, Revised Selected Papers (2013), pp. 291–306. Google Scholar
    • 42. H. Wedde and M. Farooq, A comprehensive review of nature inspired routing algorithms for fixed telecommunication networks, J. Syst. Archit. 52(8) (2006) 461–484. Crossref, ISIGoogle Scholar
    • 43. P. Wenner and A. Wells, Anatomy of a Controversy: The Question of a “Language” Among Bees (Columbia University Press, New York, 1990). CrossrefGoogle Scholar
    • 44. M. Yamashita and I. Suzuki, Characterizing geometric patterns formable by oblivious anonymous mobile robots, Theor. Comput. Sci. 411(26–28) (2010) 2433–2453. Crossref, ISIGoogle Scholar
    Remember to check out the Most Cited Articles!

    Check out these Handbooks in Computer Science