<?xml version="1.0" encoding="UTF-8"?>
<!DOCTYPE article PUBLIC "-//NLM//DTD JATS (Z39.96) Journal Publishing DTD v1.3 20210610//EN" "JATS-journalpublishing1-3.dtd">
<article article-type="research-article" dtd-version="1.3" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xml:lang="ru"><front><journal-meta><journal-id journal-id-type="publisher-id">novtexmech</journal-id><journal-title-group><journal-title xml:lang="ru">Мехатроника, автоматизация, управление</journal-title><trans-title-group xml:lang="en"><trans-title>Mekhatronika, Avtomatizatsiya, Upravlenie</trans-title></trans-title-group></journal-title-group><issn pub-type="ppub">1684-6427</issn><issn pub-type="epub">2619-1253</issn><publisher><publisher-name>Commercial Publisher «New Technologies»</publisher-name></publisher></journal-meta><article-meta><article-id pub-id-type="doi">10.17587/mau.18.166-173</article-id><article-id custom-type="elpub" pub-id-type="custom">novtexmech-418</article-id><article-categories><subj-group subj-group-type="heading"><subject>Research Article</subject></subj-group><subj-group subj-group-type="section-heading" xml:lang="ru"><subject>РОБОТОТЕХНИЧЕСКИЕ СИСТЕМЫ</subject></subj-group><subj-group subj-group-type="section-heading" xml:lang="en"><subject>ROBOTIC SYSTEMS</subject></subj-group></article-categories><title-group><article-title></article-title><trans-title-group xml:lang="en"><trans-title>Leader Selection and Clusterization Algorithms in a Static Robot Swarm</trans-title></trans-title-group></title-group><contrib-group><contrib contrib-type="author" corresp="yes"><name-alternatives><name name-style="eastern" xml:lang="ru"><surname>Воробьев</surname><given-names>В. В.</given-names></name><name name-style="western" xml:lang="en"><surname>Vorobyov</surname><given-names>V. V.</given-names></name></name-alternatives><email xlink:type="simple">gatus86@mail.ru</email><xref ref-type="aff" rid="aff-1"/></contrib></contrib-group><aff-alternatives id="aff-1"><aff xml:lang="ru"><institution>Национальный исследовательский центр "Курчатовский институт"</institution><country>Россия</country></aff><aff xml:lang="en"><institution>National Research Center "Kurchatov Institute"</institution><country>Russian Federation</country></aff></aff-alternatives><pub-date pub-type="collection"><year>2017</year></pub-date><pub-date pub-type="epub"><day>28</day><month>08</month><year>2018</year></pub-date><volume>18</volume><issue>3</issue><fpage>166</fpage><lpage>173</lpage><permissions><copyright-statement>Copyright &amp;#x00A9; Commercial Publisher «New Technologies», 2018</copyright-statement><copyright-year>2018</copyright-year><copyright-holder xml:lang="ru">Commercial Publisher «New Technologies»</copyright-holder><copyright-holder xml:lang="en">Commercial Publisher «New Technologies»</copyright-holder><license xlink:href="https://mech.novtex.ru/jour/about/submissions#copyrightNotice" xlink:type="simple"><license-p>https://mech.novtex.ru/jour/about/submissions#copyrightNotice</license-p></license></permissions><self-uri xlink:href="https://mech.novtex.ru/jour/article/view/418">https://mech.novtex.ru/jour/article/view/418</self-uri><abstract><p>Алгоритмы выбора лидера и кластеризации в статическом рое роботов* Рассматриваются задачи выбора лидера и кластеризации в группе роботов. Показаны ряд подходов и методов к решению данных задач. Определены важные моменты, которые необходимо учитывать, решая эти задачи. Представлены алгоритмы выбора лидера и кластеризации, которые в разной степени учитывают данные моменты. Проведенные вычислительные эксперименты подтверждают работоспособность алгоритмов.</p></abstract><trans-abstract xml:lang="en"><p>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.</p></trans-abstract><kwd-group xml:lang="ru"><kwd>групповая робототехника</kwd><kwd>выбор лидера</kwd><kwd>функциональная дифференциация</kwd><kwd>кластеризация</kwd><kwd>статический рой</kwd><kwd>swarm robotics</kwd><kwd>leader selection</kwd><kwd>functional differentiation</kwd><kwd>clustering</kwd><kwd>static swarm</kwd><kwd>flocking</kwd></kwd-group></article-meta></front><back><ref-list><title>References</title><ref id="cit1"><label>1</label><citation-alternatives><mixed-citation xml:lang="ru">Karpov V., Karpova I. Leader election algorithms for static swarms // Biologically Inspired Cognitive Architectures. 2015. № 12. C. 54-64.</mixed-citation><mixed-citation xml:lang="en">Karpov V., Karpova I. Leader election algorithms for static swarms // Biologically Inspired Cognitive Architectures. 2015. № 12. C. 54-64.</mixed-citation></citation-alternatives></ref><ref id="cit2"><label>2</label><citation-alternatives><mixed-citation xml:lang="ru">Каляев И. А., Гайдук А. Р., Капустян С. Г. Модели и алгоритмы коллективного управления в группах роботов. М.: Физматлит, 2009. 280 c.</mixed-citation><mixed-citation xml:lang="en">Каляев И. А., Гайдук А. Р., Капустян С. Г. Модели и алгоритмы коллективного управления в группах роботов. М.: Физматлит, 2009. 280 c.</mixed-citation></citation-alternatives></ref><ref id="cit3"><label>3</label><citation-alternatives><mixed-citation xml:lang="ru">Bina D. Effective cooperation and scalability in multi-robot teams for automatic patrolling of infrastructures // Coimbra. 2013.</mixed-citation><mixed-citation xml:lang="en">Bina D. Effective cooperation and scalability in multi-robot teams for automatic patrolling of infrastructures // Coimbra. 2013.</mixed-citation></citation-alternatives></ref><ref id="cit4"><label>4</label><citation-alternatives><mixed-citation xml:lang="ru">c.</mixed-citation><mixed-citation xml:lang="en">c.</mixed-citation></citation-alternatives></ref><ref id="cit5"><label>5</label><citation-alternatives><mixed-citation xml:lang="ru">Portugal D., Rocha R. P. Cooperative multi-robot patrol with Bayesian learning // Autonomous Robots. 2016. Т. 40. № 5. С.929-953.</mixed-citation><mixed-citation xml:lang="en">Portugal D., Rocha R. P. Cooperative multi-robot patrol with Bayesian learning // Autonomous Robots. 2016. Т. 40. № 5. С.929-953.</mixed-citation></citation-alternatives></ref><ref id="cit6"><label>6</label><citation-alternatives><mixed-citation xml:lang="ru">Tan Y., Zheng Z. Research advance in swarm robotics // Defence Technology. 2013. Т. 9. № 1. С. 18-39.</mixed-citation><mixed-citation xml:lang="en">Tan Y., Zheng Z. Research advance in swarm robotics // Defence Technology. 2013. Т. 9. № 1. С. 18-39.</mixed-citation></citation-alternatives></ref><ref id="cit7"><label>7</label><citation-alternatives><mixed-citation xml:lang="ru">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.</mixed-citation><mixed-citation xml:lang="en">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.</mixed-citation></citation-alternatives></ref><ref id="cit8"><label>8</label><citation-alternatives><mixed-citation xml:lang="ru">Dieudonne Y., Petit F., Villain V. Leader election problem versus pattern formation problem // International Symposium on Distributed Computing. Springer Berlin Heidelberg, 2010. С. 267-281.</mixed-citation><mixed-citation xml:lang="en">Dieudonne Y., Petit F., Villain V. Leader election problem versus pattern formation problem // International Symposium on Distributed Computing. Springer Berlin Heidelberg, 2010. С. 267-281.</mixed-citation></citation-alternatives></ref><ref id="cit9"><label>9</label><citation-alternatives><mixed-citation xml:lang="ru">Карпов В. Э. Коллективное поведение роботов. Желаемое и действительное // Современная мехатроника. Сб. научн. трудов Всероссийской научной школы (22-23 сентября 2011 г., г. Орехово-Зуево, Россия): Труды конференции, 2011. С. 35-51.</mixed-citation><mixed-citation xml:lang="en">Карпов В. Э. Коллективное поведение роботов. Желаемое и действительное // Современная мехатроника. Сб. научн. трудов Всероссийской научной школы (22-23 сентября 2011 г., г. Орехово-Зуево, Россия): Труды конференции, 2011. С. 35-51.</mixed-citation></citation-alternatives></ref><ref id="cit10"><label>10</label><citation-alternatives><mixed-citation xml:lang="ru">Santoro N. Design and analysis of distributed algorithms. John Wiley &amp; Sons, 2006. 589 c.</mixed-citation><mixed-citation xml:lang="en">Santoro N. Design and analysis of distributed algorithms. John Wiley &amp; Sons, 2006. 589 c.</mixed-citation></citation-alternatives></ref><ref id="cit11"><label>11</label><citation-alternatives><mixed-citation xml:lang="ru">Chaudhuri S. G., Mukhopadhyaya K. Leader election and gathering for asynchronous fat robots without common chirality // Journal of Discrete Algorithms. 2015. Т. 33. С. 171-192.</mixed-citation><mixed-citation xml:lang="en">Chaudhuri S. G., Mukhopadhyaya K. Leader election and gathering for asynchronous fat robots without common chirality // Journal of Discrete Algorithms. 2015. Т. 33. С. 171-192.</mixed-citation></citation-alternatives></ref><ref id="cit12"><label>12</label><citation-alternatives><mixed-citation xml:lang="ru">Карпов В. Э. Управление в статических роях. Постановка задачи // VII-я Международная научно-практическая конференция "Интегрированные модели и мягкие вычисления в искусственном интеллекте" (20-22 мая 2013, г. Коломна, Россия): Труды конференции. В 3-х томах. Т. 2. М.: Физматлит, 2013. С.730-739.</mixed-citation><mixed-citation xml:lang="en">Карпов В. Э. Управление в статических роях. Постановка задачи // VII-я Международная научно-практическая конференция "Интегрированные модели и мягкие вычисления в искусственном интеллекте" (20-22 мая 2013, г. Коломна, Россия): Труды конференции. В 3-х томах. Т. 2. М.: Физматлит, 2013. С.730-739.</mixed-citation></citation-alternatives></ref><ref id="cit13"><label>13</label><citation-alternatives><mixed-citation xml:lang="ru">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.</mixed-citation><mixed-citation xml:lang="en">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.</mixed-citation></citation-alternatives></ref><ref id="cit14"><label>14</label><citation-alternatives><mixed-citation xml:lang="ru">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.</mixed-citation><mixed-citation xml:lang="en">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.</mixed-citation></citation-alternatives></ref><ref id="cit15"><label>15</label><citation-alternatives><mixed-citation xml:lang="ru">Cruz N. B., Nedjah N., de Macedo Mourelle L. Robust distributed spatial clustering for swarm robotic based systems // Applied Soft Computing. 2016.</mixed-citation><mixed-citation xml:lang="en">Cruz N. B., Nedjah N., de Macedo Mourelle L. Robust distributed spatial clustering for swarm robotic based systems // Applied Soft Computing. 2016.</mixed-citation></citation-alternatives></ref><ref id="cit16"><label>16</label><citation-alternatives><mixed-citation xml:lang="ru">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.</mixed-citation><mixed-citation xml:lang="en">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.</mixed-citation></citation-alternatives></ref><ref id="cit17"><label>17</label><citation-alternatives><mixed-citation xml:lang="ru">Карпова И. П. Псевдоаналоговая коммуникация в группе роботов // Мехатроника, автоматизация, управление. 2016. Т. 17. № 2. С. 94-101.</mixed-citation><mixed-citation xml:lang="en">Карпова И. П. Псевдоаналоговая коммуникация в группе роботов // Мехатроника, автоматизация, управление. 2016. Т. 17. № 2. С. 94-101.</mixed-citation></citation-alternatives></ref><ref id="cit18"><label>18</label><citation-alternatives><mixed-citation xml:lang="ru">Воробьев В. В., Московский А. Д. Алгоритм выбора лидера в системах с меняющейся топологией // Пятнадцатая национальная конференция по искусственному интеллекту с международным участием КИИ-2016 (3-7 октября 2016, г. Смоленск, Россия): Труды конференции. В 3-х томах. Т. 1. Смоленск: Универсум, 2016. С. 149-157.</mixed-citation><mixed-citation xml:lang="en">Воробьев В. В., Московский А. Д. Алгоритм выбора лидера в системах с меняющейся топологией // Пятнадцатая национальная конференция по искусственному интеллекту с международным участием КИИ-2016 (3-7 октября 2016, г. Смоленск, Россия): Труды конференции. В 3-х томах. Т. 1. Смоленск: Универсум, 2016. С. 149-157.</mixed-citation></citation-alternatives></ref><ref id="cit19"><label>19</label><citation-alternatives><mixed-citation xml:lang="ru">Воробьев В. В. Алгоритм кластеризации коллектива роботов // Третий Всероссийский научно-практический семинар "Беспилотные транспортные средства с элементами искуственного интеллекта" (БТС-ИИ-2016, 22-23 сентября 2016 г., г. Иннополис, Республика Татарстан, Россия): Труды семинара. М: Издательство "Перо", 2016. С. 50-59.</mixed-citation><mixed-citation xml:lang="en">Воробьев В. В. Алгоритм кластеризации коллектива роботов // Третий Всероссийский научно-практический семинар "Беспилотные транспортные средства с элементами искуственного интеллекта" (БТС-ИИ-2016, 22-23 сентября 2016 г., г. Иннополис, Республика Татарстан, Россия): Труды семинара. М: Издательство "Перо", 2016. С. 50-59.</mixed-citation></citation-alternatives></ref></ref-list><fn-group><fn fn-type="conflict"><p>The authors declare that there are no conflicts of interest present.</p></fn></fn-group></back></article>
