Дифференциальная игра с простым движением

ДИФФЕРЕНЦИАЛЬНАЯ ИГРА С ПРОСТЫМ ДВИЖЕНИЕМ

Рассматривается дифференциальная игра преследования с простым движением и с невыпуклыми вектограммами игроков.

Ключевые слова: дифференциальная игра, стратегия, оператор программного поглощения.

1. Пример

Первый игрок может двигаться на плоскости с постоянной по величине скоростью, равной заданному числу а > 0. Второй игрок движется по заданной прямой I, причем величина скорости ограничена числом Ь > 0. Выберем на плоскости прямоугольную систему координат, ось Оу которой совпадает с прямой I. Тогда уравнения движения игроков примут вид

х 1 = щ, у 1 = и2, и1 + и2 = а2, у/2 = V, Н< Ь.

Цель первого игрока, который выбирает управление (и1,и2), заключается в том, чтобы как можно быстрее осуществить поимку:

х1С0 = 0, У1СО = У2 СО-

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

Считаем, что а > Ь. В противном случае второй игрок, двигаясь с максимальной по величине скоростью, может не допустить поимку (1.2).

Свяжем с первым игроком подвижную систему координат, параллельную исходной. В новых переменных х = — х1, у = —у1 + у2 уравнения движения (1.1) примут вид

х = —и1, у = —и2 + V, и\ + и2 = а2, |V| < Ь.

Обозначим через Т(х,у) оптимальное время поимки из начального состояния х(0) = х, у(0) = у. Если решать эту задачу методом динамического программирования, то для определения функции Т(х,у) будем иметь уравнение Р Айзекса [1]

Ь

и два условия

дТ //0^42 /С^Ч2

ду

Т

Приведем несколько выпуклых функций, удовлетворяющих необходимым условиям (1.4) и (1.5).

Для любых чисел

с1 > 0, с2 > 0, Ьс2 + 1 = а у' с1 + с2

функция Т(х,у) = с1 |х| + с2|у| удовлетворяет условиям (1.5), а при ху = 0 она удовлетворяет уравнению (1.4).

Функция

|у|Ь + л/х2 (а2 — Ь2) + а2у2

Т

а2 — Ь2

также удовлетворяет (1.5), а при у = 0 она удовлетворяет уравнению (1.4).

2. Игры преследования с простым движением и свойства оператора программного поглощения

Рассмотренный пример является частным случаем общей игры преследования с простым движением [2]

г = —и + V, г € Яга, и € и, V € V.

Здесь и и V — компакты в Дга.

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

г

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

V € V, стремится сделать время поимки (2.2) как можно большим.

В работе [2] эта игра рассмотрена в а-стратегиях, которые предполагают дискриминацию второго игрока. Будем рассматривать игру, когда управления игроков строятся в зависимости от реализовавшегося состояния и они допускают движения галсами [3]. Формализуем это следующим образом.

Стратегией (и, Л) ((г>,Д)) первого игрока (второго игрока) назовем правило, которое каждому состоянию Ь > 0, г € Кп ставит в соответствие конечные наборы — у первого игрока

и3 = и8(Ь,г) € и, 5 = 1,...,к = к(Ь,г), Л5 = Л8(Ь,г) > 0, Л1 + ••• + Лк = 1;

и у второго игрока

Vj = Vj (Ь, г) € V, = 1,...,т = т(Ь, г), ^ ^ (Ь, г) > 0, ^1 + ••• + = 1.

Движение системы (2.1) при стратегиях (2.3) и (2.4) будем определять с помощью предельного перехода по ломаным. Пусть задано начальное состояние Ьо > 0, г(Ь0) = € Кп и конечный момент времени р > Ь0. Возьмем разбиение

и : Ьо < *1 <    < Ьг < Ьг+1 <    < и+1 = р

с диаметром ^(и) = max (Ьг+1 — Ьг). Построим ломаную

г=0,1,...,1

Здесь обозначено

и* = и(Ьг, (Ьг)), при Ь(8-1) < г < С, 5 = 1,... , к(Ьг, ^(Ьг)),

Ь( ) = ^ ) = Ьг + (Ьг+1 — Ьг) ^ ] Лд;

