Математическое моделирование задач поиска методами теории игр

Математическая теория поиска является широко разветвленной, богатой результатами и приложениями областью прикладной математики. Первоначально теория поиска развивалась преимущественно для военных целей, но в последствии выяснилось, что методы этой теории могут с успехом применяться при исследовании многочисленных проблем производства, в вопросах экономики, экологии, медицины, спорта, права, техники и бизнеса. Большой вклад в развитие теории поиска был внесен в работах Альсведе и Вегенера [2], Бека [78,79], Брауна [81], Купмана [102,103], Сартскало [117], Стоуна [120,121] и Хеллмана [60]. Среди поисковых задач особое место занимают: a) задачи поиска объекта, активно противодействующего обнаружению (например, при поиске подводной лодки противника, при построении системы зашиты, предотвращающей проникновение террористов на охраняемые объекты, при патрулировании границ, в борьбе с контрабандой, промышленным шпионажом, в рыбном промысле и т. д.) b) задачи поиска в условиях конкурентной борьбы (например, при поиске нефтяных месторождений и других полезных ископаемых конкурирующими фирмами, при планировании схем операций в экономическом нападении, рекламной компании, торговли, бизнесе и т. д.).

Математическое моделирование таких задач осуществляется методами теории игр, что позволяет найти оптимальные стратегии поведения конкурирующих сторон. Теорию игр поиска можно классифицировать по самым разным признакам. Одна из таких классификаций основана на противопоставлении статических задач динамическим, в которых процесс поиска сводится к некоторому единичному акту. В динамических же задачах процесс поиска состоит из последовательности (может быть, бесконечной) шагов поиска и кроме того, сам объект поиска может обладать некоторыми динамическими возможностями. Статические задачи рассматриваются методами классической теории игр [5,6,9,36,37]. Значительный интерес и развитие динамические игры поиска получили после выхода в свет книги Айзекса «Дифференциальные игры» [2]. Отметим, что динамические игры поиска тесно связаны с одним из разделов теории дифференциальных игр, а именно, теорией дифференциальных игр с неполной информацией. Большой вклад в развитие теории игр с неполной информацией был внесен в работах Алперна [6870], Базара и Олсдера [73], Бастона и Востока [74−77], Батухтина [4], Гала [88−94], Захарова [45], Карлина [97], Красовского [17−21], Кряжим-ского [23,24], Куржанского [25,26], Мазалова [29], Малафеева [30], Ме-ликяна [31], Никольского [33], Осипова [35], Петрова [38,39], Петросяна [40−48], Пшеничного [52,53], Ракла [108−110], Сакагучи [111−117], Субботина [58], Томского [48], Черноусько [63], Чикрия [64−67]. Также по играм поиска отметим работы Вошбурна [126], Зеликина [12], Зенкевича [113−115], Луценко [27,28], Скитовича и Чистякова [55] и Субелмана [122]. В настоящее время, в связи с многообразным спектром проблем, моделируемых посредством игр поиска, одной из наиболее актуальных задач является создание и дальнейнее развитие методов решения задач игр поиска, нахождение оптимального поведения участников в моделируемых конфликтных ситуациях. Данная работа посвящена развитию таких методов и подходов. В ней, в частности,.

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

2. Решена дискретная задача, сформулированная Раклом, о поиске точки при помощи двух отрезков для широкого класса случаев.

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

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

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

Во всех перечисленных выше задачах построены оптимальные стратегии конфликтующих сторон.

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

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

Айзеке [96] с целью обоснования необходимости применения смешанных стратегий в дифференциальных играх с запаздыванием информации сформулировал и решил две антагонистические дискретные игры на полуоси. Сформулируем первую из этих задач. Имеются два игрока: стрелок и мишень. Мишень может двигаться со скоростью, не превосходящую з единиц, только по целочисленным точкам полуоси Ох. Стрелок в каждый момент времени производит по выстрелу по любой выбранной им точке полуоси Ох. В точке О находится бункер, достигнув которого мишень оказьюается в безопасности от огня стрелка. Стрелок обладает полной информацией о местоположении мишени с запаздыванием на единицу времени. Целью стрелка является максимизация количества попаданий в мишень до того, как она достигнет бункера. Вторая задача Айзекса формулируется аналогично первой, с тем различием, что в случае попадания стрелком в точку, в которой находится мишень, поражение мишени происходит не достоверно, а с некоторой вероятностью а, где, а 6 (0,1). Стрелок стремится максимизировать вероятность поражения мишени до того, как она достигнет бункера. Ли [100,101] предложил обобщение первой задачи Айзекса на случай, когда стрелок в каждый момент времени имеет альтернативу: вести или не вести огонь. Сакагучи [112] исследовал обобщения второй 8 задачи на случай указанной альтернативы, а Накаи [104] - без указанной альтернативы. Бастон и Восток [74] предложили обобщение игры Айзекса, когда в точке х = 0 располагается барьер, а не бункер, т. е. эта точка не является точкой, которую в целях безопасности хотела бы достичь мишень, а является точкой, через которую мишень не может перейти на отрицательную полуось. В параграфах 1 и 2 данной работы решены обобщения задачи, сформулированной Айзексом, на случай игры на плоскости и произвольного бункера и на случай, когда вероятность поражения мишени зависит от расстояния между местоположением мишени и точкой, в которую попадает выстрел.

