Петросян Л.А. и др. Теория игр

Подождите немного. Документ загружается.

ния захвата, и область С={х, у: V(х, у, Г)=/} — зону нейтраль-

ного исхода.

Пусть х, уеА. По определению А при любом е>0 игрок Р об-

ладает такой стратегией и\ (•), что

K(x,y;u;0,v())<V(x,y,T)+

при всех стратегиях v (•) игрока Е. Выбрав подходящим образом

б>0,

можно обеспечить выполнение неравенства

К (х, у; и,' (•), v (•))< V (х, у, Г)+е</.

Последнее означает, что стратегия и] игрока Р гарантирует ему

/-встречу с игроком Е из начальных состояний х, у за время Т.

В результате получаем следующее уточнение теоремы п. 4.5.

Теорема. Для любого

фиксированного

Т>0 все

пространство

делится на три

неперескающиеся

области А, В, С,

обладающие

следующими

свойствами:

1) при любых х, уеА игрок Р

обладает стратегией

и', (•), кото-

рая

гарантирует

l-встречу

игроком

на отрезке

[О,

Т]

независимо

от

действий

последнего;

2) для х, уеВ игрок Е обладает

стратегией

v\ (•), которая

гарантирует избежание

l-встречи

с игроком Р на отрезке [О, 7]

независимо

от

действий

последнего;

3) если х, уеС и е>0, то игрок Р

обладает стратегией

и', (•),

гарантирующей (1+е)-встречу

игроком

за время

независимо

от

действий

последнего.

§ 5. НЕОБХОДИМЫЕ И ДОСТАТОЧНЫЕ УСЛОВИЯ

СУЩЕСТВОВАНИЯ ОПТИМАЛЬНОЙ ПРОГРАММНОЙ

СТРАТЕГИИ УБЕГАЮЩЕГО

5.1.

Важным подклассом игр преследования являются игры,

в которых оптимальная стратегия убегающего игрока является

только функцией времени (так называемый регулярный случай).

Ограничимся рассмотрением игры преследования с предписан-

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

сены и на игры преследования по быстродействию. Пусть

(х)

