Игровая задача выбора наилучшего курса яхты

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

В известной задаче выбора наилучшего курса яхты скорость яхты зависит от угла, который образует курс яхты и направление ветра. При постоянной по направлению и по величине скорости ветра в [1] рассмотрена конкретная модель такой зависимости. Исследуется задача, когда выгоднее идти галсами, чем прямо по заданному курсу.

Если рассматривать случай, когда вектор скорости v ветра может меняться, находясь в некотором множестве V, то вектор скорости и яхты можно выбирать из некоторого множества U(у), зависящего от скорости ветра. Цель управления яхтой заключается в том, чтобы побыстрее вывести ее на заданное множество Z (например, причалить к острову). В каждый момент времени скорость ветра считается известной.

Рассмотренный пример является частным случаем задачи управления с помехой z' = -u, zERn, uEU(v)cRn, vEV(1.1)

Здесь И-множество произвольной природы; при каждом v Е V множество U(y) является непустым компактом в Rⁿ. Считаем, что ограниченным является множество

^ = U и^-(°)

vEV

Первый игрок, выбирая управление и EU(v), стремится побыстрее осуществить встречу

z(t) Е Z,(1.3)

где Z является выпуклым и замкнутым множеством в Rⁿ. Второй игрок, выбирая управление v EV, стремится сделать время встречи (1.3) как можно дольше.

Будем рассматривать игру, когда управление первого игрока строится в зависимости от реализовавшегося в момент времени t состояния z(t) и от значения в этот момент времени управления v{t) второго игрока. Будем строить управление первого игрока так, чтобы они допускали движение галсами [1].

Будем предполагать, что изменение управления v(t) с течением времени меняется не очень сильно. Чтобы строго сформулировать это допущение введем, в рассмотрение евклидов шар S в Rⁿ единичного радиуса и с центром в начале координат. Требование на v(t) запишем в следующем виде: для любого отрезка [0,р] существует число L > 0 такое, что

U (v(t)) С U (v(t)) + L(t — t)S при 0 < t < т < р.

(1-4)

Под управлением (щ Л) первого игрока понимаем правило, которое каждому состоянию t >0,z € Rn и любому v EV ставит в соответствие конечный набор us = us(t,z,v) EU(v), s = 1,...^ = k(t,z,v), Xs = Xs(t,z,v) > 0, Xi + ... + Xk = l. (1.5)

Движение системы (1.1) будем определять с помощью ломаных. Пусть заданы начальное состояние Z^o > 0, го = ^(to) Е Rn и конечный момент времени р > to- Возьмем разбиение w :t0

с диаметром

d(o>) = max(ti+i - ti).(1.7)

0

Построим ломаную

Z^t) = z^iti) - [ u*(r)dr, ti

Здесь обозначено u*(r) = u_s(ti,z_u(tt),v(t_t)) при t^^3-^ ш(1{),у(Ъ)), s

^0) = ^, 4з) = и + (ui - u) 52 A«'(

Содержательный смысл управлений (1.9) следующий. С помощью чисел X_s первый игрок разбивает отрезок [^,ti+i] точками ti = t^ < t^ < ... < t^ < ... < t^ = ^i и на каждом из промежутков (^•^s~¹\^] движется с постоянной скоростью u₈(t_t^ z^ii), v(ti)). Управление второго игрока постоянно на промежутке (f^^-1^^] и равно v(ti).

Из ограниченности множества (1.2) следует, что все ломаные (1.8) удовлетворяют условию Липшица с одной и той же константой. Следовательно, семейство ломаных (1.8) удовлетворяет условию теоремы Арцела[2]. Под движением системы (1.1) с управлением (1.5) и с начальным условием г (to) = го понимаем любую функцию z : [to,p] —>Rⁿ, которая является пределом равномерно сходящейся на отрезке [to,p] последовательности ломаных (1.8), у которых диаметр разбиения стремится к нулю.

Отметим, что u*(r)dr = (il+i - *г) 5 XsUs^Zuiti^viti)).               (1.10)

s=l

2.    Оператор программного поглощения и его свойства

