Некоторые классы конфликтно управляемых процессов с неопределенностью Грицевский, Андрей Эдуардович

Введение к работе

:'_' Актуальность тема. В настоящее время активно развивается новое направление в озлаоти теории конфликтно управляемых процессов - теория игровых задач с различными неопределенностяїли, имеющими стохаотагавскнй характер, как относительно управляемых объектов , так if относительно управлений этими объектами. Связано это о одной сторона с тем, что у таких, задач имеются ванные практические приложения, например, в задачах поиска движущихся объектов, так и с наличием определенного ігрогресса в создании новых оптимизационных: методов, которые могут быть использованы при решении таких подач.

Рассматриваемые в диссертационной работе ' проблемы исторически восходят к зрдачем теории поиска л к задачам теории Дйр9"рвяциаяышх игр с неполней информацией. В конце 60-z годов появилась первые работы, в которых рассматривались простейшие игровые модели Евдач поискового ткпз. Опубліковані к настоящему вреМэЮ! работы посвящены в основном исследованию конкретных классов игровін задач поиска или ко, как в случае с дкффареіщпальншіпі играми о неполной информацией, .либо конкретным игровн?* постановкам задач, лпбо классам задач, в которых неопределенность играат роль "яумовых" ПО'ЛОХ.

Изучением подобных кснфлиегко управляемых лпроцэссов с' различными гш1Ч»«й неопределенности занимались Н.К.Красовский, А.Н.Колмогоров, А.Б.Курканский, Е.П.Мпслов, Е.Ф.Кгакенко, В. С. Осипов, Л.А.Пвтросян, Л.С.Понтрягин, Б.Н.Пшеничный, І.Г.ЧбНЦОв, Э.ДЛерноусько, А.А.ЧикриЙ.

Среди зарубежных авторов следует ответить в пераукг очередь С.Гола, Дя.ДоббЯ, Б.Купмаяа, М.Дгану, М.Мангола, С.Поллокз, Л.Стоуна, О.Хеллмана.

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

- г -

представляется весьма актуальной.

Основной целью работы является рассмотрение достаточно широкого класса- конфликтно управляемых процессов с неопределенностью, описывающих модельное представления игровых задач типа доиска движущихся объектов. Рассмотрение различных классов допустимых управлений и соответствующих км дар представления управляемы! объект-управление. Рассмотрение для введенных; классов; объектов и управлений минимаксных оптимизационных задач'и свойств их точных и приближенных реиений. Разработка численных методов решетя подобных задач для достаточно іянроких классов управляемых объектов и допустимых управлений и изучение их сходимостоЯ.

Метода исследования, использованные в данной работе, относятся к теории ^; управляемых случайных процессов, теории динамической и стохастической оптимизации,,теории игр.

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

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

численнче метода нахождения приближенных решений соответствуй;',! л оптимизационных задач могут послукить основой для создания практически полезши алгоритмов л программ.

Апробация работа. Результаты диссертационной работа докладывались на научном семинара ИК АН Украина "Управление г. условиях конфликта и 'неопределенности", на республиканском семинаре по проблеме "Кибернетика" "Моделирование и оптимизация конфликтно управлявши процессов в различиях физических средах" п Киевском государственном университете икона Т.Г.Шевченко, нп X Всесоюзном совещании по проблемам управления (Алма-Ата, 193йг.)г на семинаре Института математики и механики Уральского отделении АН СССР (руководитель процесор Чекцов А.Г.), на семинаре Института проблем механики АН СССР (руководитель д.ф.-м.н. Пашков А.Г.).

Публикации. По теме диссертационной работа опубликовано 6 работ .

Структура її объем работы. Диссертация состоит из введения, трех глав v списка литературы. Объем работы Ю5 стр. Список ляторатурц содєрміт 132 наименования.

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

Первая глаза посвящена изучению тттшхокых. задач для стохастических кшДдастпо управляемых щюцїсьз. 3 ней приведен необходимый математический аппарат, доказаны теорему, игрсыциа аішалоїчічную роль теоремам о. существовании реаекий для управляемых систем, получены условия для суииствоваяил оптимальных рошений оптимизационных задач л изучен; классы с-оп'гимальшх решений.

