Compensation of the alternating drift of the objective function in solving the inverse problem of the manipulator kinematics in the conditions of a moving target

Galemov Ruslan Takhirovich graduate student, Department of Robotics and Technical Cybernetics, Siberian Federal University 660041, Russia, Krasnoyarskii krai, g. Krasnoyarsk, prospekt Svobodnyi, 79 galemovruslan@gmail.com Other publications by this author

Введение

Обратную задачу кинематики (ОЗК) манипулятора можно рассматривать как задачу статической оптимизации ^[1]. Если заданное положение рабочего органа меняется во время поиска по неизвестному закону и имеется возможность оперативно фиксировать эти изменения, то задача оптимизации становится задачей экстремального управления, вследствие изменения положения оптимума во времени.

Задачи оптимизации в реальном времени, где целевая функция имеет дрейф оптимума, привлекали внимание исследователей из различных областей несколько последних десятилетий. В результате чего разработано несколько производительных алгоритмов. В отличие от оптимизации статической функции, где оптимум зафиксирован, в задаче оптимизации в реальном времени необходимо найти оптимум и следовать за ним. Наиболее активное применение экстремального управления наблюдается в химической промышленности ^[2-5].

В процессе оптимизации строится последовательность входных значений направленная на достижение экстремума. Для построения последовательности входных значений используются методы прямого поиска, с различными модификациями для определения правильного направления поиска, когда модель процесса неизвестна. В работе ^[4] представлен симплексный поиск, основанный на построении нескольких симплексов на каждом шаге алгоритма, и выборе на их основе направления движения. В ^[5] представлен симплексный поиск, который совершает шаги на основе статистики, определяющей вероятность нахождения оптимума в каждом из направлений движения. В работах ^[6] и ^[7] представлены метод роя частиц и генетический алгоритм соответственно, использующие технику сброса и обновления значений целевой функции. В ^[8] используется комбинация из муравьиного алгоритма и симплексного поиска из ^[4] для задач экстремального управления.

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

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

Задача слежения n-звенным манипулятором за целью в m-мерном пространстве имеет вид:

, (1)

где .

x₀–вектор начальных обобщенных координат манипулятора; p_d(t_k), p(x)–вектор заданного конечного положения манипулятора в момент времени t_k и вектор текущего положения соответственно; λ, w–весовые коэффициенты; x–вектор переменных поиска; t_k=kT₀–дискретное время; T₀–интервал наблюдения.

При изменении p_d(t) будет изменяться целевая функция (1). Выделяем несколько видов изменения целевой функции:

· вертикальный дрейф – движение поверхности целевой функции вдоль ординат Q. В этом случае со временем меняются значения целевой функции при фиксированных аргументах, но положение оптимума остается неизменным;

· горизонтальный дрейф – движение поверхности целевой функции вдоль аргументов. В этом случае меняется положение оптимума, что приводит к изменениям значений целевой функции при фиксированных значения x;

· смешанный дрейф – комбинация вертикального и горизонтального дрейфов.

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

Компенсация дрейфа

Рассмотрим, как дрейф может повлиять на поиск экстремума. Имеем конусообразную целевую функцию Q(x,t_k) для n=2 и метод прямого поиска, состоящий из трех вершин на k-м шаге поиска, представленные на рисунке 1.

Рисунок 1 – Влияние вертикального дрейфа: а) линии уровня в начальный момент времени; б) разрез

Обозначим d_j – смещение поверхности функции Q_j в момент времени t_j относительно поверхности Q_j-1 в момент времени t_j-1. В поиске с s вершинами индексом s обозначим последнюю вершину, в которой производилось вычисление целевой функции и времени, соответственно в вершине с индексом 1 вычисление целевой функции проводилось раньше всех остальных s-1 вершин, при этом t_s=t_k. В момент времени t_s-2 вычисляется значение целевой функции Q(x_s-2,t_s-2) в вершине x_s-2. Значение Q(x_s-2,t_s-2) лежит на поверхности Q_s-2. В момент времени t_s-1 дрейф перемещает поверхность целевой функции на расстояние d_s-1, в положение Q_s-1. Здесь происходит измерение Q(x_s-1,t_s-1). В момент времени t_s поверхность смещается на расстояние d_s в положении Q_s и вычисляется Q(x_s,t_s). Из-за дрейфа поверхности целевой функции алгоритм поиска может определить неверное направление движения. Поэтому необходимо вычесть влияние дрейфа, тем самым привести все измерения к одной поверхности ^[9]. Приведем значения целевых функций из всех вершин к поверхности последнего измерения Q_s. Значение целевой функции в l-й вершине, приведенное к текущей поверхности Q_s, назовем компенсированным, и обозначим C(x_l).

