Авторефераты по всем темам  >>  Авторефераты по разным специальностям САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

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

ПАНКРАТОВА Ярославна Борисовна

C-ЯДРО В КООПЕРАТИВНЫХ ИГРАХ ГРУППОВОГО ПРЕСЛЕДОВАНИЯ

Специальность 01.01.09 - дискретная математика и математическая кибернетика А В Т О Р Е Ф Е Р А Т диссертации на соискание ученой степени кандидата физико-математических наук

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

Работа выполнена на кафедре Математической теории игр и статистических решений факультета Прикладной математики - процессов управления Санкт - Петербургского Государственного Университета.

Научный консультант: кандидат физико-математических наук, доцент Тарашнина Светлана Ивановна

Официальные оппоненты: доктор физико-математических наук, профессор Клейменов Анатолий Федорович кандидат физико-математических наук, Зятчин Андрей Васильевич

Ведущая организация: Институт прикладных математических исследований Карельского научного центра РАН (г. Петрозаводск)

Защита состоится "19" декабря 2012 г. в 17:00 час. на заседании диссертационного совета Д 212.232.59 по защите диссертаций на соискание ученой степени кандидата физико-математических наук при Санкт-Петербургском государственном университете по адресу: 190034, Санкт-Петербург, В.О., Средний пр., д. 41/43, ауд. 511.

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

Автореферат разослан " " 2012 г.

Ученый секретарь диссертационного совета, доктор физ.-мат. наук, профессор В. Д. Ногин

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

Основополагающий вклад в развитие теории дифференциальных игр внесли Н.Н. Красовский и Л.С. Понтрягин. Также фундаментальные результаты в области теории дифференциальных игр преследования получены в работах Э.Г. Альбрехта, М. Барди, Т. Башара, Р. Беллмана, А. Брайсона, Н.Л. Григоренко, Р.В. Гамкрелидзе, В.И. Жуковского, М.И. Зеликина, А.Ф. Клейменова, А.Н. Красовского, А.В. Кряжимского, В.Н. Лагунова, О.А. Малафеева, А.А. Меликяна, Е.Ф. Мищенко, М.С. Никольского, Г. Ольсдера, Ю.С. Осипова, Н.Н. Петрова, Л.А. Петросяна, Б.Н. Пшеничного, А.И. Субботина, Г.В. Томского, А. Фридмана Ф.Л. Черноусько, А.А. Чикрия, С.В. Чистякова и многих других.

Неантагонистические дифференциальные игры преследования являются в настоящее время недостаточно изученными. Здесь следует отметить работу Л.А. Петросяна и В.Д. Ширяева, в которой впервые задача преследования формализована как неантагонистическая дифференциальная игра преследования с одним преследователем и двумя убегающими на плоскости, получившая свое развитие в работах С.И. Тарашниной.

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

Основа теории кооперативных дифференциальных игр была построена Л.А. Петросяном, в развитие которой в различное время свой вклад внесли Н.Н. Данилов, Дж. Заккур, В.В. Захаров, Н.А. Зенкевич, В.И. Жуковский, С. Йоргенсен, А.Ф. Клейменов, А.Ф. Кононенко, Дж.А. Филлар, С.В Чистяков, Д.В.К. Янг и многие другие.

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

Свойство динамической устойчивости, введенное Л.А. Петросяном, означает, что игроки в каждый момент игры не имеют причин отклоняться от первоначально выбранного УоптимальногоФ поведения.

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

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

определен класс кооперативных игр преследования с одним убегающим и m преследователями и дано аналитическое описание C-ядра для случая максимального числа крайних точек, доказана его непустота и динамическая устойчивость; для неантагонистической игры простого преследования с одним преследователем и m убегающими введено понятие области эффективности стратегии наказания преследователя; определен класс кооперативных игр преследования с одним преследователем и m убегающими, построено C-ядро и доказана его непустота;

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

Основные положения, выносимые на защиту:

1. Найдено множество ситуаций равновесия по Нэшу в неантагонистической игре преследования с одним убегающим и m преследователями.

2. Для неантагонистической игры преследования с одним убегающим и m преследователями предложена формализация в виде кооперативной игры группового преследования с трансферабельными полезностями.

3. Доказано, что в кооперативной игре группового преследования с одним убегающим и m преследователями существует непустое C-ядро для любых начальных местоположений игроков.