Томас и Нисгав [125] сформулировали задачу моделирования патрулирования пролива с целью предотвращения провоза контрабанды в виде антагонистической игры следующим образом. Контрабандист, имеющий катер, должен в течении одной из к ночей совершить попытку провоза контрабанды через пролив. Таможня, имеющая в своем распоряжении т быстроходных катеров, осуществляет патрулирование пролива с целью предотвращения попыток провоза контрабанды. Вероятность захвата контрабандиста зависит от количества катеров, используемых для патрулирования в ночь осуществления попытки провоза контрабанды. Имеются ограничения на количество ночей, в течении которых могут использоваться те или иные катера. Томасу и Нис-гаву [125] удалось решить эту задачу в случае, когда в распоряжени таможни имеется только один катер. Бастон и Восток [77] предложили метод для решения двухкатерной проблемы. В параграфах 2 и 3 предложен подход, отличный от рассмотренного Бастоном и Востоком [77], предоставляющий возможность решить также трехкатерную проблему. Стоит отметить, что по своей структуре игра контрабандисттаможня близка к проблеме инспекции описанной Оуэном [36].

Гал [92] сформулировал в общем виде задачу защиты объекта от не9 законного проникновения к нему диверсанта в виде антагонистической игры следующим образом. Имеются два игрока: диверсант и охрана. Игра осуществляется в районе П, в котором имеется защищаемый объект, расположенный в точке А. Диверсант проникает в район О в неизвестный момент времени в известной точке О и, осуществляя простое движение, пытается достичь защищаемый объект. Охрана, не имея информации о текущем местоположении диверсанта, пытается построить систему охраны объекта таким образом, чтобы минимизировать вероятность успешного достижения диверсантом защищаемой зоны. Кроме того, Г ал [92] конкретизировал эту проблему в виде следующей дискретной игры. Игра протекает на целочисленном интервале О = [0,т + 1]. Защищаемая зона располагается в точке х = т + 1, а диверсант проникает в район П через точку х = 0 и, осуществляя простое движение, пытается достичь защищаемую зону. Охрана, осуществляя простое движение, пытается помещать диверсанту. В случае, если в некоторый момент времени местоположения диверсанта и охраны совпадают, вероятность обнаружения диверсанта считается равной 1 — А, где Лвероятность необнаружения диверсанта. Целью диверсанта является максимизация вероятности достижения защищаемой зоны. Лалли [98] решил проблему, сформулированную Галом, в предположении, что в точке х = 0 находится безопасная зона для диверсанта (т.е. охрана не имеет права производить там поиск). Игра продолжается конечный интервал времени, и оба игрока осуществляют простое движение с единичной скоростью. Аугер [72] обобщил этот результат на случай игры на графе состоящим из п непересекающихся дуг, соединяющих вершины, А и О, в которых находятся защищаемая и безопасная зоны соответственно. Кроме того, он предполагал, что диверсант осуществляет простое движение с единичной скоростью, и нет ограничения на движение охраны (т.е. она может осуществить поиск в любой точ.

10 ке). Алперн [70] получил некоторые предельные результаты для игры Аугера для случая произвольного графа. В главе 1 даны обобщения результатов Аугера и Лаллея на случай произвольной скорости диверсанта и ограничения на число поисковых операций охраны. Кроме того, дан положительный ответ на вопрос, сформулированный Аугером [70], о существовании оптимальной смешанной стратегии охраны состоящей только из V) чистых стратегий, где ъо — общее число так называемых ждать-бежать стратегий диверсанта.

