Abstract
Pattern Formation in multi-robot systems was proposed in the 1990’s. Since then it has been extensively studied and applied in various ways. To date, the majority of the proposed algorithms that aimed to achieve geometric patterns in the literature have overlooked the visibility limitation in physical robots. In addition, a methodology to reach a complete coordinate agreement has not been adopted by many researchers as a prerequisite towards a successful formation. It should be stressed that such limitation and methodology have a strong effect on the desired pattern approach. In this paper, a decentralized approach for circle formation is highlighted. The main advantage of forming a circle is the flexibility to be generated with different initial distributions. Moreover, circle arrangement can be utilized as a preliminary sub-task for more complex activities in multi-robot systems. To handle the aforementioned realities, this approach is proposed under a realistic robot model – i.e. one that has a short visibility range and performs the task autonomously relying on the information picked by itself, or by the vicinity. In addition, robots do not initially have a pre-defined leader nor unique IDs. Simulation results have validated the robustness and flexibility of the proposed algorithm, where a circular pattern has been successfully constructed in a self-organized manner.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
Visibility refers to the way a robot observes the surrounding universe using its sensors. Robot’s sensors take snapshots of the positions of all other robots within its visibility range with respect to its local coordinate system.
- 2.
For non-oblivious robots used in [25], the authors assume that each robot is endowed with unbounded memory to store past information and execute a non–oblivious algorithm. However, since the robots in this work rely only on the most recent past information, it is required that each robot is equipped with a a limited amount of memory. Hence, the semi-oblivious nature of the algorithm [14].
- 3.
This period is determined so as to allow all robots to broadcast their “Hello message”. A suitable negotiation mechanism can be easily devised to determine the order in which all robots broadcast.
References
Aguilera, M.K., Querzoni, L., Shapiro, M. (eds.): Principles of Distributed Systems. LNCS, vol. 8878. Springer International Publishing, Cham (2014)
Alonso-Mora, J., Breitenmoser, A., Rufli, M., Siegwart, R., Beardsley, P.: Multi-robot system for artistic pattern formation. In: Proceedings of IEEE International Conference on Robotics and Automation, pp. 4512–4517 (2011)
Ando, H., Suzuki, I., Yamashita, M.: Formation and agreement problems for synchronous mobile robots with limited visibility. In: Proceedings of 10th International Symposium on Intelligent Control, pp. 453–460, August 1995
Bahceci, E., Soysal, O., Sahin, E.: A review: pattern formation and adaptation in multi-robot systems. Technical report CMU-RI-TR-03-43, Robotics Institute, Carnegie Mellon University, Pittsburgh, PA (2003)
Barca, J.C., Sekercioglu, A.: Generating formations with a template based multi-robot system. In: Australasian Conference on Robotics and Automation, Melbourne, pp. 1–9 (2011)
Barca, J.C., Sekercioglu, Y.A.: Swarm robotics reviewed. Robotica 31(03), 345–359 (2012)
Chatzigiannakis, I., Markou, M., Nikoletseas, S.: Distributed circle formation for anonymous oblivious robots. Exp. Eff. Algorithms 33116, 1–16 (2004)
Chaudhuri, S.G., Ghike, S., Jain, S., Mukhopadhyaya, K.: Pattern formation for asynchronous robots without agreement in chirality. CoRR abs/1403.2625 (2014)
Défago, X., Souissi, S.: Non-uniform circle formation algorithm for oblivious mobile robots with convergence toward uniformity. Theor. Comput. Sci. 396(1–3), 97–112 (2008)
Edelen, M.R.: Swarm intelligence and stigmergy: robotic implementation of foraging behavior. Master’s thesis, University of Maryland (2003)
Flocchini, P., Prencipe, G., Santori, N., Widmayer, P.: Hard task for weak robot: the role of common knowledge in pattren formation autonomous mobile robots. In: 10th International Symposium, ISAAC 1999, Chennai, India, vol. 1741, pp. 93–102 (1999)
Flocchini, P., Prencipe, G., Santoro, N.: Distributed Computing by Oblivious Mobile Robots. Morgan & Claypool, San Rafael (2012)
Flocchini, P., Prencipe, G., Santoro, N., Widmayer, P.: Pattern formation by autonomous robots without chirality. In: Proceedings of the 8th International Colloquium on Structural Information and Communication Complexity, SIROCCO, vol. 8, pp. 147–162 (2001)
Flocchini, P., Prencipe, G., Santoro, N., Widmayer, P.: Arbitrary pattern formation by asynchronous, anonymous, oblivious robots. Theor. Comput. Sci. 407(1–3), 412–447 (2008)
Gazi, V.: Swarm aggregations using artificial potentials and sliding-mode control. IEEE Trans. Robot. 21(6), 1208–1214 (2005)
Gordon, N., Wagner, I., Bruckstein, A.: Discrete bee dance algorithm for pattern formation on a grid. In: IEEE/WIC International Conference on Intelligent Agent Technology, IAT 2003, pp. 545–549 (2003)
Hu, J., Feng, G.: Distributed tracking control of leader-follower multi-agent systems under noisy measurement. Automatica 46(8), 1382–1387 (2010)
Khaldi, B., Cherif, F.: An overview of swarm robotics: swarm intelligence applied to multi-robotics. Int. J. Comput. Appl. 126(2), 31–37 (2015)
Lee, G., Chong, N.Y.: Decentralized formation control for a team of anonymous mobile robots. In: Proceedings of 6th Asian Control Conference, pp. 971–976 (2006)
Liekna, A., Grundspenkins, J.: Towards practical application of swarm robotics: overview of swarm tasks. In: Proceedings of the 13th International Conference on Engineering for Rural Development, pp. 271–277 (2014)
Navarro, I., Matía, F.: A survey of collective movement of mobile robots. Int. J. Adv. Robot. Syst. 10, 73 (2013)
Prencipe, G., Santoro, N.: 4th IFIP International Conference on Theoretical Computer Science- TCS 2006. nt. Federation for Inform. Process. Springer, US, Boston, MA (2006)
Sugihara, K., Suzuki, I.: Distributed algorithms for formation of geometric patterns with many mobile robots. J. Robot. Syst. 13(3), 127–139 (1996)
Suzuki, I., Yamashita, M.: A theory of distributed anonymous mobile robots formation and agreement problems. Technical report ADA303910, Wisconsin Univ-MilwaukeeI Dept. of Elect.l Eng. and Compu. Sci. (1994)
Suzuki, I., Yamashita, M.: Distributed anonymous mobile robots: formation of geometric patterns. SIAM J. Comput. 28(4), 1347–1363 (1999)
Swaminathan, K.: Self-organized formation of geometric patterns in multi-robot swarms using wireless communication. Master’s thesis, University of Cincinnati (2005)
Swaminathan, K., Minai, A.: A general approach to swarm coordination using circle formation, pp. 65–84. Springer, Berlin, Heidelberg (2006)
Tan, Y., Shi, Y., Ji, Z. (eds.) Advances in Swarm Intelligence. LNCS, vol. 7331. Springer, Berlin, Heidelberg (2012)
Werfel, J., Petersen, K., Nagpal, R.: Designing collective behavior in a termite-inspired robot construction team. Science 343(6172), 754–8 (2014)
Yamauchi, Y.: A survey on pattern formation of autonomous mobile robots: asynchrony, obliviousness and visibility. J. Phys. Conf. Ser. 473(1), 012,016 (2013)
Yu, C.H., Nagpal, R.: Biologically-inspired control for multi-agent self-adaptive tasks. In: Twenty-Fourth AAAI Conference on Artificial Intelligence (AAAI) (2010)
Author information
Authors and Affiliations
Corresponding authors
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2018 Springer International Publishing AG
About this paper
Cite this paper
Hasan, E., Al-Wahedi, K., Jumah, B., Dawoud, D.W., Dias, J. (2018). Circle Formation in Multi-robot Systems with Limited Visibility. In: Ollero, A., Sanfeliu, A., Montano, L., Lau, N., Cardeira, C. (eds) ROBOT 2017: Third Iberian Robotics Conference. ROBOT 2017. Advances in Intelligent Systems and Computing, vol 693. Springer, Cham. https://doi.org/10.1007/978-3-319-70833-1_27
Download citation
DOI: https://doi.org/10.1007/978-3-319-70833-1_27
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-70832-4
Online ISBN: 978-3-319-70833-1
eBook Packages: EngineeringEngineering (R0)