Следуя [3], введем для игры (1.1) оператор программного поглощения D_a. Пусть X С Л^п, а > 0. Точка z Е Д(Х) тогда и только тогда, когда для любого v Е V найдется измеримое управление и : [0, а] -^ U(v) такое, что z — ^ u(r)dr Е X при некотором 0 < / < ст.

Для любого ограниченного множества F С Rⁿ п для любого отрезка [a, b] С R имеет место формула [4]

ъ

-^ F - измерима > = (Ь — d)coF

(2-1)

Здесь посредством coF обозначена выпуклая оболочка множества F.

Будем использовать операции сложения множеств X и У из 1?^п и умножение множества X на число а

X + Y = {z = x + y:xEX,yEY}, а X = {z = ах : х Е X} .

С учетом этих формул, а так же формулы (2.1), оператор программного поглощения принимает вид ад=П \J (X + aTcoU(v)).                 (2.2)

«evo

Свойство 2. 1. Do^) = х.

Свойство 2. 2. Если 0 < 6 < а, X С Y, то D^X) С D_a(Y).

Свойство 2. 3. D_a(X + У) 3D_a(X) + Y.

Свойство 2. 4. D_s(D_a(Xy) С D_e+a(X).

Свойство 2. 5. D_a(aX) = aDi(X).

Свойство 2. 6. Если X - выпуклое множество, то множество D_a{X} является выпук-

ЛЫЛ4>.

Свойство 2. 7. Если X - выпуклое множество, то D§(D_a(X)) = D^_+a(X).

Свойство 2. 8. Если X - замкнутое множество, то множество D_a(X) является замкнутым.

Свойство 2. 9. Пусть X - замкнутое множество, последовательность 0 < <7^+1 < о^,

Свойства 2.1 - 2.6 непосредственно следуют из формулы (2.2). При доказательстве свойства 2.7 применим схему доказательства из работы [5]. В силу свойства 2.1 нужно рассмотреть случай £ > 0 и а > 0. Обозначим X* = (5 + а^Х. Тогда из выпуклости множества X следует равенство ^Х* + аХ* = X. Отсюда, используя свойства 2.2, 2.3 и 2.5, получим гдадх)) = Ds(Da(SX* + aXJ) D Ds(Da(vX*) 4- 6X.) D

D D_s(SX*) + D_a(aX^ = SD^X^ + aD^) D

D (H a^X,) = ДнД^ + a)XJ = D^_a(X).

Обратное включение следует из свойства 2.4.

При доказательстве свойств 2.8 и 2.9 используется тот факт, что выпуклая оболочка компакта в Rⁿ является компактом [6, теорема 1.1.7].

3.    Оптимальное время встречи

Для каждой точки z Е Rⁿ положим T(z) = +оо, если zED_a(Z) при всех а > 0. В противном случае

T(z) = inf а, а > 0, zE D^Z).                      (3.1)

Эта функция обладает следующими свойствами.

Свойство 3. 1. Если а = T(z) < +оо, то z Е D_a(Z).

Свойство 3. 2. T(z) > 0 при любом z Е Rⁿ; T(z) = 0 тогда и только тогда, когда z Е Z.

Свойство 3. 3. Функция T(z) является выпуклой.

Доказательство свойства 3.1 следует из замкнутости множества Z и из свойства 2.9 оператора D.

Первая часть свойства 3.2 следует из формулы (3.1). Если T(z) = 0, то из свойства 3.1 следует, что z Е Dq(Z) = Z. Если же z Е Z, то равенство T(z) = 0 очевидно.

Докажем свойство 3.3. Возьмем точки z_% Е Rⁿ, г = 1,2, у которых о^ = Tfa) < +оо. Тогда из свойства 3.1 и из формулы (2.2) следует, что для любой точки v Е V найдутся числа 0 < т< < 1, £ = 1,2, такие, что Zi Е Z + aiTiCoU(v), £ = 1,2. Возьмем числа A_z > 0, Ai + А2 = 1- Тогда из предыдущего включения, используя выпуклость множеств Z и coU^v), получим

A1Z1 + A2Z2 eZ + (Ajai + X₂o-2)tcoU(v), т = -—^--п + -—^--т₂ G [0,1].

Отсюда и из формулы (3.1) получим, что T(Ai^i + Аг^) < AiT(^i) + АгТ^).