В первом параграфе вводятся определения управляемого объекта и управления для рассматриваемых конфликтно управляемо; процессов. . Пусть (х,ЧГ) к ;т,В) - два полных сепарабелышх метрически;: пространства о соотиізї'ствукщими о-алгебракп. Первое пространство будем рассматривать в качества фазового пространства состояний, а второе - в дачзетвэ фэаоЕого пространства упраЕленун. Вой

'. . с 'гриваемне в дальнейшем процессы буду г определяться над '. ': ;Г.твом X = LO.T] с R¹.

Ьудем обозначать через «^I0'^T1 и ч^!'^Т1 пространства всех Ь'гмтШ, определенных на [0,Т] и прішимаицих значения из я и <и соответственно. Через г!¹⁰'" и К¹⁰'⁷¹ обозначим минимальные а-алгебры, содержащие все цилиндрические множества вида

0_t(A) = | х(-): х(-)е К^10,11. x(t)s A ] , t_eS , АєУ

0_t(B) = 2(-): *()«= K^to-^T1, x(t)_e В | , teS , Be»

соответственно. Будем обозначать через 1 - о-алгебры, содержащие цилиндрические множества с основаниями на [0,t] , а

через чг^с= U <и и аз¹~= U ssrn.

Определение 1.1. Семейство вероятностных мер ц(А/и(- )), Асї^⁰'^ті, u(-) є i/^OT1 будем называть управляелыл объектом, если выполнено следующее условии:

V tfitO.T] и Astf ц(А/и(-)) - S¹""-измеримая функция u(-).

Определение 1.2. Семейство вероятностных кар v(B/x(-)), BgS¹⁰'". х(-) є и^ІО'^т> будем называть упра&лениел, если выполнено еледумце е условие :

V ієГО.Т] и Ее8¹ v(B/x(-)) - 41^і-измеримая функция х(-).

ОиреЗеленш 1.6. Управление о>(-/-) назовем ступенчотьи, если мэра гЧ-/х(')) для всех x(-)e«¹⁰'" сосредоточена на множестве ступенчатых функций.

Пусть {А,@,р} - некоторое вероятностное пространство. Будем говорить, что случайный составной процесс (|(t,u)),r)(t,u)), tetO.T], ьзєП, является представлением управляемого случайного процесса с управляемым объектом ц(-/-) и управлением v{-/-), если выполнены следуодие условия:

для всех Aetf^e,T5H ВеВ¹⁰-'"

р{ ((-,ь)),т)(-_,а)))_еАх{и(-)} / т)(-,ш)=и(-) } =р(А/и(-)),

#4 (С(-.ш)»т](- ,ш))е{х(-))хВ / |(-,ш)=х(- ) }=v(B/x(-)).

Пусть заданы ц(-,-) и v(-,-) - управляемый объект и 'if,-)рлпнцр. В обшем случае, вообще говоря, может но существовать

-. 5 -

такого случайного составного процесса ((t).rj(t)) в « х «' с
заданными объектом управления и управлением, кэ говоря уже о его
единственности. В случае же ступенчатых управлений тексе
представление при достаточно естественных предположениях,
существует, причем оно единственно в смысле стохастически!
эквивалентности. ^l .

В теореме І.І сформулированы условия на рассматриваемы?, объект управления и допустимую ступенчатую функцию управления , которые гарантируют для этого объекта и управления существование представления (|(t),-n(t)).

Рассмотрим теперь управление v(-/-), для которого v(D^IO'^T>)/xM) = І для всох х(-)ек'^0,г\ где D^to/"><) -пространство функций u(t), не имеющих резрывов второго рода, нэпрерывных справа и в точне t=r. Обозначим через р_о метрику в D^,0/r'(4J). Введем в б¹⁰'"^) семейство операторов s_e:

[S_eu](t) = и(\) при V^t<4w (I)

где ч_о<х<.'.. - точки, рекурренгно определяемые соотношением

a = inf [Ът;., p_D(u(t),u(a. ))>є]; если не вир р (и(*),и(т ))<є,

і>г.

то полагаем ^=1, и(Т)=и(т.₊₁). По определению fs_eu](t) верно

неравенство

вир p₀([s_su](t),u(t)) < є.

Будем обазиачать через 'if'^CD) а-алтебру борелевских шюкеств в D''^T1. Отображение [Su](t) измеримо отображает D^CC'^T' в ъ'"^,г'. Обовначим далее через v_e.(B/x(-)) управление, задаваемое равенством