9=1

V* (г) = V, (Ьг,гш (Ьг)) при *^-1) < Г < ^ ^ = 1,. . . ,ш(*г,гш (Ьг)),

У

£

9=1

Содержательный смысл управлений (2.6) дадим на примере первого игрока. С помощью чисел Л8 он разбивает отрезок [Ьг,Ьг+1] точками Ьг = Ь(0) < Ь(1) <

-/-(«) , , ;(&) | /,(8-1) ,(«)т

 < с* <    < ь* = Ьг+1 и на каждом из промежутков (Ьг , с* ] движется с

постоянной скоростью и8(Ьг,гш(С*)).

Отметим, что

и* (г)^г = (Сг+1 — Сг) ^ Лдид(Сг, (С*)) ,

г и+г к

/ и*

•^г 9=1

гк+1

/ V**

•^г д=1

Из ограниченности множеств и и V следует, что все ломаные (2.5) удовлетворяют условию Липшица с одной и той же константой. Следовательно, семейство ломаных (2.5) удовлетворяют условию теоремы Арцела [4]. Под движением

системы (2.1) с управлениями (2.3) и (2.4) и с начальным условием г(С0) = г0

понимаем любую функцию г : [С0,р] — Кп, которая является пределом равномерно сходящейся на отрезке [С0,р] последовательности ломаных

тогда и только тогда, когда для любого измеримого управления V : [0,а] ^ V найдется измеримое управление и : [0,а] ^ и такое, что

г — / и(г)^г + / v(r)dr € X при некотором Ь € [0, а].

00

Для любого ограниченного множества ^ С Кп и для любого отрезка [а, Ь] С К имеет место формула [6]

^ /

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

А,

^(.)0<*<^ ^0 '

Пересечение берется по всем измеримым функциям V : [0, а] ^ V.

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

Т

Покажем справедливость этого равенства и в рассматриваемом нами случае. Оператор (2.9) обладает следующими свойствами.

Предложение 1. Ас)^) = X.

Предложение 2. Если 0 < 6 < а и X С У, то А^(X) С А,(У).

Предложение 3. А,(X + У) 3 А,(X) + У.

Предложение 4. А^(А,(X)) С А^+Ст(X) для любых 0 < 6 < а.

Эти свойства непосредственно следуют из формулы (2.9). При доказательстве следующего свойства используется непрерывная зависимость интеграла от верхнего предела интегрирования и тот факт, что выпуклая оболочка компакта в Кп является компактом [7, теорема 1.1.7].

Предложение 5. Если X — замкнуто, то А, (X) — замкнуто.

Предложение 6. Для любого X С Кп и любого а > 0 выполнено А,(аX) =

аА^).

Доказательство. Сделаем в формуле (2.9) замену г = аз, Ь = ат, v(r) = v*(а-1r) = v*(s), 0 < з < т < 1. Получим

А. (X) = п и X + таеои — а v*(s)dsJ,

а*(.) 0<т<1 ' ^0 '

где пересечение вычисляется по всем измеримым функциям V* : [0, 1] ^ V. Отсюда следует требуемая формула.

Если в формуле (2.9) рассматривать только постоянные функции v(r) = V €

V, то получим следующее свойство.

Предложение 7. Для любого множества X С Кп

А, (X) С п и (X + Ьеои — Ьи).

0<4<ст

В работе [2] показано, что если X — замкнутое выпуклое множество, то

Д;

Оказывается, что условие замкнутости можно отбросить. В [8] доказана

Теорема 1. Если X — выпуклое множество, то выполнено (2.11).

Доказательство. В силу свойства 1 нужно рассмотреть случай 8а > 0. Обозначим X! = (8 + а)-1Х. Тогда из выпуклости множества X следует равенство 8X1 + 0X1 = X. Отсюда, используя свойства 2, 5, 6, получим

Д;(Д(X)) = Д;(Д,(8X1 + 0X1)) 3 Д;(Д,(0X1) + 8X1) 3 3 Д;(8X1) + Д,(0X1) = 8Д1№) + аД^) 3 (8 + 0^1^) =

