автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.18, диссертация на тему:Математическое моделирование задач поиска методами теории игр

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

ОД

На правах рукописи

2 0 ; 1АП 1997

ГАРНАЕВ Андрей Юрьевич

МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ ЗАДАЧ ПОИСКА МЕТОДАМИ ТЕОРИИ ИГР

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

Автореферат диссертации на соискание ученой степени доктора физико-математических наук

Санкт-Петербург 1997

Работа выполнена в Санкт - Петербургском государственной архитектурно - строительном университете

Научный консультант: доктор физ.-мат. наук,

: профессор Л.АЛГетросян

Официальные онпоненты: доктор физ.-мат. наук,

профессор Н.Н.Петров

о

диктор физ.-мат. наук, . профессор А.А;Меликяя

' доктор физ.-мат. наук, профессор М.М.Луденко

Ведущая организация: Московский государственный университет

I

■ Защита состоится ^ ' 1997 гадав / ' часов

на заседании диссертационного совета Д-063.57.52 по защите диссертаций на соискание ученой степени доктора наук в Санкт - Петербургском университете по адресу:

198904, Санкт Петербург, Старый Петергоф, Библиотечная пл., д.2 математико - механический факультет

С диссертацией можно ознакомиться в Научной библиотеке им. М . Горького Санкт - Петербургского государственного университета а адресу: 199034, Санкт - Петербург, Университетская Набережная 7/9

Автореферат разослан ' . 1997 года

Ученый секретарь диссертационного совета, д.ф.гм.н., профессор

о

Й.КДаугавет

Общая характеристика работы

Актуальность темы. Математическая теория поиска является широко разветвленной, богатой результатами и приложениями областью прикладной математики. Первоначально теория поиска развивалась преимущественно для военных целей, но в последствии выяснилось, что методы этой теории могут' с успехом применяться при исследовании многочисленных проблем производства, в вопросах экономики, экологии, медицины, спорта, права, техники и бизнеса. Большой вклад в развитие теории поиска был внесен в работах Альсведе и Вегенера, Бека, Брауна, Купмана, Сартскало, Стоуна и Хеллмана. Среди поисковых задач особое место занимают:

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

• (Ь)' задачи поиска в условиях конкурентной борьбы (например, при поиске нефтяных месторождений и других полезных ископаемых конкурирующими фирмами, при планировании схем операций в экономическом нападении, рекламной компании, торговли, бизнесе и т.д.) ' Математическое моделирование такпх задач осуществляется методами теории игр, что позволяет найти оптимальные стратегии поведения конкурирующих сторон. Теорию игр поиска можно классифицировать по самым разным признакам. Одна из таких классификаций основана на противопоставлении статических я .ач динамическим, в которых процесс поиска сводится к некоторому единичному а;:ту. В дншшиче-

сккх же задачах процесс поиска состоит из последовательности (может быть, бесконечной) Шагов поиска и кроме того, сам объект поиска может Обладать некоторыми динамическими возможностями. Статнче-. ские задачи рассматриваются методами классической теории игр. Значительный интерес и развитие динамические игры поиска получили после выхода в свет книги Айзекса "Дифференциальные игры". Отметим, что динамические игры поиска тесно связаны с одним из разделов теории дифференциальных игр, а именно, теорией дифференциальных игр с неполной информацией. Большой вгуад в развитие теории игр с неполной информацией был внесен в.работах Алперна, Бастона н Востока, Воробьева, Гала, Карлииа, Красовского А.Н., Красовского H.H., Куна, Куржанского, Ли, Мззалова, Малафеева, Меликяна, Никольского, Петросяна, Ракла, Сакагучн, Слобожанина, Томского, Черноусько, Чикряя. Также да играм поиска отметим работы Аугера, Вошбурна, Зелик ина, Зенкевича, Луценко, Петрова, Петросяна, Скитовича, Субел-мана. Развитие теории дифференпиальйых игр с неполной информацией стимулировало исследование динамических теоретике - игровых моделей поиска и обнаружения подвижного объекта. В конце 70-х годов в работах Гала было построено решение модельной задача ("принцесса и чудовище") подвижного объекта, осуществляющего простое движение. В последствии эти работы легли в основу его монографии "Игры • поиска." Наиболее систематически теоретико - игровой подхси к зад* чам поиска, впервые, в России был отражен в монографии Петросяна Зенкевича. "Оптимальный поиск в условиях конфликта." В настоящее время, в связи с многообразным спектром проблем, моделируемых по средством игр поиска, одной из наиболее актуальных задач являете