Компенсированная целевая функция для l-й вершины поиска в момент времени t_l равна значению целевой функции вычисленной в l-й момент времени с добавлением всех смещений произошедших с целевой функцией после измерения:

, (2)

где l=1…s – индекс вершины поиска. Поскольку смещения dsнеизвестны, то используются их оценки на основе скорости дрейфа. Для оценки дрейфа используем рекуррентный метод наименьших квадратов (РМНК) с повторными экспериментами и РМНК без повторных экспериментов. Разница времени между смежными измерениями времени равна времени дискретизации T₀.

При повторных экспериментах РМНК минимизирует разницу между изменением целевой функции в двух экспериментах и моделью:

l=1…s, (3)

,

,

,

где интервал времени время между экспериментами в s-й вершине; оценка скорости дрейфа

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

Рисунок 2 – Временная диаграмма оценок скорости дрейфа с повторными экспериментами

Воспользуется методом трапеций для оценки смещения целевой функции на интервале времени . Этот интервал можно разделить на две части: и . Интегрирование производится по следующим формулам:

, (4)

, (5)

, (6)

где l=1…s.

При РМНК без повторных экспериментов минимизируется разница между изменением целевой функции в соседних измеренных вершинах и оценкой смещения.

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

l=1…s, (7)

,

,

,

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

Временная диаграмма оценок скорости дрейфа представлена на рисунке 3.

Рисунок 3 – Временная диаграмма оценок скорости дрейфа без повторных экспериментов

Для оценки смещения используется метод трапеций.

, l=1…s, (8)

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

Генетический алгоритм (ГА) – итеративный эвристический алгоритм поиска, использующийся для решения многомерных задач оптимизации значений целевой функции путем случайного подбора, комбинирования и вариации исходных параметров. ГА содержит «популяцию» точек в пространстве поиска, именуемых «особи». На каждом шаге поиска создается новая популяция. С каждой новой популяцией особи будут находиться ближе к оптимуму. Чтобы создать новую популяцию на основе предыдущей ГА выполняет следующие шаги: а) вычисление целевой функции каждой особи популяции; б) выбор особей на основе значения их целевой функции; в) рекомбинация существующих особей генетическими операциями: скрещивание и мутация. ГА работает независимо над несколькими потенциальными решениями, а не над одним, что позволяет находить глобальный оптимум. Так же в поиске глобального оптимума содействует наличие случайностей в операциях выбора и рекомбинации.

Имеется задача (1). Для поиска в n-мерном пространстве одна особь будет иметь n генов, и будет представлять одну конфигурацию манипулятора. Значение целевой функции особи называется фитнесом или приспособленностью.

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

1) ;

2) создается новая популяция:

2.1) рассчитываются координаты вершины x_l,l=1…s;

2.2) вычисляется и , l=1…s;

2.3) оценивается скорость дрейфа в вершине x_l,l=1…s, по формуле (3);

2.4) вычисляется , l=1…s по формуле (6);

2.5) вычисляется , l=1…s-1;

2.6) ;

3) на основании , производятся этапы генетического алгоритма;

3.1) выбор родителей;

3.2) скрещивание;

3.3) мутация;

4) условие останова: достижение максимального числа популяций N_ga, самая приспособленная особь не меняется i_s поколений подряд: , или если целевая функция находится в определенном диапазоне значений. Если выполнены условия останова, то переход к п.5 в противном случае переход к п.2;

5) вывод результатов.

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

Алгоритм симплексного поиска с n+1 вершинами, использующий оценки без повторных экспериментов, имеет вид:

1) ;

2) формируется начальный симплекс:

2.1) рассчитываются координаты вершины x_l, l=1…s;

2.2) вычисляется , l=1…s;

2.3) оценивается скорость дрейфа в вершине x_l,l=1…s по формуле (7);

2.4) вычисляется , l=1…s, по формуле (8);

2.5) вычисляется , l=1…s-1;

2.6) ;

3) на основании ,l=1…s определяется худшая вершина x_w;

4) вычисляются координаты отраженной вершины x_s;

5) в вершине x_s:

5.1) вычисляется ;

5.2) оценивается скорость дрейфа в вершине x_s по формуле (7);

5.3) вычисляется , по формуле (8);

5.4) вычисляется , ;

6) проверка условия останова: если симплекс удовлетворяет (9) при известном или число шагов больше , то переход к п.7. Переход к п.3;

7) вывод результатов.

. (9)

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

Комбинированный поисковой метод