4. Получено аналитическое описание C-ядра для случая максимального числа крайних точек в кооперативной игре группового преследования с одним убегающим и m преследователями.

5. Доказана динамическая устойчивость C-ядра в кооперативной игре группового преследования с одним убегающим и m преследователями.

6. Для неантагонистической игры простого преследования с одним преследователем и m убегающими предложена формализация в виде кооперативной игры группового преследования с трансферабельными полезностями.

7. Доказано, что в кооперативной игре группового преследования с одним преследователем и m убегающими существует непустое C-ядро для любых начальных местоположений игроков.

Апробация работы. Основные результаты работы представлены на семинарах кафедры математической теории игр и статистических решений Санкт-Петербургского государственного университета, на семинарах Центра теории игр, на 3-й международной конференции УSpain Italy Netherlands Meeting on Game TheoryФ (Мадрид, 2007), на 2-й, 3-й и 4-й Международных конференциях УGame Theory and ManagementФ (Санкт-Петербург, 2008, 2009, 2010), на Всероссийской конференции УУстойчивость и процессы управленияФ, посвященной 80-летию со дня рождения В.И. Зубова (Санкт-Петербург, 2010), на 24-й Европейской конференции по исследованию операций (Лиссабон, 2010), на 25-й Европейской конференции по исследованию операций (Вильнюс, 2012), на семинаре института прикладных математических исследований Карельского научного центра РАН (г. Петрозаводск).

По материалам диссертации опубликованы работы [1Ц11].

Структура и объем работы. Диссертация состоит из введения, двух глав, разбитых на параграфы, заключения, списка используемой литературы и двух приложений. Общий объем диссертации 131 страница. Список используемой литературы включает 61 наименование. Работа содержит 27 рисунков и 1 таблицу.

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

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

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

В з 1.1 вводится определение игры простого преследования с одним убегающим и m преследователями.

Рассмотрим игру простого преследования, в которой участвуют m преследователей P1,..., Pm и один убегающий E. Преследование происходит на плоскости.

Игроки имеют ограниченные по модулю скорости. Максимальные скорости игроков обозначим через 1,..., m и , соответственно, причем < min{1,..., m}.

0 0 0 Игра начинается в момент времени t0 = 0 из положений P1 = z1,..., Pm = zm, E0 = z0. Каждый игрок в момент t 0 выбирает направление своего движения (вектор скорости) из своего множества допустимых управлений. Множества допустимых управлений игроков определяются следующим образом UP = { uP = (u1, u2 ) : (u1 )2 + (u2 )2 j}, j = 1, m, j j Pj Pj Pj Pj UE = { uE = (u1, u2 ) : (u1 )2 + (u2 )2 2}.

E E E E Игроки P1,..., Pm и E двигаются на плоскости с ограниченными скоростями, выбирая в каждый момент времени параметры uP UP,..., uP UP и uE UE.

1 1 m m Движение игроков описывается следующей системой дифференциальных уравнений j = uP, uP UP, j = 1, m, j j j (1) = uE, uE UE с начальными условиями 0 z1(0) = z1,..., zm(0) = zm, z(0) = z0. (2) t t t t Обозначим через P1 = z1,..., Pm = zm, Et = zt местоположения игроков в 0 произвольный момент t при движении из начальных точек z1,..., zm, z0. Будем рассматривать случай полной информации, то есть игрокам в каждый момент времени t при выборе направления своего движения известно время t и фазовые состояния свое и остальных игроков. При этом предполагается, что преследователи P1, P2,..., Pm в каждый текущий момент t обладают информацией о выборе вектора ut убегающим E в этот же момент. В этом случае говорят, что игрок E E дискриминирован.

Под стратегией игрока будем понимать функцию, зависящую от времени и текущих местоположений всех игроков. Другими словами, стратегией игрока E явt t ляется функция uE(t, z1,..., zm, zt), удовлетворяющая системе (1) с начальными условиями (2). Множество стратегий убегающего E обозначим через UE. Из условия дискриминированности игрока E следует, что стратегия преследователя Pj это функция, зависящая от времени, местоположений игроков и вектора скоt t рости убегающего E, т.е. uP (t, z1,..., zm, zt, ut ). Обозначим через UP множество j E j допустимых стратегий игрока Pj (j = 1, m).