«' 1 - ' Q

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

лируемых конфликтных ситуациях.

4 . '

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

ных, но нерешенных до сих пор проблем теории игр поиска.

!

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

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

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

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

поведения игроков и значение игры.

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

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

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

в •

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

отлична от круга. Найдена асимптотика значения игры при ыа-

i

лом радиусе обнаружения п стратегии игроков) определяющие эту асимптотику. j

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

ряда теоретпко - игровых моделей поиска, создают перспективное на- 1

<

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

Апробация результатов дкссертацхш прошла па международном конгрессе по компьютерным системам п прикладной математике (Санкт-Петербург, 1993), на международной конференции по теории игр и экономике (Санкт-Петербург, 1S96), на семинарах по теории игр Санкт - Петербургского государ степного университета, Саутгемтон-ского университета, Лондонского университета, института проблем механики РАН, па семинаре кафедры оптимального управления факультета вычислительной ы атематпкп и кибернетики Ыосхозского государственного 'университета и на Си:кт - Петербургском, городском семинаре по теории игр под руководством Петросяна. Ессл одевания, проводимые по те;.1й дксссртацглг, былп деграгданы 12 месячной postdoctoral fellowship Лслдопского короллзского с-Сщостаа н подцергхкы грантом N 93-1-51-27 ГЛпппстерства Наука, Вмсзпэй Школы п Технического Образования Российской Федерация.

Результаты дпг.сертг;,",:::: одуСликспшм в 24 научных работах, в том числа а одной г,:х:ограф;.д.

Струи-*ура р&ьоты. Д'жссртэцкт состоит из водпасяг, трех глав,

7

заключения и списка литературы. Общий объем диссертации 250 страниц. Список литературы включает 151 наименование.

Содержание работы

В введении дается краткий исторический обзор, формулируются цели и основные результаты диссертации, кратко излагается содержание работы, •

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

В параграфах 1-1.3 исследовало обобщение дискретной задачи с запаздыванием информации о текущем положении проникающего объекта, сформулированной Айзексом, на случай игры на плоскости. В исследуемой антагонистической игре на плоскости имеются два игрока: охрана и диверсант. Игра протекает в дискретные моменты времени { = 0,1,.... Диверсант может двигаться только но точкам целочисленной решетки Z'i = {(«!.?) : *,} 6 Z} плоскости Оху, Если I некоторый момент времени диверсант находится в точке (»,/), то чер« единицу времени диверсант может перейти в одну из следующих то чек: ($ -1,.?'),(» +-1,,?), (»,з - 1), (»,} +■1) или остаться ва месте в точк (»',}). Охрана имеет некоторое вооружение с к единицами боеприпасо и в каждый момент времени может производить не более одного вь стрела по любой выбранной ей точке целочисленной решетки 23. Пуст В С 21,0 ф Ъ1 и В ф 0. В множестве В расположен "бункер", д< стлгнув которого диверсант становится недосягаемым для огня охр; ны. Если диверсант, находившийся в точке (*\у), через единицу вр мени перейдет в точку £(»',]) (или останется на месте в точке {¡,})), охрана будет вестн огонь по точке £(»,,?) (или (»,;)), то вероятность л