Утверждение 3. 1. Пусть начальное состояние г(0) = zqEZ. Тогда для любого числа 0 < р < T(zq) существует точка v EV такая, что постоянное управление второго игрока v(t) = v при всех 0 < t < р обеспечивает для любого управления (1.5) первого игрока выполнение условия

z(T)EZ при всех 0 < t < р.(3.2)

Доказательство. Поскольку zqEDp(Z), то из формулы (2.2) следует, что найдется точка v EV, для которой zqEZ + tcoU(v) при всех 0

Из формул (1.8) и (1.9) следует, что при v(t) = v каждая ломаная удовлетворяет равенству z^^t) = ^0“ tu(t) при некотором u(t) Е coU(v).

Следовательно, аналогичному равенству удовлетворяет и любое движение z(t). Отсюда и из (3.3) получим (3.2).□

4.    Построение управления первого игрока

При построении управления первого игрока, обеспечивающего встречу (1.3) из начального состояния ^(0) = ^о к моменту Т(^о), воспользуемся схемой из работы [7].

Лемма 4. 1. Пусть z Е D^^Z) при 6 > 0 и а > 0. Тогда для любой точки v Е V существует точка и Е coU(v) такая, что либо z-6uEDa(Z\                          (4.1)

либо при некотором 0

z — tu Е Z.                                     (4.2)

Доказательство. Из формулы (2.2) и из свойства 2.7 отображения D следует, что для точки v EV непустым является множество чисел

О < £ < <5, z Е D^Z} + tcoU(v).                         (4.3)

Обозначим через /о верхнюю грань таких чисел t. Из замкнутости множества D_a(Z) и из компактности множества coU(v) следует, что включение (4.3) выполнено при t = to. Если to = <5, то из (4.3) следует (4.1)

Пусть 0 < to < ^ Возьмем число 0 < 7 < 5 - to, чтобы jy = а при некотором целом j > 1- Тогда из включения (4.3) при t = to получим, что z — tou± Е D37(Z) = D7(D^_^7(Z))

при некотором щ Е coU(v). Отсюда следует, что найдется число 0z — toui Е Dfj-iy^Z) + ticoU(v).

Отсюда, используя свойство 2.2 отображения D, получим, что при t = to+ t± выполнено включение (4.3). Поскольку число to является верхней гранью чисел t, удовлетворяющих (4.3), то ii = 0. Продолжая этот процесс дальше, найдем точку и Е coU(v) такую, что при t = to будет выполнено включение (4.2).                                              □

Теорема 4. 1. Пусть начальное состояние zo такое, что р = T(zq)< +оо. Тогда существует управление (1.4) первого игрока такое, что для любого управления v(t) второго игрока будет выполнено включение (1.3) при некотором t <р.

Доказательство. Обозначим

^о(^) = {z = и —и* : и Е coU(v),u* Е coU(v)} .

При каждых zERⁿ,0положим

s(£,^,v) = mins, s > 0, z E Dp-t^Z) + eUo(v) + eS.(4.5)

Множество Dp-t^Z) является замкнутым, а множества Uq(v) и 5 - компакты. Поэтому включение (4.5) выполнено при s = s(t,z,v). Из определения множества (4.4) следует, что z + e(t, z, v)(u*(t, z, v) — u(t, z, v)) E Dp~t(Z) + e(t, z, v)S(4.6)

при некоторых u*(t,z,v) E coU(v) и u(t,z,v) E coU(v).

По теореме Каратеодори [6, теорема 1.1.1]

k

u(t,z,v) = У}X_s(t,z, v)u_s(t,z,v), X_s(t,z, v) > 0,

S=1 к

^Jx_s(t,z,v) = 1, u_s(t,z,v) G U(v).                        (4.7)

Здесь к = k(t,z,v) 1.Эти функции берем в качестве управления (1.5) первого игрока.

Пусть в процессе игры реализуется управление v(t) G V второго игрока, удовлетворяющее условию (1.4). Тогда из формулы (4.4) следует, что включению (1.4) удовлетворяет и многозначная функция Uo(y(t)). Отсюда получим, что

J7o(v(t)) С Uq(v(t)) + L(r — t)S при 0                (4.8)

