Параллельные стратегии в играх преследования на сфере тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

>ГБ ОД

„ -5 Г'.-:."; и;--'

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

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

КОВШОВ Александр Михайлович

ПАРАЛЛЕЛЬНЫЕ СТРАТЕГИИ В ИГРАХ ПРЕСЛЕДОВАНИЯ НА СФЕРЕ

01.01.09— математическая кибернетика

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

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

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

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

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

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

профессор В.В.Захаров

кандидат физ.-мат. наук, доцент А. Ю. Гарнаев

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

Защита состоится " " __ 1996 в часов

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

199004, Санкт-Петербург, 10-я линия В.О. 33, аудитория 88.

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

Автореферат разослан " ^_" --1996

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

профессор В. Ф. Горьковой

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

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

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

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

Среди множества стратегий преследования значимое место занимает стратегия параллельного преследования, являющаяся наилучшей стратегией для широкого класса дифференциальных игр преследования. В работах Л. А. Петросяна впервые показана оптимальность стратегии параллельного сближения для игр простого преследования с линией жизни (1965), в игре с двумя преследователями и одним убегающим (1977) и в игре простого преследования в полуплоскости (1969). Однако, как правило, исследования ограни-

чивались играми на линейных многообразиях, либо на многообразиях, имеющих нулевую гауссову кривизну.

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

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

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

Кроме того, проводилось исследование стратегий на оптимальность в игре простого преследования на сфере и игре с линией жизни.

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

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

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

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

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

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

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

