Метод синтезированного оптимального управления для группы роботов

УДК 51-74, 519.6

DOI 10.21685/2307-4205-2018-4-4

А. И. Дивеев, Е. Ю. Шмалько

МЕТОД СИНТЕЗИРОВАННОГО ОПТИМАЛЬНОГО УПРАВЛЕНИЯ ДЛЯ ГРУППЫ РОБОТОВ1

A. I. Diveev, E. Yu. Shmalko

METHOD OF SYNTHESIZED OPTIMAL CONTROL

FOR A GROUP OF ROBOTS

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

Abstract. Background. A group of robots is a complex control object with dynamic phase constraints. To date, for such objects there are no effective algorithms for solving the problem of optimal control in the initial formulation, when control must be found in the form of a function of time in infinite-dimensional space. The main problem here is that after the reduction of the optimal control problem to the problem of finite-dimensional optimization, we obtain the objective function, which in the parameter space does not have properties of convexity and unimodality. Matherials and methods. The paper presents a new approach to solving the problem of optimal control - optimal synthesized control. Initially, we provide stabilization of the object with respect to a certain point in the state space, solving the problem of control system synthesis. Then we find such a sequence of stabilization points in the state space that, switching the stabilization points at fixed instants of time, we ensure the movement of the object from the initial state to the terminal state with the optimal value of the quality criterion. Results. The implementation of the proposed method for solving the problem of optimal control by a group of robots with phase constraints is shown. A comparison of the proposed approach with known methods of finite-dimensional optimization is presented. Conclusions. It is shown that the gradient classical methods do not find an acceptable solution. Evolutionary algorithms find solutions in all considered cases much better than classical gradient methods and random search algorithm. The method of synthesized optimal control makes it possible to find, with the help of the same evolutionary algorithms, essentially better results than the reduction methods with fewer calculations of the target functional.

1 Работа выполнена при поддержке Российского фонда фундаментальных исследований

Ключевые слова: группа роботов, оптимальное управление, метод синтезированного оптимального управления.

Key words: group of robots, optimal control, method of synthesized optimal control.

Введение

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

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

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

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

Рассмотрим задачу оптимального управления группой роботов с фазовыми ограничениями. Математическая модель каждого робота описывается системой из п = 3 уравнений [1]

Х1+(у-1)п = 0,5(и1+(у-1)т + и2+(у-1)т Х3+(у-1)п ) ,

Х2+

Х3+(у-1)п = 0,5(и1+(у-1)т - и2+(у-1)т ) ,

где п - размерность модели одного объекта, п = 3, т - размерность вектора управления для одного робота, т = 2, х = [х^...,х3+(нч)п]Т - вектор состояния всей группы роботов, и = [ир...,и2+(Nт]Т -

вектор управления группы роботов, у = 1,..., N, N - количество роботов в группе.

Управление каждым роботом имеет одинаковые ограничения

иГ ^ и+

Задано начальное положение каждого робота

ХШ7-1)п

Заданы статические фазовые ограничения

в

где г - заданная положительная величина, х*, х* - координаты центра статических фазовых ограничений.

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

5к

где

к = г - 7 +

j = 1,N -1, i = j +1,N, r0 - заданная положительная величина, определяющая габаритный размер одного робота.

Максимальное число проверок динамических фазовых ограничений равно числу сочетаний по 2 из N. Из соотношения (6) данное число получаем при j = N -1 и i = N :

k = N - N +1 + (N -1 -1)( N - 0,5( N -1)) = 1 + (N - 2)(0,5 N + 0,5) = = 1 + 0,5(N2 - N - 2) = 0,5(N2 - N) = 0,5N(N -1).

Заданы терминальные состояния для каждого робота

xi+

Задан критерий качества управления

J = tf ^ min ,

где tf - время процесса управления

