No Access

Explicit Communication Among Stigmergic Robots

Yoann Dieudonné

MIS, Université of Picardie Jules Verne, France

Search for more papers by this author

Shlomi Dolev

Department of Computer Science, Ben-Gurion University of the Negev, Israel

Search for more papers by this author

Franck Petit

LiP6/CNRS/INRIA, Sorbonne Université, France

E-mail Address: [email protected]

Corresponding author.

Search for more papers by this author

, and

Michael Segal

Communication Systems Engineering Department, Ben-Gurion University of the Negev, Israel

Search for more papers by this author

https://doi.org/10.1142/S0129054119500072Cited by:1

Abstract

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 $n \geq 2$ 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

Keywords:

References

1. A. Aljohani and G. Sharma, Complete visibility for mobile robots with lights tolerating faults, IJNC 8(1) (2018) 32–52. Crossref, Google 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. Crossref, Google Scholar
3. F. Aurenhammer, Voronoi diagrams — A survey of a fundamental geometric data structure, ACM Comput. Surv. 23(3) (1991) 345–405. Crossref, ISI, Google 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, ISI, Google Scholar
7. R. Cohen and D. Peleg, Local spreading algorithms for autonomous robot systems, Theor. Comput. Sci. 399(1–2) (2008) 71–82. Crossref, ISI, Google Scholar
8. C. R. Kube, Task modelling in collective robotics, Auton. Robots 4(1) (1997) 53–72. Crossref, ISI, Google 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, ISI, Google 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, ISI, Google 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, ISI, Google 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, ISI, Google 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, ISI, Google Scholar
19. Y. Dieudonné and F. Petit, Self-stabilizing gathering with strong multiplicity detection, Theoretical Computer Science 428 (2012) 47–57. Crossref, ISI, Google Scholar
20. S. Dolev, Self-Stabilization (The MIT Press, 2000). Crossref, Google 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, ISI, Google 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, ISI, Google Scholar
27. T. Fukuda and S. Nakagawa, Approach to the dynamically reconfigurable robotic sytem, Journal of Intelligent and Robotic System 1 (1988) 55–72. Crossref, Google 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. Crossref, Google 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, ISI, Google 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, ISI, Google Scholar
32. N. Megiddo, Linear-time algorithms for linear programming in R³ and related problems, SIAM Journal on Computing 12(4) (1983) 759–776. Crossref, ISI, Google 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 (log n)$ -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, ISI, Google 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, ISI, Google Scholar
43. P. Wenner and A. Wells, Anatomy of a Controversy: The Question of a “Language” Among Bees (Columbia University Press, New York, 1990). Crossref, Google 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, ISI, Google Scholar

Remember to check out the Most Cited Articles!
Check out these Handbooks in Computer Science

Vol. 30, No. 02

Metrics

History

Received 30 October 2017

Accepted 7 May 2018

Keywords

PDF download

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

Explicit Communication Among Stigmergic Robots

Abstract

References

Recommended