Определим момент окончания игры. Будем считать, что убегающий пойман преследователем Pj, если местоположения игроков Pj и E в некоторый момент времени совпадут. Тогда время поимки tP преследователем Pj убегающего E опреj деляется следующим образом 0 0 t tP (z1,..., zm, z0, uP (),..., uP (), uE()) = min{t : zj = zt}, j = 1, m.

j 1 m Если такого t не найдется, то будем считать tP = +.

j 0 Пусть tE(z1,..., zm, z0, uP (),..., uP (), uE()) = min{tP,..., tP }. Здесь tE пер1 m 1 m вый момент встречи убегающего E с одним из преследователей. Игра заканчивается в момент времени tE.

Выигрыш убегающего E определим как время встречи с первым из преследователей, умноженное на число ( > 0) УценуФ единицы времени. Тогда 0 KE(z1,..., zm, z0, uP (),..., uP (), uE()) = 1 m (3) 0 = tE(z1,..., zm, z0, uP (),..., uP (), uE()).

1 m Выигрыш игрока Pj (j = 1, m) положим равным 0 KP (z1,..., zm, z0, uP (),..., uP (), uE()) = j 1 m (4) 0 = - tP (z1,..., zm, z0, uP (),..., uP (), uE()).

j 1 m Рассматриваемая игра преследования может быть формализована в виде неан0 тагонистической игры в нормальной форме (z1,..., zm, z0) = N, {Ui}iN, {Ki}iN, где N = {P1,..., Pm, E} множество игроков, Ui множество допустимых стратегий i-го игрока и Ki - функция выигрыша i-го игрока (i N), определяемая формулами (3) и (4).

В з 1.2 определяются координаты точек пересечения окружностей Аполлония и доказываются некоторые вспомогательные результаты.

Для нахождения решения построенной игры преследования важно знать координаты точек пересечения соответствующих окружностей Аполлония. Mножество 0 всех точек пересечения окружностей Аполлония в игре (z1,..., zm, z0) запишем в виде A = {zij}, i = j, i, j = 1, m, при этом через ij будем обозначать наиболее 0 удаленную от E точку пересечения окружностей Аполлония A(zi, z0) и A(zj, z0).

t t Зафиксируем момент времени t и построим подыгру (z1,..., zm, zt), которая отличается от первоначальной игры только начальными местоположениями игроков. В работе выводятся формулы для вычисления координат точек пересечения окружностей Аполлония в произвольный момент времени t 0.

Для определения траекторий движения точек пересечения окружностей Аполлония в процессе преследования доказывается следующая лемма.

t t Лемма 1 Для любой подыгры (z1,..., zm, zt) игры преследования 0 (z1,..., zm, z0) выполняется равенство t zt - zij = 1 - z0 - zij, tE 0 где zij точка пересечения окружностей Аполлония A(zi, z0) и A(zj, z0), i = j, i, j = 1, m, и zt лежит на отрезке, соединяющем точки z0 и zij, т.е. расстояние от убегающего E в момент времени t > 0 до любой точки пересечения окружностей Аполлония линейно по t зависит от расстояния между убегающим в начальный момент времени и той же точкой Аполлония.

В з 1.3 находится некооперативное решение вышеуказанной игры в форме равновесия по Нэшу.

Приведем теорему существования ситуации равновесия по Нэшу в построенной 0 неантагонистической игре преследования (z1,..., zm, z0).

0 Теорема 1 В игре (z1,..., zm, z0) существует ситуация равновесия по Нэшу (u,..., u, u ), которая предписывает игрокам следующее поведение:

P1 Pm E Х игрок E движется прямолинейно с максимальной скоростью в точку , где = arg max z0 - zij, i = j, i, j = 1, m, zijA1...Am zij точки пересечения окружностей Аполлония, которые попадают в пересечение всех кругов Аполлония;

Х игроки P1,..., Pm используют стратегию параллельного сближения.

В з 1.4 строится кооперативный вариант игры группового преследования и доказывается, что характеристическая функция построенной кооперативной игры является супераддитивной.

0 Каждой неантагонистической игре (z1,..., zm, z0) поставим в соответствие некоторую кооперативную игру в форме характеристической функции 0 v(z1,..., zm, z0). Предположим, что каждый преследователь использует стратегию параллельного сближения. Характеристическую функцию игры определим следующим образом:

zj1 - z0.

0 v({Pj1}, z1,..., zm, z0) = - = gj1, j1 = 1, m, j1 - z0 - .

0 v({E}, z1,..., zm, z0) = = g0, 0 v({Pj1, E}, z1,..., zm, z0) = 0, j1 = 1, m, z0 - j1j2. 0 v({Pj1, Pj2}, z1,..., zm, z0) = -2 = -2j1j2, j1, j2 = 1, m, j1 = j2, z0 - zj1j2.

0 v({Pj1, Pj2, E}, z1,..., zm, z0) = - = -j1j2, j1, j2 = 1, m, j1 = j2, g...

z0 - j1...jm-1.

0 v({Pj1, Pj2,..., Pjm-1}, z1,..., zm, z0) = -(m - 1) = -(m - 1)j1...jm-1, j1,..., jm-1 = 1, m, j1 =... = jm-1, z0 - zj1...jm-1.

.

0 v({Pj1, Pj2,..., Pjm-1, E}, z1,..., zm, z0) = -(m - 2) = -(m - 2)gj1...jm-1, j1,..., jm-1 = 1, m, j1 =... = jm-1, z0 - .

0 v({P1,..., Pm}, z1,..., zm, z0) = -m = -mg0, z0 - z.

0 v({P1,..., Pm, E}, z1,..., zm, z0) = -(m - 1) = -(m - 1)g, (5) где zj1j2 = arg min z0 - z, j1, j2 = 1, m, j1 = j2, z(Aj1 Aj2 )...

zj1,...,jm-1 = arg min z0 - z, j1,..., jm-1 = 1, m, j1 =... = jm-1, z(Aj1 ...Ajm-1 ) z = arg min z0 - z, z(A1...Am) j1j2 = arg max z0 - z, j1, j2 = 1, m, zAj1 Aj...

j1...jm-1 = arg max z0 - z, j1,..., jm-1 = 1, m, j1 =... = jm-1, zAj1 Aj2 ...Ajm- = arg max z0 - z, zA1...Am через (Aj ... Aj ) обозначается граница множества A1 ... Am.

1 m Под кооперативным поведением понимается поведение, которое предполагает движение всех игроков с максимальной скоростью в точку z ближайшую к начальному местоположению игрока E точку, лежащую на границе множества пересечения всех кругов Аполлония.

0 Определение 1 Пару N, v(S; z1,..., zm, z0), S N, где N = P1,..., Pm, E множество игроков и v характеристическая функция, определяемая формулами (5), будем называть кооперативной игрой преследования или ТП игрой, соответ0 0 0 ствующей игре (z1,..., zm, z0), и обозначать v(z1,..., zm, z0).

0 Теорема 2 В игре v(z1,..., zm, z0) характеристическая функция v, определяемая формулами (5), является супераддитивной.

В з 1.5 строится решение кооперативной игры в форме C-ядра и доказывается его непустота. Получено аналитическое представление C-ядра для случая максимального числа крайних точек.

0 В качестве решения кооперативной игры преследования v(z1,..., zm, z0) рас0 сматривается C-ядро Cv(z1,..., zm, z0). Главным недостатком этого решения является тот факт, что оно не всегда реализуемо, т.е. может оказаться пустым. До0 казывается, что C-ядро для игры v(z1,..., zm, z0) непусто для любых начальных местоположений игроков.

Теорема 3 В кооперативной дифференциальной игре преследования 0 v(z1,..., zm, z0) существует непустое C-ядро для любых начальных местоположений игроков.

В з 1.6 доказывается динамическая устойчивость C-ядра.

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

Теорема 4 В кооперативной дифференциальной игре преследования 0 v z1,..., zm, z0 C-ядро является динамически устойчивым.

Для доказательства динамической устойчивости C-ядра используется аналитическое представление C-ядра, построенного для случая максимального числа край0 них точек. C-ядро в игре v z1,..., zm, z0 представляет собой выпуклую линейную оболочку следующих дележей:

1 = (-g0, -g,..., -g, -g, g0),...

m = (-g, -g,..., -g, -g0, g0), 0 m+1 = (-g1, -g,..., -g, -g, g1), 0 m+2 = (-g, -g2,..., -g, -g, g2),...