t = U, если t < t+ и max{|| ÄX( г+J-Х) п (t) 112: j = 1, N} < 8, (

f lt+ - иначе,

11 Ax(i+j-1)n (t)||2 = ^Z (^+(j-1)n (t) - xf (j-1)n )2 ,

t + - максимально возможное время управления; 8 - малая положительная величина.

Включим фазовые ограничения в критерий качества управления, используя функцию Хэви-сайда, как в

J = tf + Z J ^

j=1 0 i=1 j=i+1 0

где ß( x(t)) и 8 k (x (t)) определяются по формулам (4) и (5) соответственно.

Метод синтезированного оптимального управления

Решим теперь задачу (1)—(10) методом синтезированного оптимального управления. Первоначально для одного робота решим задачу синтеза управления.

Конкретная постановка задачи синтеза управления имеет следующее описание. Задана математическая модель объекта управления

X1 = 0,5

Заданы ограничения на управление

-10 = u" < ul < u + = 10, i = 1,2.

Заданы терминальные условия

xf = 0, i = 1,2,3.

Задано множество начальных условий

X0 =

Задан функционал качества

J = £ tf

где

tf =

t, если t < t+ и № (xf - Xj )2 <8, V

t+ - иначе,

К = 8, = 2 с.

Необходимо найти управление в форме

и = И

Для решения задачи используем метод сетевого оператора [3-7]. Устанавливаем множество аргументов

А =

где д1, д2, д3 - искомые параметры.

Множество функций с одним аргументом

Ц = (Р1(^) = *, Р 2 (*) = *2, р3(^) = -*, Р 4 (*) = sgn( * , р5(г) =1/г , Рб(^) = ехр^, Р7^) = 1п(| г |),

1 - ехр(-*) [1, если * > 0,

Р8(я) = --^, Р9(г) = = 1 Рю( *) = рп(*) = Р12 (*) = вшф,

1 + ехр(-*) [0 - иначе,

3 г- [ *, если * |< 1,

Ри(*) = arctan(*), Р14(*) = * , Р15(*) = 3* , Р16(*) = ^(*) = 1 , ч Р17(*) = 8§п(*)1п(| * | +1),

|^п(*) - иначе,

Р18

Множество функций с двумя аргументами содержит только две функции - сложения и умножения:

Ц2 =

В качестве базисного решения используем следующую функцию управления:

ы, =

u+, если ui > u+,

u-, если ui < u-,

ü. - иначе,

i=1

где

щ = qx(x{ - xi) + q2(x{ - x 2 ) + q3(x{ - x3), i = 1,2 q = 1, j = 1,2,3.

При поиске решения использовали следующие параметры генетического алгоритма: размер начальной популяции 512, число поколений 128, число возможных скрещиваний в одном поколении 128, вероятность мутации 0,7, количество вариаций в одном решении 8, количество бит для одного параметра 16, количество бит под целую часть параметра 4, количество поколений между сменой базисного решения 65, размерность матрицы сетевого оператора 24х24 .

В результате были получены следующие функции управления:

щ = A 1 + VA + sgn(q3 (x3 - x3 )) exp(- | q3 (x3f - x3 ) |) + sgn(x3f - x3 ) + ц(B), и2 = щ + sin(u/1) + arctan(H) + ц(B) + C - C3,

где

A = 1 - exp

( B + ^x1/ - x1 ) + C + sin(q3(x/" - x3)),

B = G + sgn(sgn(xf - x1 )q2(x2 - x2))exp(-1 sgn(xf - x1 )q2(xf - x2) |) + sin(xf - x1) +

1 - exp

x1 x1 ,

1 + ехр

С = в + sgn(sgn(х( - х1 )q2(х( - х2))ехр(- | sgn(х{ - х1 )q2(х/ - х2) |) + sin(х( - х), В = Н + С - С3 + sgn(q1 (- х1)) + агС^^) + х37 - х3),

в = *%п{Х{ -х0д2(х( -х2) + Яз(х{ -хз) + 1-^ ~х')) ,

1 + ехр(-ql(х{ -

q1 = 14,72876, q2 = 2,02710, q3 = 4,02222.

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

¥ =

0 0 0 0 0 0 1 10 0 0 12 1 15 0 0 0 0 0 0 0 0 0 0 10

0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 9 0 0 0 0 10 0 0 0

0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 13 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 2 0 0 8 0 0 0 4 13 10 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 2 0 1 19 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 2 1 0 0 0 0 0 0 12 0 0 0 19 0 0 0

0 0 0 0 0 0 0 0 0 1 1 8 0 1 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 1 1 0 0 4 20 1 0 0 0 0 0 0 20

0 0 0 0 0 0 0 0 0 0 0 1 1 10 10 0 0 0 0 20 0 16 0 16

0 0 0 0 0 0 0 0 0 0 0 0 1 1 15 0 14 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 13

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 8 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 1 0 15 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 5 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 12

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 1

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1

Теперь решим задачу оптимального управления (1)—(10). Для этой цели находим значения терминальных точек как параметров функции управления:

q = [qi = Xl • • * qnN = XnN • • * q

где K - количество временных интервалов, N - количество роботов, n - размерность математической модели одного робота.

В рассматриваемом примере N = 4, n = 3 . Выбираем величину интервала At = 0,7, при максимально допустимом времени управления t+ = 2,8, получаем K = 4 . В результате необходимо найти оптимальный по критерию (10) вектор параметров из 36 компонент.

Ограничения на значения параметров устанавливаем из возможных значений вектора состояний:

q-=-1 < qt < 11 = q+ , i = 1,2,4,5,7,8,10,11,

q- = -1,57 < qt < 1,57 = q+ , i = 3, 6,9,12.

Для решения рассматриваемой задачи оптимального управления использовали несколько наиболее популярных эволюционных и классических градиентных алгоритмов: метод роя частиц, простой случайный поиск, генетический алгоритм, метод наискорейшего градиентного спуска и современный градиентный алгоритм Adam, который сейчас широко и успешно используется для глубокого обучения искусственных нейронных сетей. С подробным описанием алгоритмов можно ознакомиться в работах [8-9]. Выполняли по 10 запусков каждым алгоритмом. С учетом более сложной реализации процесса управления устанавливали такие параметры алгоритмов, чтобы значение целевой функции при каждом запуске выполнялось приблизительно одинаковое число раз, около 65000.

Алгоритмы оцениваем по трем показателям: наилучшему найденному значению, среднему значению и среднеквадратичному отклонению. Результаты вычислительного эксперимента приведены в табл. 1.

Таблица 1

Результаты вычислительного эксперимента для синтезированного оптимального управления

Алгоритм Лучшее Среднее СКО Кол. выч. ф.

PSO 2,9684 3,205870 0,250229 65601,1

RS 6,2042 7,575347 0,913633 64514,1

GA 2,9152 3,309271 0,391569 65975,5

FGD 13,3061 14,602757 2,6462162 65362,5

Adam. 10,0278 14,684361 3,271366 69887,7

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

Наилучшее найденное решение имело следующие значения:

¿1 = [3,1284 3,4623 0,4523 5,3634 2,5503 -0,0048 5,0630 8,2054 1,3931 4,0640 6,5860 1,2307 9,0591 5,9547 0,5639 10,8086 2,3967 0,6388 6,2670 7,7357 0,4361 3,1830 1,8235 0,6301 10,1884 10,0525 0,1749 10,9119 1,4735 -0,5246 -0,7141 7,21060 -0,8569 -0,1435 2,0431 1,2178]г.

График траекторий движения всех четырех роботов на плоскости для лучшего решения приведен на рис. 1.

-2 -1 0 1 2 3 4 5 6 7 8 9 10 11

Рис. 1. Траектории движения роботов для наилучшего решения синтезированного оптимального управления

Для сравнения данная задача была решена напрямую, путем редукции задачи оптимального управления к задаче конечномерной оптимизации. Использовались те же методы, что и при экспериментах для синтезированного оптимального управления. По результатам экспериментов наилучшее значение J = 3,4987 удалось найти по методу роя частиц. Метод наискорейшего градиентного спуска показал наихудший результат и проиграл по всем показателям даже случайному поиску.

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

Заключение

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

Библиографический список

1. Suster, P. Tracking trajectory of the mobile robot Khepera II using approaches of artificial intelligence / P. Suster, A. Jadlovska // Acta Electrotechnica et Informatica. - 2011. - Vol. 11, № 1. - P. 38-43.

2. Diveev, A. I. Study of the Practical Convergence of Evolutionary Algorithms for the Optimal Program Control of a Wheeled Robot / A. I. Diveev, S. V. Konstantinov // Journal of Computer and Systems Sciences International. -2018. - Vol. 57, № 4. - P. 561-580.

3. Дивеев, А. И. Синтез системы управления группой роботов методом сетевого оператора / А. И. Дивеев, Е. Ю. Шмалько // Современные проблемы науки и образования. - 2014. - № 4. - С. 198.

4. Дивеев, А. И. Численный метод сетевого оператора для синтеза системы управления с неопределенными начальными значениями / А. И. Дивеев // Известия Российской академии наук. Теория и системы управления. - 2012. - № 2. - С. 63.

5. Дивеев, А. И. Синтез системы управления на основе аппроксимации множества оптимальных траекторий методом сетевого оператора / А. И. Дивеев, Е. Ю. Шмалько // Надежность и качество сложных систем. -2014. - № 4 (8). - С. 3-10.

6. Дивеев, А. И. Повышение надежности систем управления группой объектов за счет автоматизации процесса их синтеза / А. И. Дивеев, Е. Ю. Шмалько // Труды Международного симпозиума Надежность и качество. - 2016. - Т. 1. - С. 160-163.

7. Дивеев, А. И. Метод сетевого оператора / А. И. Дивеев. - М. : ВЦ РАН, - 2010. - 178 с.

8. Дивеев, А. И. Эффективный алгоритм для синтеза структуры системы автоматического управления / А. И. Дивеев, Н. А. Северцев, Е. А. Софонова // Труды Международного симпозиума Надежность и качество. - 2007. - Т. 1. - С. 20-23.

9. Дивеев, А. И. Численный метод вариационного генетического программирования для синтеза системы управления мобильного робота / А. И. Дивеев, С. И. Ибадулла // Труды Международного симпозиума Надежность и качество. - 2014. - Т. 1. - С. 30-34.

References

1. Suster P., Jadlovska A. Acta Electrotechnica et Informatica. 2011, vol. 11, no. 1, pp. 38-43.

2. Diveev A. I., Konstantinov S. V. Journal of Computer and Systems Sciences International. 2018, vol. 57, no. 4, pp. 561-580.

3. Diveev A. I., Shmal'ko E. Yu. Sovremennyeproblemy nauki i obrazovaniya [Modern problems of science and education]. 2014, no. 4, p. 198.

4. Diveev A. I. Izvestiya Rossiyskoy akademii nauk. Teoriya i sistemy upravleniya [News of the Russian Academy of Sciences. Theory and control systems]. 2012, no. 2, p. 63.

5. Diveev A. I., Shmal'ko E. Yu. Nadezhnost' i kachestvo slozhnykh sistem [Reliability and quality of complex systems]. 2014, no. 4 (8), pp. 3-10.

6. Diveev A. I., Shmal'ko E. Yu. Trudy Mezhdunarodnogo simpoziuma Nadezhnost' i kachestvo [Proceedings of The international Symposium Reliability and quality]. 2016, vol. 1, pp. 160-163.

7. Diveev A. I. Metodsetevogo operatora [Network operator method]. Moscow: VTs RAN, 2010, 178 p.

8. Diveev A. I., Severtsev N. A., Sofonova E. A. Trudy Mezhdunarodnogo simpoziuma Nadezhnost' i kachestvo [Proceedings of The international Symposium Reliability and quality]. 2007, vol. 1, pp. 20-23.

9. Diveev A. I., Ibadulla S. I. Trudy Mezhdunarodnogo simpoziuma Nadezhnost' i kachestvo [Proceedings of The international Symposium Reliability and quality]. 2014, vol. 1, pp. 30-34.

Дивеев Асхат Ибрагимович

доктор технических наук, начальник сектора отдела безопасности и нелинейного анализа, Федеральный исследовательский центр «Информатика и Управление» Российской Академии Наук, (Вычислительный центр им. А. А. Дородницына РАН), профессор департамента механики и мехатроники Инженерной академии Российского университета дружбы народов (119333, Россия, г. Москва, ул. Вавилова, 40) E-mail: aidiveev@mail.ru

Шмалько Елизавета Юрьевна

кандидат технических наук,

научный сотрудник отдела безопасности

и нелинейного анализа,

Федеральный исследовательский центр

«Информатика и Управление»

Российской Академии Наук,

(Вычислительный центр

им. А. А. Дородницына РАН)

E-mail: asiedora@mail.ru

Diveev Askhat Ibragimovich

doctor of technical sciences,

chief of the division of safety and nonlinear analysis, Federal research center «Computer science and control» of the Russian Academy of Sciences

Shmalko Elizaveta Yurjevna

candidate of technical sciences, scientific worker of the division of safety and nonlinear analysis, Federal research center «Computer science and control» of the Russian Academy of Sciences

УДК 51-74, 519.6 Дивеев, А. И.

Метод синтезированного оптимального управления для группы роботов / А. И. Дивеев, Е. Ю. Шмалько // Надежность и качество сложных систем. — 2018. — № 4 (24). — С. 40—47. — БО! 10.21685/2307-4205-2018-4-4.