ражения диверсанта будем считать равной а( (или аг) соответствен!

8

где £ = 1,3,4,5. Здесь а( € (0,1),£ е [1,5];1(»,;) = (»- 1,з),2{<,з) = (>.ЛЗ(»,Я = (» + 1,= (»,7-1),5(»,;) = (»',;' + 1). Охрана обладает полной информацией о местоноложепиии диверсанта с запаздыванием на единицу премени, т.е. охрана знает, где!находился диверсант, но не знает, куда он пошел. Диверсант знает, сколько единиц боеприпасов осталось у.охраны, но не знает, по каким позициям она ведет огонь. Выигрыш охраны равен единице (нулю), если диверсант поражен (не. поражен) огнем охраны. В теореме 1.1 показано, что значение игры *>((*>.?)>£)> когда диверсант первоначально находился в точке (»,.?), а охрана имела к боеприпасов, определяется из рекуррентного соотношения

ШЮГГ™

с граничными условиями

П(м).о) = 1,(»-,;) е22,

•где У((»,7'),*) = 1/(1 - v{(i,j),k)),B = {(.-,;) € £2 : существует $ € [1,5] такой, что £(»,,;) £ В}, а символом б 6 [1,5],'где

С? = 5!/(т!(5 — т)!), обозначаются такие подмножества множества [1,5], что

в если и ф ¡1,ю Ф

о для лтоСых т, V множество Ут(„ является выборкой т элементов без повторения из множества [1,5]. Кроме того, в теореке 1.1 пайдзны оптимальные поведенческие стратегии игроков.

В параграфах 2 - 2.4 рассмотрено обобщение дискретной задачи,

сформулированной Айзоксок, с запаздыванием ппЛор:.:з.цяя о текущем

9

Е

Сб^т,,

- 1

у(е(и),л-1)

Е

Ш',,

положении проникающего объекта на на случай, когда вероятность поражения проникающего игрока зависит от расстояния между его местоположением и точкой "взрыва". В исследуемой антагонистической игре на прямой имеются два игрока: охрана и диверсант. Диверсант может двигаться только по целым точкам 0,1,... прямой со скоростью, не превосходящей единицу, т.е. если в некоторый-момент Бремени диверсант находится в точке »', то через единицу времени он может перейти в одну аз следующих двух точек: г - 1 или I + 1, или остаться на месте в точке г. Охрана, первоначально вооружекля некоторым вооружением с к единицами "осколочных боеприпасов", в каждый момент времени I = 0,1,... может либо производить, либо не производить выстрел. "Осколочный боепрппас", попавший в точку »', с вероятностью щ поражает объект, находящийся в этой точке; с вероятностью а% поражает объект, находящийся в точке» —1, либо £ +-1; с вероятностью «з поражает объект, находящийся в точке»— 2, либо »' + 2. Естественно считать

• что 0 < а3 < а2 < аь Б точке 0 расположен "бункер", достигнув ко торого диверсант становится недосягаемым для огня охраны. Охран обладает полной информацией о местоположении^ диверсанта с зала: даванием на единицу' времени, т.е. охрана знает, где находился до версант, но не знает, куда он пошел. Диверсант знает, сколько едини боеприпасов осталось у охраны, но пе знает; по каким позициям 01

• ведет огогь. Выигрыш охраны равен единице (нулю), если диверсах поражен (не поражен) огнем охраны. Пусть = 1 — сц. В теоремах 2 и 2.3 показано, что значение игры «(»', к), когда диверсант первоначаг но находился в точке а охрана имела к боеприпасов, определяется следующих рекуррентных соотношений (

О

если А + > 2/?з, то

: ——— = тах(— -1--------

( Рх__Гп-УРг_

I- 1,к ~ 1)' У(1 - 1,к - 1) + к~ 1)'

А№-А)

(А - А)-1, к -1) + № - А)У(» +

если А +/?з < 2/?2, то

1^-1)}'

1 _ ( . А__• А!+А •

- тах\ у(,• _ 1, к _ !)'• - 1, к - + У(,\ к - 1)'

... . А + А

У(1-1,й-1) + У(; + 1,Л-1)'

(А - А)(У(| -1, * - 1) + У(* +. 1, * - 1)) + (2А -А- А)П». л -1) /

с начальными условиями . .

У(»,0) =1,» = 1,2,..., У(1,Ь) = 1,к=1,2.....

где !'(»,*) = 1/(1 -*0\*)). > (

Кроме того, в теоремах 2.1 и 2.3 найдены оптимальные поведенческие стратегии игроков. В теоремах 2.2 и 2.4 найдена асимптотика значения игры, а именно, показано, что если А > 0, то Нт^» У(:, Л) = А1-' и если А + А > 2/?2> то

Пт У{г,к) = &", »-+00

' если А + А < 2А, то

V л/г- п С1*/?»-ЗД-А-1*

В параграфах 2.5 - 2.5.2 рассмотрена задача, сформулированная Ай-зексом, для случая, когда охрана стремится максимизировать число попаданий в диверсанта до того, кап он достигнет "бункера".

В параграфах 2.6 - 2.6.2 исследована задача поиска даумя отрезками одной точки, сформулированная Ратслом. В частности, в теореме 2.9 доказало, что если тп> п/2, то •

1(п - т))к\ + 2

^{ГП^Ь, П.) —

2{[Ьг-т)/к\+1У 11

где Щ - наибольшее целое число меньшее а у(т,к,п) - обозначает значение игры при поиске целочисленной точке в целочисленном отрезке [1,п] двумя целочисленными отрезками состоящими из т и к точек. В теореме 2.14 показало, ч го

!т +1 . 5-

/ , ч / • (т + 1 ¿ + 1 )

при то е [2, п/2), а т - такое натуральное число, что п'= 7»и + ¿,<5 6 [1,го — 1]. В теореме 2.19 показано, что если т-четное, то v(m,2,n) = »(от/2,1, [п/2\ +■1), а если т -нечетное и чп € [3,п/2), то

и(т,2,п)==

если а + р>т если аН и В > О

(74Щ1/+2]2+1)' если а + р <т

1<5/21 + Ит - 5 - 2)/2| + 3 , д ^

(7Н-1)( Ы + 1) + 2)/2\ + 1)'" если«+^<т

и 0 < О, где 0= [<5/2] — 7+1.

В параграфе 3 решена трехкатерная задача, сформулированная Нис

гавом и Томасом, моделирующая, проблему патрулирования пролива

целью предотвращения провоза незаконного груза контрабанды посрег

ством рекуррентных игр. В исследуемой антагонистической игре им

ются два отрока: -таможня и контрабандист. Контрабандист, имеюхщ

катер, должен сделать в течении п ночей одну попытку по провозу чер

пролив контрабанды. В распоряжении таможни имеются три катер

причем <-й катер может быть использован.в течении любых к; ночей д

патрулирования пролива, где к1,кз,кз < п. Вероятность захвата кс

трабалдисга таможней, использующей < катеров в ночь попытки пе]

