Рус Eng Cn Перевести страницу на:  
Please select your language to translate the article


You can just close the window to don't translate
Библиотека
ваш профиль

Вернуться к содержанию

Кибернетика и программирование
Правильная ссылка на статью:

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

Галемов Руслан Тахирович

аспирант, кафедра робототехники и технической кибернетики, Сибирский Федеральный Университет

660041, Россия, Красноярский край, г. Красноярск, проспект Свободный, 79

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
Другие публикации этого автора
 

 

DOI:

10.25136/2644-5522.2018.4.26798

Дата направления статьи в редакцию:

08-07-2018


Дата публикации:

06-08-2018


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


Ключевые слова:

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

Abstract: The object of the study is to solve the inverse problem of kinematics, as an optimization problem, under the conditions of a moving target. The subject of the study is the consideration of the drift of the objective function, as a result of the movement of the target, in the process of optimization. To solve the inverse problem of the kinematics of a multi-link manipulator, in the conditions of the time-varying position of the target, an effective algorithm for search optimization has been developed. Its essence consists in estimating the drift velocity, the formulated objective function, at each step of the search and taking into account the influence of the drift of the target when choosing the direction of the search. The modification of the method for the variable drift velocity of the objective function is considered. Estimates of the drift velocity are calculated by the recursive least squares method based on two modes: continuous search and search movement with repeated experiments at each vertex. The drift effect on the value of the objective function is obtained by integrating the drift velocity estimates on the time interval between the measurements. The author proposes a method for taking into account the drift of the objective function in the optimization problem. The proposed method showed its effectiveness in optimization problems with one and several extremums, using the example of simplex search and the genetic algorithm, operating under conditions of unstable drift of the objective function. The experimental limits of the effectiveness of the application of the method are determined experimentally.


Keywords:

optimization, cost function drift, inverse kinematics problem, direct search methods, moving target, drift estimations, simplex search, genetic algorithm, hybrid search, extremum seeking control

Введение

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

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

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

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

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

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

, (1)

где .

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

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

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

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

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

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

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

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

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

Обозначим dj – смещение поверхности функции Qj в момент времени tj относительно поверхности Qj-1 в момент времени tj-1. В поиске с s вершинами индексом s обозначим последнюю вершину, в которой производилось вычисление целевой функции и времени, соответственно в вершине с индексом 1 вычисление целевой функции проводилось раньше всех остальных s-1 вершин, при этом ts=tk. В момент времени ts-2 вычисляется значение целевой функции Q(xs-2,ts-2) в вершине xs-2. Значение Q(xs-2,ts-2) лежит на поверхности Qs-2. В момент времени ts-1 дрейф перемещает поверхность целевой функции на расстояние ds-1, в положение Qs-1. Здесь происходит измерение Q(xs-1,ts-1). В момент времени ts поверхность смещается на расстояние ds в положении Qs и вычисляется Q(xs,ts). Из-за дрейфа поверхности целевой функции алгоритм поиска может определить неверное направление движения. Поэтому необходимо вычесть влияние дрейфа, тем самым привести все измерения к одной поверхности [9]. Приведем значения целевых функций из всех вершин к поверхности последнего измерения Qs. Значение целевой функции в l-й вершине, приведенное к текущей поверхности Qs, назовем компенсированным, и обозначим C(xl).

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

, (2)

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

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

l=1s, (3)

,

,

,

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

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

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

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

, (4)

, (5)

, (6)

где l=1s.

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

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

l=1…s, (7)

,

,

,

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

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

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

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

, l=1…s, (8)

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

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

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

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

1) ;

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

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

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

2.3) оценивается скорость дрейфа в вершине xl,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) условие останова: достижение максимального числа популяций Nga, самая приспособленная особь не меняется is поколений подряд: , или если целевая функция находится в определенном диапазоне значений. Если выполнены условия останова, то переход к п.5 в противном случае переход к п.2;

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

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

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

1) ;

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

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

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

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

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

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

2.6) ;

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

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

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

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

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

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

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

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