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

Массивное распараллеливание и разделение общих задач, обеспечиваемое совместной работой простых механизмов, намного эффективнее и экономичнее использования одного более сложного. По этому поводу со времён товарища Форда ни у кого вопросов не возникает. А если посмотреть соревнования F1, то там это кажется настолько органичным, что будто по-другому и нельзя.

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

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

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

Эти особенности присутствуют в той или иной мере во всех естественных роевых системах, но на нашем уровне технологического развития не всегда возможно воспроизвести полёт фантазии «матушки природы». Некоторые роевые природные механики нам не только недоступны технологически, но и вообще пока находятся за гранью нашего понимания и являются предметом жгучего научного интереса на стыке самых различных дисциплин и приложений. Поэтому сегодня много исследований и практических экспериментов биоинспирированных методов локализации. Каков бы ни был интерес к опыту членистоногих (и не только), на сегодняшний день серьёзные реальные приложения роевых роботизированных систем отсутствуют чуть более, чем полностью.

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

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

В естественных условиях роевые системы бывают как однородными, так и гетерогенными. В подобной организации содержится здравое зерно. Идея совершенно не моя, она «тыщупицот» раз описана в художественной литературе, а в природе существует ещё дольше. Если некоторая часть роя остаётся неподвижной и служит указателем для остального роя, то такие стационарные члены образуют глобальную систему отсчёта, а остальная часть группы локализует себя в ней с помощью RSSI (показатель уровня принимаемого сигнала). 

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

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

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

В таких условиях неплохо себя показали алгоритмы одновременной локализации и картирования (Simultaneous localization and mapping, SLAM), хотя, когда необходимы небольшие и относительно простые роботы, сложность алгоритмов и вычислительная стоимость становятся серьёзным недостатком. Помимо SLAM, существуют другие методы локализации, например, с помощью маяков и ориентиров, использующие инерциальные навигационные системы (магнитные, звуковые, оптические), псевдолиты и др.

Псевдолиты (т.е. псевдоспутники) — наземные передатчики, посылающие сигналы глобальной навигационной спутниковой системе. Как независимая система для позиционирования внутри помещений, техника псевдоспутников может быть использована для широкого спектра приложений позиционирования и навигации, где невозможно получить сигнал спутниковой системы. У этого подхода также есть свои плюсы и минусы. Основным недостатком является увеличение стоимости установки и эксплуатации навигационной сети. Кроме того, в случае отказа основного приемника сигнала вся сеть становится непригодной для использования.

Концепция псевдоспутников была предложена ещё в 1970-х годах, до запуска системы GPS. На самом деле они изначально были разработаны для тестирования пользовательского оборудования GPS. Псевдолиты могут использоваться в качестве инструмента расширения для космических спутниковых систем позиционирования. Такое расширение повышает производительность всей системы, значительно улучшая доступность и геометрию позиционирования. Кроме того, такая система позиционирования может заменить группировку космических спутников там, где использование спутниковых сигналов невозможно, например, под землей и в экранированных помещениях. Использование и проектирование навигационных систем на базе псевдоспутников — интересная тема, и в любом случае требует отдельной статьи, поэтому в будущем, может быть, я за неё возьмусь.

Инерционная локализация также является распространенным подходом. На основании одометров, акселерометров и гироскопов можно определять ориентацию и направление движения робота. Хотя полученные результаты устойчивы к изменениям окружающей среды, этот метод склонен к накоплению ошибок. Иногда для повышения точности используются дорогостоящие фильтры Калмана. Обычно предпочтение отдается радиочастотной локализации. Маяки могут покрывать большую площадь, а большинство материалов не являются помехой для распространения радиоволн, к тому же стоимость установки и эксплуатации системы относительно невелика. 

