А. К. Платонов, А. А. Кирильченко, М. А. Колганов (стр. 3 из 5)
x ¬ xs
repeat
Dmin ¬ min (D(M,o)) "o Î O
Frepulse ¬ Dmin × 1 / |D|2
Fattract¬ xg – x
Fres ¬ Fattract + a × Frepulse
x ¬ x + Fres
until ( x = xg ) or ( |Fres| = 0 )
Здесь D - вектор, доставляющий минимальное расстояние между M и препятствием o Î O. Константа a управляет влиянием препятствия на M в зависимости от расстояния. При использовании подобной потенциальной функции столкновений с препятствиями не происходит, однако, алгоритм может зацикливаться в случае достижения МР локального минимума в потенциальном поле. Для борьбы с этим явлением могут применяться различный методы, например, «барьер» из точек высокого потенциала вокруг точки локального минимума или метод Монте-Карло.
Далее для объекта M вводится дополнительная степень свободы - угол поворота q, начальная конфигурация объекта в данном случае –
( xs , qs ). Предполагается, что движется в коридоре минимального потенциала (КМП). Если он ориентирован так, что момент вращения МР в потенциальном поле минимален, то движение происходит таким образом, что главная ось направлена по касательной к КМП.
Пусть c – центр масс M, а P – множество векторов, описывающих положение некоторых контрольных точек, нормально распределенных по границе M относительно c. Предыдущий алгоритм модифицируется следующим образом:
x ¬ xs
q ¬ qs
repeat
Frepulse ¬ ( 0 , 0 )
moment ¬ 0
for each p Î P
Dmin ¬ min (D( c + p , o)) "o Î O
Frepulse ¬ Frepulse + Dmin × 1 / |D|2
moment ¬ moment + ( p ´ Dmin ) × k
endfor
Fattract¬ xg – x
Fres ¬ Fattract + a × Frepulse
x ¬ x + Fres
q ¬ q + b ´ moment
until ( x = xg ) or ( |Fres| = 0 )
Константа b управляет величиной поворота и определяется эмпирически, поскольку математическое решение нетривиально и зависит от многих факторов. Кроме того, при практической реализации алгоритма, выбор c может быть неоднозначен. В рассматриваемых примерах для трехколесного МР в качестве c бралась середина оси между двумя задними колесами.
В работе [12] представлен метод обхода препятствий мобильным роботом (МР), получивший название метода «гистограмм векторных полей» (VHF-метод). Он позволяет обнаруживать препятствия и обходить их во время движения. МР, управляемый данным алгоритмом, маневрирует быстро и без остановок даже среди большого количества неупорядоченных препятствий.
VHF-метод для представления препятствий использует сетку на двумерной декартовой плоскости. Каждой ячейке сетки ставится в соответствие характерное значение, представляющее уровень «уверенности» алгоритма в присутствии препятствия в данной ячейке. Метод использует двухуровневую систему представления данных:
· на первом уровне – детальное описание среды, окружающей робота, с помощью декартовой сетки C;
· на втором уровне – полярная гистограмма H, которая строится по данным, содержащимся в C, вокруг центра масс МР как набор значений из C, соответствующий некоторым фиксированным секторам шириной a каждый. Каждому сектору k ставится в соответствие величина hk, называемая полярной плотностью препятствий в направлении k.
Выходными данными алгоритма являются сигналы управления МР.
Пусть C*, называемая активной областью, есть область сетки C размером ws´ws, построенная вокруг МР; ее элементами являются активные ячейки cij. Тогда C преобразуется в H следующим образом: строятся векторы препятствий, направление которых относительно точки текущего положения МР определяется как
а модуль вектора
где a,b = const > 0;
dij – расстояние между активной ячейкой и МР;
c*ij – среднее значение в активной ячейке (i,j);
x0, y0 – текущие координаты МР;
xi, yi – координаты активной ячейки (i,j).
Каждому из k секторов ставится в соответствие угол из ряда 0, a, 2a,…, 360°-a. Тогда между k и c*ij существует следующее отношение:
Для каждого сектора k hk вычисляется
Таким образом, каждая из активных ячеек находится в одном из секторов. Однако, из-за дискретности сетки, в результате такого распределения ячеек могут возникать «ступеньки» в секторах, что может привести к ошибкам в выборе направления. Для того чтобы избежать искажения результата, используется сглаживающая функция
Далее вычисляется направление движения в полярных координатах, qfree, и соответствующий ему сектор kfree в H. Алгоритм выбирает более «проходимое» направление и, вместе с тем, как можно более приближенное к текущему направлению на цель qtarg.
Скорость движения МР в начальной точке устанавливается максимальной (Smax), а затем определяется на каждом шаге в соответствии с формулой
где
h``c = min(h`c , hm);
h`c – сглаженная полярная плотность препятствий в выбранном направлении движения;
hm – эмпирически установленная константа.
При этом отношение (*) гарантирует S` ³ 0 при h``c £ hm.
Статья [13] посвящена методу построения гладких трасс движения мобильного робота (МР), основанному на физической аналогии. Основными достоинствами метода являются устойчивое решение и работа не только с двоичными (препятствие или свободное пространство), но и с разнородными средами, поверхность которых может иметь неравные коэффициенты трения или углы наклона на различных участках.
В основе метода лежат физические принципы гидродинамики. Если предположить, что вся среда заполнена жидкостью, то потоки жидкости позволяют добраться из начальной точки в целевую. В этом случае оптимальным путем будет поток, направленный вдоль градиента давления, в котором достигается стационарное движение жидкости; локальный минимум не может быть достигнут, поскольку во всех точках потока удовлетворяется уравнение Лапласа. Для учета неоднородностей среды вводится внешняя сила, учитывающая силу трения и влияние проходимых препятствий, поэтому рассматриваются потоки вязкой жидкости. Основным уравнением движения вязкой несжимаемой жидкости является уравнение Навье-Стокса:
где
r - плотность жидкости;
v – вектор скорости движения жидкости;
t – время;
f – внешняя сила;
p – давление;
m - коэффициент вязкости жидкости.
Упрощенное уравнение выглядит следующим образом:
Здесь неизвестными являются вектор скорости v и абсолютная координата x.
Граничные условия:
где ¶W - границы препятствий, n – внешняя нормаль к границе препятствия.
Начальные условия:
где xS – начальная точка, xG – целевая точка.
Для решения уравнения в двумерном пространстве методом конечных разностей уравнение представляется следующим образом:
где
Если число точек сетки N, то необходимо решить разреженную систему из 3N линейных уравнений.
Результатом работы рассматриваемого алгоритма является множество так называемых «коридоров». Каждый коридор начинается в окрестности стартовой точки и заканчивается в окрестности целевой. Следование МР по осевой линии коридора гарантирует его безопасность.
Далее рассматривается случай, когда внешняя сила не равна нулю, что позволяет учитывать разнородность среды.
Полная потенциальная энергия частицы в потоке:
где S – начальная точка, G – целевая точка, T – вектор, касательный к траектории, pG – pS - разность давлений в xS и xG.