" 0 C F G H K L N P S T W Z А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Э Ю Я

ДИФФЕРЕНЦИАЛЬНЫЕ ИГРЫ

Значение ДИФФЕРЕНЦИАЛЬНЫЕ ИГРЫ в математической энциклопедии:

- раздел математич. теории управления (см. Автоматического управления теория), в к-ром изучается управление в конфликтных ситуациях. Теория Д. и. примыкает также к общей игр теории. Первые работы по теории Д. и. появились в сер. 50-х гг. 20 в.

Постановка задач теории дифференциальных игр. Различают Д. и. двух игроков и нескольких игроков. Основные результаты получены для задач с двумя игроками. Содержательное описание этих задач укладывается в следующую схему. Имеется динамическая система, в к-рой часть управляющих воздействий подчинена игроку I, а другая часть - игроку II. При постановке задачи, стоящей перед игроком I или II, предполагается, что выбор управлений этого игрока, гарантирующий ему достижение определенной цели при любом неизвестном заранее управлении противника, может опираться лишь на нек-рую информацию о текущих состояниях системы. В теории Д. и. рассматриваются также задачи управления в условиях неопределенности, когда помехи, действующие на систему, трактуются как управления противника. Напр., постановка задачи игрока I описывается следующим образом. Обычно предполагается, что движение управляемой системы задается дифференциальным уравнением

где х- фазовый вектор системы, ии v- управляющие векторы игроков I и II соответственно. Определен класс стратегий игрока I, и для каждой стратегии определен пучок движений X(U), к-рый порожден этой стратегией в паре со всевозможными управлениями противника и выходит из начального состояния системы (1). Эти понятия выбираются так, чтобы они соответствовали заданным ограничениям на управления игроков и характеру информации о текущих состояниях системы, предоставленной игроку I. На движениях x(t), t>t₀, системы (1) задан функционал (плата игры), значение к-рого игрок I стремится минимизировать (иногда функционал g зависит также от реализаций u(t), v(t), t>t₀, управлений игроков). Учитывая самую неблагоприятную реализацию движения выбор к-рой в этой задаче предоставляется противнику, качество стратегий оценивается величиной

Задача игрока I состоит в определении стратегии на к-рой достигается минимум функционала х ₁ (эта задача наз. задачей степени). Иногда рассматривается так наз. задача качества, в к-рой требуется определить условия существования стратегии удовлетворяющей неравенству где с- нек-рое заданное число.

Аналогичным образом формулируются задачи игрока II, к-рый максимизирует плату игры. Стратегии игрока II оцениваются величиной

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

Если в задачах игроков I и II классы стратегий и таковы, что для всякой пары можно определить хотя бы одно движение порожденное этой парой, то говорят, что эти две задачи составляют дифференциальную игру, определенную на классе стратегий Если в Д. и. выполняется равенство

то величина с ₀ наз. ценой дифференциальной игры.

Типичным примером Д. и. является игра преследования - уклонения. В этой игре х= ( х ₁, . . ., x_k+l) =(y₁, ..., у _k,z₁, . . ., z_l), где уи z - фазовые векторы преследователя и преследуемого соответственно, движение к-рых описывается уравнениями

Наиболее часто рассматривается случай, когда выбор управлений стеснен ограничениями вида

(2)

где Р и Q- некоторые компакты. Платой в этой игре является время до встречи, т. е.

где {у} _т и {z} _т - векторы, составленные из первых ткомпонент векторов y и z. Таким образом, сближение точек {y(t)}_m и {z(t)}_m нa заданное расстояние е трактуется как встреча объектов. В случае, когда игроки располагают информацией о текущей позиции игры (t, x(t)), т. е. в позиционной игре преследования-уклонения, существует цена игры.

Формализации дифференциальных игр. Для математич. формализации Д. и. необходимы строгие определения перечисленных выше понятий. Основное внимание в теории Д. и. было уделено задачам, в к-рых игрокам известна позиция игры, а управления удовлетворяют ограничениям (2). В этом случае естественно было определить стратегии игроков как функции u=u(t, x), v=v(t, х )со значениями в компактах Ри Qсоответственно. Оказалось, однако, что при таком подходе нередки случаи, когда приходится рассматривать разрывные стратегии, а порожденные ими движения нельзя определить известными в теории дифференциальных уравнений понятиями. Трудности, возникшие сначала на этом пути, привели к созданию иных постановок Д. и. Ниже рассмотрены такие формализации, где не используются позиционные стратегии. Затем дана формализация позиционных Д. и., к-рая охватывает разрывные позиционные стратегии и базируется на специальном определении движений.