сечения пролива контрабандистом, равна р,, где р\ < Рг < Рз- Выигр!

таможни в случае захвата контрабандиста равен 1 и —1 в противв

12

случае. В теоремах 4.1 - 4.2 найдено значение игры н определены оптимальные поведенческие стратегии 1щ>оков этой игры.

В параграфе 5 - 5.3 решена задача, сформулированная Галом, о защите объекта гри отсутствии информации у игроков о текущем местоположении противника в случае, когда ищущий игрок имеет ограничение на число поисковых операции. Кроме того, дан положительный ответ на вопрос Аугера о существовании оптимальной смешанной стратегии охраны, предписывающей с равной вероятностью играть одну нз ш чистых стратегии, где ш - общее число ждать - бежать стратегий диверсанта. В исследуемой антагонистической игре имеются два игрока: охрана н диверсант. Игра протекает на'графе, состоящем из двух — вершин О я А соединенных г» непересекающимися дугами. В вершине О располагается зона безопасности, где диверсант не достижим для поражения охраной. Защищаемый объект располагается в'вершине А, куда диверсант намерен пробраться к моменту времени Г. Игра про* текает в дискретные моменты времени t. ~ 0,1,..., Г на m равномерно расположенных отмеченных точках этого графа (па разных дугах может? быть рассоложено разное-количество отмеченных точек, т.к. дуги , могут иметь разные длины). Не теряя общности, можно предположить, что расстояние между соседними отмеченными точками равно единице. В начальный момент времена t = 0 диверсант находится в зоне безопасности (вершине О) н его задачей является достижение защищаемой гоны (вершины А) не позднее момента времени f = Т, осуществляя простое движение с единичной скоростью (т.е. в течении одной единицы времени он может перейти в одну из соседних точек вдоль дуг графа, либо остаться на месте). Охрана нэ имеет больше ипформапии о диверсанте, в частности, oéa не знает его текущую позицию. Охрана с. некоторым видом вооружения и к единицами боеприпасов располагав

ется в течении игры в защищаемой зоне и в каждый момент времени

13

может произвести по выстрелу по любой отмеченной точке. В случае попадания в ту же точку, где находится диверсант, вероятность его поражения равна 1 - Л (т.ё. Л - вероятность промаха), а в противном случае 0. Игра оканчивается в случае поражения диверсанта, либо достижения диверсантом защищаемой зовы. В случае достижения диверсантом защищаемой зоны до его поражения выигрыш диверсанта равен

