В работе [10] рассматривается архитектура систем навигации реального времени, используемых в том числе для обхода препятствий мобильными роботами (МР). Подробно рассмотрены следующие результаты:

– виды архитектуры и технологии соответствующих датчиков (сенсоров);

– представление различных моделей поведения с помощью сенсорно-управляемых алгоритмов;

– метод искусственного потенциального поля - алгоритм реального времени, разработанный специально для навигации МР во процессе движения.

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

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

Пусть угол - угловой шаг сканирования, di - результат i_го (относительно текущего направления движения МР) замера дальности от МР до препятствия. В соответствие каждому di ставится вектор силы fi, вычисляемый с помощью уравнений для искусственного потенциального поля:

(2.3)

где A - фиксированная константа. После обзора всего сектора (360) определяются новые компоненты вектора скорости Vx и Vy:

 (2.4)

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

(2.5)

при этом пересчитывается каждый раз при нахождении нового вектора скорости.

Авторами статьи [11] предложен алгоритм планирования движения выпуклого многоугольного объекта в среде, содержащей многоугольные препятствия. Представлена эвристика, базирующаяся на рассмотрении моментов, что позволяет расширить алгоритм и ввести в рассмотрение дополнительную степень свободы мобильного робота (МР) - угол поворота. Также представлены результаты построения трассы для МР, движущегося по коридору.

В работе используется следующая терминология. Пусть рабочая область пространства W, в которой действует МР, является подмножеством n. Пусть O W представляет собой множество препятствий в рабочей области, тогда свободным пространством в W будет являться множество F = W / O; задача построения пути МР в таком случае есть задача нахождения набора точек в F, определяющих траекторию движения МР из начальной точки в точку целевую.

Сначала рассматривается простой алгоритм, в котором многоугольный объект M, имеющий две степени свободы, перемещается в рабочем пространстве W, в котором присутствует конечное множество препятствий O. Текущее положение объекта M задается вектором x, начальное положение - вектором xs, а целевая точка - вектором xg. Тогда трасса строится по следующему алгоритму:

x xs

repeat

min min ((M, o)) o O

Frepulse min 1 / ||2

Fattract xg - x

Fres Fattract + a Frepulse

x x + Fres

until (x = xg) or (|Fres| = 0)

Здесь - вектор, доставляющий минимальное расстояние между M и препятствием o O. Константа a управляет влиянием препятствия на M в зависимости от расстояния. При использовании подобной потенциальной функции столкновений с препятствиями не происходит, однако, алгоритм может зацикливаться в случае достижения МР локального минимума в потенциальном поле. Для борьбы с этим явлением могут применяться различный методы, например, «барьер» из точек высокого потенциала вокруг точки локального минимума или метод Монте-Карло.

Далее для объекта M вводится дополнительная степень свободы - угол поворота , начальная конфигурация объекта в данном случае - (xs, s). Предполагается, что движется в коридоре минимального потенциала (КМП). Если он ориентирован так, что момент вращения МР в потенциальном поле минимален, то движение происходит таким образом, что главная ось направлена по касательной к КМП.

Пусть c - центр масс M, а P - множество векторов, описывающих положение некоторых контрольных точек, нормально распределенных по границе M относительно c. Предыдущий алгоритм модифицируется следующим образом:

x xs

s

repeat

Frepulse (0, 0)

moment 0

for each p P

min min ((c + p, o)) o O

Frepulse Frepulse + min 1 / ||2

moment moment + (p min) k

endfor

Fattract xg - x

Fres Fattract + a Frepulse

x x + Fres

+ b moment

until (x = xg) or (|Fres| = 0)

Константа b управляет величиной поворота и определяется эмпирически, поскольку математическое решение нетривиально и зависит от многих факторов. Кроме того, при практической реализации алгоритма, выбор c может быть неоднозначен. В рассматриваемых примерах для трехколесного МР в качестве c бралась середина оси между двумя задними колесами.

В работе [12] представлен метод обхода препятствий мобильным роботом (МР), получивший название метода «гистограмм векторных полей» (VHF_метод). Он позволяет обнаруживать препятствия и обходить их во время движения. МР, управляемый данным алгоритмом, маневрирует быстро и без остановок даже среди большого количества неупорядоченных препятствий.

VHF_метод для представления препятствий использует сетку на двумерной декартовой плоскости. Каждой ячейке сетки ставится в соответствие характерное значение, представляющее уровень «уверенности» алгоритма в присутствии препятствия в данной ячейке. Метод использует двухуровневую систему представления данных:

– на первом уровне - детальное описание среды, окружающей робота, с помощью декартовой сетки C;

– на втором уровне - полярная гистограмма H, которая строится по данным, содержащимся в C, вокруг центра масс МР как набор значений из C, соответствующий некоторым фиксированным секторам шириной каждый. Каждому сектору k ставится в соответствие величина hk, называемая полярной плотностью препятствий в направлении k.

Выходными данными алгоритма являются сигналы управления МР.

Пусть C*, называемая активной областью, есть область сетки C размером wsws, построенная вокруг МР; ее элементами являются активные ячейки cij. Тогда C преобразуется в H следующим образом: строятся векторы препятствий, направление которых относительно точки текущего положения МР определяется как:

(2.6)

а модуль вектора

(2.7)

где a, b = const > 0;

dij - расстояние между активной ячейкой и МР;

c*ij - среднее значение в активной ячейке (i, j);

x0, y0 - текущие координаты МР;

xi, yi - координаты активной ячейки (i, j).

Каждому из k секторов ставится в соответствие угол из ряда 0, , 2,…, 360-. Тогда между k и c*ij существует следующее отношение:

(2.8)

Для каждого сектора k hk вычисляется

(2.9)

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

(2.10)

Далее вычисляется направление движения в полярных координатах, free, и соответствующий ему сектор kfree в H. Алгоритм выбирает более «проходимое» направление и, вместе с тем, как можно более приближенное к текущему направлению на цель targ.

Скорость движения МР в начальной точке устанавливается максимальной (Smax), а затем определяется на каждом шаге в соответствии с формулой:

(2.11)

где h``c = min (h`c, hm);

h`c - сглаженная полярная плотность препятствий в выбранном направлении движения;

hm - эмпирически установленная константа.

При этом отношение (*) гарантирует S` 0 при h``c hm.

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

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

 (2.12)

где - плотность жидкости;

v - вектор скорости движения жидкости;

t - время;

f - внешняя сила;

p - давление;

- коэффициент вязкости жидкости.

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

(2.13)

Здесь неизвестными являются вектор скорости v и абсолютная координата x.

Граничные условия:

(2.14)

где - границы препятствий, n - внешняя нормаль к границе препятствия.

Начальные условия:

(2.15)

где xS - начальная точка, xG - целевая точка.

Для решения уравнения в двумерном пространстве методом конечных разностей уравнение представляется следующим образом:

(2.16)

где

(2.17)

Если число точек сетки N, то необходимо решить разреженную систему из 3N линейных уравнений.

Результатом работы рассматриваемого алгоритма является множество так называемых «коридоров». Каждый коридор начинается в окрестности стартовой точки и заканчивается в окрестности целевой. Следование МР по осевой линии коридора гарантирует его безопасность.

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

Страницы: 1, 2, 3, 4, 5