Среди сложившихся направлений в теории Д. и. прежде всего следует отметить цикл исследований (см., напр., [2] - [4]), восходящих к работе У. Флеминга [1]. Здесь рассматривается аппроксимация Д. и. многошаговыми играми, где игроки последовательно (по шагам) выбирают свои управления на заданных промежутках времени [t_i, t_i+1), i=0, 1, . .., N. Причем обычно выделяется игрок, выбирающий каждый раз свое управление первым и сообщающий этот выбор противнику. В зависимости от того, минимизирует или максимизирует этот игрок плату игры, различают мажорантную и минорантную многошаговые игры. Применение этого подхода сводится к доказательству теорем существования цены Д. и., определенной здесь как общее значение, к к-рому сходятся цены мажорантной и минорантной игр при измельчении разбиений [t_i, t_i+1), i=0, 1, .. ., N (увеличении числа шагов). Однако построение позиционных стратегии, не зависящих от дискретизации времени, при таком подходе, как правило, не рассматривается.

Л. С. Понтрягин предложил постановку игровых задач управления (см., напр., [5] - [8]), где допускается информационная дискриминация противника, т. <е. при постановке задачи игрока I (или II) предполагается, что кроме реализовавшейся позиции игры (t, x(t))этому игроку известно управление противника v(x)(соответственно и(t)), к-рое будет выбрано на промежутке [t, t+d].(d>0 - малое число). При таком подходе достигается удобное описание игрового процесса, что позволяет построить строгую математич. теорию для широкого круга задач конфликтного управления. Однако введение информационной дискриминации дает одному из игроков I информационное превосходство над противником и вместе с тем накладывает ограничения на поведение противника, в частности не позволяет ему формировать управление по принципу обратной связи (соответственно u[t]=u(t, x(t))). При переходе к содержательной трактовке результатов, полученных в условиях дискриминации противника, вместо информации об управлении противника, к-рое будет выбрано им на промежутке [t, t+d), можно использовать информацию об управлении, реализованном на промежутке [t-d, t). Такую замену нетрудно обосновать для систем, где

Содержательное использование глубоких теоретич. результатов, полученных в условиях дискриминации противника, достигается при рассмотрении позиционных Д. и. (см. ниже описание процедуры управления с поводырем).

Формализация позиционных Д. и. разработана Н. Н. Красовским и его сотрудниками (см., напр., [9]). Здесь рассматриваются позиционные стратегии U и V- функции u=u(t, x )и v=v(t, x), значения к-рых содержатся в компактах Ри Qсоответственно. Относительно этих функций не предполагается к.-л. условий непрерывности. Движения x(t, t₀, х ₀, U)( x(t₀) = x₀), порожденные стратегией игрока I, определяются как равномерные на любом отрезке [t₀,T]пределы последовательностей аппроксимационных движений х _k(t), k=1, 2, ..., абсолютно непрерывных функций, удовлетворяющих уравнению

где - произвольные измеримые функции,

причем

Аналогичным образом вводятся движения x(t, t₀, x₀, V), x(t₀)=x₀. При таком определении стратегий и движений справедливо следующее положение.

Альтернатива 1. Пусть для любых векторов и справедливо равенство

где s'f- скалярное произведение векторов s и f. Тогда, каковы бы ни были замкнутые множества и начальная позиция (t₀, x₀ )и момент всегда либо существует стратегия U_* такая, что для любого движения x(t)=x(t, t₀, х ₀, U_* )точка (t, x(t))попадет на М _с к моменту t=O, оставаясь в N _с вплоть до ее встречи с М _с;либо существует стратегия V*, к-рая для любого движения х(t) = x(t, t₀, x₀, V_*). гарантирует или уклонение точки (t, x(t))от попадания на М _с при или нарушение фазового ограничения раньше, чем точка (t, x(t))попадет на М _с.

К решению такой игры сближения-уклонения сводится исследование многих типов Д. и., для к-рых из альтернативы 1 следует существование цены игры. При постановке позиционных Д. и. возможны и другие определения стратегий и движений. Напр., при рассмотрении разрывных стратегий иногда удобно либо заменять разрывную правую часть дифференциального уравнения неоднозначной и использовать аппарат теории дифференциальных уравнений в контингенциях, либо аппроксимировать разрывные стратегии непрерывными (см., напр., [10]). Однако такие подходы могут оказаться неудачными. Известны примеры, в к-рых оптимальное решение Д. и., полученное в рамках описанной здесь формализации, не удается достичь и даже аппроксимировать в рамках других формализации, опирающихся на уравнения в контингенциях или непрерывные стратегии.

