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

  Содержание 

  Введение                                                                                                              4

1. Основные сведения из теории дифференциальных игр                  6
1. Определение дифференциальной игры                                             6
2. Стратегии в дифференциальной игре                                                9
3. Виды выигрышей в дифференциальных играх                               15
2. Дифференциальные игры с неполной информацией                      17
1. Игры преследования с задержкой информации у игрока Р           17
2. Существование ситуаций равновесия в играх преследования      20
3. Игра преследования с фиксированной продолжительностью и задержкой информации у обоих игроков                                                    24

  Заключение                                                                                                         28

  Список  использованных источников                                                               29

  Введение 

  Теория  дифференциальных игр – это новое  математическое направление, возникшее  всего лишь несколько лет назад. Она тесно связана с теорией  оптимального синтеза, управлением  случайными процессами; некоторые её аспекты переплетаются с такими классическими направлениями, как  дискретные игры, дифференциальные уравнения, вариационное исчисление.

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

  Одной из первых работ в области дифференциальных игр следует считать работу Г. Штейнгауза, опубликованную в 1925 г., в которой он впервые формулирует задачу преследования как дифференциальную игру преследования. После длительного времени в середине 50-х годов математики возобновили исследование дифференциальных игр. Разработанный ими метод построен на «основном» дифференциальном уравнении в частных производных первого порядка для функции значения игры, которое было, по-видимому, впервые получено Р. Айзексом.

  Среди работ этого периода следует  отметить работы В. Флеминга,  содержащие исследование вопросов сходимости значений дискретных игр к решению «основного»  уравнения, работы Л. Берковича, в которых  выведены необходимые и достаточные  условия существования ситуации равновесия в терминах характеристик  «основного» уравнения, и конечно  же, монографию Р. Айзекса, в которой  на многочисленных примерах рассматривается  весь метод нахождения решения, построенный  на использовании «основного» уравнения.

  Первые  отечественные работы по дифференциальным играм появились в середине 60-х  годов. В соответствии с целью игры и решением можно выделить следующие основные подходы к задаче преследования.

  Л.С. Понтрягин и его школа рассматривают  задачу преследования, решая ее за преследователя Р, и задачу убегания, решая ее за убегающего Е.

  Н.Н. Красовский и его школа оценивают  качество преследования по времени, прошедшему от момента начала процесса до момента l-встречи (l>0). В основу этого метода легло правило экстремального прицеливания, которое в ряде случаев дает ситуацию равновесия.

  Работа начинается с рассмотрения сведений из теории дифференциальных игр. Раскрывается определение дифференциальной игры, понятия некоторых видов стратегий. Рассматриваются три вида выигрыша в дифференциальных играх: интегральный, терминальный, смешанный. Этот материал составляет первую главу. Затем во второй главе рассматриваются дифференциальные игры с неполной информацией. Исследуются задачи в случае задержки информации о состоянии процесса у преследователя, а так же задачи с фиксированной продолжительностью и задержкой информации у обоих игроков. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

  1.Основные  сведения из теории  дифференциальных  игр

  1.1Определение  дифференциальной  игры 

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

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

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

  Развитие  игры характеризуется движением  точки (x,y) в ε. Игра заканчивается, если выполняются некоторые условия, и всегда можно сделать так, чтобы эти условия состояли в попадании точки (х,y) на некоторую поверхность, или (n - 1)-мерное многообразие, которую можно принять за часть границы пространства ε.

  По  окончании партии становится известной  численная величина, называемая платой. Целью одного игрока является ее максимизация, а другого – минимизация. Наилучшее значение платы, ее минимакс, будет называться ценой игры. Она равна плате при оптимальном действии обоих игроков. Если один из них станет действовать не оптимально, то его противник получит возможность достичь платы, более выгодной для него, чем цена.

  Чтобы получить общую картину, будем обозначать преследователя через Р, а преследуемого  – через Е. Пусть Р выбирает uU и Е выбирает vV как функции от x(y). Если эти функции достаточно просты, то после подстановки их в уравнения движения =f(x,u),=f(y,v) правые части последних становятся функциями от x(y). Тогда уравнения движения превращаются в систему обыкновенных дифференциальных уравнений. Их можно интегрировать, используя в качестве начальных условий значения (x₀,y₀) в момент начала игры. Решение определяется x,y как функции времени t и описывает развитие игры, соответствующее выбранным стратегиям. Теперь становится возможным подсчитать плату. Целью игроков является выбор таких стратегий u(х) и v(y), которые могли бы соответственно минимизировать и максимизировать выигрыш.

  Итак, местом действия является ε – область в n-мерном евклидовом пространстве и ее граница. Это граница состоит из кусков некоторых поверхностей (под поверхностями понимаются (n - 1)-мерные многообразия).

  Пусть xRⁿ, yRⁿ, uUR^k, vVR^l, f(x,u), g(y,v) – вектор-функции размерности n, заданные на R^nU и R^nV соответственно. Рассмотрим две системы обыкновенных дифференциальных уравнений

              =f(x,u),          (1.1)

              =g(y,v)          (1.2)

  с начальными условиями x₀,y₀. Игрок Р(Е) начинает движение из фазового состояния x₀(y₀) и перемещается в фазовом пространстве Rⁿ согласно (1.1) или (1.2), выбирая в каждый момент времени значение параметра uU(vV) в соответствии со своими целями и информацией, доступной в каждом текущем состоянии.

  Множество Р будем называть множеством стратегий  игрока I, а множество Е -  множеством стратегий игрока II. Элементы множеств Р и Е будем обозначать соответственно через u(.) и v(.). На декартовом произведении Р×Е задана вещественная функция К. Тройку Г=<Р, Е, К> будем называть антагонистической игрой в нормальной форме.

  Параметры uU, vV называются управлениями игроков Р и Е соответственно. Функции x(t), y(t), удовлетворяющие уравнениям (1.1), (1.2) и начальным условиям, называются траекториями движения игроков Р, Е.

  Цели  в дифференциальной игре определяются с помощью выигрыша, который может  различным образом зависеть от реализовавшихся  траекторий x(t), y(t). Игроки I и II одновременно выбирают элементы  u(.)Р и v(.)Е. После этого игрок II получает выигрыш, равный К( u(.), v(.) ), а игрок I – выигрыш, равный - К( u(.), v(.) ).

  Система S={x₀,y₀;u,v}, где uP, vE, называется ситуацией в дифференциальной игре. Каждой ситуации S единственным образом соответствует пара траекторий x(t), y(t) таких, что x(0)=x₀, y(0)=y₀, и при почти всех t[0,T], T>0 выполнены соотношения (t) = f(x(t), u(t)),(t) = f(y(t), v(t)).

  Любую траекторию x(t)(y(t)), соответствующую некоторой ситуации {x₀,y₀;u,v}, будем называть траекторией игрока Р(игрока Е).

  В итоге общий вид типичного  решения дифференциальной игры следующий: пространство игры ε разделено некоторым  числом сингулярных поверхностей на составляющие области. Внутри каждой области  решение может не существовать вовсе, но если оно существует, то удовлетворяет  определенным дифференциальным уравнениям с граничными условиями, выполняющимися на сингулярных поверхностях. Оптимальные  траектории – пути изображающей точки  x в ε при оптимальной игре обеих сторон, - если они в разумном смысле единственны, могут иметь острые углы, только если они пересекают сингулярные поверхности. Кроме того, может случиться, что некоторые области содержат сингулярные многообразия меньшей размерности, чем поверхности, или такие многообразия могут лежать на самих сингулярных поверхностях.

  1.2.Стратегии  в дифференциальной  игре 

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

  Синтезирующие стратегии

  В игре с предписанной продолжительностью Т информационное состояние каждого игрока определяется фазовыми векторами состояний x(t), y(t) в текущий момент t и временем t, прошедшим с момента начала игры. Поэтому рассматриваем стратегию игрока Р(Е) как вектор-функцию u(x,y,t) (v(x,y,t)) со значениями в множестве управлений U(V). Стратегии такого типа будем называть синтезирующими.

  Программные стратегии

  Если управления представляют функции, зависящие от времени: u=u(t), v=v(t), то их называют программными управлениями. А стратегии такого вида программными.

  Позиционные стратегии

  В случае полной информации стратегию  игрока Р(Е) стали бы рассматривать как вектор-функцию u(x,y,t) (v(x,y,t)), т.е. отождествлять стратегии игроков с синтезирующими управлениями. Стратегии такого типа будем называть позиционными.

  Кусочно-программные  стратегии

  В дифференциальной игре, игрокам которой  предоставляется возможность неоднозначного выбора управлений в каждом информационном состоянии, в качестве стратегий  выбираем кусочно-программные стратегии. Кусочно-программная стратегия u(.) игрока Р состоит из пары {σ, α}, где σ – некоторое разбиение 0≤ t₀^'≤ t₁^'≤ …≤ t_n^'≤ … отрезка времени [0,∞) точками t_k^' , не имеющими конечных точек сгущения; α – отображение, ставящее в соответствие каждой точке t_k^' и фазовым состояниям x(t_k^'), y(t_k^') некоторое измеримое программное управление u(t) при t[ t_k^', t_k+1^' ). Аналогично кусочно-программная стратегия v(.) игрока Е состоит из пары {τ, β}, где τ – некоторое разбиение 0≤ t₀^''≤ t₁^''≤ …≤ t_n^''≤ … отрезка времени [0,∞) точками t_k^'' , не имеющими конечных точек сгущения; β – отображение, ставящее в соответствие каждой точке t_k^'' и позициям x(t_k^''), y(t_k^'') некоторое измеримое программное управление v(t) при t[ t_k^'', t_k+1^'' ).

  Стратегия параллельного сближения

   Пусть точка Е в момент времени t имеет скорость v(t)={v₁(t),v₂(t)}, ||v(t)||≤β<α. Обычно преследователю неизвестно, как дальше будет двигаться точка Е, однако, с точки зрения преследователя, часто наиболее вероятным является продолжением игроком Е движения со скоростью v(t)={ v₁(t), v₂(t)}. Для каждого такого движения существует, очевидно, единственное постоянное управление =(₁, ₂) игрока Р, которое гарантирует ему встречу с точкой Е за минимальное время. Это управление предписывает ему движение по лучу РВ, направленному в точку встречи, которое мы будем называть быстродействием в точку встречи (Рисунок 1).

   Параллельным  сближением (П-стратегией) называется способ преследования точкой Р точки Е, при котором управление игрока Р в каждый момент времени совпадает с управлением, гарантирующим ему    быстродействие в точку встречи.

  П-стратегию  можно определить как вектор-функцию

   (x₁, y₁, x₂, y₂,v)={₁(x₁, y₁, x₂, y₂, v₁,v₂), ₂(x₁, y₁, x₂, y₂,v₁,v₂)},   (1.3)

ставящую  в соответствие каждой паре точек  Р={ x₁, y₁}, Е={ x₂, y₂} и управлению v={v₁,v₂} управление точки Р, гарантирующее быстродействие в точку встречи В. Пусть игрок Е выбирает постоянное управление v(t)с={c₁,c₂}, т.е. перемещается по некоторой полупрямой [E₀,) из точки E₀. Тогда, как это следует из определения П-стратегии, траектория игрока Р, начинающего движение из точки Р₀, также будет полупрямой [Р₀,). Лучи [E₀,) и [Р₀,) пересекаются в точке В встречи игроков Р и Е. Точку, в которой находится игрок Р(Е) в момент времени t обозначим через z₁(t)(z₂(t)) (Рисунок 2) . Тогда отрезок [z₁(t),z₂(t)] при всех t[ 0, t_р] (t_р – время до встречи в точке В) параллелен отрезку Р₀Е₀. Таким образом, при использовании преследователем П-стратегии отрезок, соединяющий игроков Р и Е, в каждый момент времени до встречи параллелен отрезку Р₀Е₀, т.е. перемещается параллельно самому себе. Кроме того, из определения П-стратегии следует, что его длина убывает.

   Пусть Е начинает движение из начала координат и использует некоторое  управление v={v₁,v₂}. Выберем систему координат таким образом, чтобы Р в начальный момент времени находилась в точке z₁(0)={0,α}. Поскольку при использовании П-стратегии отрезок [z₁(t),z₂(t)] остается параллелен отрезку [z₁(0),z₂(0)], то проекции скоростей игроков Р и Е на ось х равны между собой (u₁= v₁). Кроме того, величина скорости игрока Р при параллельном сближении равна α. Это приводит к следующей системе дифференциальных уравнений для определения траекторий игроков при параллельном сближении, когда убегающий использует управление v={v₁,v₂}, v₁=v₁(t, x₁, y₁, x₂, y₂), v₂=v₂(t, x₁, y₁, x₂, y₂) (Рисунок 3):

                      ₁= v₁, х₁(0)=0,

              ₁= - _{, y1}(0)=α,

              ₂= v₁, х₂(0)=0,

              ₂= v₂, y₂(0)=0.

    Управление (1.3) можно найти и чисто  геометрическим способом по следующему  правилу:

1. Построить множество всех точек А, для которых выполняется условие |PA| _=|EA| α. При _< α² таким множеством является окружность Аполлония.
2. Построить луч ЕС, выходящий из точки Е по направлению вектора v={v₁,v₂}. Точка пересечения луча ЕС и окружности Аполлония является, очевидно, точкой встречи В (Рисунок 4). Следовательно, вектор (1.3) направлен по лучу РВ и имеет длину α, т.е

= (x₁, y₁, x₂, y₂,v) =α∙ РВ/|РВ|.

   Оказывается, что при параллельном сближении множество точек встречи  всевозможных движениях убегающей  точки Е имеет интересную геометрическую структуру: оно заполняет круг Аполлония.

  Стратегии погонного преследования

  Пусть заданы точки Р={ x₁, y₁}- преследователь, Е={ x₂, y₂} – преследуемый, перемещающийся в плоскости с ограниченными по модулю скоростями, имея возможность в каждый момент времени изменить направление своего движения. Это означает, что движение точки Р описывается системой дифференциальных уравнений: ₁= u₁, ₁= u₂,   (1.4)

где u₁, u₂ удовлетворяют условию _≤ α².  (1.5)

  Из (1.4), (1.5) следует, что точка Р движется на плоскости с ограниченной скоростью, не превосходящей числа α, и, выбирая  параметр u=( u₁, u₂), может управлять направлением своего движения. Такое движение называется простым движением.

  Будем предполагать, что точка Р преследует точку Е={ x₂, y₂}также совершающую простое движение в той же плоскости:

               ₂= v₁, ₂= v₂,     (1.6)

где  v₁,v₂ удовлетворяют условию _≤ β²     (1.7)

  Движения  точек Р и Е определяются системой:

              ₁= u₁(t, x₁, y₁, x₂, y₂),

               ₁= u₂(t, x₁, y₁, x₂, y₂),            

              ₂= v₁(t, x₁, y₁, x₂, y₂),

              ₂= v₂(t, x₁, y₁, x₂, y₂).

   Целью преследователя Р в самом  простом случае является встреча  с точкой Е, целью Е является избежание  встречи («встреча» - совпадение местоположений Р и Е). Если максимальная скорость точки Р превосходит максимальную скорость точки Е (α>β), то существует множество способов движения Р, при которых он может осуществить встречу с Е. Очевидно, что при этом Р должен знать текущее местоположение убегающего Е. Одним из таких способов является стратегия погонного преследования.

  Говорят, что точка Р преследует точку  Е по погонной линии, если скорость точки Р в процессе преследования  всегда направлена по отрезку РЕ и  максимальна по величине (Рисунок 5). В этом случае для проекций скорости Р имеем следующие формулы:

   u₁(t, x₁, y₁, x₂, y₂)=α  _,            

  u₂(t, x₁, y₁, x₂, y₂)=α _.

  Кривая  x₁= x₁(t), y₁= y₁(t), удовлетворяющая уравнениям (1.8) при управлении (1.9) и некотором фиксированном управлении точки Е, называется погонной линией.

  Пусть кусочно-программная стратегия игрока Р состоит из пары {Δ, u_Δ}, где Δ- некоторое разбиение t₀^Δ=0< t₁^Δ<…< t_n^Δ<… отрезка времени [0,), не имеющее конечных точек сгущения; u_Δ= u_Δ(t, x₁, y₁, x₂, y₂)={u₁^Δ(t, x₁, y₁, x₂, y₂), u₂^Δ(t, x₁, y₁, x₂, y₂) } – любая вектор-функция на множестве R⁵={ t, x₁, y₁, x₂, y₂}, принимающая значение в круге (1.5). Аналогично кусочно-программная стратегия игрока Е состоит из пары {σ, v_σ}, где σ - некоторое разбиение t₀^σ =0< t₁^σ <…< t_n^σ <… отрезка времени [0,), не имеющее конечных точек сгущения; v_σ= v_σ(t, x₁, y₁, x₂, y₂) - любая вектор-функция, принимающая значение в круге (1.7).

  Стратегией  погонного преследования называется стратегия: 

  _Δ=  ,  (1.10) 

  где Δ – некоторое разбиение отрезка  [0,), а функции, стоящие в правой части (1.10), при х₁=х₂, у₁=у₂ можно доопределить произвольным образом.

  На  Рисунке 6 для различных Δ изображены траектории игрока Р, совершающего погонное преследование игрока Е, убегающего по прямой. Можно, очевидно, совершать погонное преследование игрока Е, движущегося

Рисунок 6

по произвольной траектории х₂(t), у₂(t), а не только по ломанной, как это имеет место при применении игроком Е кусочно-программной стратегии. 
 

  1.3.Виды  выигрышей в дифференциальных  играх 

  Каждая  ситуация S={x₀,y₀; u(.),v(.)} в кусочно-программных стратегиях однозначно определяет траектории x(t), y(t) игроков Р и Е. Степень предпочтительности этих траекторий будем оценивать посредством функции выигрыша К, которая каждой ситуации ставит в соответствие некоторое вещественное число – выигрыш игрока Е. Выигрыш игрока Р равен –К. Это означает, что игра антагонистическая, поскольку сумма выигрышей игроков Р и Е в каждой ситуации равна нулю. Рассмотрим игры с функцией выигрыша трех видов: интегральный, терминальный, смешанный.

  Интегральный  выигрыш. В Rⁿ× Rⁿ заданы некоторое многообразие S размерности m и непрерывная функция M(x,y) >0. Пусть в ситуации S={x₀,y₀; u(.),v(.)} t_п - первый момент попадания траектории x(t), y(t) на S.

  Тогда  К(x₀,y₀; u(.),v(.))= _,

  где x(t), y(t) – траектории игроков Р и Е, соответствующей ситуации S.

  Терминальный  выигрыш. Заданы некоторое число Т>0 и непрерывная на {x,y} функция М(x,y). Выигрыш в каждой ситуации S={x₀,y₀; u(.),v(.)} определяется следующим образом: К(x₀,y₀; u(.),v(.))= М(x(T), y(T)),

где x(T)=x(t)|_t=T, y(T)=y(t)|_t=T. Здесь x(t), y(t) – траектории игроков Р и Е, соответствующие ситуации S.

  Смешанный выигрыш. Смешанный выигрыш определяется следующим образом:

    К(x₀,y₀; u(.),v(.))= + М(x(T), y(T))            (1.11).

  Интеграл  берется вдоль траектории, которую  х проходит в ε на протяжении партии; нижний предел интегрирования соответствует начальной точке в ε ; верхний предел есть время окончания игры – когда х достигает ε. Для каждой партии второе слагаемое в (1.11) есть значение функции М в терминальной точке, т.е. в точке, где х встречается с ε и игра оканчивается. Если первое слагаемое в (1.11) равно нулю, то игра имеет интегральный выигрыш; если второе слагаемое в (1.11) равно нулю, то игра имеет терминальный выигрыш.