0 2m = (-g, -g,..., -g, -gm, -gm), 0 2m+1 = (-g1, g1 - 2g0,..., -g, -g, 2g0 - g),...

0 3m-1 = (-g1, -g,..., -g, g1 - 2g0, 2g0 - g), 0 3m = (g2 - 2g0, -g2,..., -g, -g, 2g0 - g),...

0 4m-2 = (-g, -g2,..., -g, g2 - 2g0, 2g0 - g),...

0 m +2 = (gm - 2g0, -g,..., -g, -gm, 2g0 - g),...

0 m +m = (-g, -g,..., gm - 2g0, -gm, 2g0 - g).

В з 1.7 рассматриваются примеры, иллюстрирующие полученные результаты.

Во второй главе рассматривается неантагонистическая игра группового преследования с одним преследователем и m убегающими.

В з 2.1 вводится определение неантагонистический игры простого преследования с одним преследователем и m убегающими.

Рассмотрим неантагонистическую игру простого преследования, в которой участвуют преследователь P и убегающие E1,..., Em. Игра происходит в плоскости, движения игроков простые. Будем считать, что игроки E1,..., Em дискриминированы, т. е. преследователь в каждый момент времени знает направления движения (векторы скоростей) убегающих игроков в этот же момент времени. Движение иг0 0 роков начинается в момент времени t = 0 из начальных положений zP, z1,..., zm.

Пусть максимальная скорость преследователя P, i максимальная скорость t t убегающего Ei (i = 1, m), причем > max i. Обозначим через Ei = zi местоi=1,...,m t t положение убегающего Ei в момент времени t, а через P = zP местоположение преследователя в момент времени t, t > 0.

Движения игроков описываются следующей системой дифференциальных уравнений zP = uP, uP UP, (6) zi = uE, uE UE, i = 1, m, i i i с начальными условиями 0 zP (0) = zP, zi(0) = zi, i = 1, m, (7) где zP, z1,..., zm R. Множества допустимых управлений UP, UE имеют следуi ющий вид UP = {uP = (u1, u2 ) : (u1 )2 + (u2 )2 = 2}, P P P P UE = {uE = (u1, u2 ) : (u1 )2 + (u2 )2 = i }, i = 1, m.

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

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

t t t Стратегией убегающего Ei является функция uE (t, zP, z1,..., zm), удовлетвоi ряющая системе (6) с начальными условиями (7). Обозначим через UE множество i допустимых стратегий игрока Ei, i = 1, m. Стратегию преследователя P определим как функцию времени, местоположений всех игроков и векторов скоростей t t t убегающих, т.е. как функцию uP (t, zP, z1,..., zm, ut,..., ut ).

E1 Em Далее поясним, как происходит игра. Игрок P в начальный момент времени диктует убегающим E1,..., Em определенный способ поведения и выбирает порядок очередности встреч с убегающими. Для этого он фиксирует некоторый порядок и вычисляет общее время преследования, учитывая то, что убегающие используют предписанное поведение. Затем игрок P последовательно преследует убегающих, используя -стратегию, в соответствии с выбранным порядком.

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

Обозначим множество всех возможных порядков преследования через . Введем определение стратегии наказания преследователя P.

Определение 2 Будем говорить, что тройка u = , uP, p называется стратеP гией наказания преследователя P, где 0 0 Х (zP, z1,..., zm, uE,..., uE ) порядок преследования, выбранный пресле1 m дователем в начальный момент времени t = 0 для некоторого фиксированного набора стратегий убегающих uE,..., uE ;

1 m t t t Х uP (t, zP, z1,..., zm, ut,..., ut ), t 0, стратегия преследования, заклюE1 Em чающаяся в последовательном преследовании убегающих игроком P ;

Х p = p(t, ut,..., ut ) элемент наказания, который состоит в изменении E1 Em порядка преследования в случае, если вектор скорости какого-либо из убегающих в момент времени t будет отличен от соответствующей компоненты вектора (ut,..., ut ).

E1 Em Множество стратегий наказания преследователя обозначим через UP = {u }.

P Определим момент окончания игры. Убегающий Ei считается пойманным, если местоположения игроков P и Ei в некоторый момент времени совпадают. Под окончанием игры понимается момент поимки преследователем последнего убегающего.