Если условие (4) нарушается, то различают постановку Д. и. в классе стратегий одного и контрстратегий другого игроков, к-рой отвечает детерминированное решение Д. и., и постановку Д. и. в классе смешанных стратегий обоих игроков, содержание к-рой раскрывается при аппроксимации смешанных стратегий соответствующими стохастическими процедурами управления. Контрстратегии U_v, V_u отождествляются с функциями борелевскими по переменным v, и соответственно. Движения x(t, t₀, x₀, U_v),x(t₀)=x₀, определяются как пределы аппроксимационных движений x_k(t).(3), где

Аналогично определяются движения x(t, t₀, х ₀, V_u). Смешанные стратегии отождествляются с функциями m=m(t, x), v=v(t, x), значениями к-рых являются вероятностные меры, заданные на компактах Р, Q соответственно. Движения x(t₀)=x₀, определяются как пределы аппроксимационных движений x_k(t),удовлетворяющих уравнению

где

v_k[t]- некоторая слабо измеримая функция. Аналогичным образом вводятся движения

Для Д. и. сближения-уклонения всегда справедлива альтернатива 2 (альтернатива 3), формулировка к-рой получается из формулировки альтернативы 1 заменой стратегии одного из игроков на соответствующую контрстратегию (соответственно, заменой стратегий U* и V* смешанными стратегиями и ). Для Д. н., сводящихся к игре сближения-уклонения и рассматриваемых в классе позиционных стратегий одного из игроков и контрстратегий противника (в классе смешанных стратегий и ), устанавливается существование цены Д. и., причем здесь не предполагается условие (4). Решения Д. и. в указанных классах стратегий могут оказаться неустойчивыми по отношению к информационным помехам. Для стабилизации этих решений вводится процедура управления с поводырем (см. [9]). Здесь наряду с реальной системой рассматривается эталонная система - поводырь, движение к-рой моделируется в вычислительной машине и известно с любой требуемой точностью. Управление игрока в реальной системе и движение поводыря формируются так, чтобы движения исходной и моделируемой систем взаимно отслеживались, причем поводырь сохраняется на нек-ром мосту, соединяющем начальную позицию с целевым множеством. Такая процедура управления оказывается устойчивой к ошибкам измерения и помехам, действующим на систему. При моделировании движения поводыря можно использовать конструкции, допускающие дискриминацию противника.

Методы теории дифференциальных игр. Один из методов решения Д. и. был предложен Р. Айзексом [11]. Этот подход примыкает к методу динамического программирования и основан на интегрировании специального уравнения с частными производными, решение к-рого определяет цену игры c₀(t, х )как функцию исходной позиции игры. Оптимальные стратегии игрока I (или II) выбираются здесь так, чтобы обеспечить невозрастание (неубывание) цены игры вдоль порожденных ими движений системы. Однако нередки случаи, когда цена игры является разрывной функцией позиции игры, поэтому применение данного подхода требует специального анализа решений вблизи поверхностей разрыва функции c₀(t, x )или ее частных производных. Полное исследование сингулярностей и обоснование этого метода оказываются весьма сложными и их удается осуществить лишь в немногих примерах.

Наиболее полно изучены линейные Д. и., т. е. случай, когда

где А, В, С- непрерывные матрицы соответствующих размерностей. Для линейных задач преследования и уклонения Н. Н. Красовский сформулировал правило экстремального прицеливания (см., напр., [12]), к-рое позволило решить эти задачи (без дискриминации противника) при условии регулярности и, в частности, в случае однотипных объектов. Элементы этого решения вписываются следующим образом. Пусть - множество программного поглощения, т. е. совокупность точек для к-рых для всякого управления существует управление и такое, что пара этих управлений переводит систему из состояния на множество в момент времени t=J. Вводится функция

где М _e- евклидова е-окрестность целевого множества М. В области Г _J= {(t, x):e₀(t, x,J)>0} величина e₀(t, х,J) определяется соотношением

где для функции xизвестно простое выражение через опорные функции множеств Р, Q и выпуклого множества М(см. [12]). При условии выпуклости функции х по переменной l(сильное условие регулярности) в области максимум в (5) достигается на единственном векторе l₀(t, x,J), к-рый выбирается в качестве краевого условия в принципе максимума, определяющем выбор экстремального управления u₀. Построенная таким образом стратегия обеспечивает встречу с множеством Мк моменту t=J из любой позиции (t₀, х ₀), где e₀(t₀, х ₀,J)=0. [Указанные построения опираются лишь на информацию о позиции игры и эффективно реализуются на ЭВМ.] Решение задачи сближения с помощью программной конструкции можно получить и при ослабленных условиях регулярности.