= Д;+Ст ((8 + 0^1) = Д;+Ст (X).

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

Теорема 2. Пусть X — замкнутое выпуклое множество и г € Дг+о(X) при 8 > 0, 0 > 0. Тогда для любого измеримого управления v : [0, 8] ^ V существует точка и € сои такая, что либо

г — 8и + [ v

./0

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

г — £и + [ v

./о

Доказательство. Из формул (2.9) и (2.11) следует, что для измеримого управления V : [0,8] ^ V непустым является множество чисел

0 < т < 8, г + [ v

о

Обозначим через то верхнюю грань таких чисел т. Из замкнутости множества До (X) и из компактности множества сои следует, что включение (2.14) выполнено при т = т0. Если т0 = 8, то из (2.14) следует (2.12).

Пусть 0 < т0 <8. Возьмем такое число 0 < 7 < 8 — т0, чтобы ^'7 = 0 при некотором целом ] > 1. Тогда из включения (2.14) при т = т0 получим, что

ГТ0

г — т0и1 + v

0

при некотором и1 € сои. Отсюда следует, что для управления v1(r) = v(т0+r) € V при 0 < г < 7 найдется число 0 < £ < 7 такое, что

ЛТ0 гЬ

г — т0и1 + / v(r)dr + / v(т0 + г)^г € Д(^-1)7(X)+ £соЦ.

00

Отсюда, используя свойство 2, получим, что при т = т0 + £ выполнено включение (2.14). Поскольку число т0 является верхней гранью чисел т, удовлетворяющих включению (2.14), то £ = 0. Продолжая этот процесс дальше, найдем точку и € сои такую, что при £ = т0 будет выполнено включение (2.13).

Теорема 3. Если X — выпуклое множество в Яга и а > 0, то

п и

vЄV 0<і<а ^ЄооУ 0<і<а

Доказательство. Поскольку V С ссУ, то правая часть (2.15) содержится в левой. Считаем, что а > 0.

Пусть точка г принадлежит левой части (2.15). Покажем, что она принадлежит правой части. Возьмем любой вектор V Є ссУ. По теореме Каратеодори [7, теорема 1.1.1]

к к

V = ЛіV,, V Є V, Лі > 0, Лі = 1, к < п +1.

і=1 і=1

Для каждого vi найдется число і Є [0, а] такое, что

г Є X + іісси — і^, і = 1,..., к.

Считаем, что все і > 0. В противном случае г Є X и, следовательно, принадле-

жит правой части (2.15). Рассмотрим числа

Лі „ „ Л Л_ 1 к

т. = ^ > о. * = £ 77 г -• £* = !•

.= 1 .=1

Умножим г-е включение на число 7. и сложим их. Получим

к к 11 к 1 г € X +> 7.^.оои — > 7.^. = X + -сои — ^/ Л.^. = X+Ьсои — Ь = - < а.

.=1 .=1 .=1

Следовательно, точка г принадлежит правой части (2.15).

Теорема 4. Если X — выпуклое замкнутое множество, то

д

v€V 0<£<а

Доказательство. При а = 0 в формуле (2.16) стоит равенство. Пусть а > 0 и точка г принадлежит правой части (2.16). Покажем, что г € Д (X).

Возьмем любое измеримое управление V : [0, а] ^ V. Нужно показать, что

г + / v

0

Рассмотрим в начале случай, когда управление v(r) непрерывно в точке г = 0. Из формулы (2.8) получим, что

1 (Ь

- v(r)dr = и(Ь) € сои, 0 < Ь < а.

Ь Уо

Функция V(^) является непрерывной при 0 < Ь < а. Из непрерывности функции v(r) при г = 0 следует, что £>(£) ^ v(0) при Ь ^ 0+. Положим V(0) = v(0). Тогда функция V(^) € сои будет непрерывной при 0 < Ь < а.

Зафиксируем число 0 < Ь < а. Поскольку точка г принадлежит правой части (2.16), то, используя формулу (2.15), получим, что

г + ги

при некотором 0 < т < а.

Множества X и сои являются выпуклыми и замкнутыми, причем множество сои ограничено. Отсюда следует, что множество чисел т € [0, а], удовлетворяющих включению (2.18), является отрезком I(Ь) С [0,а]. Используя непрерывность функции V(^), получим, что

если ^ Ь, тк ^ т, тк € I(Ьк), то т € I(Ь).

По теореме Катутани [9] многозначное отображение Ь ^ I(Ь), Ь € [0,а], имеет неподвижную точку Ь € I(Ь). Полагая в (2.18) т = Ь, получим требуемое включение (2.17).

Пусть функция v(r) не является непрерывной в точке г = 0. Построим последовательность управлений ^ : [0,а] ^ и, непрерывных в точке г = 0 и сходящихся почти всюду на [0,а] к v(r). Для каждого такого управления при некотором Ьд € [0,а] выполнено включение (2.17). Можно считать, что Ьд ^ Ь € [0, а] (иначе перейдем к сходящейся подпоследовательности). Из теоремы Лебега [4] следует, что

^к ^

/ ^(г)^г ^ v(r)dr.

00

Отсюда, учитывая замкнутость множеств X и сои, получим включение (2.17). Обратное включение в (2.16) следует из свойства 7.

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

Будем рассматривать случай, когда множество Z является выпуклым и замкнутым. Будем считать, что функция (2.10) Т(г) = +то, если включение (2.10) не выполнено при всех а > 0.

Из формулы (2.16) вытекают следующие свойства функции Т(г).

Предложение 8. Если а = Т(г) < +то, то г € Д ^).

Предложение 9. При любом г € Яга Т(г) > 0; Т(г) = 0 тогда и только тогда, когда г € Z.

Предложение 10. Функция Т(г) является выпуклой.

Теорема 5. Пусть начальное состояние г0 таково, что р = Т(г0) < +то. Тогда существует стратегия (2.3) первого игрока такая, что для любой стратегии

(2.4) второго игрока будет выполнено включение (2.2) при некотором Ь < р.

Доказательство. При каждых г € Яга, 0 < Ь < р положим

е

при некоторых м* € сои, м € сои. Если включение (3.1) не выполнено при любом е > 0, то полагаем е(Ь,г) = +то. Поскольку множество Др-4^) является

замкнутым, а сои — компакт, то

г + е

при некоторых м*(Ь,г) € сои, м(Ь,г) € сои. По теореме Каратеодори

П+1 П+1

м(Ь,г) = ^^ Л5(Ь,г)м5(Ь,г), Л5(Ь,г) > 0, Л8(Ь, г) = 1, м8(Ь,г) € и.

«=1 «=1

Эти функции берем в качестве стратегии первого игрока.

Пусть второй игрок выбрал допустимую стратегию (2.4). Возьмем разбиение ш отрезка [0,р] и построим ломаную (2.5) с функциями (2.6). Обозначим

г. = ^(Ь), м(г) = м(Ь, ^(Ь.)), м*г) = м*(Ь., ^(Ь.)), е. = е(Ь., ^(Ь.)).

Тогда из (3.2) следует, что при г = 0 выполнено включение

г. + е.м*.) — е.м

причем е0 = 0. Предположим, что в момент Ь., г < I + 1, включение (3.3) выполнено.

На отрезке времени [Ь.,Ь.+1] второй игрок реализует управление ^*(г) € и, определяемое формулой (2.6). Из включения (3.3), используя теорему 2, найдем м € сои такое, что либо

/**г+1

г. + е.м*.) — е.мм —

либо при некотором Ь € [Ь., Ь.+1]

г. + е.м*) — е.мм —

'ч

Рассмотрим первый случай. Из формулы (2.7) получим, что

/•*г+1

г.+1 = г. — (Ь.+1 — Ь. )м« + / V. (г)^г.

Л;

Отсюда и из (3.4) будем иметь

г.+1 +

Пусть Ь.+1 — Ь. > е.. Тогда (Ь.+1 — Ь. — е.)м(^ + е.м*^ € (Ь.+1 — Ь.)сои. Отсюда, используя включение (3.6) и формулу (3.1), получим, что е.+1 < Ь.+1 — Ь..

Пусть Ь.+1—Ь. < е.. Тогда (е.—Ь.+1 +Ь.)м(.) + (Ь.+1—Ь.)м € е.сои. Следовательно, согласно включению (3.6), е.+1 < е..

Объединяя оба случая будем иметь, что включение (3.3) выполнено при г + 1

и

е.+1 < шах

Рассмотрим теперь случай, когда выполнено включение (3.5). На отрезке [Ь.,Ь.+1 ] первый игрок реализует управление м.(г) € и (2.6). Из формул (2.5) и

(3.5) имеем, что

(Ь) + / м.(г)йг + е.м*.) — е.м(.) — (Ь — Ь.)м € Z•

Л;

Из этого включения и из формулы (2.8) следует, что

(Ь) + (Ь — Ь. + е.)м+ — (Ь — Ь. + е.)м+ € Z

при некоторых м+ и м+ из сои. Отсюда, используя определение числа е(р, г) (3.1) и свойство 1, получим, что

е

Поскольку е0 = 0, то из неравенства (3.7) получим, что для всех г, для которых выполняется включение (3.4), выполнено неравенство е. < ^(ш). Если включение (3.4) выполняется для всех г < /, то в конечный момент времени е(р,гш(р)) < ^(ш). Отсюда и из (3.8) следует, что для каждой ломаной (2.5) найдется число 0 < Ь(ш) < р, при котором

при некоторых м*(ш) и м(ш) из сои.

Пусть последовательность ломаных г^к (Ь) с диаметрами разбиения ^(ш&) ^ 0 равномерно на отрезке [0,р] сходится к движению г(Ь). Можно считать, что последовательности

Ь(шк) ^ Ь* € [0,р], м*(шк) ^ м* € сои, м(шк) ^ м € сои

(иначе перейдем к подпоследовательностям). Из равномерной сходимости ломаных получим, что г^к (Ь(шк)) ^ г(Ь*). Отсюда и из (3.9) следует, что г(Ь*) € Z.

Теорема 6. Пусть г0 € Z. Для любого числа 0 < р < Т(г0) найдется вектор

V € V такой, что стратегия второго игрока v(i. г) = V при всех 0 < Ь < р, г € Яга обеспечивает для любой стратегии (2.3) первого игрока выполнение условия

г

Доказательство. Поскольку г0 € ), то из формулы (2.16) следует, что най-

дется V € V, при котором

г0 + ^v € Z + Ьсои при всех 0 < Ь < р.

Из формулы (2.5) следует, что при стратегии у(Ь,г) = V в каждый момент времени 0 < Ь < р движение г (Ь) представимо в виде

г(Ь) = г0 — Ьм(Ь) + Ьу при некотором м(Ь) € сои.

Отсюда и из (3.11) получим (3.10).

При практическом вычислении множества (2.16) полезна следующая лемма. Лемма 1. Пусть V С сои. Тогда

А.

Доказательство. Пусть г € А.(X). Возьмем любой V € V. Тогда г € X + Ьм — Ьу при некоторых м € сои, 0 < Ь < а. Поскольку V € V С сои, то

г € X + Ьм + (а — Ь)у — ау € X + асои — ау.

Следовательно, точка г принадлежит правой части (3.12). Обратное включение очевидно.

В случае (3.12) время преследования (2.10) определяется из условия Т(г) = Т)(г), где

Т0

В 1963 г. Н. Н. Красовский [10] ввел понятие первого момента поглощения. Применительно к рассматриваемым играм он определяется формулой (3.13).

Теорема 7. Если множество Z выпукло и замкнуто, а в точке г € Яга функция Т0(г) < +то, то Т(г) = Т0(г).

Доказательство. Из формул (2.10) и (3.13) следует неравенство Т(г) < Т0(г). Нужно показать, что Т(г) > Т0(г).

Отметим, что при а = Т0(г) включение (3.13) выполнено. Для любого V € V множество чисел 0 < а < Т0(г), для каждого из которых выполнено включение г + ау € Z + асои, является выпуклым и замкнутым. Значит, оно является отрезком [а(у),Т0(г)]. Покажем, что

а0 = вир а

Допустим, что а0 < Т0(г). Тогда а0 € [а(у),Т0(г)) при любом V € V. Стало быть, при этом а0 выполнено включение (3.13). Но это противоречит определению числа Т0(г).

Пусть Т

4. Решение примера

Рассмотрим игру (1.3), в которой множество Z является кругом радиуса е > 0 с центром в начале координат.

Для нахождения оптимального времени преследования воспользуемся формулой (3.13), которую запишем в исходных переменных (1.1). Областью достижимости первого игрока в момент времени Ь является круг радиуса аЬ с центром в точке Хі, у1. Областью достижимости второго игрока является отрезок ЫЬ, лежащий на оси Оу с центром в точке у2 длиной 2ЬЬ.

Рис. 1

Первый момент поглощения будет являться минимальным из положительных моментов времени Ь, для каждого из которых точки М и Ь принадлежат кругу радиуса аЬ + е с центром в точке Е. Как следует из рис. 1, первый момент поглощения является решением следующей задачи:

Ь ^ шт, Ь > 0, (у1 — у2 + Ы)2 + х\ < (е + аЬ)2,

(У1 — У2 — Ьг)2 + х1 < (е + аЬ)2.

В переменных (1.3) предыдущая задача об определении первого момента поглощения примет вид

Ь ^ шіп, Ь > 0, /1(Ь) = (а2 — Ь2)Ь2 + 2Ь(ае — Ьу) + е2 — х2 — у2 > 0,

/2(£) = (а — Ь )£ +2£(ае + Ьу) + е — х — у > 0.

Если у > 0, то /1 (^) < /2(£) при всех £ > 0, и если у < 0, то /1 (^) > /2(£) при всех

£ > 0. Поэтому первый момент поглощения является решением задачи

£ ^ шт, £ > 0, /(£) = (а2 — Ь2)£2 + 2£(ае — Ь |у|) + е2 — х2 — у2 > 0.

Первым моментом поглощения будет являться первый положительный корень

квадратного уравнения /(£) = 0. Поскольку рассматривается случай х2 + у2 > е2 22

и а > Ь , то это квадратное уравнение имеет только один положительный корень

Т

а2 — Ь2

Рис. 2

В случае точной поимки (е = 0) эта функция принимает вид (1.6). График этой функции изображен на рис. 2.

Список литературы

1. Айзекс, Р. Дифференциальные игры / Р. Айзекс. — М. : Мир, 1967.

2. Пшеничный, Б. Н. Игра с простым движением и выпуклым терминальным множеством, / Б. Н. Пшеничный // Теория оптимальных решений : тр. семинара. — Вып. 3. — Киев : Ин-т кибернетики, 1969.— С. 3—16.

3. Крэггс, Дж. У. Задачи управления движением. Математическое моделирование /

Дж. У. Крэгсс. — М. : Мир, 1979.— С. 24—36.

4. Колмогоров, А. Н. Элементы теории функций и функционального анализа /

A. Н. Колмогоров, С. В. Фомин.— М. ; Наука, 1972.

5. Пшеничный, Б. Н. Структура дифференциальных игр j Б. Н. Пшеничный jj Докл. АН СССР.— 1969.— Т. 184, № 2.— С. 285—287.

6. Hermes, H. The generalized differential equation X Є R(t, x) j H. Hermes jj Advances in Mathematics.— 1970.— № 4.— P. 149—169.

7. Пшеничный, Б. Н. Выпуклый анализ и экстремальные задачи / Б. Н. Пшеничный. — М. ; Наука, 1980.

8. Ухоботов, В. И. К вопросу об окончании за первый момент поглощения /

B. И. Ухоботов j/ Прикл. математика и механика.— 1984.— Т. 48, № 6.—

C. 892—897.

9. Боненбласт, Х. Ф. Об одной теореме Вилля / Х. Ф. Боненбласт, С. Карлин j/ Бесконечные антагонистические игры ; сборник. — М. ; Физматгиз, 1963.— С. 489—496.

10. Красовский, Н. Н. Об одной задаче преследования j Н. Н. Красовский jj Прикл. математика и механика.— 1963.— Т. 27, № 2.— С.244—254.