Айзеке [2] сформулировал антагонистическую игру поиска «принцесса и чудовище». Игрок 5 («чудовище» или ищущий игрок), начиная из фиксированной известной обоим игрокам точки и осуществляя простое движение в районе поиска П с максимальной скоростью, равной единице, пытается обнаружить игрока Я («принцессу» или прячущегося игрока). Игрок Я сам произвольно выбирает свое первоначальное местоположение в районе поиска О. Игроки не получают никакой информации о текущем местоположении противника. Под временем обнаружения понимается время сближения на расстояние г, где г — радиус обнаружения. Айзеке [2] показал, что для районов поиска с достаточно регулярной границей и неподвижным игроком Я, значение игры приблизительно равно шее (12)/(4г), где тев (П) — мера множества П. Алперн [68] и Зеликин [12] решили задачу «принцесса и чудовище» с шщвиж-ным игроком Я на окружности П в предположении, что оба игрока осуществляют простое движение с единичными скоростями в О, а их первоначальное местоположение выбирается независимо друг от друга в соответствии с равномерным распределением на П. Обнаружение игрока Я происходит в случае, если оба игрока окажутся в один и тот же момент времени в одной и той же точке. Алперн [68] и Зеликин [12] нашли оптимальные стратегии игроков и показали, что значение игры равно 31-/4, где Ь — длина окружности П. Андерсон и Арамендиа [71] И на основе линейного программирования предложили алгоритм построения оптимальных стратегий игроков игры «принцесса и чудовище» на графе в предположении, что игра протекает в течении конечного интервала времени. Гал [91,92] решил задачу «принцесса и чудовище» с подвижным игроком Я на графе специального вида, состоящего из двух вершин, соединенных к непересекающимися дугами единичной длины в предположении, что игрок S не может ждать в вершинах и скорость игрока Я не больше скорости игрока S. Он показал, что значение игры равно 1 /к. Алперн и Асик [69] решили проблему Гала при к = 3 опустив предположение, что игрок S не может ждать в вершинах графа. Гал [91,92] также решил задачу «принцесса и чудовище» при поиске в прямоугольно подобных районах поиска О. Он построил стратегии игроков, позволяющие сделать вывод о том, что значение игры при малых радиусах обнаружения асимптотически эквивалентно mes (?)/(2r). Лаллей и Робине [99] предложили стратегию игрока S, отличную от предложенной Галом [91,92], дающую ту же самую оценку для значения игры в выпуклом районе поиска в предположении, что игроку Я запрещено движение в малой окрестности границы района поиска. В главе 3 представлено обобщение метода, предложенного Галом, позволяющее получить асимптотику значения игры в случае, когда вектограмма скоростей игрока S отлична от круга.

Изучение игр типа тактических дуэлей или игр с выбором момента времени началось с 1948 года, когда корпорация RAND собрала группу специалистов, цель которой состояла в изучении значения и структуры неопределенностей войны и конкурентной борьбы и построении схем для оптимизации будущих операций в экономическом нападении. Приведем пример одной такой проблемы. Предположим, что две аналогичные.

М V «компании типа книга — почтой намереваются издать свои ежегодные каталоги. Проблема поиска оптимального момента выпуска каталога.

12 является важным вопросом. Компания, которая первая выпустит свой каталог, получает возможность опередить конкурента. С другой стороны, компания, которая ждет дольше, может нажить капитал на недостатках каталога своего конкурента. С аналогичной ситуацией выбора сталкиваются, например, конкурирующие нефтедобывающие компании при принятии решения о продолжительности геологоразведочных работ и моментом времени подписания контракта на добычу нефти. Карлин [97] систематизировал методы предложенные для решения подобных задач, сформулированных в виде антагонистических игр. Сакагучи [113] сформулировал и решил задачу с выбором момента времени с фиксированным моментом окончания в виде неантагонистической игры. Те-раока [124] и Сакагучи [114] исследовали данную неантагонистическую игру в случае, когда момент окончания игры является случайным. Стоит отметить, что в работах [114,113, 124] оптимальные стратегии по Нэшу искались среди довольно ограниченного класса стратегий игроков. Во второй главе предложен оригинальный метод, позволяющий искать равновесия по Нэшу среди всех стратегий игроков. На основе этого нового метода исправлена ошибка, допущенная Тераока [124] при решении игры с выбором момента времени, когда момент окончания игры является случайным с непрерывной функцией распределения. Решена задача, сформулированная Сакагучи [114], об игре с выбором момента времени, когда момент окончания игры является случайным с дискретной функцией распределения. Также диссертантом исследована проблема, когда игрок получает информацию о действиях противника с некоторой вероятностью и решено обобщение задачи, предложенной Хамерсом [86], о дележе с дискаунтным фактором по времени.

Перейдем к краткому изложению содержания диссертации.

ЗАКЛЮЧЕНИЕ

.

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

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

2. Решена дискретная задача, сформулированная Раклом, о поиске точки при помощи двух отрезков для широкого класса случаев. Найдены оптимальные стратегии игроков и значение игры.

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

4. Обобщен метод, предложенный Лаллеем, что дало возможность диссертанту решить задачу, сформулированную Г алом о за.-щите объекта при отсутствии информации у игроков о текущем местоположении противника в случае, когда ищущий игрок имеет ограничение на число поисковых операций. Дан положительный ответ на вопрос Аугера о существовании оптимальной смешанной стратегии охраны, состоящей только из т чистых стратегий, где IV — общее число так называемых ждать-бежать стратегий диверсанта. Найдены оптимальные стратегии игроков и значение игры.

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

6. Развит подход, позволяющий распространить формализм Га.

V I и ла для решения задачи, предложенной Аизексом, в играх поиска с полным отсутствием информации. На основе этого подхода решена задача поиска при условии, если вектограмма скоростей ищущего отлична от круга. Найдена асимптотика значения игры при малом радиусе обнаружения и стратегии игроков, определяющие эту асимптотику.

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