Исследование линейных задач преследования при различных предположениях регулярности проводилось Е. Ф. Мищенко, Л. С. Понтрягиным, Б. Н. Пшеничным (см., напр., [13], [14], в частности, описано [13] решение линейной задачи преследования при так наз. условиях локальной выпуклости, при к-рых имеет место указанное выше сильное условие регулярности).

Одним из наиболее удобных способов решения игровых задач управления является прямой метод. В тех задачах, где возможно применение этого метода, управление игрока выбирается так, чтобы при любом противодействии противника осуществлялось отслеживание нек-рого вспомогательного процесса, приводящее к успешному окончанию игры. В случае однотипных объектов (С=- В, Q=XP,) и при условии дискриминации противника прямой метод решения задачи преследования назначает выбор управления игрока I в виде суммы двух слагаемых, одно из к-рых копирует управление противника, а другое совпадает с решением программной задачи на быстродействие перевода системы

на целевое множество М. Впервые прямой метод был описан Л. С. Понтрягиным [5] для линейной задачи преследования. Позднее были указаны условия, при к-рых прямой метод дает оптимальный результат [15]. Затем прямой метод был развит для решения нелинейных задач и для задач с интегральными ограничениями (см., напр., [16], [17]). Во всех этих исследованиях прямой метод использовался при условии дискриминации противника; он был развит также и для решения позиционных игр (см., напр., [9]).

Задача об убегании. В этой задаче требуется определить условия, при к-рых преследуемый объект может обеспечить уклонение от встречи с преследователем при всех . Исследование этого вопроса было начато Л. С. Портрягиным и Е. Ф. Мищенко (см. [7], [8]), к-рые указали условия разрешимости линейной задачи об убегании и получили оценку гарантируемого расстояния между преследующей и преследуемой точками. Подход, предложенный ими, был обобщен затем для исследования других случаев задачи об убегании.

