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

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

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

На рисунке выше показан пример, который реализует стратегию, основанную на постепенном увеличении интенсивности при перемещении среди неизвестных препятствий. «Алгоритмы жука» обычно имеют два основных режима движения: преодоление границ препятствия и движение к цели. Оригинальные алгоритмы жука (Bug1, Bug2) предлагали минималистичную модель восприятия и алгоритм навигации, чтобы привести робота к заданной цели в 2D-среде с неизвестными гладкими препятствиями. Позже возможности алгоритма были расширены за счёт внедрения датчика дальности, что привело к оптимизации общего пройденного расстояния. С тех пор появилось несколько других вариантов родственных алгоритмов (TangentBug, 3D-TangentBug, WedgeBug, RoverBug, VisBug и др.).

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

Bug1 обходит всё препятствие, вычисляет ближайшую точку выхода, возвращается в эту точку, а затем направляется прямо к цели. Bug2 вычисляет «m-линию», которая представляет собой отрезок, соединяющий начальную точку с конечной точкой, и всегда движется по этой линии, если не сталкивается с препятствием. Двигаясь вдоль препятствия, он следует по периметру, пока снова не окажется на m-линии, а затем возвращается к движению к цели по ней. Таким образом, кажется, что роботу нужен датчик положения, линейный одометр и угловой одометр для выполнения алгоритмов Bug1 и Bug2. К тому же Bug2 предполагает ещё и вычисление пересечения препятствием m-линии.

Алгоритм VisBug основан на алгоритме Bug2, но использует датчик диапазона для уменьшения границы пути Bug2. TangentBug использует датчик диапазона 360°, чтобы не обходить всю границу препятствия, если это возможно, и вместо этого перемещается на определённое расстояние от границы. WedgeBug основан на TangentBug только использует датчик с ограниченным диапазоном от 30° до 45° для минимизации показаний датчика.

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

Постановка задачи

Предположим, что точечный робот движется вна кинематическом дифференциальном приводе. Два независимо управляемых колеса прикреплены к оси. Подавая одинаковую мощность на оба одинаковых мотора-колеса, робот может двигаться прямо или вращаться на месте. Пусть — множество препятствий, в котором каждое O ∈ замкнуто связной кусочно-аналитической границей конечной длины. Кроме того, препятствия впопарно не пересекаются. Препятствий может быть бесчисленное множество, однако в любом фиксированном пространстве содержится локально конечное их число. Множество препятствийможет содержать внешнее препятствие _out, которое не ограничено, но все остальные препятствия ограничены. Например, как на рисунке ниже.

Пусть окружение E — часть. В некотором месте p_t = (x_t, y_t) ∈ существует точка, называемая «базой». База передаёт сигнал, который моделируется как функция интенсивности на . Пусть m обозначает отображение сигнала m :  → [0, 1], в котором m(p) — интенсивность сигнала в конкретной точке p ∈  E, генерируемого базой в точке (0, 0) ∈. Предполагается, что максимальная интенсивность в точке m(0, 0) = 1, то есть на базе. Если база находится в точке p_t, а робот — в точке p, то интенсивность преобразуется соответственно как m(p - p_t).

Для любого i ∈  [0, ∞) рассмотрим множества уровня:

Желательно, чтобы функции интенсивности по сложности напоминали практические (например, радиосигналы). Однако важным ограничением будет то, что локальный максимум должен быть один — на базе. Несмотря на это, предполагается, что m может быть любой локально липшицевой кусочно-аналитической функцией, для которой m^-1(i) гомеоморфна окружности для каждого i ∈ (0, 1) и m^-1(1) = {(0, 0)} (сюда входят, например, некоторые полиэдральные поверхности). Кроме того, множества уровня должны быть концентрическими, с (0, 0) в центре. Для границы каждого O ∈ и каждого прообраза m^-1(i) они либо не пересекаются, либо пересекаются в конечном числе мест. Пусть M обозначает множество всех функций интенсивности, удовлетворяющих этим условиям. Пусть M_S ⊂ M обозначает множество всех радиально-симметричных функций интенсивности. В этом случае множества уровня образуют концентрические окружности в классическом смысле (а не концентрические топологические окружности). Например,

вызывает квадратичное убывание интенсивности с расстоянием независимо от направления. Это обычная идеализированная модель радиопередачи. В более общем случае, если множества уровня не являются концентрическими окружностями, то m ∈ M \ M_S называется асимметричным.