Обсугадение работы. Основные результаты работы были доложены на Международном конгрессе по компьютерным системам и прикладной математике (СБАМ'ЭЗ) в Санкт-Петербурге, на Международной конференции по интерваль-

ным вычислениям и методам компьютерной алгебры в науке и инженерии (1п1егуаГ94) в Санкт-Петербурге, на семинарах кафедры математической статистики, теории надежности и теории массового обслуживания факультета прикладной математики — процессов управления Санкт-Петербургского университета и кафедры оптимального управления факультета вычислительной математики и кибернетики Московского университета.

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

Структура и объем работы. Работа состоит из введения, трех глав, включающих 11 параграфов, и библиографии. Работа содержит 9 рисунков. Объем основной части работы составляет 110 страниц. Библиография включает 20 ссылок.

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

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

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

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

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

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

Обозначим вектор скорости убегающего за Не, а догоняющего — за г>р. Очевидно, что эти векторы являются касательными к сфере в точках Е и Р соответственно. Поставим в соответствие каждому вектору скорости по большой окружности Се и Ср (радиус большой окружности совпадает с радиусом сферы), таким образом, чтобы большие окружности проходили соответственно через точки Е и Р, а векторы уе и ьр были бы, соответственно, касательными векторами этих окружностей в этих точках. Еще одну большую окружность Сре проведем через две точки Р и Е. Эта большая окружность является пересечением сферы с плоскостью, проведенной через три точки Р, Е и центр сферы О. Эту плоскость можно однозначно построить, только если точки Р, Е и О не лежат на одной прямой, то есть, в тех случаях, когда точки Р и Е не совпадают или не являются диаметрально противоположными точками на сфере. Если хотя бы одна из больших окружностей Се и Ср не совпадает с большой окружностью Сре, то Се и Ср пересекаются ровно в двух точках на сфере.

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

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

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

У тв ер ждсние 2. Каждому выбранному направлению движения убегающего соответствует свое время движения игроков до точки встречи.

Замечание. Доказаны существование и единственность ьр, однозначно определяемого углом ф, зависящим от расстояния Л и угла тр, а угол ф задается вектором скорости убегающего ге, то есть можно ввести в рассматрение функцию ГЦ: ИР = Щ (уе, А; р,а)-

Определение. Выбор догоняющим скорости Ур по функции II1 мы будем называть параллельной геодезической стратегией преследования па сфере или просто — Щ-стратегией.

Утверждение 3. (Наискорейшее свойство Лх-стратегии). Если убегающий движется вдоль одной и той же большой окружности с постоянной скоростью <т, то догоняющий не сможет догнать его раньше момента времени t = т, определяемого П1-стратегией.

Следствие. Если убегающий движется вдоль геодезической дуги ЕМ\, а догоняющий вдоль геодезической дуги РМ\ и догоняющий попадает в точку М\ раньше догоняющего, то центр преследования М* лежит внутри геодезической дуги ЕМ\.

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

Далее рассматривается движение изменение положения игроков в движении. Исследуется Щ-стратегия при движении убегающего в точку М не по геодезической дуге, а по двузвенной ломаной линии.

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

Утверждение 5. Если в начальном положении геодезическое расстояние А между игроками принадлежит множеству А, где Л(0) = 0, --тг и{тг} , то при любом выборе убегающим напра-

р-\- (Т 1

вления своего движения, выполняются условия утверждения 4.

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

Во второй главе работы приводится доказательство

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

Теорема. (О вложенности линий мгновенных центров преследования.) Если в начальный момент времени I — 0 геодезическое расстояние А между игроками таково, что А < -л'(р— сг)/(р + сг), и убегающий движется по кусочно-гладкой траектории, а догоняющий применяет Щ-стратегию, то имеет место вложенность ГЦ-пет ель.

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

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

Утверя^цение 20. Если начальное положение игроков таково, что Щ-петля Ьц} (0) пересекает линию жизни с, то в игре с линией жизни побеждает убегающий.

Утверждение 21. Если начальное положение игроков таково, что П¡-петля ¿П1 (0) не пересекает линию жизни с, и геодезическое расстояние А(0) между игроками таково, что А(0) < 1г(р—а)/(р+т), то в игре с линией жизни побеждает догоняющий.

В третьей главе рассматривается параллельная относительная стратегия Эта стратегия является еще одним способом распространения параллельной стратегии (П-стратегии) с плоскости на сферу.

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

На сфере вводятся подвижные или относительные координаты. Пусть начало относительных координат совпадает с центром сферы, а ось Ох всегда направлена на догоняющего. Положим, что скорость убегающего сг равна 1.

Пусть в начальный момент времени догоняющий находится в некоторой точке Р. Соединим точку Р с точкой Е геодезической дугой. В работе показано, что при р > <т догоняющий сможет сближаться с убегающим, оставаясь все время на одной и той же геодезической дуге РЕ в относительных координатах.

Утвср ждение 25. Если на, плоскости и на сфере угол между вектором скорости убегающего у^ л вектором направления на догоняющего к один и тот же, то на сфере скорость сближения игроков будет не меньше, чем на плоскости.

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

Рассмотривается игра простого преследования на многомерной сфере.

Пусть сфера Б"-1 находится в гс-мерном евклидовом пространстве Л", в котором задан ортонормированный базис О = {¿1,..., е„}. И пусть центр сферы совпадает с началом координат. Сфера 5Г1_1 состоит из таких точек А Е Лп, у которых радиус-вектор гд имеет единичную длину. На сфере присутствуют п + 1 игроков, представляющие собой подвижные точки. Одна из этих точек — убегающий, остальные —

догоняющие. Будем обозначать точку, в которой находится убегающий буквой Е, а точки, в которых находятся догоняющие — г = 1, п, где г — порядковый номер догоняющего.

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

ВЫВОДЫ

В первых двух главах рассмотрен один из способов распространения на сферу стратегии параллельного преследования на плоскости.

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

Удалось показать, что успешность Щ-стратегии качественно зависит от геодезического расстояния между игроками в начальный момент игры. При этом можно выделить следующие промежутки:

к = [0,Л°]:

Ь =

О, тг

р- а

р+ а

1з =

р + а

<т р — а , *-

и

р-и

ТГ-, 7Г

Для расстояний между игроками из 1\, где

\о = (р-а)т\

а т является корнем уравнения

о

бн! сгт'

эт рт

.о

■о

Щ-стратегия обладает всеми основными свойствами П-стра-тегии на плоскости, являясь оптимальной в игре простого преследования и в игре с линией жизни.

При геодезических расстояниях между игроками из 12 Щ-стратегия сохранет оптимальность в игре с линией жизни, поскольку на таких расстояниях сохраняется вложенность стратегических петель (на плоскости стратегической петлей для П-стратегии является окружность Аполлония), однако в игре простого преследования без фазовых ограничений оптимальности уже нет, поскольку существуют стратегии убегания, позволяющие сделать скорость сближения меньше р — а.

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

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

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

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

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

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

1. Kovshov А. М. The pursuit дате on a sphere. — International Congress on Computer System and Applied Mathematics CSAM'93, Abstracts, 1993, St. Peterburg, p. 29.

2. Kovshov A. M. Two-person Pursuit Game on the Half-sphere. — International Conference on Interval and Computer-Algebraic Methods in Science and Engineering INTERVAL'94, 1994, St. Peterburg, p. 148-149.

3. Ковшов A. M. Игра простого преследования несколькими объектами на сфере. — Тезисы докладов конференции "Моделирование и исследование устойчивости систем, 1994, Киев, с. 64-65.