48277 (588532), страница 4

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 4)

Первое является попыткой ответить на вопрос: можно ли эффективно задавать силовое поле так, чтобы отсутствовали устойчивые точки равновесия в принципе. Достаточно очевидно, что в общем случае ответ на этот вопрос положительный. Действительно, функция потенциала в точке x, равная минимальной длине допустимого пути от x к g – точке цели, задает такое поле. Однако эту функцию в общем случае считать весьма непросто. Koditschek с соавторами в серии работ [4,5] и др. предложили свой подход к этой проблеме, который хотя и отличается оригинальностью, в итоге, оказывается, вряд ли намного проще способа, указанного выше. Вначале рассматривается «Сферический мир». Для плоскости это окружности-препятствия, окруженные окружностью-рамкой. В этом мире результирующая сила определяется не как сумма сил, действующих от различных препятствий, а как произведение таких сил. Эти два положения позволяют избежать наличия точек равновесия силового поля, что зафиксировано теоретически.

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

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

Ниже приводятся некоторые ранее не публиковавшиеся результаты исследования алгоритмов, основанных на методе потенциалов, полученные в ИПМ в 70 – 80 х гг. прошлого века.

Критическое отношение шага к радиусу обходимой окружности для появления информационного дребезга 0.1 для степенной функции и 0.3 для экспоненты.

Подобным образом исследовалось влияние информационного дребезга для плавного контура (окружность радиуса 1) при обходе методом потенциалов.

В статье [9] описывается мобильный робот (МР), разработанный фирмой Hitachi, Ltd. (Япония) в 1984 г., в котором, в частности, для реализации управления автономным перемещением, был использован так называемый «метод потенциального наведения ». Он предусматривает оснащение робота дальномерами, измеряющими расстояние до объектов в рабочей зоне. Принцип этого метода схематически представлен на рис. 3, где обозначено: X_k – точка нахождения робота в текущий момент времени; t_k - направление передвижения робота до текущего момента времени; t_k+1 – направление передвижения робота в текущий момент времени; X_G – целевая точка; g – вектор, направленный к целевой точке; r_max – максимальный радиус; r_i^* - вектор, проведенный до объекта, находящегося в рабочей зоне робота.

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

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

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

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

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

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

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

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

(2.3)

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

(2.4)

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

(2.5)

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

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

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

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

x x_s

repeat

_min min ((M, o)) o O

F_{repulse min} 1 / ||²

F_attract x_g – x

F_res F_attract + a F_repulse

x x + F_res

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

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

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

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

x x_s

_s

repeat

F_repulse (0, 0)

moment 0

for each p P

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

F_repulse F_repulse + _min 1 / ||²

moment moment + (p _min) k

endfor

F_attract x_g – x

F_res F_attract + a F_repulse

x x + F_res

+ b moment

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

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

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

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

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

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

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

Пусть C^*, называемая активной областью, есть область сетки C размером w_sw_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, , 2,…, 360-. Тогда между k и c^*_ij существует следующее отношение:

(2.8)

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

(2.9)

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

Характеристики

Список файлов ВКР