Интенсификация – процесс уменьшения области поиска ГА. Используется для повышения шансов нахождения глобального оптимума, а так же увеличения точности поиска в целом. Смысл её заключается в увеличении концентрации особей генетического алгоритма в перспективной области (promising area) ^[11]. Перспективная область – область пространства поиска генетического алгоритма в которой, вероятнее всего, находится глобальный оптимум. Она считается найденной, если в ней находится лучшая особь популяции и большая часть других особей. В процессе интенсификации происходит уменьшение размера области поиска и объема популяции.

Интенсификация характеризуется параметром сжатия , который регулирует, какая доля области поиска и популяции останется после интенсификации.

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

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

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

Для сохранения достоинств и устранения недостатков рассмотренных методов поиска был разработан комбинированный метод поиска. Суть его заключается в том, что на каждом шаге генетического алгоритма его лучшие особи передаются в алгоритм Нелдера-Мида, где вокруг них строятся симплексы и производится симплексный поиск. Результаты поиска сравниваются с особями ГА и при необходимости заменяют их. Алгоритм работы комбинированного поискового метода представлен на рисунке 4.

Эксперименты

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

Использовалась конусообразная целевая функция со знакопеременным вертикальным дрейфом с частотой дискретизации и k – дискретным временем:

, (10)

,

.

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

Рисунок 4 – Блок-схема алгоритма КПМ

График скорости дрейфа и её оценки представлены на рисунке 5.

Рисунок 5 – Скорость и оценка дрейфа

Результаты одной итерации комбинированного поискового метода с интегральной оценкой дрейфа представлены на рисунке 6.

Рисунок 6 – Результаты работы алгоритма с компенсацией и без компенсации

Следующая целевая функция со знакопеременным вертикальным дрейфом – функция Химмельблау в дискретном времени:

, (11)

,

.

Результаты одной итерации комбинированного поискового метода с интегральной оценкой дрейфа представлены на рисунке 7.

Рисунок 7 – Результаты работы алгоритма с компенсацией и без компенсации

Чтобы определить границы эффективности оценок построим график зависимости среднеквадратичной ошибки поиска от отношения сигнал-дрейф. Отношение полезный сигнал – максимальная скорость дрейфа отражает степень влияния дрейфа на значение целевой функции. Где a–уровень полезного сигнала (10); b–максимальная скорость дрейфа (10). Среднеквадратичная ошибка равна:

, (12)

. (13)

где – значение оптимума; – найденное значение на i-м поиске; N – число экспериментов.

При N=1000, значениях начальной длины ребра симплекса и коэффициента растяжения симплекса, указанных в таблице 1, получены графики, представленные на рисунке 8.

Таблица 1 – Значения начальной длины ребра симплекса и коэффициенты растяжения

Рисунок 8 – Зависимость среднеквадратичной ошибки от отношения сигнал / дрейф

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

Эксперименты с решением обратной задачи кинематики проводились на модели трехзвенном манипуляторе в среде MATLAB. Кинематическая схема манипулятора представлена на рисунке 9.

Рисунок 9 – Кинематическая схема трехзвенного манипулятора

Данный манипулятор является не избыточным, поэтому ОЗК имеет малое () число решений. Параметры Денавита-Хартенберга для манипулятора представлены в таблице 2.

Таблица 2 – Параметры трехзвенного манипулятора

Движение цели происходило по траекториям, представленным в таблице 3. Траектория 1 – окружность с радиусом 1 м на плоскости x₀y₀ с рабочим органом, ориентированным в сторону положительного направления оси x₀. Траектория 2 – синусоида на плоскости x₀y₀ с рабочим органом, ориентированным в сторону положительного направления оси x₀. Вектор состоит из следующих элементов: – положение по оси x₀, – положение по оси y₀, – угол отклонения от положительного направления оси x₀.

Таблица 3– Заданные траектории для рабочего органа манипулятора

Построенные траектории движения рабочего органа представлены на рисунке 10 и рисунке 11.

а)

б)

в)

г)

Рисунок 10 – Результаты решения ОЗК для траектории 1: а) заданная и пройденная траектории; б) ошибки положения; в) ошибки ориентации; г) траектории обобщенных координат

а)

б)

в)

г)

Рисунок 11 – Результаты решения ОЗК для траектории 2: а) заданная и пройденная траектории; б) ошибки положения; в) ошибки ориентации; г) траектории обобщенных координат

Из рисунка 10а и рисунка 11а видно, что траектория рабочего органа проходит достаточно близко к траектории цели. Как показывает рисунок 10б и рисунок 11б ошибки положения в рабочем пространстве находится в диапазоне 10^-2 метра. Из рисунка 10г и рисунка 11г видно, что простроенные траектории не имеют скачкообразных изменений обобщенных координат и пригодны для дальнейшего использования в качестве задающего воздействия регулятора привода манипулятора.

Заключение

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