Введение к работе
Актуальность темы. Объектами исследования данной диссертационной работы являются задачи группового простого преследования со многими участниками, а именно: задачи с использованием преследователем П-стратегии или стратегии параллельного сближения.
Основоположником теории дифференциальных игр стал Р.Айзеке, впервые определивший понятие "дифференциальная игра". В нашей стране динамические задачи конфликтного управления рассматриваются с 1965 года. Первые работы в этой области принадлежат Н.Н. Красовскому, Л.С. Понтрягину и Л.А. Петросяну, заложившим основу развития теории дифференциальных игр в СССР и в постсоветском пространстве.
В развитие дифференциальных игр внесли свои результаты А.А. Азамов,
Э.Г. Альбрехт, М. Барди, В.Д. Батухтин, Т. Башар, Р. Беллман, Ю.И. Бердышев,
Н.Л. Григоренко, М.И. Гусев, В.Г. Гусейнов, Н.Н. Данилов, В.И. Жуковский,
В.В. Захаров, М.И. Зеликин, А. Земба, Н. Калтон, А.Ф Клейменов,
А.Н. Красовский, А.А. Меликян, А.В. Мезенцев, Е.Ф. Мищенко,
М.С. Никольский, Н.Н. Петров, B.C. Половинкин, Б.Н. Пшеничный, Б.Б. Рихсиев, И.С. Раппопорт, Н.Ю. Сатимов, Н.Н. Субботина, Г.В. Томский, В.Н. Ушаков и другие.
Обобщением дифференциальных игр преследования двух участников являются дифференциальные игры с участием группы преследователей и одного или группы убегающих. Различные постановки дифференциальных игр с участием группы преследователей были рассмотрены в работах А.А. Азамова, Н.Л. Григоренко, П.Б. Гусятникова, В.И. Жуковского, В.Л. Зака, Р.П. Иванова, Е.Ф. Мищенко, М.С. Никольского, Н.Н. Петрова, Л.А. Петросяна, Б.Н. Пшеничного, И.С. Раппопорта, Б.Б. Рихсеева, Н.Ю. Сатимова, Ф.Л. Черноусько, А.А. Чикрия и других.
Данная работа базируется на геометрическом подходе к задачам простого преследования, который был предложен в работах Л.А. Петросяна, В.Д Ширяева, Г.В. Томского, Б.Б. Рихсиева, Н.А. Зенкевича.
В диссертационной работе исследуется задача простого преследования с одним преследователем и несколькими убегающими. Эта задача исследуется в антагонистической постановке, когда убегающие игроки действуют как один игрок. Задача такого рода ранее рассматривалась в литературе по теории игр. Полное решение задачи преследования на плоскости с одним преследователем и двумя убегающими при дополнительном предположении, что преследователь использует стратегию параллельного сближения и не меняет порядок преследования в процессе игры представлено в работе Л.А. Петросяна и В.Д. Ширяева. Учитывая сказанное, едва ли можно было ожидать полного решения рассматриваемой задачи. Поэтому мы пошли по пути построения численных методов, позволяющих моделировать процесс преследования на ЭВМ, используя для построения стратегии убегающих с определенными свойствами, оптимальность которых обоснована в более простых случаях. К числу таких свойств относится использование прямолинейных движений убегающими, что доказано нами в параграфе 1.1 главы 1 для задачи преследования с "линией жизни" и задержкой у преследователя, а также для задачи преследования с одним преследователем и двумя убегающими в пространстве. Таким же образом рассматривается метод касательных, оптимальность которого доказана в задаче преследования с двумя убегающими и доказан нами для случая трехмерного пространства в параграфах 2.1, 2.2, главы 2.
Вызывают трудности в решении таких задач и чисто технические проблемы. Например, при решении задач с четырьмя и более игроками необходимо обработать большой объем информации, связанный с выбором условно оптимальных решений. Появление интегрированных комплексных программ позволило по-новому взглянуть на возможности использования численных методов при решении задачи группового преследования. Поэтому становится необходимым разработка новых методов и алгоритмов, требующих минимальных затрат времени в программной реализации, т.е. исследование таких задач является актуальной задачей.
Цель работы. Целью работы является разработка методов математического моделирования, включая теорию, численные алгоритмы и программную реализацию для приближенного решения задач простого преследования с одним преследователем и группой убегающих на двумерной плоскости и в трехмерном пространстве.
Научная новизна.
Рассмотрена задача простого преследования с "линией жизни", когда преследователь начинает движение с задержкой времени. Найдены оптимальные стратегии убегающего и преследователя.
Найдено решение задачи простого преследования с одним преследователем и двумя убегающими в трехмерном пространстве в случае, когда выигрышем убегающей коалиции является время преследования.
Доказано, что пространственная задача с одним преследователем и двумя убегающими сводится к задаче преследования на плоскости, поскольку оптимальная траектория убегающей коалиции лежит в одной плоскости.
Разработаны алгоритмы расчета поведения убегающей коалиции, приближенного к оптимальному, на плоскости и в пространстве для задачи простого преследования с одним преследователем и тремя убегающими при условии, что преследователь использует П-стратегию и выбирает при этом наилучший для себя порядок преследования.
Методы исследования. Для исследования поставленных задач в диссертационной работе применяются методы теории игр, дифференциальной геометрии, теории дифференциальных игр и, в частности, геометрический метод, с помощью которого изучение пространственной задачи сводится к исследованию плоских задач, а также аппарат компьютерного моделирования.
Теоретическая и практическая ценность. Результаты диссертации носят как теоретический, так и прикладной характер. Основные теоретические результаты диссертации являются новыми. Выводы и положения, сформулированные в диссертации, базируются на строгих математических доказательствах. Теоретическая ценность заключается: в поиске оптимальных
стратегий убегающего и преследователя в задаче с "линией жизни" и задержкой времени у преследователя; в нахождении решения задачи простого преследования с одним преследователем и двумя убегающими в трехмерном пространстве.
Все прикладные результаты работы являются новыми; разработанные алгоритмы и их реализация могут служить основой для расчетов аналогичных задач преследования. Использование предлагаемых алгоритмов решения задач группового простого преследования может помочь поиску оптимальной траектории убегающей коалиции в смысле максимизации времени преследования в более сложных задачах.
Апробация работы. Результаты диссертационной работы неоднократно докладывались и обсуждались на XIII Международной конференции студентов, аспирантов и молодых ученых «Ломоносов», секции: Вычислительная математика и кибернетика (Москва: 2006), на семинаре "Теория игр и конфликтно управляемые процессы" под руководством заведующего кафедрой математической экономики СП. Кайгородова, на научной конференции "Лаврентьевские чтения РС(Я)" (Якутск: 2002, 2004, 2005), на IV Международной конференции по математическому моделированию (Якутск, 2004), на Всероссийской школе-семинаре "Математическое моделирование развития северных территорий" (Якутск: 2004, 2005, 2006, 2008).
Публикации. Основные результаты диссертации опубликованы в 14 работах — 9 тезисах и докладах, 5 статьях.
Структура и объем диссертации. Диссертация состоит из введения, двух глав, разбитых на 9 параграфов, заключения и списка литературы. Общий объем составляет 99 страниц. Список цитируемой литературы содержит 49 наименований. Рисунки во введении нумеруются натуральными порядковыми числами. Формулы, рисунки и таблицы в каждой главе нумеруются тремя натуральными числами, первое из которых указывает на номер главы, второе — номер параграфа, третье — номер формулы, рисунка или таблицы в параграфе.