В качестве маяков для локализации роботов, перемещающихся внутри помещений, иногда используют технологию радиочастотной идентификации (RFID). Установленные пассивные RFID-метки формируют сетку на всём рабочем пространстве. Когда робот, оснащенный считывателем RFID, перемещается по территории, считыватель сканирует метку, а положение оценивается путём сопоставления идентификатора с картой, содержащей информацию о локализации меток. Несмотря на высокую точность, потребность в карте, содержащей идентификатор и расположение меток, ограничивает практическое применение таких систем.

В этой статье мы рассмотрим относительно простую систему, основанную на уровне принимаемого сигнала (RSSI). Основная идея состоит в том, чтобы определить местоположение робота не в робоцентрической системе, а в глобальной системе координат, позволяющей членам роботизированного роя использовать общую карту.

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

Исследований, да и практических реализаций навигации, основанной на RSSI разнородных источников (WLAN, GSM и т. д.), достаточно много, и большая их часть работает по схожим паттернам. Анализируя слепки сигналов и их мощность, система может определять своё местоположение, сравнивая его с картой слепков. Чем интересна такая система, так это тем, что при использовании существующей инфраструктуры сводится на нет необходимость развёртывания новой навигационной сети, правда, серьёзным недостатком является необходимость наличия карты слепков сигналов, охватывающей всю интересующую область.

Итак, постановка задачи.

Локализация робота основана на RSSI. По электромагнитному сигналу координаты источника в трёхмерном пространстве могут быть рассчитаны как в робоцентрической системе, так и в глобальной системе координат. Для достижения цели используются три маяка, создающие общую трёхмерную систему координат для всех роботов. Исходя из этого, были сделаны следующие предположения:

• все роботы оснащены датчиками, способными считывать RSSI,

• два робота выступают в роли импровизированных якорей,

• маяк (в нашем случае робот) размещается в центре системы координат.

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

Приёмники размещаются по внешнему периметру робота, а приёмопередатчик в центре, как показано на схематическом рисунке ниже.

Каждый датчик способен идентифицировать как источник сигнала, так и мощность сигнала. Мощность сигнала S обратно пропорциональна квадрату расстояния d между датчиком и источником (1). Используя (1), можно рассчитать расстояние между источником и каждым датчиком (2).

Координаты каждого датчика в роботоцентрической системе можно увидеть в таблице ниже. Пусть (x_S, y_S, z_S) — координаты источника сигнала в роботоцентрической системе. Используя (2), расстояние между каждым датчиком (центр, передний, левый, правый) и источником показано ниже.

Вычитая уравнение (4) из (3) и (6) из (5), можно вычислить координаты источника x_Sи y_S, соответственно. Путём замены значений x_Sи y_S в уравнении (3) можно рассчитать координату z_S. С помощью (7) вычисляются координаты маяка (x_b, y_b, z_b) и якорных роботов (x_a1, y_a1, z_a1), (x_a2, y_a2, z_a2).

A. Расширенная локализация

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

Обновленные центральные координаты робота представлены в следующей таблице. 

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

Алгоритм поиска местоположения маяка (Find_Beacon_Location)

Б. Глобальная локализация

Как уже было описано выше, робот способен вычислять координаты трёх маяков в робоцентрической системе. Зная их относительное положение, можно рассчитать глобальное положение робота. Пусть A — центр системы координат, а B и C — маяки, определяющие оси X и Y, соответственно.

Используя векторы и определяем три новых вектора, используя внешние произведения (8), и нормализуем их.

Пусть будет вектором между центром робота R и A. Теперь мы можем вычислить координаты робота в глобальной системе, определяемой тремя векторами , , . Координаты робота (x_r, y_r, z_r) представляют собой скалярное произведение и  , , соответственно (9).

Теперь представим полный алгоритм.

 Алгоритм получения глобальных координат (Get_Global_Coordinates)

Чтобы оценить эффективность данного подхода к локализации, реализуем алгоритм в симуляторе Webots. Для упрощения возьмём рой из четырёх одинаковых универсальных роботов круглой формы с радиусом 20 см, оснащённых четырьмя радиоприёмниками, способными фиксировать мощность сигнала по периметру, и радиопередатчиком в центре. Три из них служат маяками.