Предположим, что выбранный преследователем порядок очередности встреч имеет вид = {1,..., i,..., m}.

Определим выигрыш Ei как KE (u, uE,..., uE,..., uE ) = Tk, (8) i P 1 i m ki, k=1,m где Tk время, потраченное преследователем на поимку убегающего Ek (k = 1, m) в соответствии с порядком преследования . Индекс i обозначает очередность преследования убегающего Ei в соответствии с выбранным порядком преследования = {1,..., i,..., m}, а индекс k (k i) соответствует убегающим, преследуемым до игрока Ei включительно.

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

KP (u, uE,..., uE ) = -T, (9) P 1 m m где T = Tk общее время преследования в игре и выбранный порядок k=преследования.

Рассматриваемую неантагонистическую игру преследования представим в нор0 0 мальной форме (zP, z1..., zm) = N, {Ui}iN, {Ki}iN, где N = {P, E1,..., Em} множество игроков, Ui множество допустимых стратегий i-го игрока и Ki функция выигрыша i-го игрока (i N), определяемая формулами (8) и (9).

0 0 В з 2.2 описываются множества стратегий игроков в игре (zP, z1..., zm).

Множество стратегий игрока P составляют функции u, соответствующие разP личным порядкам преследования . Игрок P стремится минимизировать общее время преследования, а убегающие стремятся, по возможности, оттянуть момент поимки. Другими словами, среди m! различных порядков преследования преследователь выбирает тот порядок, который дает наименьшее общее время преследования. Обозначим его через и соответствующую стратегию преследо вателя через u.

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

j Пусть Ei убегающий, которого P преследует в данный момент времени, j j {1,..., m} (будем называть его текущим убегающим); Ei j-й по порядку преследования убегающий среди непойманных, j {1,..., m}, j > j.

Опишем два типа поведения убегающего Ei (i = 1, m):

j Х Игрок Ei, j {1,..., m}, использует тип поведения [uj ], в соответствии Ei с которым движется с максимальной скоростью вдоль прямой, проходящей j через местоположения игроков P и Ei в момент начала его преследования, в направлении от P (в предполагаемую точку его поимки Nj ).

j Х Игрок Ei, j {1,... m}, использует тип поведения [uj ], в соответствии с Ei которым движется по прямой c максимальной скоростью к точке встречи j преследователя P с текущим убегающим Ei, j > j, то есть к точке Nj, где Tj j Nj = P и Tj время встречи преследователя P с убегающим Ei.

В течение всей игры в некоторый момент tE > 0 каждый убегающий Ei измеi j j няет свой тип поведения с Ei на Ei. Следовательно, стратегия u (t, ) убегающего Ei Ei (i = 2, m) может быть представлена как [uj ], 0 t < tE, Ei i u (t, ) = Ei [uj ], t tE.

Ei i Следует отметить, что игрок E1 использует только поведение [uj ] и его страEi тегия имеет вид u (t, ) = [uj ], t 0.

E1 E В работе выписаны условия, при которых ситуация (u, u,..., u ) является P E1 Em равновесной по Нэшу.

В з 2.3 представлены неравенства, обеспечивающие существование описанного равновесия по Нэшу в стратегиях наказания.

В з 2.4 введены определения эффективной по отношению к убегающему стратегии наказания, полностью эффективной стратегии наказания и области эффективности стратегии наказания преследователя. Кроме того, приведены примеры построения областей эффективности стратегии наказания.

Определение 3 Стратегию наказания преследователя P будем называть эффективной по отношению к убегающему Ei, если время жизни игрока Ei, i {2,..., m}, в случае следования предписанной преследователем стратегии u, будет больше, Ei чем если он от нее отклонится.

Определение 4 Стратегию наказания преследователя P будем называть полно0 0 стью эффективной в игре (zP, z1,..., zm), если она эффективна по отношению ко всем убегающим Ei, i = 2, m.

В з 2.5 строится кооперативная игра группового преследования с одним преследователем и m убегающими и доказывается, что характеристическая функция построенной кооперативной игры является супераддитивной.

Рассмотрим произвольную перестановку упорядоченного множества индексов M = {1, 2,..., m}. С этой перестановкой связана подстановка k, т.е. такая взаимно-однозначная функция k : M M, что для k M значение k M представляет собой элемент из M, в который переходит k M в перестановке .