Возьмем разбиение w (1.6) и построим ломаную (1.8) с функциями (4.7). Обозначим z. = Zu(ti), Щ = v(ti), U^ = u(tt,Zi,Vi),U^ = U*(ti,Zi,Vi), Et = £(tt,Zi,Vi).

Тогда из (4.6) следует, что при г = 0 выполнено включение z% + ZiU^ — ZiU^ Е Dp-tz(Z) + ZiS,                       (4.9)

причем во = 0. Предположим, что в момент времени t^ i < 1 + 1 выполнено включение (4.9). Тогда, используя лемму 4.1, найдем точку и Е coU(yi) такую, что либо

Zi + е+У - EiU^ - (ij₊₁ - t^u G Dp-ъ+г (^z) + ^ei^             (4-10)

либо при некотором t Е [^,^+1]

Zi + ZiU^ — ZiU^ - (t- ti)u E Z + z_%S.                    (4.11)

Рассмотрим случай (4.10). Из формулы (1.10) получим, что z^i = Zi — (^+i — ti)u^.

Отсюда и из (4.10) будем иметь, что

^+1 + (^+1 ~ ti ~ £г)и^ + z:iU^ — (^1 — 1_г)и Е Dp-t^^Z) + ZiS. (4.12)

Пусть £_г+1 — 1_г> z_t. Тогда (^₊i — ti - Zi)u^ + ZiU^ E (^+i - t^coU(vi). Отсюда и из (4.12) получим, что

^+1 £ Dp-t_i+1(Z) + (ti^i—t_l)UQ(vi)+z_lS С T>p-t_l+1(^) + (^H4^—£г)^о(^ш) + (^        ~ti\²)S.

Здесь было использовано включение (4.8). Отсюда и из (4.5) следует, что

£г+1 < ft+1 “ У(1 + Ь(^ф1 ^—ti}}.

Пусть ^+1 -1_г< Zi. Тогда

(е_г - f_z+i + ti)u^ + (^+i - ti)u Е ZiCoU^Vi)

и, как следует из (4.12) и (4.8),

^+1 £ D_p-t_i+1(Z) + ZiUo(vi) + ZiS С

С D_p-t_z+1(Z) + s^oGm-i) + (^ + £fe+i “ ti)zi)S.

Отсюда и из (4.5) следует неравенство

£г+1 < £г(1 + ife+1 — ^))-

Объединяя оба случая, будем иметь, что включение (4.9) выполнено при i + 1, причем сг+1 < max(^+i - t^ sj(l + £(^+i - ^)).                   (4.13)

Поскольку €о = 0, то из этого неравенства следует, что для всех t^ для которых выполняется включение (4.10), будет выполнено

£»+i<

Обозначим

Го = со U r0(v).

vev

Из ограниченности множества (1.2) следует ограниченность множества Uq.

Пусть включение (4.10) выполнено для всех i <1. Тогда из (4.5) и (4.14) следует, что z^eZ + S^iUo + S), 6(w)=d(u)#L.              (4.15)

Рассмотрим случай, когда для какого-то i < I выполнено включение (4.11). На отрезке [^,^+1] реализуется управление и*(г) G U(viY которое определяется формулами (1.9). Из (4.11) и (1.8) следует, что

+   и* (r)dr + SiU^ - €iU^ - (t- ti)u e Z + SiS,

Jtz

Поскольку t u*(r)dr e (t — ti)coU(vi), то из предыдущего включения получим, что z^f) ez + (t-ti + 6i)(U^ + S)cZ + d(^}{l + epL)(Uv + SY         (4.16)

Отсюда и из (4.15) следует, что для каждой ломаной (1.8) найдется число 0 < t(a}) < р такое, что при t = t^) выполнено включение (4.16).

Пусть последовательность ломаных z^ (t) с диаметром разбиения d(wk) —> 0 равномерно на отрезке [0,р]сходится к движению z(t). Для каждой ломаной в точке t = tfak) выполнено включение (4.16). Можно считать, что t(wk) "^ t* (иначе перейдем к последовательности). Из равномерной сходимости ломаных следует, что z_CUk(t(iVk)) —> z(t*). Отсюда и из включения (4.16) получим, что z(t*) е Z.                                                            □