(СЕ(УУ)

— множество достижимости игрока Р

(Е)

из начального

состояния х (у) к моменту времени Г, т. е. множество тех позиций,

в которые может попасть игрок Р

(Е)

из начального состояния х (у)

в момент Т, используя всевозможные измеримые программные

управления и (/), (v (/)), /е[0, 7] при условии, что движение проис-

ходит в соответствии с системой x=f(x, и) (y=g (у, v)). Введем

в рассмотрение величину

Рт(хо,

Уо)=

max min p (x, у), (5.1)

260

называемую иногда (см. [7, 39, 40]) гипотетическим рассогласовани-

ем множеств С\

(у

)

и С£

(х

)

(см. пример 8 п. 2.6 гл. II).

Функция р

(х

) обладает следующими свойствами:

1°.

Рт

(х

Уо)>0,

(х

)\тшо

(хо,

УоУ,

2°.

(х

, уо)=0, если С? (*о)

С|

(у

);

3°.

Если V

(х

, Т) — значение игры Г (х

Уо,

Т) с предписан-

ной продолжительностью и терминальным выигрышем р (х (Т),

у (Г)), то

У(х

,Уо, Т)^рт(х

,Уо).

Действительно, свойство 1° следует из неотрицательности функ-

ции р (х, у). Пусть Ср

(хо)

зС?

(уо).

Тогда для любого у'е С\

(у

)

существует такое jc'eCj

(х

что р (х',

у')=0,

{х'=у

), откуда полу-

чаем

2°.

Свойство 3° следует из того, что игрок Е, выбирая направ-

ление движения на точку МеС|

(у

ДОЯ

которой

Рт

(хо,

Уо)=

min р (х, М),

хеСЦхо)

всегда гарантирует получение выигрыша

рт

(х

уо).

Точка М назы-

вается

центром

преследования.

5.2. Пусть Г

(х

уо,

Т) — дискретная игра преследования с ша-

гом 8

(S =

k+l

—

предписанной продолжительностью Г, дискри-

минацией игрока Е

начальными состояниями х

, у

. Тогда справе-

длива следующая теорема.

Теорема. Для того чтобы для любых х

Уо^И"

и Т=дк,

к=

2, ...,

выполнялось равенство

РТ

(ХО,

УО)=УЯ\

Г, (Х

, У

О,

Т), (5.2)

необходимо

достаточно,

чтобы для всех

, y

elC, 5>0 и Т=5к,

к=

2, ...,

имело место соотношение

Рт(х

,Уо)= max min p

-s (x, у) (5.3)

(Val T

(хо,

Уо,

Т)

—

значение игры

(х

, Т)).

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

261

Лемма. Для любых х

y<>eR

, Т^Ь

выполняется неравенство

Рт(х

Уо)< max min

-s(x,

у).

yeC^tm) xeC'

)

Доказательство. По определению функции р

имеем

max min p

(х, y) =

уеС'^о) дгбС«(д:о)

= max min max min p (x, y).

уеС'

(у

) хеС

(х

) увС^Чу) ieCj<

(дс)

Для всех хе С?

(х

)

имеет место включение Cp~

(х)

Ср

Сле-

довательно, для любых хеСр (х

уеС~Е~

(у)

min p(x,y)^ min p (х, у).

«CJ-'M

ieC

(xo)

Тогда для всех

хеС

(х

yeC

)

max min р (х, у)^ max min р (x, у)

уеС

-Чу) «с;-'**) уеС

-'(у) хеСЦхо)

min max min р(х,у)^ max min p(x,y).

xeC^xo) yeC

-'(y) хпС^Чх) уеС^Чу) xeC^xo)

Таким образом,

max min р

-ь (x, y)^ max max min p (x, y)=

yeC^o) xeC^(xo) yeC^lyo) yeC^fy) хеСЦхо)

= max min p (x,

);

>eCjOo) xeC

(xo)

— лемма доказана.

Перейдем к доказательству теоремы.

Необходимость. Пусть выполняется условие (5.2) и не выпол-

няется условие (5.3). Тогда согласно лемме существуют такие <5>0,

хо,

у о е

R",

ТО

8к

^1, что

ho (*o,

Уо)<

max min pVo-a (л:, у). (5.4)

yeC'^fyo) хеС'^хо)

262

Пусть u° (•) — оптимальная стратегия игрока Р в игре Г

(х

, у

) и на 1-м шаге игры игрок Е выбирает точку