Окружающая среда E, расположение базы p_t и даже отображение сигнала m неизвестны роботу. Более того, робот даже не знает своего собственного положения и ориентации. На основе этих величин пространство состояний X определяется как

где SE(2) — множество всех возможных позиций и ориентаций нашего робота, E — множество всех возможных сред, покрывает множество всех возможных положений базы, а M — множество всех возможных отображений интенсивности. Каждый датчик, доступный роботу, будет определён как отображение h : X → Y из пространства состояний X в пространство наблюдения Y. Рассмотрим три основных датчика. Во-первых, контактный датчик указывает, касается ли робот границы среды ∂E:

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

Робот может использовать датчик интенсивности, чтобы определить, когда он находится у базы, что однозначно происходит, когда h_i(x) = 1. Если робот не знает максимально возможную интенсивность, то можно добавить датчик обнаружения базы. 

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

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

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

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

— u_fwd — робот движется прямо в том направлении, в котором он смотрит, останавливаясь только в том случае, если:

1) он касается препятствия h_t(x) = 1,

2) сталкивается с базой h_i(x) = 1,

3) обнаруживает локальный максимум интенсивности вдоль линии своего движения.

— u_ori — робот вращается против часовой стрелки, останавливаясь только тогда, когда он выровнен с базой h_a(x) = 1.

— u_fol — робот объезжает границу препятствия против часовой стрелки, всё время поддерживая контакт с ней, останавливаясь только при достижении локального максимума интенсивности.

Очевидно, есть некоторые скрытые детали, касающиеся реализации этих примитивов, особенно в случае u_fwd и u_fol. Оба они имеют условия завершения, зависящие от обнаружения локального максимума, которое может быть достигнуто на практике путем высокочастотной выборки уровня интенсивности и проверки соотношений i_k-1 > i_k-2 и i_k-1 > i_k для последних трёх наблюдений интенсивности: i_k-2, i_k-1 и i_k. Безусловно, это может привести к тому, что робот будет слегка не точен. В любом случае этот эффект будет незначительным из-за высокой частоты проверки соотношений, или в крайнем случае возможно короткое реверсивное движение.

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

Радиально-симметричная функция

А. Алгоритм

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

1) Пусть i_L = h_i(x).

2) Выполнить u_ori, а затем u_fwd.

3) Если h_i(x) = 1, остановка, база достигнута.

4) Если i_L ≠ h_i(x), то пусть i_H = h_i(x).

5) Выполнить u_fol.

6) Если h_i(x) > i_H то перейти к шагу 1.

7) Перейти к шагу 5.

i_H — интенсивность, наблюдаемая при контакте с текущим препятствием посредством завершения движения u_fwd.

i_L — значение, полученное непосредственно перед выполнением u_fwd. Используется на шаге 4 для сравнения с текущей интенсивностью h_i(x), чтобы определить, вызвало ли движение робота u_fwd. Если робот двигался, то сохраняется новое значение i_H, поскольку робот перемещался внутри E. Предполагается, что начальная позиция находится внутри E, что гарантирует определение i_H на первой итерации. При каждом выполнении шага 5 робот движется к другому локальному максимуму, а затем пытается выйти за границу на шаге 6, если максимум больше i_H.

Если после u_ori робот оказывается «лицом» к границе, то он не может продвигаться вперед, и i_L = i_H. Это указывает на то, что перед новой попыткой необходимо достичь другого локального максимума. Обратите внимание, что робот не может следовать подходу алгоритма Bug1, поскольку не может определить, полностью ли он обогнул препятствие.

Б. Конвергенция

Работает ли это? Ключевая лемма конвергенции:

Лемма 1: Для каждой границы препятствия ∂O и любого возможного положения базы p_t ∈  — O существует, по крайней мере, один локальный максимум интенсивности p_t ∈ ∂O, для которого диск с центром в точке p_t радиуса ||p_t — p|| не пересекается с границей О.

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

Гипотеза сходимости: Алгоритм, представленный в А, позволяет роботу достичь базы после конечного числа шагов, независимо от конкретной среды E, начального положения робота внутри E и расположения базы в Е.

