Leader Selection and Clusterization Algorithms in a Static Robot Swarm
https://doi.org/10.17587/mau.18.166-173
Abstract
The paper presents the problem of clustering and leader selection in a group of robots, using a static swarm model - fixed network at some point in time, consisting of the robots connected to one another via the communication channels. Robots use only local interaction, the topology of the swarm and the number of the robots is not known beforehand. It is proposed to take into account the relative positions of the robots and their neighbors, i.e., their local topology, which is known to them, and allows them, in the long run, to choose their leader out of the robots located close enough to the topological center of the whole group. It is known that the group has peripheral robots - those which have not all the communication channels occupied. They initiate the leader selection procedure by transmitting its weight to the center of the group. This allows to create there a subgroup of robots, with the biggest weights, one of which becomes the leader. It is considered as an option, when the static topology of the swarm changes, i.e. some robots are eliminated in the process of voting. It is demonstrated that in all these cases the leader selection algorithm succeeds. In addition, a clustering algorithm is proposed to solve the problem of the functional differentiation of robots, which will quickly produce their integration into subgroups. The conducted computing experiments prove the efficiency of the algorithms.
References
1. Karpov V., Karpova I. Leader election algorithms for static swarms // Biologically Inspired Cognitive Architectures. 2015. № 12. C. 54-64.
2. Каляев И. А., Гайдук А. Р., Капустян С. Г. Модели и алгоритмы коллективного управления в группах роботов. М.: Физматлит, 2009. 280 c.
3. Bina D. Effective cooperation and scalability in multi-robot teams for automatic patrolling of infrastructures // Coimbra. 2013.
4. c.
5. Portugal D., Rocha R. P. Cooperative multi-robot patrol with Bayesian learning // Autonomous Robots. 2016. Т. 40. № 5. С.929-953.
6. Tan Y., Zheng Z. Research advance in swarm robotics // Defence Technology. 2013. Т. 9. № 1. С. 18-39.
7. Canepa D., Potop-Butucaru M. G. Stabilizing flocking via leader election in robot networks // Symposium on Self-Stabilizing Systems. Springer Berlin Heidelberg, 2007. С. 52-66.
8. Dieudonne Y., Petit F., Villain V. Leader election problem versus pattern formation problem // International Symposium on Distributed Computing. Springer Berlin Heidelberg, 2010. С. 267-281.
9. Карпов В. Э. Коллективное поведение роботов. Желаемое и действительное // Современная мехатроника. Сб. научн. трудов Всероссийской научной школы (22-23 сентября 2011 г., г. Орехово-Зуево, Россия): Труды конференции, 2011. С. 35-51.
10. Santoro N. Design and analysis of distributed algorithms. John Wiley & Sons, 2006. 589 c.
11. Chaudhuri S. G., Mukhopadhyaya K. Leader election and gathering for asynchronous fat robots without common chirality // Journal of Discrete Algorithms. 2015. Т. 33. С. 171-192.
12. Карпов В. Э. Управление в статических роях. Постановка задачи // VII-я Международная научно-практическая конференция "Интегрированные модели и мягкие вычисления в искусственном интеллекте" (20-22 мая 2013, г. Коломна, Россия): Труды конференции. В 3-х томах. Т. 2. М.: Физматлит, 2013. С.730-739.
13. GroB R., Magnenat S., Mondada F. Segregation in swarms of mobile robots based on the Brazil nut effect // 2009 IEEE/RSJ International Conference on Intelligent Robots and Systems. IEEE, 2009. С. 4349-4356.
14. Chen J. et al. Segregation in swarms of e-puck robots based on the brazil nut effect // Proc. of the 11th International Conference on Autonomous Agents and Multiagent Systems. 2012. Т. 1. С. 163-170.
15. Cruz N. B., Nedjah N., de Macedo Mourelle L. Robust distributed spatial clustering for swarm robotic based systems // Applied Soft Computing. 2016.
16. Di Caro G. A., Ducatelle F., Gambardella L. A fully distributed communication-based approach for spatial clustering in robotic swarms // Proc. of the 2nd Autonomous Robots and Multirobot Systems Workshop (ARMS), affiliated with the 11th International Conference on Autonomous Agents and Multiagent Systems (AAMAS) (Valencia, Spain, June 5). 2012. С. 153-171.
17. Карпова И. П. Псевдоаналоговая коммуникация в группе роботов // Мехатроника, автоматизация, управление. 2016. Т. 17. № 2. С. 94-101.
18. Воробьев В. В., Московский А. Д. Алгоритм выбора лидера в системах с меняющейся топологией // Пятнадцатая национальная конференция по искусственному интеллекту с международным участием КИИ-2016 (3-7 октября 2016, г. Смоленск, Россия): Труды конференции. В 3-х томах. Т. 1. Смоленск: Универсум, 2016. С. 149-157.
19. Воробьев В. В. Алгоритм кластеризации коллектива роботов // Третий Всероссийский научно-практический семинар "Беспилотные транспортные средства с элементами искуственного интеллекта" (БТС-ИИ-2016, 22-23 сентября 2016 г., г. Иннополис, Республика Татарстан, Россия): Труды семинара. М: Издательство "Перо", 2016. С. 50-59.
Review
For citations:
Vorobyov V.V. Leader Selection and Clusterization Algorithms in a Static Robot Swarm. Mekhatronika, Avtomatizatsiya, Upravlenie. 2017;18(3):166-173. (In Russ.) https://doi.org/10.17587/mau.18.166-173
Views:
504
.png)
Email this article 