Алгоритм перестроения. 
Применение CF-алгоритма в позиционировании группы мобильных автономных роботов

Рассмотрим алгоритмы перестроения из базового шаблона в другие шаблоны. Каждый шаблон отличный от окружности требует своего алгоритма построения. Каждый алгоритм перестроения начинается с выбора лидера группы. Поиск лидера в анонимной децентрализованной системе удобно осуществлять с помощью алгоритма типа Лас-Вегас, с учетом начальных допущений данный алгоритм путем конечного числа итераций с вероятностью единица даст результат. В данной статье для выбора лидера группы был применен алгоритм Айтаи-Роде [Itai et al., 1980], [Tel, 2000]. Для реализации данного алгоритма поиска лидера было сделано допущение о том, что каждый робот способен генерировать случайное число. Лидер находится путем конечного числа голосований в группе. После выполнения алгоритма поиска лидера группы следующим шагом в алгоритме перестроения является выравнивание вектора направления движения каждого робота в соответствии с вектором направления движения робота лидера. Перечисленные шаги:

выбор лидера;

выравнивание векторов направления движения роботов, являются одинаковыми для всех алгоритмов перестроения.

Рассмотрим дальнейшие этапы алгоритма перестроения в горизонтальную линию. Робот лидер маркирует каждого робота, раздавая временные идентификационные номера. Далее робот лидер передает желаемую позицию первому роботу согласно идентификационному номеру, тот передает дальше так же согласно следующего идентификационного номера и так далее, пока не будет задействован последний робот в группе. В данном алгоритме каждый робот, кроме последнего и робота лидера являются дополнительными лидерами, так как задают желаемые позиции следующему за ним роботу. На рисунке 3 изображен ход выполнения перестроения.

Из рисунка видно, как идет перестроение в линию. Для большей наглядности при получении данного рисунка шаг и допустимая ошибка позиционирования были увеличены.

При рассмотрении других шаблонов, алгоритм перестроения из базового шаблона будет отличаться количеством дополнительных лидеров. Так, например, для построения в ромб робот лидер посылает в кольцо информационный пакет, который выделяет дополнительных трех лидеров, которые в свою очередь начинают отправку информационных пакетов для формирования ребер ромба.

алгоритм позиционирование мобильный робот.

Рис. 4. Последовательность ходов роботов при перестроении в ромб

Рассмотренный способ позиционирования роботов позволяет использовать гомогенные группы роботов без явной уникальности каждого члена группы, что позволяет применять роботов различной технической оснащенности, если конечно уровень оснащенности удовлетворяет указанным в данной статье допущениям. Отрицательной стороной данного метода позиционирования группы автономных мобильных роботов является его громоздкость и большие требования к временным ресурсам.