Содержание к диссертации
Введение
Глава I. Дифференциальная игра пожка с неполной информацией о местоположении убегающего 12
1.1. Постановка игровой задачи поиска 12
1.2. Сведение дифференциальной игры с неполной информацией к динамической игре с полной информацией 27
1.3. Теорема существования значения динамической игры поиска 32
1.4. Уравнение Айзекса - Беллмана для функции значения игры 36
1.5. Достаточные условия для функции значения игры поиска 49
Глава II. Игра поиска с неполной информацией о местоположении обоих игроков 64
2.1. Постановка задачи. Сведение к динамической игре с полной информацией 64
2.2. Теорема существования значения игры. Уравнение Айзекса - Беллмана 68
Глава III. Игры с распределением ресурса одним или обоими игроками 78
3.1. Игровая задача поиска с распределением ресурса обоими игроками в дискретные моменты времени 78
3.2. Игровая задача поиска с распределением ресурса обоими игроками при условии, что количество вложенного ресурса влияет на эффективность дальнейшего поиска 86
3.3. Игровая задача поиска подвижного объекта, перемещающегося в дискретные моменты времени 97
3.4. Игровая задача поиска с распределением ресурса в непрерьгоном пространстве поиска 103
Заключение 106
Литература 107
- Сведение дифференциальной игры с неполной информацией к динамической игре с полной информацией
- Достаточные условия для функции значения игры поиска
- Теорема существования значения игры. Уравнение Айзекса - Беллмана
- Игровая задача поиска с распределением ресурса обоими игроками при условии, что количество вложенного ресурса влияет на эффективность дальнейшего поиска
Введение к работе
Во многих практических задачах ( в геологоразведке, при спасении терпящих бедствие и т.д. ) приходится сталкиваться с необходимостью оптимально с той или иной точки зрения организовать поиск движущихся или неподвижных объектов, причем сам процесс поиска, несмотря на различие условий и специфику конкретных задач, часто характеризуется общими для всех случаев элементами и принципами организации, что делает математические модели процесса поиска необходимым и в значительной степени универсальным инструментом исследования и решения поисковых задач.
В настоящее время по данной тематике опубликовано более ста работ. Работа положила начало созданию математической теории оптимального поиска объектов. В статье Ч задачи поиска формулируются как задачи оптимального распределения ресурсов, в которых в качестве критерия рассматривается либо вероятность обнаружения объекта поиска, либо ожидаемое время поиска, либо ожидаемый доход ( при условии, что искомый объект тлеет определенную ценность, сравнимую с затратами на проведение поиска). Сам поиск трактуется как случайный процесс, так как, во-первых, местоположение искомого объекта рассматривается как случайная величина, распределение которой известно, и, во-вторых, на средства обнаружения ищущего оказывает влияние ряд постоянно действующих случайных факторов. Район, в котором находится объект поиска, называется пространством поиска. Оно может быть непрерывным или дискретным. За время, истекшее после выхода статьи С 3 , была создана достаточно полная теория оптимального распределения ресурсов при поиске неподвижного объекта Li9 г 5,23]у а также объекта, перемещающегося в дискретные моменты времени L.W, о31.
В работах [Si - % 5 1 получены необходимые и достаточные условия для оптимального плана распределения ресурса при поиске движущегося объекта, когда его движение зависит от случайных параметров или описывается марковским процессом. Библиографию по задачам оптимального поиска до 1968 года можно найти в [If-1 J, за последующие семь лет - в С 3 J t За период с 1975 по 1980 годы - в [3.
Следует отметить, что постановка задачи оптимального поиска в следующей формулировке: найти оптимальную функцию плотности распределения ресурса поиска - не всегда приемлема, что отмечалось еще в С? J . В некоторых случаях целесообразнее искать оптимальную траекторию движения ищущего. В работах Le& 9 D рассматривалась задача именно в такой постановке, т.е. как задача оптимального управления ( в С6$3 рассмотрен более общий случай ) . В 63 автором получены необходимые условия оптргмальности траектории движения ищущего при поиске подвижного объекта в форме принципа максимума Л.С.Понтрягина для усредненных функционалов .
Во всех уже упоминавшихся работах объект поиска считался пассивным в том смысле, что он не препятствует действиям ищущего, т.е. не уклоняется от обнаружения. В том случае, когда объект поиска преследует цель оттянуть сколь возможно дольше момент обнаружения, либо остаться необнаруженным в течение определенного времени, мы имеем дело с игровой задачей поиска.
Игры поиска являются антагонистическими играми двух лиц. Их можно разделить на две группы:
- игры поиска, в которых стратегией организующего поиск игрока является распределение дискретного или непрерывного ресурса в пространстве поиска и ( или ) во времени;
- игры поиска, в которых оба игрока выбирают траекторию
- в движения ( или множества траекторий ).
К играм второй группы относится известная игра "принцесса и чудовище" , поставленная Р.Айзекоом [Zl , являющаяся игрой с полным отсутствием информации о местоположениях игроков. Дифференциальные игры этого типа рассматривались в ряде работ ( € у -%Ц І и др.) ив том числе в монографии ? 4 J , в которой получены оценки для значений игр поиска типа "принцесса и чудовище" в различных пространствах ( на графах специального вида, на бесконечной прямой, в ограниченной области ) и найдены стратегии игроков, которые эти приближенные значения реализуют, причем считается, что движение игроков является простым.
Несомненный интерес представляют дифференциальные игры с более полной информацией у игроков и с более сложным движением. Большой вклад в развитие теории дифференциальных игр с неполной информацией внесен советскими математиками, в первую очередь Н.Н.Красовским и его учениками ( А.Б.Кряжимским, В.Д.Батухтиным, А.Б.Куржанским, Ю.С.Осиповны, А.И.Субботиным и другими ), С.М.Никольским, Л.А.Петросяном, Ф.Л.Черноусько.
В работах [ 4, 2& ,2 Г - 3 5" , 40 , н 6 SB 1 с ис пользованием экстремальной конструкции Н.Н.Красовского решается ряд задач сближения ( уклонения ) при условии, что доступная информация о текущем состоянии системы определяется либо процессом наблкщения части фазовых координат, либо так называемой информационной областью X5, 31 J , т.е. областью, содержащей в момент t фазовые координаты исследуемой конфликтно управляемой системы.
К играм с неполной информацией следует отнести также игры с задержкой информации, изучению которых посвящены работы [16, , 0,5 ] и др.
В монографии С б 5"] исследуются дифференциальные игры, в которых один из противников может наблюдать другого не во все время движения, а лишь на некоторых временных интервалах. Игры с неполной информацией этого типа сведены к известным классам игр с полной информацией.
В данной работе рассматривается класс дифференциальных игр с неполной информацией, непосредственно не охватываемый упомянутыми задачами, а именно дифференциальные игры, в которых каждому игроку известен закон движения и управление противника ( до текущего момента ) и плотность распределения вероятности местоположения одного или обоих игроков в начальный момент времени. Подобные игры рассматривались в Сз9] , где получены теоремы существования значения дифференциальных игр поиска в случае, когда удается свести игру с неполной информацией к динамической игре с полной информацией и независимыми движениями игроков. В настоящей работе рассматривается класс дифференциальных игр поиска, сводимых к динамическим играм с полной информацией, но с зависимыми движениями. Такое сведение удается получить благодаря переходу из пространства фазовых координат объектов в пространство вероятностных плотностей распределений в качестве новых пространств состояний системы. Теория динамических игр с полной информацией разрабатывалась в работах [21, ,2 ,36,37,38 1, ,52, 60 .
Необходимо указать также на связь рассматриваемых в первой и второй главах динамических игр с играми в системах с распределенными параметрами Г2 !.- 2-3 , /3- 5} . Общим является то, что динамика игр задается уравнением в частных производных. Методы, основанные на теории Н.Н.Красовского Г2в 313 и развитые Ю.С.Осиповым и другими авторами в работах игр в системах с распределенными параметрами существенно используют некоторые специальные свойства дифференциальных операторов ( как то, эллиптичность, монотонность и т. д. ), входящих в уравнения динамики рассматриваемых ими систем. Этими свойствами исследуемая в настоящей работе задача не обладает.
Основная часть диссертации состоит из трех глав.
Первая глава посвящена изучению антагонистической дифференциальной игры поиска ( игры с неполной информацией ). В первом параграфе формулируется задача игрового поиска. Рассматривается случай, когда на всем протяжении игры ( максимальная продолжительность поиска фиксирована и известна игрокам ) оба игрока знают местоположение ищущего игрока Р , но не знают местоположения преследуемого игрока Е" . Игрокам известна лишь плотность распределения вероятности местоположения Q0(y) в R в начальный момент времени "t t0 . Кроме того игрокам известны управления свое и противника до текущего момента t . Выигрышем игрока является вероятность его не обнаружения игроком Р к моменту окончания игры Т . В качестве допустимых стратегий рассматриваются кусочно-программные стратегии I О О J. Во втором параграфе осуществляется сведение дифференциальной игры с неполной информацией к динамической игре с полной информацией .
В § 1.3 доказано существование значения динамической игры, а следовательно, и исходной дифференциальной игры поиска.
В § 1.4 доказано, что при определенных ограничениях, накладываемых на систему дифференциальных уравнений, задающих динамику дифференциальной игры поиска, функция значения игры, если она является непрерывно дифференцируемой, удовлетворяет уравнению, аналогичному известному уравнению Мзекса-Беллмана .
В § 1.5 выводятся достаточные условия для функции значения игры, основанные на этом уравнении.
В главе II изучается игра поиска, отличающаяся от игры, рассмотренной в главе I , только информированностью игроков. Предполагается, что информация о местоположении игрока 2 имеет такое же содержание, что и информация об игроке Е , а именно: известна только плотность распределения вероятности местоположения игрока Р в If .
В § 2.2 для данной игры формулируется и доказывается теорема о существовании значения игры, а также утверждения аналогичные утверждениям главы I о непрерывно дифференцируемой функции значения игры.
В главе III рассматриваются игры, относящиеся к первой группе игр поиска ( согласно приведенной классификации ), а именно игры с распределением поискового ресурса. В данной главе в качестве функции выигрыша рассматривается либо вероятность обнаружения уклоняющегося от обнаружения игрока Е ( выигрыш игрока В ), либо вероятность его не обнаружения ( выигрыш игрока ЕГ ).
В § 3.1 рассматривается игра поиска, в которой оба игрока имеют в своем распоряжении ограниченные бесконечно делимые ресурсы. Ресурс ищущего имеет смысл ресурса поиска, а ресурс уклоняющегося от обнаружения игрока - ресурса защиты, так как, если этот игрок при помощи своего ресурса обнаружит ищущего раньше, то он может организовать свои действия так, чтобы остаться необнаруженным до конца поиска. Доказывается существование ситуации равновесия, а также теорема, позволяющая свести задачу нахождения оптимальных стратегий к решению задачи максимизации.
В § 3.2 построена следующая математическая модель процесса поиска с противоположными интересами участвующих в нем сто - 10 -рон. Уклоняющийся от обнаружения игрок Е имеет ограниченный ресурс действия, который он должен использовать в определенные дискретные периоды в заданном районе таким образом, чтобы при этом остаться необнаруженным игроком J? . Ищущий игрок распределяет ограниченный ресурс в дискретные периоды поиска, причем эффективность поиска зависит от количества ресурса, вложенного игроками к данному моменту времени. Рассмотрены два варианта воздействия на эффективность поиска накопленного ресурса действия. Доказывается существование решений в таких играх. Рассмотрены частные случаи. Приведены их аналитические решения или указаны пути их численного решения.
В § 3.3 рассматривается игра поиска, в которой пространство поиска дискретно и конечно. В дискретные моменты времени убегающий Е переходит из одного района в другой, причем матрица перехода фиксирована и известна преследователи. Если на каком-то шаге игроки оказываются в одном и том же районе, то игрок Р обнаруживает игрока с определенной вероятностью. Стратегией игрока Е является выбор начального распределения вероятности, стратегией игрока J? - распределение конечного бесконечно делимого ресурса поиска на каждом из этапов. Доказывается теорема о существовании в этой игре значения и указан способ ее численного решения.
В § 3.4 рассматривается игра поиска, в которой организующий поиск игрок Р распределяет бесконечно делимый ограниченный ресурс в ограниченной области пространства К. , а уклоняющийся от обнаружения игрок выбирает распределение вероятности своего местоположения в этой области с учетом различной эффективности вложения ресурса поиска в различных ее точках. Неигровой вариант этой задачи рассматривался в работах как задача оптимального распределения ресурса при известной плотности распределения объекта поиска в заданной области. Приводится решение игры.
Сведение дифференциальной игры с неполной информацией к динамической игре с полной информацией
Условие la гарантирует существование, единственность и продолжимость непрерывного решения задачи Коши для системы ( і. і) с любыми начальными данными I 2.0 , 5 Ъ j . Условие 16 гарантирует существование, единственность и продолжимость непрерывного и непрерывно дифференцируемого по начальным данным решения системы С 1.2/
Пусть - полная совокупность первых интегралов системы (І.2.) ( т.е. матрица Якоби yv/dU неособая ) при фиксированном управлении 1Tel t0,T} , определенных при , причем tyvtyifcc) SLU для любых UЄ R . Функции u J; (ut b)t i= 1, . ,., я непрерывно дифференцируемы по совокупности аргументов при почти всех t = t ї""3 и кроме того, частные производные являются непрерывными функциями на R при любом фиксированном Игроки в процессе игры имеют следующую информацию. Оба игрока знают начальное местоположение игрока Р : ЭсС -Х . » а также плотность 0о (ч) распределения вероятности местоположения игрока Е в момент t to . Пусть плотность й0 (и) является непрерывно дифференцируемой на R функцией с компактным носителем, т.е. 5uflf goty)«Kg. где К« - компактное подмножество пространства R . Кроме того, игрокам известны управления свое и противника до текущего момента времени, а следовательно, а каждый момент времени t 6. Є\Іо- іим известно и местоположение x(t) игрока Р . Здесь t - момент окончания поиска, т.е. либо І — jT , если до момента Т объект Е не обнаружен, либо t - это момент обнаружения игрока Е игроком Р . Под обнаружением объекта Е понимается установление с ним прямого энергетического контакта. Обнаружение осуществляется с помощью средств обнаружения ( оптических, радиолакационных или других приборов ), работа которых основывается либо на фиксировании сигнала, отраженного от объекта поиска Е , либо на приеме собственного излучения Е Процесс поиска зависит от параметров технических средств обнаружения и особенностей окружающей среды ( если известны свойства объекта поиска, влияющие на обнаружение ) С 1 1 . В процессе поиска применение средств -обнаружения сочетается с активным маневром носителя этих средств, т.е. преследующего игрока JP , что и отражает система (І. і). Пусть фиксированы ОС - начальное местоположение игрока В , 1» - начальное местоположение игрока Е ( оно неизвестно игроку Р ),14 1 р№оіч, tr = D t,to?T) . Поиск будем рассматривать как случайный процесс, ход и исход которого зависит от ряда случайных факторов. Рассмотрим случайный процесс {Я (), = «tfc T)}f где IWt) ( при фиксированном t[tjTj ) - дискретная случайная величина со спектральными значениями 0 , і , 2 ... { число обнаружений, т.е. энергетических контактов, за время t c). Этот случайный процесс моделирует процесс поиска, если он обладает следующими свойствами: А)Ш-0; Б) число обнаружений попадающих на данный отрезок времени ІЛ.ір tij , не зависит от того, сколько обнаружений приходится на другие, непересекающиеся с ним отрезки времени для любого конечного множества tA t z . t ; В) вероятность попадания более одного обнаружения на элементарный отрезок времени [І 71 + d t J мала по сравнению с вероятностью попадания на него только одного обнаружения, и эта последняя вероятность зависит только от местоположения игроков в момент I и длины отрезка времени; т.е. процесс является марковским с переходной функцикй Функцию 0 $) принято называть функцией обнаружения иг рока . Как видно из - вероятность того, что в течение интервала Lt,Udt] не произойдет ни одного обнаружения объекта Е , если в момент t игрок находится в точке СС , а игрок Е - в точке и . Условие 3. Функция 1(ос0ц) является непрерывной вместе со своими частными производными 2xl 2#/,j = i,...,ii aceR Замечание I.I. Функция 4( ) на практике определяется экспериментально. Примером функции (х., и) , обладающей свой-ствами из условия 3, может быть функция обнаружения для визуального поиска объекта, находящегося на поверхности моря, в случае, если носителем является самолет, курсирующий на высоте П ft 8 1 , а именно: где A - коэффициент, зависящий от метеоусловий. Найдем формулу для вычисления вероятности (?t0g х (U-,1f) необнаружения игрока Е игроком Р за время Т t0 , если известно, что в момент t0 игрок J? находился в точке Х0е R. , плотность распределения вероятности местоположения игрока Е в R. равна Qoljd) t S и Е использовали управления 1ЛЄ соответственно.
Достаточные условия для функции значения игры поиска
Рассмотрим дифференциальную игру, отличающуюся от игры Г ftcX gJ), описанной в главе I , информированностью игроков, а именно: в каждый момент времени teftojT] игроки знают уп-раления свое и противника с момента начала игры to до момента t и плотности Ро(эс) и Чо(у) » гДе Ро(к) - начальная ( в момент t0 ) плотность распределения вероятности местоположения игрока Р в R , 0[о(%) то же Для игрока " . Выигрышем игрока Е снова служит вероятность его необнаружения игроком J? к моменту окончания поиска I . Имея такую информацию, игроки в каждый момент времени t могут вычислить совместную плотность распределения вероятности местоположения игрока и местоположения необнаруженного игрока Е ( аналог Ч и, Ы ) в главе I ). Обозначил ее jt4tV (0C} 3t) , Такті образом jutv (x j,b)dxoty = Вер [xjb)e Dfr), 4y(b)& DAf)» поиск при использовании игроком Е управления ve 0Ь tt0,t) , а игроком - управления It. Є Dbp Ct», t) до момента t неудачен j , где Х СЬ) - координаты игрока 2 , Ць- ) - координаты игрока Е в момент t , D(x) / Dfjf) /- малая окрестность точки э / U /, имеющая меру сЛХ I (ли /. Вероятность Q(u7V i ctfl) не обнаружения игроком РІГ- рока Е за время Т- t при условии, что до момента Ї игрок Б не обнаружен, если Е использовал на \Т) управление Ve DbE ,Т) , - управление и е рКт , а совместная плотность распределения вероятности местоположения игрока )2 и местоположения необнаруженного игрока Е в момент t равна "fa )» вычисляется по формуле J Г г Вывод формулы (2-і) аналогичен выводу Сі. 2?) , а вывод уравнения (2.-2.) аналогичен выводу уравнения (і. . З; в главе I. За УЧУ метим, что при t - to начальное условие (2.3.) имеет вид В качестве функции выигрыша игрока Б в игре поиска следует рассматривать функционал КА Ы,У 3 to, Я0хр ) » определенный на - 66 Как и раньше считаем, что К для всех "Ь ІлсДЗ, где V - компактное подмножество пространства & , V - компактное подмножество пространства R г . Под решением задачи (1.2.} , (1.) понимается функция 0, и,ъ 6 У 0 , непрерывно дифференцируемая по совокупности аргументов почти при всех tG-l-b-іТ) и такая, что почти при всех t"6ft,Tj Qu,v удовлетворяет С 2.2.) , а при t -условию (2.3). Кроме того, как ив І.І полагаем, что p0fac) и Ца(ч) имеют компактные носители в к Решение уравнения (2..2.) при начальном условии (і. Ъ) имеет вид ( аналогично формуле (l.lb Замечание 2.1. Здесь и далее предполагаем выполненными условия 16, 2 и 3 из I.I главы I и аналогичные условия для правых частей системы (1-і) и полной совокупности первых интегралов 5Ти (: ,) ( ї-и-Г гІ , . .. 5?Г.) ) ЭТ0Й системы, таких, что Х Ы ) - X , а именно: 1) существуют непрерывные в области задания частные произ водные 2) полная совокупность первых интегралов ЭСцб "/ является непрерывно дифференцируемой по совокупности аргументов вектор -функцией при почти всех ; при любом фиксированном ы It TJ функции В остальном данная игра не отличается от дифференциальной игры r iio o, 0ta) , описанной в I.I главы I.
Теорема существования значения игры. Уравнение Айзекса - Беллмана
Рассматривается следующая игра поиска с распределением ресурса. Ищущий игрок Р располагает конечным бесконечно делимым ресурсом поиска 0 , который он может использовать в моменты t/ Є [0,11,1 = 1,... 9Л/ . Цель игрока В состоит в том, чтобы за л/ периодов поиска обнаружить объект Ь , который также имеет в распоряжении конечный бесконечно делимый ресурс & 0 и может использовать его с целью обнаружения игрока в моменты t; Є-іО) -0 А - !, . . . У0\ В общем случае отличные от i I,...)/(/ , причем если игроку Е удается обнаружить игрока 2 до того, как Р обнаружит Н , то игрок Е может обеспечить свое необнаружение до конца поиска, поэтому впредь будем называть ресурс игрока Е ресурсом защиты.
Старатегией игрока является вектор X распределения ресурса сС : X aCj.j ...,0 ) 5 Of с - количество ресурса, направляемое игроком Б в момент tc V сг , ЭСс 0? I - L,.. .,// Стратегия игрока В - вектор и распределения ресурса : М Множество допустимых стратегий игрока S обозначим ЗС , а игрока E - j . Выигрышем К (Х-}у) игрока Г в ситуации i u) , где является вероятность обнаружения противника. Игра антагонистическая, то есть игрок Е стремится минимизировать Kfaj#). Игроки характеризуются своими функциями эффективности вложения ресурса р (і) и 1Е (j) ( 1 = 1,.... - і"-I, ...; М ), определяемыми следующим образом: р(0дН 4 О (Д2) равно вероятности обнаружения игрока Е. при дополнительном вложении ресурса Д2 на 6 -ом этапе поиска при условии, что Е не обнаружен до дополнительного вложения ресурса д.2 игроком Р и не обнаружил игрока ( где }- О при Д2- 0 ). є (j) определяется аналогично. Тогда вероятность ёр(с,В-) ( eL (А , ) ) обнаружения игрока Е ( Р ) противником на I -ом ( J -ом ) этапе поиска при условии, что игрок В. ( Р ) не обнаружил г ( Е ), будет равна [ Ч % J : Предполагается, что выполнены условия: Введем обозначения Тогда формула СЗ- 1) перепишется в виде Здесь Pi ( j ) имеют смысл вероятности обнаружения при вложении единичного ресурса. Ясно, что 0 Ри Л // j і)- jM . Учитывая (ъ 2 ) , можно написать формулу для определения К ( Ч) : j ( t )- моменты действия игрока E (Г ). Считается, что оба игрока знают моменты вложения ресурса противником. Не умаляя общности, можно считать, что Гд. , t , так как ясно, что игрок не будет вкладывать ресурс защиты после последнего вложения ресурса поиска игроком Р При решении игры можно воспользоваться методшш геометрического программирования, как это сделано в Г 1 1 J в применении к дискретным дуэлям. Обозначим Теорема 3.1. В данной игре поиска существует ситуация равновесия в чистых стратегиях. Доказательство. По определению - 81 Множества и J - выпуклые компакты евклидовых пространств. Функции nfbp)? ОС 1- і) и - )-) ЦЇ &ІЇ)) представимы в виде Из этого представления видно, что "Рчи.-рУ/ OC l-1) и Yl(l- )?f,S(t)Jвыпуклы по ОС и V соответственно при фиксированных остальных переменных. Следовательно, КіЗД/ выпукла по U при фиксированном X ( как линейная комбинация выпуклых функций с положительными коэффициентами ). С другой стороны, Ho так как &(і) &(i-i) по определению (Ъ. 40 . Следовательно, Kfcw) вогнута по ос при фиксированном « , как линейная комбинация выпуклых функций с отрицательными коэффициентами. Таким образом, выполнены все условия обобщения теоремы - 82 ион Неймана о минимаксе Следовательно, в описанной игре существует ситуация равновесия в чистых стратегиях.
Игровая задача поиска с распределением ресурса обоими игроками при условии, что количество вложенного ресурса влияет на эффективность дальнейшего поиска
Рассматривается следующая игра поиска объекта Е" / пре следуемого/, движение которого является случайным блужданием в дискретном пространстве поиска, состоящем из Лг районов, пре следователем . В распоряжении преследователя J? в каждый из периодов поиска имеется единичный ресурс, который игрок Р может произвольно распределять между А/ районами. В течение каждого из М периодов поиска объект Б не перемещается из одного района в другой. Пусть t - номер периода поиска ( t { J.,..., Mj ),1- номер района ( І6 \i,.. . jJ/\ ). В случае, если в течение t периодов ) объект Е не обнаружен, игрок Е перемещается в соответствии с матрицей перехода А atj 5 , где &ii есть вероятность перехода в району при условии, что Б находился в районе Матрица перехода известна преследователю. Пусть Я- . - до ля ресурса, направляемого преследователем в район І в период І, . Ясно, что Стратегией игрока E является вектор начального распределения вероятностей р- (pi , - - ) pj/ ) , где р есть вероятность того, что игрок Е находится в районе І перед началом первого периода поиска, Стратегией игрока x является набор распределений ресурса на всех этапах поиска, т.е. причем 2» t удовлетворяют условию {"Ь. L/9 ) Выигрышем игрока Е в рассматриваемой игре является веро ятность его необнаружения за ТА периодов поиска. Игра антагони стическая, т.е. цель игрока состоит в том, чтобы минимизиро вать выигрыш противника. Выигрыш в ситуации (р, Н ) будем обо значать через . Ясно, что для любой ситуации V(p «)6Lo,i]. Возможности преследователя при определенном способе поиска и типе датчиков характеризуются набором функций обнаружения 1 4 определяемых следующим образом: l foc) есть вероятность обнаружения игрока Е при условии, что Е находится в районе І , преследователь направляет в район I ресурс в количестве ОС В дальнейшем будем рассматривать экспоненциальные функции обнаружения, то есть функции вида Lr7ir&, iJ где of- 0 - коэффициент эффективности поиска. Пусть V[p,5)s VfpiZ) , где V/p, ) задана HaJ" Z , где р J р удовлетворяет т.е. 1//+ і - % (ец)при t OjAH 0i l,f\/ .Найдем вид функции V/p ). Из формулы полной вероятности следует, что где Q Ы/1) есть вероятность необнаружения игрока Е" при использовании игроком стратегии Я" при условии, что Е находится в районе I перед началом первого периода поиска. Введем обозначения: следует, что функции /у являются строго выпуклшш по Л . Следовательно, функция выигрыша v (pjS) также строго выпукла по К ( как линейная комбинация выпуклых функций ) при любом фиксированном р е-J Кроме того, Vtp 2) линейна, а следовательно, вогнута по р при фиксированном г = Z Множества замкну ты, ограничены и выпуклы. Функция VYp7i?J непрерывна на У У. Z . Следовательно, в игре с такой функцией выигрыша существует ситуация равновесия в чистых стратегиях ( по теореме фон Неймана Г &\ У\ ), то есть где p " и Z- - оптимальные стратегии игроков p и -P co ответственно. Причем, так как функция V(p32/ строго выпукла по Z. при фиксированном р , оптимальная стратегия игрока J? единственна. Для нахождения оптимальных стратегий игроков можно восполь-зоватеся одним из численных методов нахождения седловых точек, рассмотренных, например, в L Lh З .В частности можно использовать обобщенный на бесконечные антагонистические игры итеративный метод Брауна-Робинсон С & 3 .