Итак, три робота, действовавшие как маяки, постоянно излучали радиосигнал с уникальным идентификатором, что позволяло роботу идентифицировать источник сигнала. Чтобы ещё больше повысить точность, каждый маяк передавался по отличному каналу, что уменьшало генерируемый шум. Для каждого источника также усреднялся RSSI, что уменьшало шумовую ошибку. Робот циклически перемещался по трём заданным каналам, что позволяло ему идентифицировать и определять положение каждого маяка. Наконец, были рассчитаны и отражены глобальные координаты.

Во время эксперимента робот был статичен при расчёте своего положения. После успешного расчёта он перемещался случайным образом, и новое положение также рассчитывалось и фиксировалось. Было произведено 10 итераций. Ошибка (т. е. евклидово расстояние между реальным и рассчитанным глобальным местоположением) для каждого местоположения усреднялась и использовалась в качестве метрики. В бесшумной среде расчётное положение совпадало с реальным, независимо от расстояния до маяков или ориентации робота.

Чтобы оценить этот подход в более реальных условиях, в эксперимент постепенно вводился шум. Всего описанный выше процесс был повторен 5 раз с 5 различными уровнями шума: 10%, 20%, 30%, 40% и 50%. Как видно на графике ниже, для 10 % шума ошибка составила 0,6 м, а для 20 % шума — 1,4 м. Дальнейшее увеличение шума оказало ещё большее влияние.

Поскольку помехи связаны с расстоянием до источника, был проведён эксперимент, в котором расстояние между роботом и маяками постепенно увеличивалось. Три маяка были размещены вручную, образуя равнобедренный треугольник. Такое размещение гарантировало, что расстояние между роботом и двумя маяками будет одинаковым. Сторона образовавшегося треугольника составила 4 м, а уровень шума был установлен в 10%. Проведено 10 итераций, а результаты также усреднены. Далее на графике можно увидеть, что ошибка составила 0,6 м, когда робот находился ближе к источнику, что может свидетельствовать о более высоком уровне генерируемого шума при меньшем расстоянии между роботом и источником. Наилучшие результаты наблюдались, когда робот находился на расстоянии 3-3,5 м от маяков. Стоит отметить, что для расстояний до шести метров расчётная ошибка определения местоположения составляла менее одного метра.

Также был проведён эксперимент с использованием другого роя уже из трёх устройств. Первый робот был размещён вдали от маяков, второй рядом с двумя из них, а третий рядом с тремя роботами-маяками. Роботы сообщали о своем глобальном местоположении 10 раз с временной задержкой между каждым расчётом. Уровень шума — 10%. Также был введён дополнительный шум, когда каждый робот излучал случайный сигнал, имитирующий среду, в которой роботы коммуницируют друг с другом. На рисунке ниже видно положение каждого робота. Результаты показывают, что даже дополнительный шум (информационный обмен между членами роя) не сильно влияет на процесс локализации. Стоит отметить, что на расчёты влияет расстояние между роботом и маяками (как я уже указывал выше).

И каков итог?

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

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

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

Также я вижу ещё как минимум одно направление для исследований, а именно информационная безопасность такой навигационной системы. Открытый обмен навигационной информацией стопроцентно вызовет интерес недоброжелателей и потребует каких-то мер. Также наверняка потребуются какие-то технологические средства установления факта достоверности прямой и обратной связи («свой-чужой»). Учитывая экономику, это должны быть какие-то простые и эффективные протоколы информационного обмена и шифрования, нетребовательные к вычислительным ресурсам, но это уже совсем другая история.

НЛО прилетело и оставило здесь промокод для читателей нашего блога:
-15% на заказ любого VDS (кроме тарифа Прогрев) — HABRFIRSTVDS.