1, и в противном случае, он равен 0, т.е. целью диверсанта является максимизация успешного достижения защищаемого объекта. В теореме 5.1 показано, чтох{к,гд,Л) = (А*+18 + Х'(ы - з))/ш является значением этой игры, где в = к— гы,г = [к/т]. Кроме того, в теореме 5.1 Найдены оптимальные стратегии игроков.

В параграфе 6 - 6.3 рассмотрена задача из параграфа 5 в предположении, что диверсант может двигаться со скоростью не превосходящей и, где и > 1. В теореме 6.3 найдено значение этой игры и оптимальные стратегии игроков.

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

Параграфы 7 - 8.4.3 посвящены исследованию следующей двухпер-сонвой игры с неопределенные моментом окончания, являющейся обобщением классической дуэли. Имеются два игрока: игрок 1 и игрок

2. Каждый из игроков имеет по ружью с одним патроном, когорыв

он может выстрелить в любой момент времени ез интервала [0,1] пс

целп. Точность поражения » - ьш игроком мншепн характеризуете*

непрерывной строго возрастающей функцией А; : [0,]^ [0,1], на

зываемой функцией точности, так, что если игрок г производит сво;

выстрел в момент времени х, то вероятность поражения мишени раг

14

па Л;(я). Игрок, .черпый поразпшттй мишень, является победителей, и игра закапчивается. Кроме того, соревнование оканчивается В случайный момент времени Т пз (0,1] с дадной плотностью распределения II (я). Каждый ю игроков выбирает момент выстрела. В параграфах 7-7.4 считается, что II является непрерывкой. В параграфах 7-7.2 ружья предполагаются бесшумвьшп, т.е. каждый из игроков пе знает, поразил лп его противник мишень или промахнулся. Пусть • А";(ж) = Рг {соревнование не закончилось в момент времени х, игрок » поражает цель, стреляя в момент времени в}. Тогда

Следуя Тераока предполагаем, что К; и А{ 6 С1 [0,1], причем, А,-(О) — О, А;(1) = 1,/Г;(0) = /<Т;(1) = 0. Кроме того, предполагаем, что ^¡.является унимодальной функцией, а именно, существует такое гщ € [0,1], что ИГ,— строго возрастает па интервале [0,га,] п строго убывает па интервале [т,-, 1] и пусть /4;(а) > 0 при я € (0,1).

Для случая ГП1 = тз = т в. теореме 7.1 доказано, что в данной игре ■ существует единст&ешгое релшовеске по Нэшу (-Рь-Гз), причем,

* Г 0,1 если х € [0, а)

¿•¡(г) = если я € [в,т), (=1,2,

1, если х € [т, 1]

где а — тах{а1(т); б2(т)},о<(л) - единственный корень вкйтервале (0,г] урачиенпя <р;(а,з) = 1,

¥>,(«, а) = -ЭД 1'(1/КМ)'/Мь') ¿V .

я (/^(а^Л^а)) - Еектор платежей, сзстватствухощпй ргвисгеекк) по

Если т.1_ ф тг, без гготэрл общности ютжео считать, что гг»з < г»1. В

15 •

ад»

теоремах 7.2 и 7.3 доказало, что в этом случае в данной игре существует единственное равновесие по Нэшу причем,

если (1- Л2(т2))^1(т1) > #1(т2), то (Fb.Fi) = (тит3), если (1 - ^(тз^^Отц) < К^ггц), то

г0, если а € [0, а)

<р1(а,х), если х £ [а^пц) (р! (а,та), если а; € [т2,гп1)' 1, если х е [п»1,1]

О, если ж 6 [0, а)

у?

!рг(а, ж), если ж £ [а, тг) , , 1, если а 6 [тг, 1]

. где а = шах{а1(г7г2), а,}, а, - единственный корень в интервале (0,та] уравнения.

К1{т1)[К1(а)/К1(т2) - Л2(т3)(1 - р»(о,т,))] = ЛГ?(а)

и (^(а), К-2{а)) - вектор платежей, соответствующий равновесию по Нэшу (Я, Я).

В параграфе 7.2 приведен контрпример показывающий незавершенность работы Тераоха то. исследуемой выше игре. В параграфах 7.3, 7.4 по казацо, что в случаях шумного и бесшумно-шумного вариантах исследуемой игры нарушается единственность равновесия по Нэшу. В пара. графах 8 -8.4.3 гашена задача Сакагучи, предложившего исследовать данную, игру и случае дискретного Я. В параграфах 8-8.2.2 рассмотрен бссшу лпый вариант этой игры и найдено единственное равновесие по Нэшу. В параграфах 8.3 -8.4.3 исследованы шумный и бесшумно шумный варианты исследуемой игры и показано, что в этих случая: нарушается единственность равновесия по Нэшу. * В параграфе 9 исследу-тгся описанная в параграфе 7 игра с фнксирс

валким моментом окончания в предполо:кепЕН, что игрок может с иош

16

торой вероятностью получить информацию о моменте выстрела своего противника. В теореме 9.1 найдено равновесие по Нэшу у исследуемой игры.

В параграф«110 исследуется ситуация, когда два игрока делят нормализованный бесконечно делимый ресурс. В момент времени £ = (!) игрок»,» = 1,2 имеет право получить а,- -ю часть бесконечно делимого ресурса, где а = «х 4- а» < 1. Игроки 1 и 2 должны выбрать моменты времени х и у из интервала [0, оо) соответственно для того, чтобы потребовать свою часть бесконечно делимого ресурса. Если х < у, то игрок 1 получает -к> часть бесконечно делимого ресурса, а игрок 2 оставшуюся (1 — а^Ц -ю часть бесконечно делимого ресурса, где 61 и - дискаунтные факторы. Если х > у, то игрок 2 Получает агг^К -ю часть бесконечно делимого ресурса, а игрок 1 оставшуюся (1 — аа)<5* ~н> часть бесконечно делимого ресурса. Если я '= у, то каждый из игроков получает зарезервированную за ним часть бесконечно делимого ресурса штос половину остатка, т.е. игроки I и 2 получают («1 + а/2)5* и («2 + а/2)5$ -е части бесконечно делимого ресурса соответственно, где £ = 1 — Предполагается,! что игрок »' получает информацию о выборе игрока ] с вероятностью Д, где 6 [0,1]. Пусть > 0 и

--если О

-15^" если 7; = О

1(® + Тг-:

если 7,- ^ 0

' ~ Т)/Т>, если 7.' = о

при а; 6 [о, Г] и

^¡(г) - 1 при х е (Т, оо),

где 'Г = тш{Г1, 2а} и 7,- = аф} — ау. В теореме 10.1 доказано, что если

АА > 0, то является единственным равновесием по Нэшу. В

17

теореме 10.2 показало, что если ßißj = 0, то единственность равновесия по Нэшу нарушается. .

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

В параграфах .11 - 11.2 исследована следующая игра. Имеются два игрока: игрок Л (прячущийся) и игрок S (ищущий). Игра протекает в прямоугольном множестве ii. Игрок И осуществляет простое движение со скоростью w > 0 в множестве П. Игрок S в начальный момент времени располагается в точке О € П, известной обоим игрокам, и осуществляет движение с вектограммой скоростей Р в множестве Я, од Р - ромбовидное множество. Каждый игрок в любой момент времеш

•'А

знает свое местоположение, но не знает местоположение противника . В момент времени, когда расстояние между игроками становится н больше г > 0, имеет место обнаружение игрока Н. Целью игрока / является максимизация времени, необходимого игроку S для его обнс ружепня. В теоремах 11.1 и 11.2 построены стратегии игрошв, позвал: юхцие определить асимптотику значения игры v(r) при малом радиу< обнаружения и показало, что'

mes(fl)

ирп г —f 0,

4

где Ль Аз - некоторые параметры псктограмыы сгоростей Р, mes(fi) мера множеств?- £7.

Основные результаты диссертации опубликованы в следующих работах. • '

1. FapHaeB А.Ю. Одна задача поиска подвижного объекта. В кн.: Математические методы оптимизации и управления в сложных системах. Калинин: Изд-во Калининского гос. ун-та, 1986, с.88-96.

2. Гарнаев А.Ю. Задача поиска движущегося объекта. В кн.: Ди-

I ' . •

намические системы и управление. Саранск: Изд-во Мордовского rocJ

ун-та, 1986, с.46-57.,

3. Гарнаев А.Ю. Об одной задаче поиска на плоскости. В кн.: Многошаговые, иерархические, дифференциальные и кооперативные игры. Калинин:' Изд-во Калининского ун-та, 1986, с.56-64.

4. Гарнаев А.Ю. Решение задачи поиска в области. Вестник ЛГУ, сер.1, 1987,вып.2, с.8-14.

5. Гарнаев А.Ю., Гарнаева Г.Ю. Об'одной дискретной игре с неполной информацией. В кн.: Математическое и программное обеспечение задач конфликтного управления. Тез. докл. семинара ВЦ АН Арм.ССР, Ереван, 1987, с.27-30. " .

6.' Гарнаев А.Ю. Одна дискретная игра на плоскости с запаздыванием информации. В кн;: Теоретико-игровые методы в разработке информационно-распознающей системы. Владивосток, ДО АН СССР,

! 1989, с.24-31.

7. Гарнаев А.Ю. Об одной теоретико-игровой задаче поиска в прямоугольнике. В кн.: Теория игр и ее приложения, Кемерово: Изд-во Кемеровского гос. ун-та, 1989, с.97-108.

, 8. Гарнаев АЛО., Седых Л.Г. Об одной дискретной игре на плоскости с запаздыванием информации. В кн.: Кибернетика н вычислительная техника. Киев: Наукова руина., 1989, вын.83, с.44-49.

9. Гарнаев А.Ю., Седых Л.Г. Одна игра nonci;а тина "кшуший-

ищущий". Автоматика, 1990, N 3, с.72-74.

10. Гарнаев А.Ю. Одна дискретная игра на плоскости с запаздыванием информации, Автоматика и телемеханика, 1989, N 12 ¿27-36.

I

11. ГарнаевА.Ю. Одна даскретнгц игра на прямой с запаздыванием информация, Автоматика и телемеханика, 1990, N 12, с.51-59.

12. Петросян Л.А., Гарнаев А.Ю. Игры поиска, Л.: Изд-во Санкт-Петербургского университета, 1992, 216с.

13. Garnaev A.Y. A search game in a rectangle. Journal of Optimization Theory and Applications, 1991, vol.69, p.531-542.

14. Garnaev A.Y. A remark on the princess and monster searLu game. International Journal of Game Theory, 1992, vol.20, p.269-276.

15. Garnaev A.Y. On simple mix game. International Journal of Game Theory, 1992, vol.21, p.234-247.

16. Garnaev A.Y. A remark on a helicopter-submarine game. Naval Research Logistics, 1993, vol.40, p.745-753.

17. Garnaev A.Y. On a mix game, Int. Year-B. Game Theory Appl., .1993, vol.1, p.25-33.

18. Garnaev A.Y. A remark on a customs and smuggler game. Nava Research Logistics, 1994, vol.41, p.287-293.

19. Garnaev A.Y. The value of sample information in a cov:r-up game Mathematica Japonica, 1995, vol.41, p.253-259.

20. В as toil V.J-, Garnaev A.Y. A Teraoka-type two-person nonzero-sur silent duel. Journal of Optimisation Theory and Applications, 1995, vol.81! p.539-551.

21. Garnaev A.Y. On a Sakaguchi's problem in non-zero-sum games < timing. Mathematica Japonica, 1996, vol.44, p.291-301.

22. Baston V.J., Garnaev A.Y. A fast infiltration game or1 n arcs. Nav Research Logistics, 1993, "ol.43, p.481-489.

23. Garnaev A.Y., Garnaeva G.Y. An infiltration game on acircumferei

20

Game Theory and Applications, 199fl, vol. 2, ,p.U-lfl.

24. Gamaev A.Y. On & problem in timing games, In; Proceeding of the Seventh Internationa) Symposium on Dynamic Gomes and Applications. Eds. J.A. Filar, V. Galtsgory and F, Imado. Birkhauser Publisher, 1988, p.271-282.

(решения от " l/djisfcj? v . I- :?

присудил ;yHí;zy>o стслек^ ДОК .Ts

I г ..............

íy Нач^ль^лк управлений ВАК Foc

//

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ АРХИТЕКТУРНО - СТРОИТЕЛЬНЫЙ УНИВЕРСИТЕТ

МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ ЗАДАЧ ПОИСКА МЕТОДАМИ ТЕОРИИ ИГР

05.13.18 - теоретические основы математического моделирования, численные методы и комплексы программ

диссертация на соискание ученой степени доктора физико-математических наук

Научный консультант:

доктор физ.-мат. наук, профессор Л .А. Пет росян

Санкт-Петербург

На пра,ва.х рукописи

ГАРНАЕВ Андрей Юрьевич

СОДЕРЖАНИЕ

Введение .......................................................... 5

Глава I. Проблемы о защите объекта ......................................................20

1. Игра на плоскости ........................................................................20

1.1. Основные результаты .......................................23

1.2. Обсуждение результатов ................................................................25

1.3. Доказательство теоремы 1.1 и леммы 1.1 ....................................26

2. Игра на прямой ............................................................................34

2.1. Случай & + 03 > 2Д ..............................................................................37

2.2. Случай 0i + 0з < 202 ..............................................................................39

2.3. Обсуждение результатов ......................................................................41

2.4. Доказательство лемм 2.1,2.2 и теорем 2.1-2.4 ............................42

2.5. Обсуждение второй проблемы Айзекса ..........................................54

2.5.1. Случай Tii + газ < 2га3 ......................................................55

2.5.2. Случай щ + щ> 2п2 ...............*...................................57

2.6. Игра на отрезке .................................................................................59

2.6.1. Случай к = 1 ..........................................................................................62

2.6.2. Случай к- 2 ..........................................................................................66

3. Проблема о таможне-контрабандисте ................................................73

4. Трехкатерный вариант проблемы таможня-контрабандист .. 80 4.1. Решение игры ............................................................................................82

5. Задача защиты объекта на графе ........................................................88

5.1. Случай к > w ..............................................................................................91

5.2. Случай wn<k<w ................................................................................101

5.3. Случай к < wn ........................................................................................106

6. Задача защиты объекта от быстрого диверсанта ......................111

6.1. Диверсант двигается вдоль одной дуги ......................................114

6.2. Основной результат .................................................................120

2

6.3. Случай простого движения охраны ...........................124

Глава II. Игры с выбором момента времени ......................................128

7. Дуэль, момент окончания которой имеет непрерывную функцию распределения ..................................................................................................128

7.1. Единственность равновесия по Нэшу .....................................137

7.2. Обсуждение результата ......................................................................145

7.3. Шумная дуэль ..........................................................................................146

7.4. Бесшумно-шумная дуэль ....................................................................151

8. Дуэль, момент окончания которой имеет дискретную функцию распределения ...................................................................154

8.1. Случай (I) ..................................................................................................157

8.2. Случай (И) ................................................................................................165

8.2.1. Подслучай (а) ......................................................................................166

8.2.2. Подслучай (Ь) ......................................................................................170

8.3. Шумная дуэль ..........................................................................................173

8.3.1. Случай Ki(p) > Ki{ 1) при г = 1,2 ..............................................173

8.3.2. Случай К{{р) < Ki( 1) при г = 1,2 ..............................................176

8.3.2. Случаи Ki(p) < Ki( 1) и Kj(p) > Kj( 1) ......................................179

8.4. Бесшумно-шумная дуэль ....................................................................180

8.4.1. Случаи К2{р) > К2{ 1) ......................................................................181

8.4.2. Случай К>(р) < #¿(1) при i = 1,2 ..............................................182

8.4.3. Случай Ki(p) > üTi(l) и Kj(p) < Kj( 1) ....................................188

9. Смешанная дуэль с фиксированным моментом окончания .. 189

10. Дуэль во время дележа ........................................................................198

Глава III. Игры поиска при отсутствии информации ....................209

11. Постановка задачи и формулировка основных результатов . 209

11.1. Оценка сверху ожидаемого времени обнаружения ................214

11.2. Оценка снизу ожидаемого времени обнаружения ..................223

Заключение ........................................................................................................236

3

Литература ................. — ............................... 239

ВВЕДЕНИЕ

Математическая теория поиска является широко разветвленной, богатой результатами и приложениями областью прикладной математики. Первоначально теория поиска развивалась преимущественно для военных целей, но в последствии выяснилось, что методы этой теории могут с успехом применяться при исследовании многочисленных проблем производства, в вопросах экономики, экологии, медицины, спорта, права, техники и бизнеса. Большой вклад в развитие теории поиска был внесен в работах Альсведе и Вегенера [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] и