Программное обеспечение системы принятия решений адаптивного робота (стр. 6 из 8)

x ¬ x + F_res

until (x = x_g) or (|F_res| = 0)

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

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

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

x ¬ x_s

q¬q_s

repeat

F_repulse¬(0, 0)

moment¬ 0

for each pÎ P

D_min¬ min (D(c + p, o)) "o Î O

F_repulse¬ F_repulse + D_min× 1 / |D|²

moment¬moment + (p ´D_min) × k

endfor

F_attract¬ x_g – x

F_res¬ F_attract + a× F_repulse

x ¬ x + F_res

q¬q + b ´moment

until (x = x_g) or (|F_res| = 0)

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

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

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

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

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

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

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

(2.6)

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

(2.7)

где a, b = const > 0;

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

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

x₀, y₀– текущие координаты МР;

x_i, y_i – координаты активной ячейки (i, j).

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

(2.8)

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

(2.9)

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

(2.10)

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

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

(2.11)

гдеh``_c = min (h`_c, h_m);

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

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

При этом отношение (*) гарантирует S`³ 0 при h``_c£h_m.

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

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

(2.12)

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

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

t – время;

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

p – давление;

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

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

(2.13)

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

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

(2.14)

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

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

(2.15)

где x_S – начальная точка, x_G – целевая точка.

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

(2.16)

где

(2.17)

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

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

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

Полная потенциальная энергия частицы в потоке:

(2.18)

где S – начальная точка, G – целевая точка, T – вектор, касательный к траектории, p_G – p_S– разность давлений в x_S и x_G.

В случае присутствия силы трения F:

(2.19)

Механическая работа силы трения L×F зависит от длины траектории L. В случае достаточно большой величины F:

(2.20)

Все траектории имеют ограниченную длину

(2.21)

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

Для тестов данного метода использовался 4-х колесный МР на полигоне 60 м´ 100 м с препятствиями [13]. Внешняя сила f задавалась в виде: