Swarm robotics is based on the characteristics displayed by the insects and their colony and is applied to solve real world problems utilizing multi-robot systems. Research in this field has demonstrated the ability of such robot systems to assemble, inspect, disperse, aggregate and follow trails. A set of mobile and self-sufficient robots which has very restricted capabilities can form intricate patterns in the environment they inhabit. However, coordination of multiple robots to accomplish such tasks remains a challenging problem. Pattern formation is one of typical problems in the field of multi-robot cooperation. Compare to traditional multi-robot coordination algorithm, the method based on swarm robots to solve the issue of pattern formation has better scalability and dynamic adaptability and robustness. The swarm robots have only local perception and very limited local communication abilities, so one of the challenging tasks while designing swarm robotic systems with desired collective behaviour is to understand the effect of individual behaviour on the group performance. So fault tolerance is another issue to deal with. This paper reviews the background knowledge and some noticeable achievements in the field of pattern formation and fault tolerance.

Swarm robotics, pattern formation, swarm intelligence, particle swarm intelligence, fault tolerance

[1] Bonabeau, E., Dorigo, M., and Theraulaz, G. (2000). Inspiration for optimization from social insect behaviour. Nature, 406(6791):39–42.
[2] Bonabeau, E., Dorigo, M., and Theraulaz, G. (1999). Swarm Intelligence: From Natural to Artificial Systems. Oxford University Press, New York.
[3] Dorigo, M. and Sahin, E. (2004). Guest editorial. special issue: Swarm robotics. Autonomous Robots, 17:111–113.
[4] Nouyan, S., Campo, A., and Dorigo, M. (2008). Path formation in a robot swarm. Selforganized strategies to find your way home. Swarm Intelligence, 2(1):1–23.
[5] Sugihara, K. and Suzuki, I.: Distributed Algorithms for Formation of Geometric Patterns with Many Mobile Robots. Robotic Systems 13 (1996) 127–139
[6] Suzuki, I. and Yamashita, M.: Distributed Anonymous Mobile Robots: Formation of Geometric Patterns. SIAM J. on Computing 28 4 (1999) 1347–1363
[7] Prencipe, G.: Corda: Distributed Coordination of a Set of Atonomous Mobile Robots. In Proc. 4th European Research Seminar on Advances in Distributed Systems, May 2001, 185–190
[8] Prencipe, G.: Instantaneous Actions vs. Full Asynchronicity: Controlling and Coordinating a Set of Autonomous Mobile Robots. In Proc. 7th Italian Conf. on Theoretical Computer Science, October 2001, 185–190.
[9] Suzuki, I. and Yamashita, M.: Distributed Anonymous Mobile Robots – Formation and Agreement Problems. In Proc. 3rd Colloq. on Structural Information and Communication Complexity (1996) 313–330
[10] Defago X, Konagaya A (2002) Circle Formation for Oblivious Anonymous Mobile Robots with No Common Sense of Orientation. In Proceedings of the second ACM international workshop on Principles of mobile computing, pp.97-104.
[11] Ryan O. Abel, Soura Dasgupta And Jon G. Kuhl, “Coordinated Fault Tolerant Optimal Control Of Autonomous Agents: Geometry And Communications Architecture”. In Communications In Information And Systems Vol. 11, No. 2, pp. 173-196, 2011
[12] Debasish Pattanayak, Kaushik enMondal, H. Ramesh and Partha Sarathi Mandal, “Fault-Tolerant Gathering of Mobile Robots with Weak Multiplicity Detection”, ICDCN ’17 January 4–7, 2017, Hyderabad, India
[13] 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. In Proc. 10th Int`l Symp. on Algorithms and Computation (ISAAC`99), volume 1741 of LNCS, pp93-102, Chennai, India, Dec. 1999. Springer.
[14] Alan F.T. Winfield and Julien Nembrini : Safety in numbers: fault-tolerance in robot swarms, Int. J. Modelling, Identification and Control, Vol. 1, No. 1, 2006
[15] Yun X, Alptekin G, Albayrak O (1997) Line and circle formation of distributed physical mobile robots. Journal of Robotic Systems, 14(2):63-76.
[16] Cohen, R. and Peleg, D.: Robot Convergence via Center-of-Gravity Algorithms. In Proc. 11th Colloq. on Structural Information and Communication Complexity (2004) 79–88.
[17] Bingu Shim, Beomho Baek, Suntae Kim, Sooyong Park: “A Robot Fault-tolerance Approach Based on Fault Type”.
[18] Okay Albayrak: “Line and Circle Formation of Distributed Autonomous Mobile Robots with limited sensor range”, Journal of Robotic Systems— 1997,p:64-76
[19] Chatzigiannakis I, Markou M, Nikoletseas S (2004) Distributed Circle Formation for Anonymous Oblivious Robots. In 3rd Workshop on Efficient and Experimental Algorithms, Lecture Notes in Computer Science, 3059:159-174.
[20] Michael, Andrew Mario, "Circle formation algorithm for autonomous agents with local sensing" (2004). Thesis. Rochester Institute of Technology.
[21] Cem Unsal, "Self organization in large populations of mobile robots", MS Thesis, Virginia Polytechnic Institute and State University, May 1993.
[22] T. Balch and M. Hybinette, "Social potentials for scalable multi-robot formations", Proceedings of IEEE International Conference on Robotics and Automation, pp. 73-80, April 2000
[23] T. Balch and M. Hybinette, "Behavior-based coordination of large-scale robot formations", Proceedings of Fourth
[24] T. Balch and R.C.Arkin, "Behavior-based formation control for multirobot teams", IEEE Transactions on Robotics and Automation, pp. 926-939, Vol. 14, December 1998.
[25] J. Fredslund and M.J.Mataric, "Robot formations using only local sensing and control", Proceedings of IEEE International Symposium Computational Intelligence in Robotics and Automation, pp. 308-313, Aug. 2001
[26] J. Fredslund and M.J. Mataric, "A general algorithm for robot formations using local sensing and minimal communication", Proceedings of IEEE Transactions on Robotics and Automation, pp 837-846, Vol. 18, October 2002
[27] J. Fredslund, M. J. Matarić, “Robots in formation using local information,” in 7th International Conference on Intelligent Autonomous Systems, Marina Del Rey, California, 2002, pp. 100-107.
[28] Flocchini, P., Prencipe, G., Santoro, N., Widmayer, P.: Arbitrary pattern formation by asynchronous, anonymous, oblivious robots. Theor. Comput. Sci. 407, 412–447 (2008)
[29] Ani Hsieh, M., Kumar, V., Chaimowicz, L.: Decentralized controllers for shape generation. Robotica 26, 691–701 (2008)
[30] Noa Agmon and David Peleg, “ Fault-Tolerant Gathering Algorithms for Autonomous Mobile Robots” ,SIAM (Society for Industrial and Applied Mathematics) Journal of Computing, 2006 , Vol. 36, No. 1, pp. 56–82
[31] Chirag Maheshwari, Circle Formation by Autonomous, Anonymous and Oblivious Mobile Robots, a project report at NIT Guwhati, 2014
[32] Pilar Arques(B), Fidel Aznar, and Mireia Sempere, Positioning of Geometric Formations in Swarm Robotics. In 2016
[33] Flocchini, P., Prencipe, G., Santoro, N., Viglietta, G.:Distributed Computing by Mobile Robots: Uniform Circle Formation ,18th International Conference on Principles of Distributed Systems, 2016
[34] S. Das, P. Flocchini, N. Santoro, and M. Yamashita : Forming sequences of geometric patterns with oblivious mobile robots. Distributed Computing, 28(2): 131-145, 2015.
[35] Yamauchi, Y., Yamashita, M.: Pattern formation by mobile robots with limited visibility. In: 20th International Colloquium on Structural Information and Communication Complexity (SIROCCO), pp. 201–212 (2013)
[36] Fujinaga, N., Ono, H., Kijima, S., Yamashita, M.: Pattern formation through optimum matching by oblivious corda robots. In:14th InternationalConference on Principles of Distributed Systems (OPODIS), pp. 1–15 (2010)
[37] M. Mamino, G.Vigliettay, Square Formation by Asynchronous Oblivious Robots, CCCG 2016
[38] Dongdong Xu, Xingnan Zhang, Zhangqing Zhu, Chunlin Chen, and Pei Yang, Behavior-Based Formation Control of Swarm Robots, Hindawi Publishing Corporation Mathematical Problems in Engineering Volume 2014, Article ID 205759, 13 pages
[39] Karthikeyan Swaminathan and Ali A. Minai (2006), General Approach to Swarm Coordination using Circle Formation, in Stigmergic Optimization, A. Abraham, C. Grosan, and V.Ramos (Eds.), Springer verlag , pp 65-84.
[40] In 2010 Blesson Varghese and Gerard T. McKee, “A Mathematical Model, Implementation and Study of a Swarm System”,  Robotics and Autonomous Systems 58(3):287-294, March 2010 
[41] Anand. A, Nithya. M and Sudarshan TSB, Coordination of Mobile Robots with Master-Slave Architecture for a Service Application, International Conference on Contemporary Computing and Informatics (IC3I), IEEE 2014, p:539-543
[42] S. Gan Chaudhuri, S. Ghike, S. Jain and K. Mukhopadhyaya, Pattern Formation for Asynchronous Robots without Agreement in Chirality, Elsevier March 2014
[43] Bjerknes, J. D. and Winfield, A. F. (2013) On fault tolerance and scalability of swarm robotic systems. In: Martinoli, A., Mondada, F., Correll, N., Mermoud, G., Egerstedt, M., Hsieh, M., Parker, L. And Sty, K., eds. (2013) Distributed Autonomous Robotic Systems: The 10th International Symposium. (83) Springer, pp. 431-444. ISBN 9783642327223
[44] Ross Mead, Jerry B. Weinberg, “Cellular Automata for Control and Interactions of Large Formations of Robots”, Thesis 2008, Southern Illinois University Edwardsville Edwardsville, Illinois
[45] Fault-Tolerant Formations of Mobile Robots, Ross Mead, Rob Long, and Jerry B. Weinberg, Member, IEEE, The 2009 IEEE/RSJ International Conference on Intelligent Robots and Systems October 11-15, 2009 St. Louis, USA
[46] Debdipta Goswami, Chiranjib Saha, Kunal Pal, Nanda Dulal Jana and Swagatam Das, “Multi-Agent Shape Formation and Tracking Inspired from a Social Foraging Dynamics”, 2014, arXiv [cs.NE]
[47] Xingyan Li and Lynne E. Parker, “Sensor Analysis for Fault Detection in Tightly-Coupled Multi-Robot Team Tasks” Proc. of IEEE International Conference on Robotics and Automation, Rome, Italy, 2007.
[48] Christensen, A.L., O’Grady, R. and Dorigo, M., “From Fireflies to Fault Tolerant Swarms of Robots” IRIDIA – Technical Report Series Technical Report No. TR/IRIDIA/2008-002 January 2008