Предложенное Л. С. Понтрягиным [6] понятие альтернированного интеграла позволило описать структуру множества начальных позиций, из к-рых возможно окончание линейной игры преследования в заданный момент времени t-J. Альтернированный интеграл определяется как предел рекуррентной процедуры, в к-рой исходное множество А ₀ совпадает с целевым множеством а каждое последующее множество А _i+1 определяется по предыдущему операцией программного поглощения, т. е. A_i+1=W(t_i+1, t_i, А _i, где t_i+1=t_i-D, t₀=0, D>0 - шаг рекуррентной процедуры. Б. Н. Пшеничный [18] при исследовании структуры Д. и. преследования в качестве элементарной операции также использовал программное поглощение, где в отличие от предыдущего случая требовалось лишь, чтобы продолжительность перехода из точек на А _i не превосходила числа Д, но, вообще говоря, не равнялась этому числу. Такая рекуррентная процедура позволила в общем случае нелинейной системы описать структуру множества позиций, из к-рых игру преследования можно окончить к заданному моменту времени.

Была также предложена экстремальная конструкция для решения позиционных Д. и. (см., напр., [9]). Этот подход используется как для решения конкретных примеров, так и при доказательстве общих положений, в частности альтернатив 1-3, указанных выше. Напр., при решении задачи сближения с в классе стратегий при условии (4), согласно экстремальной конструкции, в пространстве позиций выделяется множество образующее мост, к-рый соединяет начальную позицию с целевым множеством М _с и лежит целиком во множестве N _с. Мост обладает так наз. свойством u-стабильности, т. е. для любых и существует решение х(t)уравнения в контингенциях

для к-рого либо либо при нек-ром Вводится экстремальная к мосту W_n стратегия определяемая соотношением

где w- вектор, для к-рого (t, w)- точка множества W_u, ближайшая к позиции (t, х). Экстремальная стратегия удерживает движения на мосту W_u и тем самым доставляет решение задачи о сближении.

В этой конструкции основным моментом является определение подходящих стабильных мостов, после чего построение экстремальных стратегий не доставляет больших трудностей. Использование известных рекуррентных процедур для определения таких мостов ограничивается значительными трудностями вычислительного характера, поэтому важным является исследование эффективных способов построения стабильных мостов. Один из таких способов доставляет прямой метод. Другой способ - построение стабильных мостов в форме множеств регулярного программного поглощения. В нелинейном случае программное поглощение определяется с помощью специальных программных управлений-мер (см., напр., [9]). В регулярных случаях программного поглощения решение задач конфликтного управления можно довести до алгоритмов, реализуемых на ЭВМ.

Основные направления исследований дифференциальных игр. Изложенные выше результаты относились в основном к Д. и., в к-рых движение описывается обыкновенным дифференциальным уравнением (1), где управляющие векторы удовлетворяют ограничениям (2). Аналогичные результаты получены для игровых задач управления, в к-рых движение описывается дифференциальными уравнениями с отклоняющимся аргументом, а также для задач с интегральными ограничениями на управления игроков (см., напр., [17]).

Для исследования структуры Д. и. представляет интерес изучение задач конфликтного управления, где движение задается обобщенной динамич. системой (см., напр., [19], [20]). Рассмотрено решение Д. и. в классе квазистратегий, к-рые формируют управление игрока по реализовавшемуся управлению противника; предложены также итерационные процедуры для определения функции цены и стабильных мостов (см., напр., [21] ). .

Кроме Д. и. с двумя игроками, рассматриваются также Д. и. Nлиц. Постановка Д. и. Nлиц обычно предполагает, что каждый из игроков, распоряжающийся выбором своего управления, стремится минимизировать нек-рый функционал, определенный на траекториях управляемой системы. При этом допускается использование ими лишь информации о текущих позициях игры. Задача заключается, напр., в определении условий, при к-рых в таких играх имеется точка равновесия по Нэшу в заданном классе стратегий игроков.

Важный раздел теории Д. и. составляют игровые задачи управления с неполной информацией. В этих задачах предполагается, что неполнота информации заключается либо в незнании части компонент фазового вектора x(t), либо в измерении текущей позиции игры с нек-рым запаздыванием, либо в неточном измерении положения фазовой точки x(t), причем возможен случай, когда для погрешности измерения указаны лишь допустимая область, и случай, когда задано нек-рое статистич. описание этой погрешности.

Лит.:[1] Fleming W. H., "Contributions to the theory of games", 1957, v. 3, p. 407-12; [2] Varai.ya P., Lin Jiguan G., "SIAM J. Contr.", 1969, v. 7, №1, p. 141 - 57; [3] Петров Н. Н., "Докл. АН СССР", 1970, т. 190, №6, с. 1289-91; [4] Friedman A., "J. Different, equat.", 1970, v. 7, № 1, p. 111-25; [5] Понтрягин Л. С, "Докл. АН СССР", 1967, т. 174, № 6, с. 1278-80; [6] его же, там же, т. 175, Jss 4, с. 764-66; [7] его же, "Тр. Матем. ин-та АН СССР", 1971, т. 112, с. 30 - 63; [8] Понтрягин Л. С, Мищенко Е. Ф., "Дифференц. уравнения", 1971, т. 7, № 3, с. 436-45; [9] Красовский Н. Н., Субботин А. И., Позиционные дифференциальные игры, М., 1974; [10] Кротов В. Ф., Гурман В. И., Методы и задачи оптимального управления, М., 1973; [11] Айзеке Р., Дифференциальные игры, пер. с англ., М., 1967; [12] Красовский Н. <Н., Игровые задачи о встрече движений, М., 1970; ИЗ] Мищенко Е. Ф., Понтрягин Л. С, "Докл. АН СССР", 1967, т. 174, № 1, с. 27-29; [14] Пшеничный Б. Н., "Кибернетика", 1967, № 6, с. 54-64; [15] Гусятников П. Б.,Никольский М. С, "Докл. АН СССР", 1969, т. 184, №3, с. 518-21; [16] Чикрий А. А., сб. "Теория оптимальных решений. Тр. семинара", в. 3, К., 1969, с. 17-25; [17] Никольский М. С, "Дифференц. уравнения", 1972, т. 8, № 6, с. 964-71; [18] Пшеничный Б. Н., "Докл. АН СССР", 1969, т. 184, № 2, с. 285- 87; [19] Nаrdzewski С. R., "Adv. in game theory. Ann. of Math. Studies", 1964, p. 113-26; [20] В о x i n E., "J. Optimiz. theory and appl.", 1969, v. 3, №3, p. 153-63; [21] Ченцов А. Г., "Матем. сб.", 1976, т. 99, .№ 3, с. 394-420.

М. С. Никольский, А. И. Субботин.