Определим характеристическую функцию игры следующим образом:

0 0 , v({P }; zP, z1,..., zm) = -T 0 0 v({Ei }; zP, z1,..., zm) = Ti, i1 = 1, m, 1 0 0 v({P, Ei }; zP, z1,..., zm) = Ti, i1 = 1, m, 1 0 0 v({Ei, Ei }; zP, z1,..., zm) = Ti i2, i1, i2 = 1, m, i1 = i2, 1 2 (10) 0 0 v({P, Ei, Ei }; zP, z1,..., zm) = Ti i2, i1, i2 = 1, m, i1 = i2, 1 2...

0 0 v({E1,..., Em}; zP, z1,..., zm) = Ti...im, 0 0 0 v({P, E1,..., Em}; zP, z1,..., zm) = T, где Ti = min Tk, ki Ti i2 = min Tk + Tk, ki1 ki...

im-i2 im Ti i2...im = min Ti + Tk +... + Tk + Tk, 1 k=i1 k=i1 k=i T = max - T, (11) Ti = max -T + Tk, ki Ti i2 = max - T + Tk + Tk, ki1 ki...

im-i T = max Ti + Tk +... + Tk.

1 k=i1 k=i0 0 Определение 5 Пару N, v(S; zP, z1,..., zm), S N, где N множество игроков и v характеристическая функция, определенная формулами (10)-(11), будем называть кооперативной игрой преследования или ТП игрой, соответствующей иг0 0 0 0 0 ре преследования (zP, z1,..., zm), и обозначать v(zP, z1,..., zm).

0 0 Теорема 5 В игре v(zP, z1,..., zm) характеристическая функция v, определяемая формулами (10)-(11), является супераддитивной.

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

0 0 Теорема 6 В кооперативной игре преследования v(zP, z1,..., zm) существует непустое C-ядро для любых начальных местоположений игроков.

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

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ Публикации в изданиях, рекомендованных ВАК 1. Панкратова Я.Б. Решение кооперативной дифференциальной игры группового преследования. Дискретный анализ и исследование операций. 2010.

т. 17, № 2, с. 57-78.

2. Pankratova Ya., Tarashnina S. How many people can be controlled in a group pursuit game. Theory and Decision. Kluwer Academic Publishers. 2004. 56, p. 165181.

Публикации в других изданиях 3. Pankratova Y. A cooperative version of one group pursuit game // 25 European Conference on Operational Reseach, Vilnuis, 2012, p. 221.

4. Панкратова Я.Б. Кооперация в одной игре группового преследования // Всероссийская конференция посвященная 80-летию со дня рождения В.И. Зубова УУстойчивость и процессы управленияФ, СПб, 2010. с. 168Ц169.

5. Pankratova Y., Tarashnina S., Marchenko I. Cooperative solutions for a group pursuit game between a pursuer and m evaders // The 4-th International Conference Game Theory and Management, St.Petersburg, 2010. p. 123-124.

6. Pankratova Y. Cooperation in a group pursuit game // 24 European Conference on Operational Reseach, Lisbon, 2010. p. 295.

7. Pankratova Ya., Tarashnina S. The importance of cooperation in a group pursuit game between a pursuer and m evaders // The Third International Conference Game Theory and Management, St.Petersburg, 2009. p. 198-199.

8. Pankratova Ya., Tarashnina S. Time-consistency of the core in group pursuit games // The Second International Conference Game Theory and Management, St.Petersburg, 2008. p. 216.

9. Pankratova Y. Some cases of cooperation in differential pursuit games. Contribu tions to Game Theory and Management. Collected papers. / Editors L.A. Petrosjan, N.A. Zenkevich. St.Petersburg. Graduated School of Management, SPbGU, 2007.

p. 361-380.

10. Pankratova Y. On cooperative differential game of pursuit // SING3. Spain Italy Netherlands Meeting on Game Theory. Madrid, 2007. p. 127.

11. Pankratova Ya., Tarashnina S. How many people can be controlled in a group pursuit game. The volume УEssays on Cooperative Games - in honor of Guillermo OwenФ. Kluwer Academic Publishers. 2004. p. 165-181 (reprint from УTheory and DecisionФ).

   Авторефераты по всем темам  >>  Авторефераты по разным специальностям