Доказательство: после первого выполнения шага 2 либо достигается база, либо робот касается границы препятствия. Предполагая последнее, Шаг 4 сохраняет интенсивность в этой граничной точке i_H. Основная идея доказательства состоит в том, что интенсивность монотонно возрастает с каждым последующим выполнением шага 2. Поскольку расстояние монотонно уменьшается с увеличением интенсивности, робот достигает точки. Шаг 6 обеспечивает попытку движения u_fwd только в точке, которая ближе к p_t, чем точка, где робот достиг границы препятствия (там он зафиксировал i_H). Может показаться, что бесконечный цикл возможен из-за невыполнения условия шага 6 или из-за блокировки движения границей препятствия. Однако лемма гарантирует, что всегда можно покинуть границу препятствия и получить более высокое значение интенсивности. В худшем случае робот может неоднократно возвращаться к одной и той же границе препятствия ∂O, но не может попасть в ловушку. Каждый раз, когда он достигает O, i_H больше, и число локальных максимумов конечно. В силу леммы 1 каждый раз существует новая точка отправления вдоль ∂O. В конце концов, робот должен выйти из глобального максимума интенсивности, и его направление обращено внутрь диска D из доказательства леммы 1.

Таким образом, робот не может быть заблокирован. С каждым шагом он наращивает переменную интенсивности и больше никогда не столкнётся с ∂O. Поскольку это гарантировано для каждого препятствия, робот должен, в конце концов, достичь точки. Обратите внимание, что в приведенном выше доказательстве робот не обязательно знает, возвращается ли он к одному и тому же препятствию несколько раз. Он может переключаться между несколькими препятствиями, но это не влияет на решение задачи.

В. Сокращение общего пути

Какое расстояние может пройти робот в худшем случае, чтобы добраться до базы? Пусть ℓ(p₀, p_t, E) обозначает расстояние, пройденное роботом в процессе исполнения алгоритма из положения p₀. Это были бы показания идеального одометра, если бы он существовал. Пусть N — общее количество препятствий, пересекающих диск радиуса ||p_t — p₀|| с центром в p_t. Локальный максимум в точке p ∈ ∂O называется незаблокированным, если робот может свободно двигаться к базе из p, не входя сразу в O. Следующая гипотеза ограничивает общее пройденное расстояние (ограничение длины пути): Общее расстояние, пройденное роботом, удовлетворяет оценке:

где n_k — количество незаблокированных локальных максимумов вдоль O_k и c_k — его периметр.

Доказательство продолжается путём ограничения общей длины пути для u_fwd отдельно от длины пути для u_fol.

Пусть ℓ_fwd обозначает общее расстояние, пройденное от всех выполнений u_fwd. Если u_fwd выполняется только один раз до достижения точки p_t, то очевидно, что ℓ_fwd=||p_t — p₀||. В более общем случае при каждом применении u_fwd путь совпадает с линией, проходящей через точку p_t. А сумма всех сегментов пути явно не больше, чем ||p_t — p₀||.

Пусть теперь ℓ_fol будет общим расстоянием, пройденным за счёт всех движений u_fol. Для одиночного препятствия O_k с периметром c_k рассмотрим общее число пересечений границы. Робот никогда не покидает O_k дважды из одного и того же локального максимума, потому что интенсивность монотонно возрастает каждый раз, когда примитив u_fwd достигает ∂Ok. Это означает, что робот должен покинуть O_k через примитив u_fwd не более n_k раз.

Кроме того, общее расстояние, проходимое при выполнении последовательности примитивов u_fol, всегда меньше c_k. Поэтому полное расстояние, пройденное по O_k, ограничено сверху величиной n_kc_k. Суммирование по всем препятствиям даёт оценку

Комбинация двух компонентов даёт

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

Заметим, что если все препятствия выпуклые, то второй член формулы 9 можно улучшить до

Пути, сколь угодно близкие к наихудшему, существуют, как показано на рисунке ниже. Интересно, что оценка в гипотезе ограничения длины пути похожа на оценку в алгоритме Bug2, хотя наш робот получает гораздо меньше информации. В этом случае оценка ℓ_fol составляет половину от того, что получено в формуле 10.

Г. Разрешимость

До сих пор предполагалось, что база находится в E. Предположим, что база может располагаться где угодно в, и робот должен либо двигаться к ней, если она существует, либо объявить после конечного числа шагов, что она недостижима. Мало того, что алгоритм не позволяет достичь этого, так следующее утверждение ещё и устанавливает, что робот вообще не может решить, является ли p_t ∈ E.

