Surrounding Robots – A Discrete Localized Solution for the Intruder Problem –
László Blázovics*, Tamás Lukovszki**, and Bertalan Forstner*
*Department of Automation and Applied Informatics, Faculty of Electrical Engineering and Informatics, Budapest University of Technology and Economics, Magyar Tudósok körútja 2., 1117 Budapest, Hungary
**Faculty of Informatics, Eötvös Lóránd University, Pázmány Péter sétány 1/C 1117 Budapest, Hungary
Decentralized algorithms are often used in the cooperative robotics field, especially by large swarm systems. We present a distributed algorithm for a problem in which a group of autonomous mobile robots must surround a given target. These robots are oblivious, i.e., they have no memory of the past. They use only local sensing and need no dedicated communication among themselves. We introduce, then solve the problem in which the group of autonomous mobile robots must surround a given target – we call it the “discrete multiorbit target surrounding problem” (DMTSP). We evaluate our solution using simulation and prove that our solution invariably ensures that robots enclose the target in finite time.
-  P. Baranyi and A. Csapó, “Definition and Synergies of Cognitive Infocommunications,” Acta Polytechnica Hungarica, Vol.9, pp. 67-83, 2012.
-  V. Gazi and K. Passino, “Stability analysis of swarms,” IEEE Trans. on Automatic Control, Vol.48, No.4, pp. 692-697, April 2003.
-  T. Chu, L. Wang, and T. Chen, “Self-organized motion in anisotropic swarms,” J. of Control Theory and Applications, Vol.1, pp. 77-81, 2003.
-  N. Leonard and E. Fiorelli, “Virtual leaders, artificial potentials and coordinated control of groups,” Proc. 40th IEEE Conf. on Decision and Control, Vol.3, pp. 2968-2973, August 2001.
-  R. Cohen and D. Peleg, “Convergence Properties of the Gravitational Algorithm in Asynchronous Robot Systems,” SIAM J. Comput., Vol.34, No.6, pp. 1516-1528, June 2005.
-  A. Cord-Landwehr et al., “A new Approach for Analyzing Convergence Algorithms for Mobile Robots,” Proc. 38th Int. Colloquium on Automata, Languages and Programming (ICALP 2011), Vol.6756, pp. 650-661, 2011.
-  A. Cord-Landwehr et al., “Collisionless gathering of robots with an extent,” Proc. 37th Int. Conf. on Current Trends in Theory and Practice of Computer Science (SOFSEM 2011), Vol.6543, pp. 178-189, 2011.
-  V. Gervasi and G. Prencipe, “Robotic cops: the intruder problem,” IEEE Int. Conf. on in Systems, Man and Cybernetics 2003, Vol.3, pp. 2284-2289, Oct. 2003.
-  N. Santoro, “Distributed Algorithms for Autonomous Mobile Robots,” 4th IFIP Int. Conf. on Theoretical Computer Science (TCS 2006), Vol.209, pp. 11, 2006.
-  L. Blázovics, T. Lukovszki, and B. Forstner, “Target Surrounding Solution for Swarm Robots,” 18th EUNICE IFIP Int. Conf. in Information and Communication Technologies, Vol.7479, pp. 251-262, 2012.