Рассматривается вопрос корректности одного алгоритма построения приближенных решений Штакельберга в линейной неантагонистической позиционной дифференциальной игре двух лиц с терминальными показателями качества и ограничениями на выбор управлений, заданными в виде выпуклых многогранников. Определяются условия на показатели качества игроков, при наложении которых можно обеспечить сходимость алгоритма.
2.1 Постановка исходной задачи (1) где x(t) 2 Rn фазовый вектор системы, t 2 T , [t0; #] R, # фиксированный момент окончания игры (здесь и далее символ ¾,¿ означает ¾по определению равно¿). Игроки 1 и 2 распоряжаются выбором управлений u(t) 2 P Rp и v(t) 2 Q Rq соответственно. Здесь множества P и Q выпуклые многогранники. Матрицы A(t), B(t) и C(t) поэлементно-непрерывные на T матрицы-функции размеров n n, n p, n q.
Обозначим G T R компактное множество такое, что (t0; x0) 2 G и всякая траектория (1), начавшаяся в G, остается в G. Игроки имеют полную информацию о текущей позиции (t; x(t)).
Показатель качества игрока i имеет вид: где i : Rn ! R непрерывные функции такие, что множества уровня
Ii , i(x(#)) ! max; i = 1; 2;
Mic , fx 2 Rnj i(x) > cg; i = 1; 2; суть выпуклые множества для любого c 2 R.
Рассматривается игра в чистых позиционных стратегиях. Используемая в работе формализация стратегий и решений в неантагонистической позиционной дифференциальной игре взята из [2]. Определение 1. Чистая позиционная стратегия первого [второго] игрока [2]
Пара функций U , (u(t; x; "); 1(")) [V , (v(t; x; "); 2("))], где u( ) [v( )] произвольная функция позиции (t; x) 2 G и положительного параметра ", принимающая значения из P [Q]. Функции i(") : (0; 1) ! (0; 1) монотонные, удовлетворяющие условию
"li!m0 i(") = 0: 2.2 Рассматриваемые движения системы
В теории позиционных дифференциальных игр [4] рассматриваются одновременно несколько типов движений, отвечающих паре статегий. В частности, вводится понятие аппроксимационных движений или ломаных Эйлера. Они наиболее удобны для практических построений. В теории неантагонистических игр вводятся аналогичные конструкции. Определение 2. Закон управления [2]
Тройка (U; "1; 1) [(V; "2; 2)] называется законом управления первого [второго] игрока, где U [V ] чистая позиционная стратегия, "i выбранные параметры точности, а i , ftikgkK=i 1 конечные разбиения временно´го отрезка T такие, что k ik , max (tik+1 tik) 6 i("i):
16k<Ki Определение 3. Аппроксимационные движения [2]
Пусть заданы законы управления игроков (U; "1; 1) и (V; "2; 2), где U = (u(t; x; "); 1(")) и V = (v(t; x; "); 2(")) суть чистые позиционные стратегии, а 1 = ftj1gjK=11 и 2 = ft2kgkK=21 конечные разбиения временно´го отрезка T .
Апроксимационным движением или ломаной Эйлера из некоторой начальной позиции (t ; x ) 2 G будем
называть функцию x[t; (t ; x ); (U; "1; 1); (V; "2; 2)], t 2 [t ; #], которая является пошаговым решением
дифференциального уравнения:
(2)
(
Предельное движение, порожденное парой чистых позиционных стратегий (U; V ), где U = (u(t; x; "); 1(")) и V = (v(t; x; "); 2(")), из начальной позиции (t ; x ) 2 G, определяется как непрерывная функция x[t; (t ; x ); U; V ], являющаяся равномерным на [t ; #] пределом последовательности аппроксимационных движений fx[ ; (t ; xm); (U; "1m; 1m); (V; "2m; 2m)]gm при m ! 1, xm ! x , "im ! 0, i = 1; 2, при выполнении условий (t ; xm) 2 G, k imk 6 i("im). Определение 5. Согласованные движения [2]
Законы управления игроков (U; "1; 1) и (V; "2; 2) называются согласованными по параметру точности, если "1 = "2 = ". Аппроксимационные движения, порожденные согласованными законами, также называются согласованными. Предельные движения, являющиеся пределами последовательности согласованных ломаных Эйлера, называются согласованными движениями.
Будем обозначать согласованные движения с помощью индекса c. 2.3 Решение по Штакельбергу
Далее кратко излагается обобщение понятия решения неантагонистической игры по Штакельбергу [3], описанное в [2, c. 33-40]. Будем считать выполненными следующие предположения (1.7°, 1.8° [2, c. 33]): • Первый игрок, называемый лидером, объявляет свою стратегию U второму игроку до начала игры. • Второй игрок, называемый ведомым, выбирает рациональную стратегию V , исходя из условия: min 2(xc[#; (t0; x0); U ; V ]) ! max;
V где xc[t; (t0; x0); U ; V ] согласованное движение, исходящее из позиции (t0; x0) 2 G со стратегиями U и V . Задача игрока 1 нахождение стратегии U S1, которая обеспечивает максимальное значение показателя 1 из (2) при условии рациональности игрока 2. Рациональный ответ является стратегией V S1 игрока 2. Пара (U S1; V S1) называется решением по Штакельбергу (с лидером игроком 1) или S1-решением. 2.4
Вспомогательные антагонистические игры Алгоритм построения S1-решений опирается на решение нестандартных задач оптимального управления [2], сформулированных с использованием вспомогательных антагонистических позиционных дифференциальных игр i; i = 1; 2. Динамика этих игр описывается уравнением (1). В игре i игрок i максимизирует показатель Ii, в то время как игрок (3 i) противодействует ему. Известно [7], что в обеих играх 1 и 2 существуют универсальные седловые точки
(u(i)(t; x; "); v(i)(t; x; ")); i = 1; 2; и существуют непрерывные функции цены 1(t; x) и 2(t; x). Универсальность стратегий означает, что они оптимальны для любой начальной позиции в G.
Существование функций цены позволяет ввести множества уровня
Wici , f (t; x) 2 T
Rn j i(t; x) > ci g; ci 2 R; i = 1; 2:
Заметим, что Wici(#) = Mici (
В [1, 2, 5] выписана структура S1-решений, использующая стратегию u(2)(t; x; ") и позволяющая свести задачу построения S1-решений к задаче нахождения некоторых программных управлений u(t), v(t), t 2 T .
Итак, требуется найти измеримые управления u : T 7! P и v : T 7! Q такие, что порождаемое ими
движение x( ) удовлетворяет неравенству
(
Допустимые движения в неантагонистической игре Определение 6. Допустимое движение.
Назовем решение x( ) системы (1), порожденное измеримыми управлениями u( ) и v( ), S1-допустимым,
если для него выполнено условие (
Очевидно, что S1-допустимые движения доставляют игроку 2 значение выигрыша, не меньшее 2(t0; x0). Через D1 G обозначим множество позиций, заметаемых S1-допустимыми траекториями, т.е. множество D1 = f(t; x(t)) j x( ) S1-допустимо; t 2 T g. Через D1(#) обозначим сечение f(t; x(t)) 2 D1 j t = #g, то есть множество концов допустимых траекторий. Известно [2], что D1(#) компактно. 3
Численный метод Для численной аппроксимации решений Штакельберга предлагается следующая вычислительная схема. Пусть В этом определении будем рассматривать те c2, для которых D1(#) \ @M2c2 6= ?. Из постановки задачи и определения множества D1(#) следует, что любая пара (c1; c2), где c1max(c2) , x2D1m(#a)\x@M2c2 1(x); c2 2 R: c1 = c1max(c2); c2 2 arg max cmax(c) c2[c2;c2] 1 (8) (9) есть пара выигрышей, доставляемых игрокам некоторым S1-решением. Значения c2 и c2 должны быть выбраны так, чтобы выполнялись условия c2 6 2(t0; x0), maxx2D1(#) 2(x) 6 c2 6 maxx2Rn 2(x). Таким образом, задача нахождения решения Штакельберга может быть сведена к задаче (условной) максимизации. Рассмотрим её более подробно.
В [6] представлен ряд эффективных методов численной глобальной оптимизации. Для их применения требуется липшицевость максимизируемой функции и функций, задающих область поиска максимума (в виде системы неравенств). Таким образом, для эффективного решения задачи (9) требуется липшицевость функции cmax(c2) на её области определения. Отрезок [c2; c2] включает её область определения и может 1 быть даже несколько больше, чем требуется. Истинные границы области определения (minx2D1(#) 2(x) = 2(t0; x0) и maxx2D1(#) 2(x)) можно установить с заданной точностью в процессе вычислений. Рассмотрим задачу приближённого вычисления функции cmax(c2) (8). Данная задача есть задача услов1 ной максимизации. Условие x 2 @M2c2 заменяется на два неравенства c2 6 2(x) 6 c2 + , где > 0 есть некоторый параметр точности. Главная сложность кроется в условии x 2 D1(#).
В [5] задача численной максимизации решалась через вычисление многоугольной аппроксимации множества D1(#) перебором значений c2 с заданным шагом. Для задач с фазовым пространством размерности больше двух данный подход сталкивается со сложностью требуемых для этого процедур вычислительной геометрии (и в смысле вычислительной сложности, и в смысле сложности корректной программной реализации). Поэтому представляется разумным оперировать не целыми множествами в Rn, как это делалось в [5] (для случая n = 2), а отдельными допустимыми траекториями [8] (сечения мостов аппроксимировались выпуклыми многогранниками).
Будем считать, что эффективно вычислима : Rn 7! f0; 1g индикаторная функция некоторой аппроксимации множества D1(#). Для ускорения вычисления (x) можно также воспользоваться тем фактом, что D1(#) M1 1(t0;x0) \ G(#). В [6] также рассматривается случай частичной вычислимости ограничений в задаче условной оптимизации, что позволяет использовать условие (x) = 1 в качестве ограничения поиска максимума.
На практике, для определения факта попадания некоторой точки x в D1(#) выполняется попытка построить аппроксимацию S1-допустимой траектории, ведущей в позицию (#; x). Итак, если для некоторого x 2 Rn окажется, что (x) = 1, то в процессе вычисления (x) будет получена аппроксимационная S1допустимая траектория, ведущая в позицию (#; x), и порождающие её кусочно-непрерывные управления u(t), v(t). Таким образом, вычисление (9) влечёт вычисление численной аппроксимации S1-решения.
Выполнение условий Липшица
Рассмотрим S1-допустимые траектории x( ), обеспечивающие выигрыш ведомого игрока 2(x(#)) = c2.
Предположим, что c2 выбрано таким образом, что множество таких траекторий не пусто. Заметим, что из
определения S1-допустимой траектории следует, что такие траектории не заходят во внутренность W2c2 (
Предположим также, что функция c1max(c2) (8) определена на отрезке [c2; c2]. Исследуем липшицевость c1max(c2) в двух случаях. 4.1
Условие Липшица в случае гладкости i Условие Липшица для c1max(c2) имеет вид: 9L > 0 8c02; c020 2 [c2; c2] jc1max(c02) cmax(c020)j 6 Ljc02 1 c020j Поскольку из равенства c02 = c020 следует cmax(c02) = cmax(c020), то для этого случая (10) выполнено.
1 1
Поэтому возьмем точки x0; x00 2 Rn, такие что 2(x0) 6= 2(x00), и сформулируем условие следующего вида:
9L > 0 8x0; x00 2 G(#) : 2(x0) 6= 2(x00) j 1(x0)
1(x00)j 6 Lj 2(x0)
2(x00)j:
Пересечение @Mic \ G(#) обозначим как cM0ic. Учитывая (
Выберем точки x0 2 Mc202 и x00 2 Mc2020 . Для выбранных точек показатель второго игрока равен соответственно 2(x0) = c02 и 2(x00) = c020, а функция 1(x) для этих точек достигает максимума на данных множествах. То есть:
maxc0 1(x0) = c1max(c02); x02M22
maxc00 1(x00) = c1max(c020): x002M22 Таким образом, можно взять точки x0 2 M01c1max(c02) \ M02c02 , и x00 2 M01c1max(c020) \ M02c020 . Подставив в выражение (11) соответствующие значения 1 и 2, получаем условие (10). Утверждение доказано. Теорема 1. Условие (11) выполняется для i(x), определенного на Rn, если выполнены следующие предположения: 1. Функции i(x), i = 1; 2, гладкие на G( )
Rn. 2. Все @ @2x(jx) , 1 6 j 6 n, не обращаются в нуль ни в какой точке x 2 G( ).
Множество G( ) компактно, а значит на нем i(x) имеют непрерывные и ограниченные частные производные: 9Kij : 8x 2 G( ) Здесь xj это координаты x = (x1; x2; :::; xn)> 2 Rn. Из теоремы о среднем для функций многих переменных следует истинность 9 2 (x0; x00) i(x0) i(x00) = Xn @ i ( ) xj; j=1 @xj (10) (11) (12) (13) (14) Так как частные производные ограничены при любых x 2 G( ), то они ограничены и при а значит, исходя из (13), выполняется следующее неравенство: 2 (x0; x00)
G( ), xj = x0j x00;
j Минимум частных производных существует, так как это непрерывные функции, определенные на компакте. При этом, в соответствии с предположением 2, имеем kj2 6= 0. Следовательно, справедливо следующее неравенство: Пусть K1 = maxj Kj1; k2 = minj kj2, причем k2 6= 0, так как 8j kj2 6= 0. Тогда из (14) и (15) следует (15) j 2(x0) 2(x00)j > n X kj2j xjj; j=1 Здесь и в дальнейшем x = x0 x00. Вообще говоря, такое условие будет выполняться для ограниченной функции на ограниченном множестве. Поскольку G(#) компакт в Rn, а функция 2(x) непрерывна на нем, то она ограничена на этом компакте.
Так как функция 2(x) ограничена, то модуль разности можно записать j 2(x0) 2(x00)j = r1 > 0, поскольку выполняется 2(x0) 6= 2(x00). В то же время и x0 6= x00, а значит на ограниченном множестве выполнено k xk = r2 > 0. Разделив два эти равенства друг на друга и приравняв rr12 = L2, немедленно получаем условие (16).
Обсуждение результатов Получены достаточные условия липшицевости функции c1max(c2) (8). В первом случае (теорема 1) требуется гладкость показателей i(x) (2) на компакте G(#) Rn и выполнение условия @ @2x(jx) 6= 0. Данные условия довольно жесткие и существенно ограничивают выбор показателей игроков. Во втором случае (теорема 2) уже не требуется гладкость функций. Вместо этого достаточно липшицевости 1(x). Условие неравенства нулю инфимума L2(x0; x00) (16) можно рассматривать как некоторый аналог условия, накладываемого на частные производные в первом случае. Если предположить, что 2(x) гладкая и ни одна из частных производных @ 2(x) не обращается в нуль, то inf L2(x0; x00) также будет ненулевым.
@xj Выполнение полученных в работе условий открывает возможность применения эффективных методов численной оптимизации к задаче построения решений Штакельберга в представленном классе позиционных дифференциальных игр с терминальными показателями качества. Список литературы [1] S. I. Osipov. On the implementation of the algorithm for constructing solutions for the class of hierarchical games. Avtom. i telemech. 11: 195-208, 2007 (in Russian). = С.И. Осипов. О реализации алгоритма построения решений для класса иерархических игр Штакельберга. Автом. и Телемех. 11: 195-208, 2007. [2] A. F. Kleimenov. Non-zero-sum positional differential games. Nauka, Ekaterinburg, 1993 (in Russian). = А.Ф. Клейменов. Неантагонистические позиционные дифференциальные игры. Наука, Екатеринбург, 1993. [8] D. R. Kuvshinov. Numerical contruction of Nash solutions in a linear positional differential game of two persons with a phase space of more than two dimensions. Trudy IMM UrO RAN, 19(1):170-181, 2013 (in Russian). = Д.Р. Кувшинов. Численное построение решений по Нэшу в линейной позиционной дифференциальной игре двух лиц с фазовым пространством размерности больше двух. Труды ИММ УрО РАН, 19(1):170-181, 2013.
On the estimate of algorithms of constructing Stakelberg’s solutions in linear non-antogonistic positional two-person game
Alexander A. Karasev1, Dmitriy R. Kuvshinov1;2, Sergey I. Osipov1 1 – Ural Federal University (Yekaterinburg, Russia) 2 – Krasovskii Institute of Mathematics and Mechanics (Yekaterinburg, Russia) game, Lipschitz condition,
The problem of justifying one algorithm for constructing approximate Stackelberg solutions in a linear nonantagonistic positional differential game of two persons with terminal quality indicators and restrictions on the choice of controls given in the form of convex polyhedra is considered. The conditions for the players’ quality indicators are determined, upon application of which it is possible to ensure the convergence of the algorithm.