-V(B/x(-)) = vUut-): [S_eu]{. )єВ>/х(-)) - <2)

Эта мера действительно является управлением, так кок для любого цилішдрического множества В с основанием над Ю,і) множество tu(-)s lSgU-](-)eB} є 4f(D), где yt_(D) _ ₀-_алгебра в У"^л\и),

порождаемая цилиндрическими множествами с основшшсм над to,t].

Обозначим через (_e(t),-r)_g(t)) представление управляемого процесса с объектом управления (*(/) и управлением v„{-/-). Приведем условия, когда существует предел птого представления при е-»0 и являющийся представлением объекта управления ц( /) ;: управлением !'(/).

Теорема 1.2. Пусть v - локально компактное пространство и пусть управление v{-/') для управляемого объекта ц(-/-) удовлетворяет следующим условиям:

.!. Для всех x(.)eD⁽'^TJ(«) v(D^to'¹'('u)/x(-))=I;

2. Существуют такие представления ((t),n_c(t)) объекта (і;-/-) с управлением r_e(V-) что_яШ стохастически непрерывна го te[0,T], Ti_g(t) с вероятностью I но имеет разрывов, второго рода я равномерно непрерывны по є.

С. Для представленая объекта ц(-/-) с детерминированным управлением u(- )eD^LO'^TI(w) функция |(t»u(-)) стохастически непрерывна яо совокупности переменных, равномерна по є и разномерно ограничена на tetO.TJ.