j*eCi(y

Для

которой

min р

о-г (х, у*)= max min

Го

(х, у). (5.5)

Пусть х°

(8)

— состояние, в которое переходит Р на 1-м шаге

при использовании стратегии м° (•), а й° (•) — оптимальная страте-

гия Е в игре Г« (х° (8), у*, Т

—8). Рассмотрим следующую страте-

гию v (•) игрока £ в игре r

(х

, у

в момент /=0 он выбирает

точку у*, а начиная с момента t=8, игрок Е использует стратегию

° <•>•

Обозначим через й° (•) сужение стратегии и° (•) на отрезке

[8,

Из (5.2), (5.4), (5.5) (согласно формуле (5.2) р

(х

, у

) — значение

игры Т

{

(хо,

уо,

Т) находим

Рт

(х

, у

)Ж (и

(), v (•);

XQ,

уо,

=К(й°(.),;°(.);х° (8), У, Т

-д)

=Рто-Лх°(Ь),У*)> min

(x,y*)

xeC'

(xo)

= max min

-S(X,

y)>p

, y

уеС'

(уо) xeC^lxo)

Полученное противоречие доказывает необходимость условия (5.3).

Достаточность. Заметим, что условие (5.3) совместно с усло-

вием

(хо,

.Ио)|г-о=Р

(хо,

уо) показывает, что функция

(х

)

удовлетворяет функциональному уравнению для функции значения

игры F

(хо,

уо,

Т). Как следует

из

доказательства теоремы

п.

2.2, это

условие является достаточным для того, чтобы рт(х

Уо)

было

значением игры Г

(х

, у

, Т).

5.3.

Лемма. Для того

чтобы

в игре Г (х

, уо, Т)

существовала

оптимальная

программная

стратегия

игрока Е (т. е. стратегия,

являющаяся

функцией

только

времени),

необходимо

достаточно,

чтобы

Val Г (ль,

Уо,

Т) =

(хо,

уо).

(5.6)

Доказательство. Достаточность. Пусть v* (0, te[0, T] —

допустимое управление игрока Е, переводящее точку у

в некоторую

263

точку М такую, что

Рт

(хо,

)

= min р (х, М).

хеС

(х

)

Обозначим v* () = {ff, v* (/)}, где разбиение а отрезка [0, 7] состоит

из двух точек

=0,

Очевидно, v* (-)еЕ. Согласно теореме п.

3.4 гл. I v* ()еЕ — оптимальная стратегия игрока Е в игре

Г (х„,

Уо,

Т), если

Val Г (х

, у

, Т)=М К

(и

(), ** (•); х

, у

, Т).

«()6Р

Но это равенство следует из (5.6), поскольку

inf К (« (•), v* (); х

, у

о,

Т)=р

(хо,

и()бР

Необходимость. Пусть в игре Г (х

, у

, Т) существует оп-

тимальная программная стратегия игрока Е, тогда

Val Г (хо, у

, Т)= sup inf К

(и

(•), v (•); х

, у

, Т)=

»()6Б и()еР

= max inf р (х (Г), у)=р

(х

Лемма доказана.

Теорема. Для того чтобы при любых х

Уо^Л?,

Т>0 в игре

Г (х

Уа,

Т) игрок Е имел

оптимальную программную

стратегию,

необходимо

достаточно,

чтобы

для любых <5>0, х

Уо^Я",

Т^Ь

выполнялось равенство

Рт(хо,Уо)=

max min р

-г (*. у). (5.7)

уеС'^о) *еС'

(х

)

Доказательство. Достаточность. Из условия (5.7) соглас-

но теореме п. 5.2 следует соотношение (5.2), из которого предель-

ным переходом (см. теорему п. 3.7) получим

Рт

(х

)

= Val Г (х

уо,

Т).

Отсюда согласно лемме п. 5.3 следует существование оптимальной

программной стратегии игрока Е.

264

Необходимость условия (5.7) следует из теоремы п. 5.2, по-

скольку существование оптимальной программной стратегии игро-

ка Е в игре Г (х

у«,

Т) влечет существование таковой во всех играх

Га (х

, у

, Т), Т=8к, к^

и справедливость соотношения (5.3).

§ 6. ОСНОВНОЕ УРАВНЕНИЕ

В данном параграфе будет показано, что при определенных

условиях функция значения дифференциальной игры удовлетворяет

уравнению в частных производных, которое называется основным.

Впервые в монографической литературе оно было рассмотрено

Р.

Айзексом [1] и его часто называют уравнением Айзекса—Бел-

лмана.

6.1.

Используя теорему

п.5.3,

выведем уравнение в частных про-

изводных для функции значения дифференциальной игры. Будем

предполагать, что для игры Г (х, у, Т) выполнены условия теоремы

п. 5.3. Тогда функция рт(х, у) представляет собой значение игры

Г (х, у, Т) продолжительностью Т из начальных состояний х, у.

Пусть в некоторой области ft пространства

Л"

[О,

оо)

функция рт(х, у) имеет непрерывные частные производные по

всем переменным. Покажем, что в этом случае функция р

(х,

у) в области ft удовлетворяет дифференциально-экстремальному

уравнению

—

-max £

—

gi (у, «)-mm £ —// (х, «)=0, (6.1)

01 veV (_] oyt

u ,_! OX,-

где функции ft (х,

и),

(у, v), i=

..., п, определяют закон движения

игроков в игре Г (см. (3.1), (3.2)).

Предположим, что (6.1) не выполняется в некоторой точке

(х, у, Г) eft. Пусть, для определенности,

Р V

'Р / ч V

'Р г

\ п

—

-max £

—

(У,

»)-max £

—

ft (х, и)<0.

ОТ „

у ,_,

ОУх

ueV

iml

OXi

Пусть veV таково, что в рассматриваемой точке (х, у, Г)eft

выполнено соотношение

'Р ( ~\ V

'Р < \

h — gi(y. «)=max 2^

—

(У,

v).

Тогда при любом и е

U в

точке (х, у,

Т) е

ft имеет место неравенство:

265

£-t£ft(y.3-l£yi(*..i)<0. (6.2)

ST ~ dy

~ Эх,'

Из непрерывной дифференцируемости функции р по всем перемен-

ным следует, что неравенство (6.2) вьшолняется и в некоторой

окрестности S точки (х, у, Т). Выберем число 8>0 настолько

малым, чтобы точка (х (т), у (т),

T—x)eS

при всех те[0,

8].

Здесь

х (т) = х+j Д* (0, и (0) А,

(t)=y+\g(y (0, * (0) А

о о

— траектории систем (3.1J, (3.2), отвечающие некоторому допусти-

мому управлению и (/) и v (t) = v соответственно и начальным усло-

виям х (0) = х, у (0)=у. Определим функцию

8Т

\(х (т),

(т),

Г-т) ._, 8y

|(х

(т),

Т-х)

-£?,

у;(х(т),«(т)),т€[о,г].

Функция

(т) непрерывна по г, поэтому найдется число с<0 такое,

что (7 (т)<с при те[0, 3]. Отсюда имеем

{

G (т)

е?г<с<5.

(6.3)

Нетрудно убедиться в том, что

Afo^jW.

T-x)

Из (6.3) получаем

Рг (*. У)~РТ-Й (х

(8),

у (8))^с8.

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

Рт

(х, у)< max min р

-з (х', у

у'бС'

(у)

х'еС^х)

что противоречит (5.7).

Таким образом, мы показали, что в том случае, когда у игрока

Е в игре Г (х, у, Т) при любых х, у

е R",

Т>

существует оптималь-

ная программная стратегия, значение игры V (х, у, Т) (оно совпада-

266

ет с р

(х, у) согласно лемме п. 5.3) в области пространства

Я"

[0,

оо), где существуют непрерывные частные производные

у этой функции, удовлетворяет уравнению

dV " dV " dV

—=max £ —

(У.

«)+min £ — ft

(

") (6-4)

при начальном условии V (x, у, Т)\

Тш0

=р (х, у). Предположим, что

каким-то образом удается определить й,

доставляющие max

min

8V 3V

в (6.4) как функции от х, у и —, —, т. е.

дх

ду

Подставляя выражения (6.5) в (6.4), получаем

при условии

V(x,y,T)\

=p(x,y).

Таким образом, для определения V (х, у, Т) имеем задачу Коши

для уравнения в частных производных первого порядка (6.6) при

начальном условии (6.7).

Замечание. При выводе функциональных уравнений (6.4), (6.6)

и доказательстве теоремы п. 5.3 мы не использовали конкретный

вид функции выигрыша, поэтому теорема остается справедливой

для любого непрерывного терминального выигрыша Я (х (Г),

у (Г)). Однако в этом случае вместо величины р

(х, у) необходимо

рассмотреть величину

(х, у)= max min H(x',y

Уравнение (6,4) также справедливо для значения дифференциаль-

ной игры с предписанной продолжительностью и любым терми-

нальным выигрышем, т. е. если в дифференциальной игре с пред-

писанной продолжительностью Г (х, у, Т) и терминальным выиг-

рышем Я (х (Г), у (Г)) у игрока Е существует оптимальная про-

граммная стратегия, то значение игры V (х, у, Т) в области про-

странства Я

хД

х[0, оо), где существуют непрерывные частные

производные, удовлетворяет уравнению (6.4) при начальном усло-

267

(6.5)

(6.6)

(6.7)

вии V (х,

у,

Г)|у=о=Я (х, у) или уравнению (6.6)

тем же началь-

ным условием.

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

выигрыша равна времени до момента встречи. Предположим, для

определенности, что терминальное многообразие ^является сферой

р (х, у)=1, />0. Будем предполагать, что множества С£ (х) и

С'

(у)

непрерывны по

в нуле равномерно относительно

у.

Пусть имеет смысл величина

в (х, у, /)=max min

t'„

(х, у; и (/), v (/)),

• м

«ю

где t

'„

(х,

у;

и (t), v (/)) — время сближения

на /

— расстояние иг-

роков

Рта.

Е, движущихся из начальных точек х,

при использова-

нии измеримых программных управлений и (t) и v (t) соответствен-

но.

Предположим также, что функция

(х,

у, /)

непрерывна

по

совокупности аргументов.

Игру на быстродействие будем обозначать через

(х

, у

). Так

же как это было сделано

в § 4, 5,

можно вывести необходимые

и достаточные условия существования оптимальной программной

стратегии игрока Е в игре преследования на быстродействие. Спра-

ведлива следующая теорема.

Теорема. Для того

чтобы игрок

при

любых х

eR"

игре

(XQ,

уо) имел

оптимальную программную

стратегию,

необходимо

достаточно,

чтобы при любом

S>0 и

любых

Xu,y

etC

выполнялось

равенство

(хо,

Уо,

l)=5+

max min в

(х', у', I).

Для игры преследования

по

быстродействию уравнение (6.4)

принимает вид

" дв

при начальном условии

0(x,y,t)W

-,=0.

(6.9)

Здесь предполагается существование непрерывных частных произ-

водных первого порядка функции в (х,

у,

I) по

х, у.

Полагая, что

каким-то образом можно определить и, v, доставляющие max и min

„ „

дв дв - - ( 8в\ -

(6.8) как

функции

от х, у, —, —, т. е.

и=и\х,

—

дх

ду \ дх)

268

4-Э

перепишем уравнение (6.8) в виде

при условии

0(Х,У,1)\Р(*.У)-1=0- (6.11)

Вывод уравнения (6.8) аналогичен выводу уравнения (6.4) для

игры преследования с предписанной продолжительностью.

Обе задачи Коши (6.4), (6.7) и (6.8), (6.9) являются нелинейными

относительно частных производных, поэтому при их решении воз-

никают значительные трудности.

6.3.

Перейдем теперь к выводу уравнений характеристик для (6.4). Предполо-

жим,

что функция V (х, у; Т) имеет непрерывные вторые смешанные производные на

. ./ dV\ . /

пространстве, функции g, (у, в), /

(

(х, и) и функции и=и\х, —I, v=v\y,

имеют непрерывные первые производные по всем переменным, а множества U,

V имеют вид параллелепипедов a

, m=\, ..., к и

<<7f,

q=\, ..., /, где

и=(щ,

...,

)eU,

»=(»i,...,

vj)eV.

Обозначим

dV " dV

(x.

у,

т)-—- Z—Л

С*.

«)- Z г- ft

СУ.

")•

Функция В (х, у, Г)=0, поэтому беря частные производные по xj х

получим

ВВ 8*V " 8*V *SV df,

-Irr/rl

всем

дх

дТдх

к iml

dx,dx

k (

{

дх,дх

,_, 8ytdx

-Z п

*'- Z

— I Z

-rfA-—

m-\

dUl

» \-l

> '

' д ( • 8V \ X

-Z-[Т-гЧТГ'

(612)

Для каждой фиксированной точки (х,_у, T)eR хЛ

[0,

оо) максимизирующее

значение v и минимизирующее значение й в (6.4) лежат либо внутри, либо на границе

интервала ограничений. Если это внутренняя точка, то

д ( " 3V \ д ( » dV \

г- Z-/< .-о. - 1тб --

Если же й (v) лежит на границе, то здесь могут представиться два случая. Исследуем

269