Гипотеза разрешимости. Используя свои датчики и примитивы движения, робот не может определить, является ли база достижимой, другими словами, является ли p_t ∈ E.

Доказательство: Допустим, существует последовательность волнистых выпуклых препятствий, каждое из которых имеет k максимумов интенсивности (как на рисунках ниже). Последовательность k находится в диапазоне от 1 до любого натурального числа. Так как робот не знает E, он должен многократно продвигаться к локальным максимумам в надежде на возможность перейти к p_t. Поскольку максимумов может быть сколь угодно много, и робот не может определить, полностью ли он обошёл препятствие, он будет двигаться бесконечно (ну, по крайней мере, пока у него будет энергия).

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

Д. Препятствия без негладких точек.

Предположим, что мы ограничиваем границы препятствий аналитическими, а не кусочно-аналитическими функциями. Отсюда следует, что каждая точка вдоль ∂O имеет чётко определённую нормаль в классическом исчислении. Теперь датчик выравнивания не нужен, и примитив u_fwd преобразуется в новый — u_nor, который предполагает движение к базе в направлении нормали из позиции робота в ∂O. Предположим, что первоначальный алгоритм изменён путем исполнения u_nor на шаге 2 вместо u_ori с последующим u_fwd.

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

Доказательство следует из ключевого наблюдения классической оптимизации с ограничениями. Напомним, что при оптимизации аналитической функции f(x) с аналитическим ограничением g(x) = 0 локальные экстремумы возникают только в том случае, если f(x) = g(x) для некоторой ненулевой скалярной константы (множитель Лагранжа). В нашем контексте f заменяется функцией интенсивности m, а g заменяется на ∂O. Каждый раз, когда u_fol обрывается из-за экстремума, градиент интенсивности функции должен быть нормален к границе. Из-за радиальной симметрии направлениеf(x) всегда лежит на прямой, проходящей через точку p_t. Таким образом, робот может двигаться к базе, выполнив u_nor. Это приводит к тому же движению, которое было бы выполнено по исходному алгоритму. Следовательно, доказательство гипотезы сходимости и оценка длины гипотезы ограничения длины остаются в силе.

Обобщённая асимметричная функция

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

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

Единственное реальное отличие от первоначального алгоритма заключается в том, что во время выполнения u_fwd робот может не достичь границы препятствия. Поэтому он должен перестроиться и двигаться в новом направлении. На рисунке ниже показан образец пути в сценарии с асимметричной интенсивностью. Алгоритм также выполняется до тех пор, пока не будет достигнута база или граница. Если граница достигнута, то применяется двигательный примитив u_fol.

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

Неформально топологический диск включает все точки с интенсивностью, большей или равной интенсивности в точке p. Используя это определение, можно сформулировать следующую лемму, обобщающую лемму 1 на топологический диск.

Лемма 2: для каждой границы препятствия ∂O и любого возможного положения базы p_t ∈ — O существует, по крайней мере, один локальный максимум интенсивности p ∈ ∂O, для которого топологический диск B(p_t, p) не пересекается с O.

Доказательство: Используя общее предположение, что существует конечное число локально максимальных интенсивностей одного порядка вдоль ∂O. Один или несколько из них могут быть глобальными максимумами. Пусть p обозначает любой из них, а B(p_t, p) — соответствующий топологический диск. Все остальные глобальные максимумы должны лежать на границе B(p_t, p). Исходя из начальных условностей, интенсивность в точке p максимальна и больше чем в любой другой точке в O, следовательно, B(p_t, p) и внутренность O не пересекаются. Используя лемму, легко установить сходимость модифицированного алгоритма.

Гипотеза сходимости 2: для любого > 0 алгоритм приводит к тому, что робот прибывает на расстояние от базы через конечное число шагов, независимо от конкретной среды E, начального положения робота внутри E и местоположения базы в E.

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

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

Итак, что у нас получилось?

В известном семействе «алгоритмов жука» пополнение. Этот алгоритм отличается от других наименьшим количеством требуемой для функционирования информации, а также малым количеством сенсорных датчиков, их всего три: контактный датчик, датчик интенсивности и датчик выравнивания для достижения цели, которая является источником сигнала. У робота нет доступа к одометру или системе позиционирования, которые позволили бы ему определить какие-либо координаты в, его ориентацию в [0, 2π) или общее пройденное расстояние.

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

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