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

Размещено на http://www.allbest.ru/

Уфимский государственный авиационный технический университет

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

Ф.Б. Биктимиров (koi8-r@yandex.ru)

Е.В. Лапшова (levvel.888@gmail.ru)

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

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

Применение позиционирования коллектива роботов в различные формации может найти применение в решении реальных задач:

окружение области или объекта;

формирование равномерно распределенных групп или единиц роботов для защиты территории, построения сетей сбора, обработки информации;

изучение, разведка местности, представляющей опасность для человека;

транспортирование грузов;

сборка, ремонт объектов.

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

алгоритм позиционирования в окружность (в зарубежной литературе circle formation algorithm);

алгоритм позиционирования в другую формацию.

В данной работе в разделе 2 представлен обзор существующих методик и алгоритмов, в разделе 3 рассматривается CF-алгоритм, основанный на вычислении потенциала области.

Обзор литературы

В существующих исследованиях в области позиционирования следует выделить несколько направлений применения алгоритмов позиционирования. Так можно различать алгоритмы по способу управления централизованные [WangBao et al., 2008], [NafRn et al., 2006] и децентрализованные [Parke LE, 2000], так же свою специфику накладывает техническое обеспечение роботов [Webers et al., 2002], [Trianni et al., 2006] и проблемы, на решение которых направлены применяемые алгоритмы, например, задачи исследования и построения карты местности, так называемые SLAM-алгоритмы (Simultaneous Localization and Mapping). В исследовании CF-алгоритмов следует выделить работу Сузуки [Suzuki et al., 1999], [Suzuki et al., 1996]. В своих работах Сузуки применяет модель робота, который обладает сенсорами, позволяющими мгновенно определять позицию соседнего или любого робота в группе. На модели Сузуки базируются работы Дефаго и Конагая [Defago et al., 2002]. Так же следует выделить работы [Leonard et al., 2001], [Olfati et al., 2002], в которых рассматривается применение искусственных потенциалов для позиционирования.

CF-алгоритм для позиционирования группы роботов

Представленный в данном разделе алгоритм базируется на следующих допущениях:

робот имеет сенсоры, позволяющие определять расстояние до любого робота из группы, находящегося в зоне видимости;

робот не имеет устройств хранения данных о своих предыдущих состояниях;

роботы обмениваются информацией между собой;

любой робот из группы способен генерировать случайное число;

каждый робот имеет вектор направления движения;

все роботы в группе одинаковы по характеристикам и не идентифицируются каким-либо уникальным ключом.

Для построения окружности добавим следующие условия: координаты центра окружности и радиус формируемого шаблона построения задаются для каждого робота заранее.

Данный алгоритм основан на вычислении оптимального потенциала области в зоне видимости одного робота. Зона видимости разделена на равные части (области). Робот может передвигаться в направлении каждой зоны, на рисунке 1 представлена зона видимости робота. Стрелками на рисунке показано, по каким направлениям может перемещаться робот.

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

Рис. 1. Зона видимости

На рисунке 2 представлен результат выполнения алгоритма для 11 роботов.

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

Рис. 2. Результаты выполнения алгоритма для 11 роботов

Алгоритм перестроения

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

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

выравнивание векторов направления движения роботов,

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

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

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

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

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

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

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

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

Список литературы

1. 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.

2. Itai A., Rodeh M. Symmetry breaking in distributed networks // Foundations of Computer Science. 1980.

3. Leonard N. E., Fiorelli E.. Virtual leaders, artificial potentials and coordinated control of groups. In IEEE Conference on Decision and Control, Orlando, FL, Dec. 2001.

4. NafRn David J., Mehmet Akar, Sukhatme Gaurav S. Lateral and Longitudinal Stability for Decentralized Formation Control, 2006

5. Olfati R., Murray R. M. Distributed cooperative control of multiple vehicle formations using structural potential functions. In 15th Triennial World Congress, Barcelona, Spain, 2002.

6. Ostergaard E., Mataric MJ, Sukhatme GS (2001) In IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), 2.

7. Parke LE (2000) Proceedings of the 5th International Symposium on Distributed Autonomous Robotic Sys tems, DARS, Springer Verlag, 4.

8. Suzuki I., Yamashita M. (1996) Distributed Anonymous Mobile Robots- Formation and Agreement Problems, In Proc. Third Colloq. On Struc. Information and Communication Complexity (SIROCCO).

9. Suzuki I., Yamashita M. (1999) Distributed Anonymous Mobile Robots: Formation of Geometric Patterns, Siam J. Comput., 28(4).

10. Swaminathan Karthikeyan, Minai Ali A. A General Approach to Swarm Coordination using Circle Formation. 2008

11. Tel Gerard. Introduction to Distributed Algorithms. Ed. 2^nd. // Cambridge University Press. 2000.

12. Trianni Vito, Dorigo Marco. Self-organisation and communication in groups of simulated and physical robots, Springer-Verlag 2006.

13. WangBao XU, CHEN XueBo. Artificial moment method for swarm robot formation control, 2008.

14. Webers Christfreid, Zimmer Uwe R. Motion Control of Mobile Robots-From Static Targets to Fast Drives in Moving Crowds, 2002.

Размещено на Allbest.ru