4. Функция т]_є\.,х(-)). определяемая соотношением для всех Б.-'.В¹⁰''" И x(.)eD^IO'^TI(«) P(Ti_s(-,x(-))eB} = V_e(B/x'(.)), с вероятностью І не имеет разрывов второго рода и равномерно непрерывна по е.

б. Для произвольного а>0 и u₀(- )еіі^0шТ'ци) существует R>0,

что для всех х(.)еЮ¹⁰'""(И) v(D^to,T,(tu) \ {u(-)sp₀(u(t),u(t))

Тогда существует представление объекта (!(/) о управлением v(-/-) ({(t>,Tj(t)), что (t) стохастически непрерывна по t, а т)(1) с вероятностью I не имеет разрывов второго рода.

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

Пусть (,) и (v,<5) - два полных сепарабелькых метрических пространства с соответствующими о-алгеор&ш. Пусть (<и,й>) и (v,D) - компактные метрические пространства о о-алгебрэми на них. Пусть

F': c^,0'^TJ(«)xD^I0'^r](¹i^;)xC^,0-T,(⁴ir)xD^t0'^T,(v)-» R - такая ограниченная

функция, что функции Г(- , ,у(- ).v(-)) и F(x(- ),u(- ) ,)

непрерывны по совокупности . аргументов х{- )е0^,о/"(к)»

u{-')erI'^T,(v) и у(-)eO^,OT,(w), v(. іетУ⁰'*¹^) соответственно.

Пусть на ларах (*,Н), («J,») и (v,G), (w,>) заданы управляемые объекта -с соответствующими управлениями

у'(/ ),у^є{-/- ) и )/(/ ),-/(/), для которых выполнены условия теоремы 1.2. Следовательно, существуют представления

(Є"¹ (t)_t7}^E{t)) и (^p(t),if (t)). Эти представления порождают пи

пространствах o'⁰'^T1m)xtf^,0,T'(ty) и c^[0'^T,(v)xl>"^vr,(u') регулярные вероятностные меры, которые будем обозначать как ц^Е(-/-)ev^K(./-) и \i^v(-/- )&?(/)) соответственно. Существует единственная регулярная вероятностная мера (і(-> на топологическом произведения пространств с'⁰'"" («)xtf⁰'^T1 (ч )xC^to'^T' (tf)хв'^,т' (v ), являющаяся производонием мер ц^Е(-Л )«v^E(-/-) и u^p('/- )г>^р(-/-)). Й, следовательно, верна следующая теорема.

Теорема 1.3. При , приведенных внке предположениях об управляемых объектах \f(-/-) и ц^р(-А) с соответствующими управлениями V^е(/) и г-^р ( /) и функции F(,,,,) существует

ФУНКЦИЯ S ! rpm(C^,o'^T1(»)xD^lo-^TI(tL'))xrpm(0^co'^T,(^)xD^,o-^T,(^,V)}-* R, где tpm(') - множество вероятностных регулярных мер но соответствующем пространстве, однозначно определяемая, соотношением

s(\f(- /-)<&i?(- /- ),\f {-/ )іґ [/-)) *

= f P(x(.),u(-),y(-),v(.)) ii(d(U(-),u(-),y(-),v(-)), -(3)

гдец(.) = ((.i^E(-/Oev^E(./-) x \x^r{/УвУ*(/)).

Пусть вшіолкеші предположения теоремы 1.3. Тогда МОЖНО сформулировать следующую игровую постановку основной проблеш.

По заданным объектам управления |і^Е ( / ) и ц' ( / ) и
функционалу платы S игрокам Р и F, нужно найти такие управления
v^E(-/- )є31 и 1^(-/- )eW из классов допустимых управлений К 'и ж,
подмножеств классов управлений с вероятностью I, не содержащих
разрывов второго рода, чтобы игроку Р минимизировать, а игроку Е
максимизировать значение " функции

3(Ц.*(-Л )8^(./- ),(!'(./ )41^ (/ )).

Интересующие нас проблеми могут быть формально записаны как: максимизировать га v^c(-/- )_GJl функцию e_ve H(^e(- ),т|^е(- )), где

H(x(-),u(0)= inf (е^ р(^ж(-),1^=(. ),?'( ),V<-)) J« (4) v'e!R

мшшмизировать по t'^p(V- )еЗГ функция) e_7J? Q(^p(- ),if(- )), где

Qiy(;).v(-))= вир [ E^ {f (O.if (-),f(0,tf(0) ] (Б) " V^E'Jt

Теореыа 1.4. Пусть выполнены предположения теоремы 1.3. Пусть также множества Ш и 31 таковы, что для всех

r(-;_eD^to-^T,(») _Hy(-)_ei)^[0'^T1(v)

I V^е (xf'^T,(0)/x(- ))=1,

v" (D^I0'^T,(W₀)/y(. ))=1.

гдє 4'₀«j.k w_ocv компактные мнокедтва, тогда, существуют такие регулярные вероятностные меры гТ'еЯІ и ї^єЗЇ, что

8(|1^с(_г/-)г^(-л ).!/(/ )^(-/-)) < < 8(м."(-/0*^(-/О.М-*(-/Ові?(-/0) < < 8(^(-/-)^(-7-),^(-/0^(-/0) для всех ТҐєїїі. и Л=51 и

inf E^fsup [ е^ Р(^к(-),^(-),f (0,Tf(0) )) =
v'eBl V^E_eSi __ ' ..

= вир Е_уЕ[ inf (e_vf Р("(-).тґ^:(О.Є^,(-),тГ(.))']) =

= е-Ё E-r ї(Є"(0,т)"(О.Є^р(0.тґ(0,). (6)

В третьем параграфе доказанн теоремы 1.4 и І.Бо существовании решений - минимаксной задачи (6) для параметризованного класса допустимых управлений и для класса управлений с простыми ограничениями.

Во второй главе излагается численный метод решения минимаксной задачи (6) в том случае, когда класс допустимых управлений одного из игроков является параметризуемым.

В первом параграфе дана формальная постановка рассматриваемой задачи. '

Рассмотрим следующую минимаксную задачу: найти Еектор х, на котором достигается минимум функции

_ 9 -

T(x) = max Г v(x,y)OH(y) . (7}

при условии

хєХсЕ", . (8>

где yeY_cE^m,a к - множество таких фунсціїй распределения н, которое удовлетворяют сотношениям

Q^k(H) = K_yq^k(y) = J q^k(y)dH(y) < 0, к=Т7Г> (9)

J dH(y) = I, (10!

' Y q^k(y), k=T7I, - заданные функции.

Возможные метода минимизации т(х) зависят от процедуры нахоадения решения "внутренней" моксимизационной задачи: найти такую функция распределения н, которая максимизирует

Q(H) = Е_>л(у) = j" q(y)dH(y) * (II) У

при ограничениях

Q^k(H) = E_yq^k(y) = J q^k(y)dH(y) S 0. k=TTT. (121

J cffi(y) = I, "(13)

где q*. k=U7T, - заданные функции ге^е*.

Репеїше задачи (II)-(ІЗ) wokho свести к решению' следующей задачи линейного программирования :

найти точки у¹ є Y, j = ITEt t < 1+1 и действительные числа v,t і = Г7і такие, что

і
J q (У* ) = max (14)

при условии

2 qV)^ < о, i-ІТз; (lb)

I p. = I, p. > o. j=TTt. (16)-

і **

Лалеє в этой параграфе оішсана основная идея численного

алгоритма решения задачи (П.)-(13).

Б параграфе два рассмотрена двойственная к задаче

min, mas [ q(y) --J iiq^k(y) 1, (17)

D' = u : u = (u₄,u_,. . .1^), u>0, i=l,m !.

Доказана следующая теорема 2.1. '-'. Теореиа 2.1. Пусть

1. Y компакт- и q^v(y), v = ОТІ, непрерывны.

2. int со z /О-Тигда

1. Решение обеих задач (II)-(13) и (17) существует и
оптимальные значения для обеих функций совпадают.

2. Для любого решения и* задачи (II )-(13) существует uW,

'Г.'ІКСЙ, что .

йога н" Y(u").

Дулее б параграфа рассмотрена задача

Kaxg(H)i (18)

g^l(H) < 0, i-lTmj (19)

J i5H(y) = I. (20)

' ^Y гцо g'(H), i=J7m, - задажше нелинейные функции, зависящие от

Функций р.?,спрэделения н, определенной на множестве У. В Теореме

2.Р. указаны условия на функцій, g, что существует реиение задачі;

ilO)-(SO), и конаю указать двойственную задачу, вид которой

эквивалентен (17).

Теорема 2.3. (Условия оптимальности). Пусть вшгалнены предположения теоремы 2.Ї и пусть р - решение задачи (14)-(16} при фиксированных у = (y*.y^z,... ,у"), УбЕ¹*"¹". Тогда у,р будут решением задачи (II)-(13), если для заданного у существует решение (u,u,...,u) задали (17), такое, что і q(y) - У ) - \,_t < О для всех у_еу. (21)

к = 4

Теорема 2.4 дополняет георему 2.1 и позволяет свести рЗІІГСІГИГС задачи (II)-(13) к решению двойственной задачи (17).

В третьей параграфе дан численный алгоритм решения задачи (ІІ)-(ІЗ) и доказана теорема 2.Б о его сходимости. Рассштрш функцию

ф³(и) = шах Г q(y^s-^j) - У ^^ ]

Где {у*^л,у'*^г,. ..,у^вЛп} - приближенное решение по у па в-той итерации, а р^э определяется через решение и* '=* (и,и, ...u"_{) двойственной задачи (17).}

Teopelia З.б. Пусть наполнены условия теореми 2.1 и верни следующие дополнительные условия:

1. Существует иеубцзакщая функция x(t), tetO.m), t(Q)=Q,
t(t)>0 для t>0, что

7₃ 1 -х(ф(и" )-фЪ/>).

2. є > О, є -»0 для в -» оо.

Тогда каждая сходящаяся подпоследовательность последовательности {у^в'¹.у^в'²Г...,У^а'^и,}.Р* сходится к решению задачи (ІІ)--(ІЗ).

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

о) I 6_а > 0, _в -> О ДЛЯ о оо, J ^о ~ ^¹ Кг*-⁰"

2.г. /и О.

.1 Tory;a J pq(y^E'¹) = и стремится к решению (II )-(13).

В третьей плаве рассматривается модификация задачи (II)-(13) для случая, когда "внешняя" задача имеет вид: найти такой вектор параметров управления х, zeS"-, который максимизирует

С!(к) = E^q(y) = | q'U.jrJ^Jy) (22)

У при ограничении

х є S,

где ц_х - семойстБО мер, соответствующих некоторому множеству марковских однородных процессов с функциями переходов Р .

В первом параграфе даны математическая постановка рассматриваемой задачи и принятые ограничения. Основная олокшеть h использовании идеи алгоритма из второй глави заключается в нахождении стохастического субградаента функции q(k). Предлагается следующая его оценка:

G*' (Щ-О^-* (U) v - *^{4с х}~^с

где о~'₌(и),а^*_с(а) - функции от случайной величины и, равномерно распределенной нэ [0,1.]*-и имеющие функции распределения М- и о, соответственно.

"х-с

Во втором параграфе предложены численный мотод решения задачи (ІІ)-(ІЗ) к теорема о сходимости метода.

В третьем параграфа приведены доказательства теірамм 3.1, 3.2 и'вспомогательной теоремы 3.3.