Численные методы решения задач группового преследования тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

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

На плавя* т/*-«—иси

OQ344D^OU

Варламова Анастасия Гаврииловна

ЧИСЛЕННЫЕ МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ГРУППОВОГО ПРЕСЛЕДОВАНИЯ

01 01 09 — дискретная математика и математическая кибернетика

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

РГБ ОД

2 е АВГ 2008

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

003445456

Работа выполнена на кафедре математической экономики Института математики и информатики ГОУ ВПО "Якутский государственный университет имени М К Аммосова"

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

профессор Леон Аганесович Петросян

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

Николай Никандрович Петров, доктор физико-математических наук, Андрей Юрьевич Гарнаев

Ведущая организация

ГОУ ВПО «Кемеровский государственный Университет»

Защита состоится «29» октября 2008 г в 16 часов на заседании совета Д 212 232 59 по защитам докторских и кандидатских диссертаций при Санкт-Петербургском государственном университете по адресу 199004, В О, Средний пр , д 41/43, ауд 513

С диссертацией можно ознакомиться в научной библиотеке им М Горького Санкт-Петербургского Государственного Университета

Автореферат разослан «/¡^ » июля 2008 г

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

доктор физ -мат наук, профессор В Д Ногин

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

Актуальность темы. Объектами исследования данной диссертационной работы являются задачи группового простого преследования со многими участниками, а именно задачи с использованием преследователем П-стратегии или стратегии параллельного сближения

Основоположником теории дифференциальных игр стал Р Айзеке, впервые определивший понятие "дифференциальная игра" В нашей стране динамические задачи конфликтного управления рассматриваются с 1965 года Первые работы в этой области принадлежат Н Н Красовскому, Л С Понтрягину и Л А Петросяну, заложившим основу развития теории дифференциальных игр в СССР и в постсоветском пространстве

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

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

Данная работа базируется на геометрическом подходе к задачам простого преследования, который был предложен в работах Л А Петросяна, В Д Ширяева, Г В Томского, Б Б Рихсиева, Н А Зенкевича

В диссертационной работе исследуется задача простого преследования с одним преследователем и несколькими убегающими Эта задача исследуется в антагонистической постановке, когда убегающие игроки действуют как один игрок Задача такого рода ранее рассматривалась в литературе по теории игр Полное решение задачи преследования на плоскости с одним преследователем и двумя убегающими при дополнительном предположении, что преследователь использует стратеыпо параллельного сближения и не меняет порядок преследования в процессе игры представлено в работе Л А Петросяна и В Д Ширяева Учитывая сказанное, едва ли можно было ожидать полного решения рассматриваемой задачи Поэтому мы пошли по пути построения численных методов, позволяющих моделировать процесс преследования на ЭВМ, используя для построения стратегии убегающих с определенными свойствами, оптимальность которых обоснована в более простых случаях К числу таких свойств относится использование прямолинейных движений убегающими, что доказано нами в параграфе ] 1 главы 1 для задачи преследования с "линией жизни" и задержкой у преследователя, а также для задачи преследования с одним преследователем и двумя убегающими в пространстве Таким же образом рассматривается метод касательных, оптимальность которого доказана в задаче преследования с двумя убегающими и доказан нами для случая трехмерного пространства в параграфах 2 1, 2 2, главы 2

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

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

1 Рассмотрена задача простого преследования с "линией жизни", когда преследователь начинает движение с задержкой времени Найдены оптимальные стратегии убегающего и преследователя

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

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

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

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

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

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

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

Апробация работы. Результаты диссертационной работы неоднократно докладывались и обсуждались на XIII Международной конференции студентов, аспирантов и молодых ученых «Ломоносов», секции Вычислительная математика и кибернетика (Москва 2006), на семинаре "Теория игр и конфликтно управляемые процессы" под руководством заведующего кафедрой математической экономики С П Кайгородова, на научной конференции "Лаврентьевские чтения РС(Я)" (Якутск 2002, 2004, 2005), на IV Международной конференции по математическому моделированию (Якутск, 2004), на Всероссийской школе-семинаре "Математическое моделирование развития северных территорий" (Якутск 2004, 2005, 2006, 2008)

Публикации. Основные результаты диссертации опубликованы в 14 работах — 9 тезисах и докладах, 5 статьях

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

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

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

В первой главе рассматривается задача простого преследования со многими участниками на двумерной плоскости Глава состоит из четырех параграфов

В первом параграфе главы рассмотрена задача простого преследования с "линией жизни" и задержкой времени у преследователя Рассматривается антагонистический случай Предположим, что задано некоторое замкнутое выпуклое множество 5 с К2 Две точки — преследователь Р и убегающий Е, обладая ограниченными по модулю линейными скоростями аир соответственно, перемещаются во множестве 5, имея при этом возможность в каждый момент времени изменять направление движения (простое движение), причем а>Р Игра происходит следующим образом Пусть задано некоторое число Т> 0, называемое задержкой времени у преследователя с момента начала игры В течении времени Т преследователь остается неподвижным, а убегающии начинает движение с начала игры Игра заканчивается, как только убегающий Е достигает "линии жизни" — границы заданного множества Ь' — или происходит захват до достижения границы множества Л' Считается, что захват произошел, если расстояние между ним и преследователем Р достигает значения, равного / (/ = 0) В начальный момент времени игроки находятся во множестве 5, и целью убегающего Е является достижение границы множества 5 до момента поимки Игрок Р преследует противоположную цель, т е стремится осуществить поимку до того, как тот достигнет "линии жизни" Предполагается также, что преследователь Р использует П-стратегию или стратегию параллельного сближения Пусть Р°, Е° — начальные местоположения игроков Р и Е Для различных Р° и Е° имеем различные игры преследования с "линией жизни" и задержкой времени Т > 0 у

7

преследователя с момента начала игры, которые будем обозначать через ГТ(Р°,Е°,s) Рассмотрим игру, когда убегающий меняет направление движения конечное число раз Доказана теорема

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

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

U{P°,ET) — те во множестве точек N,

для которых выполняется условие

p(N,P°)(0>p{N,ET), <a = @-, (1)

а

где Р0(е°) —начальное местоположение игрока Р{Е), Ет —множество точек, определяющих местоположение игрока Е в момент времени Т > 0 при его прямолинейном движении, а (/?) — постоянная линейная скорость убегающего (преследователя)

Решим игру с "линией жизни" Гт(р° ,Е° ,s) для любого замкнутого выпуклого множества S Обозначим через S(P0,E") множество (1) Пусть

Тогда, при параллельном сближении какую бы кусочно-постоянную стратегию ни применял игрок Е, встреча игроков происходит в S

Предположим, что множество

S{P°,E°)

имеет непустое пересечете с дополнением CS множества S Тогда, убегая по прямой Е°Е', где Е' — любая точка пересечения множеств

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

\е9р°\

Теорема 1.2. В игре ГТ{Р° ,Е° ,S) при Т = -——^ множество точек встречи

игроков при прямолинейном движении убегающего Е, при = совпадает с границей множества U, представляющего собой множество точек

встречи игроков, а оптимальная траектория состоит в движении убегающего по ломаной, имеющей не более одной вершины (прямая или одновершинная ломаная), при этом вершина может находиться на расстоянии ДГ, где Т — время, в течение которого игрок Р ожидает начала преследования, р — постоянная линейная скорость убегающего

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

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

В третьем параграфе, на основе теоремы 1 2 предложен алгоритм "оптимизации по касательной" Ранее такая задача была исследована в работе J1 А Петросяна и В Д Ширяева для задачи простого преследования с одним преследователем и двумя убегающими на двумерной плоскости

В конце главы приведено описание программного кода реализации алгоритмов

Программы реализованы в интегрированной среде Visual Basic При всевозможных движениях убегающей коалиции программа выводит координаты точек захвата, траектории преследователя при использовании им П-стратегии И, наконец, выводит траекторию убегающей коалиции, которая максимизирует время преследования На рисунке 1 показаны оптимальные траектории убегающей коалиции

Рис. 1

Также предусмотрена процедура определения оптимального порядка преследования в задаче с тремя убегающими.

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

—~—лл!

Рис.2

Во второй главе рассматривается задача простого преследования с тремя убегающими в трехмерном пространстве Я3.

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

1) стратегии преследователя J]n — стратегия параллельного сближения, примененная сперва к первому убегающему, затем ко второму убегающему, Г]21 — стратегия параллельного сближения, примененная сперва ко второму убегающему, затем к первому убегающему,

2) стратегии убегающего //,' {р\ ) — стратегия первого (второго) убегающего, состоящего в движении по прямой в точку захвата, //j2 (//22) — стратегия первого (второго) убегающего, состоящего в движении в противоположную сторону от точки захвата первого убегающего,

К {r]t, //,', //Г') — функция выигрыша убегающей коалиции (время преследования обоих убегающих, при использовании преследователем П-стратегии сперва к игроку затем к З-i (г = 1,2), а первым убегающим используется стратегия (р\), а вторым убегающим — (flt')) Игру с одним преследователем и убегающей коалицией, состоящей из двух игроков, в трехмерном пространстве обозначим через г(р°,Е\)

Теорема 2.1. В игре существует ситуация равновесия,

которая строится следующим образом

а) оптимальная стратегия Р (т]: ) (г = 1,2) определяется из условия

кк з-,' W,, МГ) = ппп{к{т),2, и), ц\), К(т]2!, #, //_:)},

б) оптимальная стратегия (д|) (/ =1,2) — движение по прямой к точке N (¡V = Р! = Е''), где N — точка касания сферы с эллипсоидом с фокусами в точках Р" и 1% : и содержащим эту сферу,

в) оптимальная стратегия E, t ) (/ = 1,2)—движение по прямой NE^

от Р1'

Значение игры равно величине

\\р° 771+1^1 ¡р^Ыл®';!]

mm\ --!—!-, ---—--- >

[ а-0, or-A J 11

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

Во втором параграфе основным результатом является доказательство следующей теоремы

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

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

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

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

3 вместо окружностей Аполлония рассматриваются сферы Аполлония

Учитывая все эти особенности, были сформулированы основные

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

1 захват первого убегающего на плоскости, где расположены начальные положения преследователя и первого убегающего,

2 захват второго и третьего убегающего на плоскости, где расположена точка захвата первого убегающего и начальные положения остальных убегающих

Рассмотрен алгоритм оптимизации "по касательной" для случая преследования в пространстве

В четвертом параграфе подробно описан алгоритм оптимизации "по касательной" для случая преследования в пространстве

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

Теорема 2.2. В игре

среди оптимальных траекторий

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

В пятом параграфе дано описание программного кода реализации задачи преследования в пространстве с учетом овалов Декарта

Разработана процедура для расчета параметров xol,yol,zol,rl сферы, на которой происходит захват первого убегающего circlepar3{xa,ya,za,xbl,ybl, zbl, vbl, delta, xol,yol, :ol,rl)

Для расчета координат точки захвата первого убегающего на сфере предусмотрен вызов процедуры coord_cl(l,m,n,xa,ya,za,xol,yol,zol,rI,xcl_l, ycl_l,zcl_l,xcl_2,ycl_2,zcl_2, cl paratn), которая по направляющим 1,т,п луча, выходящего из точки А(ха,уа,:а) определяет координаты двух точек пересечения луча и сферы

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

planepar(xcl, ycl, zc 1, xbl, yb2, zb2, xb3,yb3, zb3, а, Ь, с) — рассчитывает параметры а,Ь,с плоскости, на которой расположена точка С3

anglcmatrix(.rc], jyj], zcl, xb2,yb2,zb2,a,b,c, all 1, a/12, a/13, a/21, a/22, a/23, a/31, a/32, a/33) — рассчитывает коэффициенты матрицы косинусов углов между осями старой и новой систем координат

coorddef у, z, хо _ 1, уо _ 1, zo _ 1, л: _ 1, у _ 1, z _ 1, al 11, a/12, a/13, a/21, a/22, a/23, a/31, a/32, a/33) — определяет координаты точки (x,y,z,) в новой системе координат

two_casat(xa_п,уа_n,xb\_n,yb\_п, xb2_n,yb2_n,va,vbl n vb2_п, max) — процедура для решения задачи преследования на плоскости с двумя

13

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

Процедура Main_Prog3(lacl, xb2, yb2, vb2, xcl, ycl, dtau, tau!) позволяет рисовать овалы Декарта для второго и третьего убегающих В результате получаем семейство овалов Декарта на плоскости ас2

Затем с помощью процедуры coorddef производится возврат к координатам в старой системе координат (трехмерной)

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

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

Основные результаты, выносимые на защиту:

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

2 решение задачи простого преследования в трехмерном пространстве для игры с одним преследователем и двумя убегающими,

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

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

Публикации по теме диссертационной работы [1] Варламова А.Г. Об одном геометрическом методе решения задачи простого преследования менаду одним преследователем и двумя убегающими в пространстве R3 / А.Г. Варламова // Наука и образование —

Якутск, 2007. - № 1 (45) 2007. - С. 67-70 (статья принята к печати 20 октября 2006 г.).

Варламова А Г Одна задача многошаговой оптимизации на плоскости / Варламова А Г // Информационные технологии в науке, образовании и экономике тез докл [науч ред В И Васильев] -Якутск, 2001 - С 25 Варламова А Г Задача многошаговой оптимизации на плоскоти / Варламова А Г // Лаврентьевские чтения науч конф студентов и молодых ученых PC (Я) тез докл - Якутск, 2002 - С 5-6

Варламова А Г Моделирование выбора очередности поимки в одной игре простого преследования / Варламова А Г // Республиканская научно-практическая конференция «Математика Информатика Образование», посвященная 25-летию математического факультета ЯГУ тез докл [науч ред M С Троева] -Якутск, 2002 -С 61-62

Варламова А Г Задача многошаговой оптимизации с неаддитивным функционалом / Варламова А Г // VIII Лаврентьевские чтения науч конф молодых ученых и специалистов Дальневосточного федерального округа сб ст -Якутск, 2004 -Т 1, секция Математика, механика и физика - С 8-12 Варламова А Г Алгоритм «оптимизации по касательной» / Варламова А Г // IV Международная конференция по математическому моделированию тез докл / М-во образования Рос Федерации, Якут гос ун-т им M К Аммосова, [отвред ИЕ Егоров] -Якутск, 2004 - С 119-120

Варламова А Г Задача преследования как задача оптимизации в динамических процессах / Варламова А Г // Математическое моделирование развития северных территорий в условиях рынка Всерос школы-семианр студентов, аспирантов, молодых ученых и специалистов тез докл [редкол В И Васильев идр] -Якутск, 2004 - С 56-58

Варламова А Г Геометрический метод решения задачи простого преследования с п убегающими / Варламова А Г //IX Лаврентьевские чтения науч конф студентов и молодых ученых Секция - Математика, механика, физика сб ст Т 1 -Якутск, 2005 -С 22-26

Варламова А Г Метод решения задачи преследования с тремя убегающими / Варламова А Г // III Всероссийская школа-семинар студентов, аспирантов,

[10] [11]

[12]

[13]

[14]

молодых ученых и специалистов тез докл [редкол Васильев В И и др ] -Якутск, 2005 -32-33

Варламова А Г Задача преследования с пятью убегающими как задача оптимизации в динамических процессах / Варламова А Г // Мат заметки ЯГУ - Якутск, 2005 - Т 12, № 1 - С 46-51

Варламова А Г Групповое преследование одним преследователем двух убегающих в пространстве R3 / Варламова А Г // Международная молодежная научная олимпиада «Ломоносов-2006» тез докл XIII Международной конференции студентов, аспирантов и молодых ученых «Ломоносов», секция Вычислительная математика и кибернетика / М-во образования Рос Федерации, Московский гос ун-т, [редкол Ложкин С А идр] -Москва, 2007 -С 12-13 Варламова А Г Геометрическое расположение одного преследователя и двух убегающих в пространстве R3 / Варламова А Г // Математическое моделирование развития Северных территорий Российской Федерации тез докл IV Всероссийская школа-семинар студентов, молодых ученых и специалистов [редкол Васильев В И и др ] - Якутск, 2006 - С 34-35 Варламова А Г Групповое преследование одним преследователем нескольких преследуемых в пространстве R3 / Варламова А Г // Мат заметки ЯГУ -Якутск, 2006 - Т 13, № 1 - С 50-57

Варламова А Г, Петросян Л А Задача простого преследования с одним преследователем и несколькими убегающими в коалиционной игре / Варламова А Г // Математическое моделирование развития Северных территорий Российской Федерации тез докл Всероссийская школа-семинар студентов, молодых ученых и специалистов [редкол Васильев В И и др ] - Якутск, 2008

-С 51-53

Подписано в печать 2 07 2008 г Формат 60x84 1/!6 Бумага офсетная Печать риюграфическая Уел печ л 10 Гарнитура тайме Тираж 100 эк ч Закат 4309

Отпечатано в отделе оперативной полиграфин химического факультета СПбГУ 198504 Сшиа-Петербч'рг, Петротворец Университетский пр 26

ГЛАВА 1. ЗАДАЧА ПРЕСЛЕДОВАНИЯ СО МНОГИМИ УЧАСТНИКАМИ НА ДВУМЕРНОЙ ПЛОСКОСТИ.

§ 1.1. Задача простого преследования с "линией жизни" и задержкой у преследователя.

§ 1.2. Алгоритм определения параметров окружности Аполлония.

§ 1.3. Алгоритм оптимизации "по касательной" на плоскости.

§ 1.4. Описание программного кода двумерной задачи.

ГЛАВА 2. ОСОБЕННОСТИ РЕШЕНИЯ ЗАДАЧИ ПРЕСЛЕДОВАНИЯ С ОДНИМ ПРЕСЛЕДОВАТЕЛЕМ И НЕСКОЛЬКИМИ УБЕГАЮЩИМИ В ТРЕХМЕРНОМ ПРОСТАНСТВЕ.

§ 2.1. Аналитическое решение задачи преследования двух убегающих.

§ 2.2. Преобразование трехмерной задачи в двумерную.

§ 2.3. Подход к решению задачи преследования трех убегающих.

§ 2.4. Алгоритм оптимизации "по касательной" в пространстве.

§ 2.5. Описание программного кода трехмерной задачи.

Актуальность темы. Объектами исследования данной диссертационной работы являются задачи группового простого преследования со многими участниками, а именно: задачи с использованием преследователем П-стратегии или стратегии параллельного сближения.

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

Основоположником теории дифференциальных игр стал Р.Айзеке, впервые определивший понятие "дифференциальная игра". В 1951 году Р. Айзексом были получены первые результаты по дифференциальным играм. В нашей стране динамические задачи конфликтного управления рассматриваются с 1965 года. Первые работы в этой области принадлежат Н.Н. Красовскому, Л.С. Понтрягину и JI.A. Петросяну, заложившим основу развития теории дифференциальных игр в СССР и в постсоветском пространстве. В этих работах исследовались антагонистические дифференциальные игры, моделирующие конфликт между двумя сторонами, имеющими противоположные интересы.

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

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

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

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

Данная работа базируется на геометрическом подходе к задачам простого преследования, который был предложен в работах Л.А. Петросяна [12, 13, 14, 15, 16, 17, 18, 19, 20, 21], В.Д Ширяева [20, 34], Г.В. Томского [12, 19, 30], Б.Б. Рихсиева [18, 27], Н.А. Зенкевича [35].

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

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

Н.Н. Петровым [8, 9, 10, II] исследовалась задача простого преследования группой преследователей группы убегающих при равных возможностях всех участников. При условии, что все убегающие используют программные стратегии, а затем преследователи определяют свои движения на основе информации о выборе убегающих и, кроме того, каждый преследователь может поймать не более одного убегающего. В этих предположениях были получены достаточные, а в некоторых случаях и необходимые условия убегания в задаче простого преследования.

Очень важным в задаче простого преследования является оптимальность П-стратегии для преследователя, введенной в 1965 году JI.A. Петросяном в статье "Об одном семействе дифференциальных игр на выживание в пространстве R"" [17]. В этой статье рассматриваются игры простого преследования с "линией жизни", и показана оптимальность П-стратегии для преследователя. В других работах Л.А. Петросяна [12, 13, 14, 15, 16, 18, 19, 20], Г.В. Томского [12, 19], Б.Б. Рихсиева [18, 27], В.Д. Ширяева [20, 34] оптимальность П-стратегии показана для более широкого класса задач простого преследования.

Стратегия параллельного сближения для преследователя стала инструментом решения различных задач преследования, в том числе группового преследования. Согласно J1.A. Петросяну [17], при использовании преследователем П-стратегии геометрическое место точек встречи преследователя и убегающего со скоростями а и /3 в случае, когда встреча игроков является поточечной, т.е. 1 = 0 (/ — радиус захвата), есть круг Аполлония, построенный для начальных местоположений игроков Р° и Е{\ граница которой определяется формулой р{р\с) р(Е\с) а р ' где С — точка встречи игроков, р(/1,В) — евклидово расстояние между точками А и В.

Абсолютное большинство работ со многими убегающими по данной теме исследовались в рамках бескоалиционной теории. А случай игры, в которой имеется убегающая коалиция с двумя убегающими на плоскости, был рассмотрен только в работе J1.A. Петросяна и В.Д. Ширяева [20].

В работе J1.A. Петросяна и В.Д. Ширяева рассмотрена задача простого преследования с одним преследователем и двумя убегающими на плоскости. В работе исследуются коалиционный и бескоалиционный подходы. Важной составной частью задач является отыскание ситуации равновесия. Следует также отметить, что если в бескоалиционной игре строится ситуация равновесия по Нэшу, то в коалиционной же игре методом геометрических конструкций выписывается ситуация равновесия. В работе конструируется оптимальная траектория игроков путем нахождения точек встречи для первого убегающего с учетом, что последний убегающий движется вдоль прямой, проходящей через точку встречи и точку начального местоположения второго убегающего. Согласно оптическому свойству эллипса [1, 24], можно найти такую точку встречи игроков в случае коалиционной игры, которая была бы оптимальной точкой встречи для убегающего с учетом интереса противника. Такая точка встречи определяется как точка касания с внешней стороны окружности Аполлония с эллипсом, фокусы которого — точки начальных местоположений преследователя и второго убегающего. Решение игры строится на предположении, что преследователь выбирает один из двух способов поочередной поимки. Полученные результаты по групповому преследованию с одним преследователем и двумя убегающими на плоскости послужили теоретическим фундаментом предлагаемой диссертации.

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

Однако полное решение известно только в задаче преследования на плоскости с одним преследователем и двумя убегающими при дополнительном предположении, что преследователь использует стратегию параллельного сближения и не меняет порядок преследования в процессе игры. Учитывая сказанное,' едва ли можно было ожидать полное решение рассматриваемой задачи. Поэтому мы пошли по пути построения численных методов, позволяющих моделировать процесс преследования на ЭВМ, используя для построения стратегии убегающих с определенными свойствами, оптимальность которых обоснована в более простых случаях. К числу таких свойств относится использование прямолинейных движений убегающими, что доказано нами в параграфе 1.1 главы 1 для задачи преследования с "линией жизни'* и задержкой у преследователя, а также для задачи преследования с одним преследователем и двумя убегающими в пространстве. Таким же образом рассматривается метод касательных, оптимальность которого доказана в задаче преследования с двумя убегающими и доказан нами для случая трехмерного пространства в параграфах 2.1, 2.2, главы 2.

Рассмотрим типичную теоретико-игровую задачу преследования. В теории игр участники конфликта условно называются игроками —• преследователь и убегающий, а их решения или способы действий — стратегиями. Будем обозначать преследователя через Р, а убегающего — через Е. В более сложных случаях участников игры может быть больше двух. В общем случае Р и Е — разумные противники с противоположными интересами. Но если каждый из них управляет лишь одним движущимся объектом, то символами Р и Е будут обозначаться сами эти объекты. Игра преследования обычно считается оконченной, когда произошел захват. В дальнейшем иногда вместо выражения произошел захват, будем говорить, что произошла встреча игроков или поимка убегающего. Захват означает, что расстояние \РЕ\ стало меньше некоторой заранее заданной положительной величины / (/ > 0). Число / называется радиусом встречи, а сама поимка —- /-встречей. В диссертационной работе будут рассматриваться задачи простого преследования в случае поточечной поимки, т.е. когда / = 0, в предположении, что игроки совершают простое движение.

Пусть а — максимальная линейная скорость преследователя и [5 — максимальная линейная скорость убегающего, причем а > /?. Так как скорость точки Р превосходит скорость точки Е, то существует множество способов движения Р, при которых он может осуществить встречу с Е.

Будем отмечать верхними индексами положения игроков в соответствующие моменты времени, а нижними — номер участника. Местоположение преследователя в момент времени t обозначим через Р', а местоположение убегающего в этот момент времени / — через Е'. Время отсчитывается с момента начала преследования.

Точки Е' при 0 < t <Т описывают линию, которая называется траекторией убегающего па отрезке времени г]. Геометрическое место точек Р' для всех О < t <Т называется траекторией преследователя па отрезке времени [(), Т].

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

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

Пока убегающий движется по лучу е"а", преследователь перемещается по лучу Р"В", где В0 — точка, определяемая условиями поточечной поимки (/ = 0, / — радиус захвата):

1) в" лежит на луче е"л",

2) -= L-r-, а р т.е. точка В" достигается преследователем и убегающим одновременно, если убегающий движется по лучу Е"А" (рис.1).

Рис.1

Пусть в момент времени tf убегающий меняеч направление своего движения и некоторое время движется по лучу Е''А''. Тогда преследователь движется по лучу Р'В'', где В1'— точка поточечной поимки на Е''А'', удовлетворяющая условию

Р1'В1' Е'В'' а /3

Если в момент времени t2 убегающий снова меняет направление движения, то преследователь начинает двигаться к новой точке поточечной поимки В' и т.д. При использовании преследователем стратегии параллельного сближения отрезок Р'Е' параллелен отрезку Р"Е" в каждый момент времени t>0. Действительно, при 0</</, имеем (рис.2)

Р"Рп at а

Р'В'

Е"Е' fit Р Е'В следовательно, Р'Е' || Р"Е". Таким же образом доказывается, что Р1 Е' || Р'1 Е1' при ts <t<t2, поэтому Р'Е' || Р"Е" при 0<t<t: и т.д. Это свойство объясняет, почему процесс преследования с использованием П-стратегии называется параллельным сближением.

Рис.2

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

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

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

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

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

Научная новизна

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

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

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

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

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

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

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

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

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

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

В первом параграфе главы рассмотрена задача простого преследования с "линией жизни" и задержкой времени у преследователя. Рассматривается антагонистический случай. Предположим, что задано некоторое замкнутое выпуклое множество s с r2. Две точки -— преследователь р и убегающий е, обладая ограниченными по модулю линейными скоростями а и /? соответственно, перемещаются во множестве S, имея при этом возможность в каждый момент времени изменять направление движения (простое движение), причем а> Р. Игра происходит следующим образом. Пусть задано некоторое число Т> О, называемое задержкой времени у преследователя с момента начала игры. В течении времени Т преследователь остается неподвижным, а убегающий начинает движение с начала игры. Игра кончается, как только убегающий Е достигает "линии жизни" — границы заданного множества S — или происходит захват до достижения границы множества S. Считается, что захват произошел, если расстояние между ним и преследователем Р достигает значения, равного / (/ = 0). В начальный момент времени игроки находятся во множестве S, и целью убегающего Е является достижение границы множества S до момента поимки. Игрок Р преследует противоположную цель, т.е. стремится осуществить поимку до того, как тот достигнет "линии жизии". Предполагается также, что преследователь Р использует П-стратегию или стратегию параллельного сближения. Пусть Р1), — начальные местоположения игроков Р и Е. Для различных Р0 и Е° имеем различные игры преследования с "линией жизни" и задержкой времени Т> О у преследователя с момента начала игры, которые будем обозначать через Г, [Р°,Е",S). Рассмотрим игру, когда убегающий меняет направление движения конечное число раз. Доказана теорема:

Теорема 1.1. При параллельном сближении множество точек встречи игроков в игре г, (p",e",s) при всевозможных движениях убегающего е совпадает с множеством, ограниченным огибающей семейства окружностей Аполлония, которое обозначим через U{P",E')— т.е. во множестве точек /V, для которых выполняется условие p{N,Pi')(D>p{N,El), со=£, (1) а где Р"{е") — начальное местоположение игрока Р(е), е' —множество точек, определяющих местоположение игрока Е в момент времени Т > О при его прямолинейном движении, а (/?) — постоянная линейная скорость преследователя (убегающего).

Сравним траектории убегающего при прямолинейном движении

Е°С Р°С ---= Т

Р а и при движении с одним поворотом

Е°ЕТ

ЕГС

PC jB а где Ег — точка поворота траектории убегающего в момент времени Т > 0, С — точка встречи игроков. Имеем

О г-/

ЕиЕ

Е7С

Е°С

Равенство должно выполняться в силу одинакового Т. Значит, либо существует такая точка Е1, что выполняется равенство, либо точка Ет лежит на прямой Е°С. Но может оказаться, что при одинаковом Т > О

Е1 С^Е^С^Е"Е' . Таким образом, справедлива следующая теорема.

Теорема 1.2. В игре Г7(р" ,Е" ,S) при Т

Е°Р° Р множество точек встречи

Р°Е° игроков при прямолинейном движении убегающего Е, при х = совпадает с границей множества U, представляющего собой множество точек встречи игроков, а оптимальная траектория состоит в движении убегающего по ломаной, имеющей не более одной вершины (прямая или одновершинная ломаная), при этом вершина может находиться на расстоянии рТ, где Т — время, в течение которого игрок Р ожидает начала преследования, /? — постоянная линейная скорость убегающего.

Уравнение границы множества точек встречи игроков при прямолинейном движении убегающего в декартовой системе при Р0 = (0;0), Е° =(а\0) запишется в виде х2 .2 2хаа2 ^ се2(а2-Т/32))2 4Т2а2/3А(х2 + у2)

2)

2~Р2 а2-р2 J (a2-jS3f ' где а и J3 — постоянные линейные скорости преследователя и убегающих соответственно, Т — время, в течение которого игрок Р ожидает начала преследования. При Т = ~ в (2) получается частный случай овала Декарта — улитка Паскаля.

Ввиду того, что множество, представляющее собой множество точек встречи игроков, будет симметрично относительно прямой Р°Е{), достаточно рассмотреть одну его часть. Уравнение одной части огибающего семейства окружностей имеет вид а2 f ^ • --------^

ТВ х------ а V х-а)2 + у2 у у 02(*г+У2).

Во втором параграфе рассмотрена задача простого преследования с одним преследователем и тремя убегающими на двумерной плоскости. Обозначим начальное местоположение преследователя и убегающих через Р" и Е", / = 1,2,3, а через — постоянные линейные скорости преследователя и убегающих соответственно. Преследователь использует П-стратегию. Предполагается также, что в начальный момент времени игроки обладают полной информацией о действиях других игроков. В этих предположениях ищется наилучший ответ убегающей коалиции в смысле максимизации времени преследования. Описан алгоритм определения параметров окружности Аполлония и овалов Декарта.

В третьем параграфе, на основе теоремы 1.2 предложен алгоритм "оптимизации по касательной". Ранее такая задача была исследована в работе J1.A. Петросяна и В.Д. Ширяева для задачи простого преследования с одним преследователем и двумя убегающими на двумерной плоскости.

В конце главы приведено описание программного кода реализации алгоритмов.

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

Во второй главе рассматривается задача простого преследования с тремя убегающими в трехмерном пространстве R*.

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

1) стратегии преследователя: rj]2 — стратегия параллельного сближения, примененная сперва к первому убегающему, затем ко второму убегающему, г/21 — стратегия параллельного сближения, примененная сперва ко второму убегающему, затем к первому убегающему;

2) стратегии убегающего: //,' (//,) — стратегия первого (второго) убегающего, состоящего в движении по прямой в точку захвата, //,2 (//,) — стратегия первого (второго) убегающего, состоящего в движении в противоположную сторону от точки захвата первого убегающего; к(/7/3 /у,-') -— функция выигрыша убегающей коалиции (время преследования обоих убегающих, при использовании преследователем П-стратегии сперва к игроку /, затем к 3-i (/=1,2), а первым убегающим используется стратегия (//)), а вторым убегающим — Игру с одним преследователем и убегающей коалицией, состоящей из двух игроков, в трехмерном пространстве обозначим через

Теорема 2.1. В игре г(р° ,Е°) существует ситуация равновесия, которая строится следующим образом: а) оптимальная стратегия Р (rji (/= 1,2) определяется из условия

K{,lj-I, М',, К') = тт{к[г]1;, , /и]), /ф,,, /л]. //!)}; б) оптимальная стратегия Et (//)) (/=1,2) — движение по прямой к точке TV (n = Рт' - \ где N — точка касания сферы с эллипсоидом с фокусами в точках Р" и и содержащим эту сферу;

16 в) оптимальная стратегия Е,: (jii'i") (/ = 1,2)—движение по прямой от Р1'.

Значение игры равно величине p"n\+ne"2 p"n\+ne'; о min< а - /?, ' ос- Pi

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

Теорема 2.2 была доказана тремя различными способами.

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

1. начальные положения участников игры находятся в разных плоскостях;

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

3. вместо окружностей Аполлония рассматриваются сферы Аполлония.

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

1. захват первого убегающего на плоскости, где расположены начальные положения преследователя и первого убегающего;

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

Теорема 2.2. В игре среди оптимальных траекторий

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

Рассмотрен алгоритм оптимизации "по касательной" для случая преследования в пространстве.

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

В пятом параграфе дано описание программного кода реализации задачи преследования в пространстве.

Апробация работы. Результаты диссертационной работы неоднократно докладывались и обсуждались на XIII Международной конференции студентов, аспирантов и молодых ученых «Ломоносов», секции: Вычислительная математика и кибернетика (Москва: 2006), на семинаре "Теория игр и конфликтно управляемые процессы" под руководством заведующего кафедрой математической экономики С.П. Кайгородова, на научной конференции "Лаврентьевские чтения РС(Я)" (Якутск: 2002, 2004, 2005), на IV Международной конференции по математическому моделированию (Якутск, 2004), на Всероссийской школе-семинаре "Математическое моделирование развития северных территорий" (Якутск: 2004, 2005, 2006, 2008).

Публикации. Основные результаты диссертации опубликованы в 14 работах, — 9 тезисах и докладах, 5 статьях [36]-[49].

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

Основные результаты, выносимые на защиту:

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

2. решение задачи простого преследования в трехмерном пространстве для игры с одним преследователем и двумя убегающими;

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

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

ЗАКЛЮЧЕНИЕ

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

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

1. Адамар Ж. Элементарная геометрия. М., Учпедгиз, 1958. - 760 с.

2. Айзеке Р. Дифференциальные игры. М.: Мир, 1967. - 9 с.

3. Григоренко Н.Л. К задаче группового преследования // Тр. МИАМ СССР. 1988.-Т. 185.-С. 66-73.

4. Дж. фон Нейман, О. Моргенштерн. Теория игр и экономическое поведение. / Перев. с анг. под ред. и с доб. Н.Н. Воробьева. М.: Наука, 1970. - 708 с.

5. Красовский Н.Н. Игровые задачи о встрече движений. М.: Наука, 1970.-420 с.

6. Красовский Н.Н., Субботин А.И. Позиционные дифференциальные игры. М.: Наука, 1974. — 456 с.

7. Моденов П.С. Аналитическая геометрия. — М.: Изд-во Моск. ун-та, 1965. —563 с.

8. Петров Н.Н. Об одной задаче группового преследования с фазовыми ограниченичми // Прикладная математика и механика. — 1988. Т. 52.-Вып. 6.-С. 1030-1033.

9. Петров Н.Н. Об одной задаче преследования со многими убегающими//Вестник Удмур. ун-та. 2000. - № 1.-С. 131-136.

10. Петров Н.Н. Одна задача простого преследования с фазовыми ограничениями // Автоматика и телемеханика. 1992. - № 5. - С. 22— 26.

11. Петров Н.Н. Простое преследование жесткосоединенных убегающих // Автоматика и телемеханика. 1997. -№ 12. - С. 89-95.

12. Петросян Л.А., Томский Г.В. Геометрия простого преследования. -Новосибирск: Наука, 1983. 142 с.

13. Петросян Л.А. Дифференциальные игры преследования. Л.: Изд-во Ленингр. ун-та, 1977.-222 с.

14. Петросян Л.А. Дифференциальные игры на выживание со многими участниками//Докл. АН СССР. 1965.-Т. 161.-№ 2.-С. 285-287.

15. Петросян Л.А. Игры преследования с «линией жизни» // Вестн. Ленингр. ун-та. 1967.-№ 13.-Вып. З.-С. 76-85.

16. Петросян Л.А. Игры преследования с «линией жизни» со многими участниками // Изв. АН АрмССР. Мат. 1966. - Т. 2. - № 5, С. 333340.

17. Петросян Л.А. Об одном семействе дифференциальных игр на выживание в пространстве R" II Докл. АН СССР. 1965. - Т. 161. -№ 1. - С. 52-54.

18. Петросян Л.А., Рихсиев Б.Б. Преследование на плоскости. М.: Наука, 1991.-95 с.

19. Петросян Л.А., Томский Г.В. Элементарные задачи преследования и убегания. Якутск: ЯГУ, 1989. - 77 с.

20. Петросян Л.А., Ширяев В.Д. Групповое преследование одним преследователем нескольких преследуемых // Вестник ЛГУ. № 13. - 1980.-С. 50-56.

21. Петросян Л.А., Данилов Н.Н. Кооперативные дифференциальные игры и их приложения. Томск: Изд-во Том. ун-та, 1985. - 276 с.

22. Понтрягин Л.С. Избранные научные труды. М.: Наука, 1988. - Т. 2: Дифференц. уравнения. Теория операторов. Дифференц. игры. -575 с.

23. Понтрягин Jl.С. Математическая теория оптимальных процессов и дифференциальные игры // Тр. МИАМ СССР. 1985. - Т. 169. - С. 119-157.

24. Постников М. М. Аналитическая геометрия. — М.: Наука, 1973. — 751 с.

25. Пшеничный Б.Н. Простое преследование несколькими объектами // Кибернетика. 1976. - № 3. - С. 145-146.

26. Пшеничный Б.Н., Раппопорт И.С. Об одной задаче группового преследования // Кибернетика. 1979. № 6. С. 145-146.

27. Рихсиев Б.Б. Дифференциальные игры с простым движением. Ташкент.: Фан. 1989.

28. Сатимов Н.Ю, Маматов М.Ш. О задаче преследования и уклонения от встречи в дифференциальных играх между группами преследователей и убегающих // Докл. АН Узб. ССР. 1983. № 4. С. 3-6.

29. Теория игр. Аннотированный указатель публикаций по 1968 г. / Под ред. Н.Н.Воробьева. Ленинград: Наука, 1976. - 226 с.

30. Томский Г.В., Уланов В.А. Игры в общих управляемых системах. -И.: Изд-во Иркут. ун-та, 1987. -208 с.

31. Fleming W.H. A note on differential games of prescribed duration. Contributions to the theory of games // Ann. Math. Stud. 1957. - No. 39. -P. 407-412.

32. Чикрий А.А. Групповое преследование при ограниченных координатах убегающего // ПММ. 1982. - Т. 46. - № 6. - С. 906913.

33. Чикрий А.А. Дифференциальные игры с несколькими преследователями // Матем. теория управления. Варшава, 1983. -С. 81-107.

34. Ширяев В.Д. Об одной коалиционной дифференциальной игре трех лиц//Вестн. Ленингр. ун-та. 1980.-№ 19. - Вып. 4. - С. 116-118.

35. Петросян Л.А., Зенкевича Н.А. Оптимальный поиск в условиях конфликта. Ленинград: ЛГУ, 1987. - 75 с.

36. Варламова А.Г. Об одном геометрическом методе решения задачи простого преследования между одним преследователем и двумя убегающими в пространстве R} / А.Г. Варламова // Наука и образование. Якутск, 2007. - № 1 (45) 2007. - С. 67-70.

37. Варламова А.Г. Одна задача многошаговой оптимизации на плоскости / Варламова А.Г. // Информационные технологии в науке, образовании и экономике: тез. докл. науч. ред. В.И. Васильев. -Якутск, 2001.-С.25.

38. Варламова А.Г. Задача многошаговой оптимизации на плоскоти / Варламова А.Г. // Лаврентьевские чтения: науч. конф. студентов и молодых ученых PC (Я): тез. докл. Якутск, 2002. - С. 5-6.

39. Варламова А.Г. Алгоритм «оптимизации по касательной» / Варламова А.Г. // IV Международная конференция по математическому моделированию: тез. докл. / М-во образования Рос.

40. Федерации, Якут. гос. ун-т им. М.К. Аммосова; отв.ред. И.Е. Егоров. Якутск, 2004. - С. 119-120.

41. Варламова А.Г. Метод решения задачи преследования с тремя убегающими / Варламова А.Г. // III Всероссийская школа-семинар студентов, аспирантов, молодых ученых и специалистов: тез. докл. редкол.: Васильев В.И. и др.. Якутск, 2005. - 32-33.

42. Варламова А.Г. Задача преследования с пятью убегающими как задача оптимизации в динамических процессах / Варламова А.Г. // Мат.заметки ЯГУ. Якутск, 2005 - Т. 12, № 1. - С. 46-51.

43. Варламова А.Г. Групповое преследование одним преследователемнескольких преследуемых в пространстве R / Варламова А.Г. // Мат.заметки ЯГУ. -Якутск, 2006 Т. 13, № 1. - С. 50-57.