Методы теории компромиссных игр в задачах управления воздушным движением

Актуальность темы

.

Диссертация посвящена исследованию применимости методов теории оптимального управления и теории компромиссных игр {Satisficing Game Theory — SGT) [90] для решения задач построения региональной системы организации воздушного движения (ОрВД) на основе концепции свободного полета (Free Flight) [69], в частности, обеспечения предотвращения конфликтов между воздушными судами (ВС). Задачи организации воздушного движения и предотвращения конфликтов между ВС исследуются в работах Г. С. Бюшгенса,.

A.Б. Куржанского, Е. А. Федосова, Г. А. Крыжановского, В. В. Купина, П. И. Реутова, Т. Г. Анодиной, В. И. Мокшанова, Л. Е. Рудельсона, В. И. Власова, В. П. Мутовкина, В. В. Соломенцева, О. Н. Назимова, A.JI. Ройзенсона, А. И. Болыпева, Е. В. Чепель, Я. Ван Доорна, Д. Янга, Б. Х. Давидсона, B.JI. Суханова, С. А. Трофимова, JI.B. Вишняковой, О. В. Дегтярева, В. П. Егоровой, A.B. Кан,.

B.Н. Канадина, И. Ф. Зубковой, С. Г. Пятко, Э. Я. Фалькова, A.M. Гайфуллина,.

A.B. Бобылева, В. А. Ярошевского, A.C. Белоцерковского, В. В. Вышинского,.

B.JI. Кузнецова, П. В. Филонова, В. Г. Бобрякова, В. В. Александрова, О. В. Карсаева, C.B. Кулешова, A.B. Чунтула, J.K. Kuchar, J.C. Hill, J. Krozel и др. В соответствии с современными воззрениями, в диссертации в понятие воздушного конфликта включены не только столкновения ВС, но также опасные сближения и попадания в вихревые следы окружающих ВС. Для конфликтов типа попадание в спутный след представлен аппроксимационный подход к моделированию вихревых возмущений, возникающих при движении ВС. Разработанная математическая модель эволюции вихревых возмущений и реализованные с ее использованием эффективные алгоритмы маневрирования ВС для избегания вихревых следов на плоскости и в пространстве являются важными и необходимыми компонентами системы ОрВД, или комплекса имитационного моделирования ОрВД. Проверка работоспособности алгоритмов проводится в разработанном автором комплексе имитационного моделирования ОрВД, в основу которого положена концепция свободного полета.

Использование концепции свободного полета означает представление находящихся в воздушном пространстве ВС в виде независимых взаимодействующих агентов. Агенты преследуют свои собственные цели, однако способны (в своих интересах) учитывать цели соседних агентов (работы W.C. Stirling, D.H. Wolpert, J.K. Archibald, F. Bellomi). В настоящее время существует четкая тенденция перехода от централизованных систем ОрВД, где решения принимает диспетчер, к децентрализованным, в которых каждое ВС наделяется большими полномочиями, отсутствует централизованный контроль (работы Г. С. Бюшгенса, Б. Х. Давидсона, B.JI. Суханова, С. А. Трофимова, Н. М. Гревцова, T.S. Perry). За счет снижения нагрузки на диспетчеров ОрВД при децентрализованном подходе снижается роль человеческого фактора при возникновении воздушных конфликтов, а, значит, уменьшается вероятность возникновения авиационных происшествий.

В диссертации рассматривается относительно простая задача движения ВС на плоскости. Плоское движение нередко используется для моделирования сложного движения маневрирующих объектов (работы JI.A. Петросяна, Ф. Л. Черноусько, R. Isaacs). ВС представляет собой безынерционную точку, управляемую по скорости и направлению, на которые обычно накладываются определенные ограничения. Для разрешения конфликтных ситуаций в воздухе (столкновение, опасное сближение, избегание вихревых следов) между ВС, применяется основанный на теории компромиссных игр подход для описания (формализации) процедур принятия решений, который дополняется разработанной математической моделью вихревых возмущений. В рамках применяемого компромиссного подхода разработаны методы построения функций рисков и преимуществ для ВС, в зависимости от типа конфликтной ситуации. Функция риска (ФР) определяет количественную оценку вероятности возникновения конфликтов с окружающими ВС. Функция преимущества (ФП) отражает тенденцию к достижению поставленной цели: применительно к ВСдостижение пункта назначения. Методика построения ФР и ФП в задаче избегания столкновений ВС рассматривалась в работах F. Bellomi, J.K. Archibald.

Математическое и компьютерное моделирование — высокоэффективный и относительно низкозатратный метод исследования сложных систем. Особую важность средства и методы математического и компьютерного моделирование приобретают при исследовании таких сложных систем, для которых проведение натурного эксперимента является трудоемкой и дорогостоящей задачей. К таким сложным системам относятся системы ОрВД. Ошибки в натурных экспериментах в работающей системе ОрВД могут привести к непоправимым последствиям (катастрофам ВС и человеческим жертвам). Введению новых правил должна в обязательном порядке предшествовать их проверка на комплексах имитационного моделирования ОрВД. Аналогично, достаточно сложной задачей является обнаружение спутного следа за движущимся ВС, который не виден для обычного глаза. Воздействие спутного следа на ВС исследовалось в работах В. А. Ярошевского, А. М. Гайфуллина, А. С. Белоцерковского, В. В. Вышинского, А. В. Бобылева, G. Huppertz, F. Barbaresco. Для обнаружения вихревого следа на практике используется различное, порой дорогостоящее, оборудование [40], которым, по тем или иным причинам, не может быть оснащен каждый борт. В этом случае, создание эффективной модели эволюции вихревого следа за ВС, надежно апробированной и работающей на бортовом компьютере ВС, может оказаться решающей альтернативой в решении проблемы избегания вихревого следа.

Цель работы.

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

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

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

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

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

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

4. Предложен способ разрешения конфликтов трех видов с помощью маневров ВС только в двух плоскостях. Для маневров в ГП управлением выступают допустимые направления движения ВС. Для маневров в ВП использован метод Брайсона-Миеле, в котором управлением выступают допустимые направление и скорость движения ВС. Для реализации метода Брайсона-Миеле использован численный метод поиска экстремума с помощью изолиний.

5. На языке высокого уровня реализован алгоритм разрешения воздушных конфликтов ВС в соответствии с п. 4. с возможностью многопоточного параллельного выполнения.

6. Разработан программный комплекс для математического моделирования процесса управления воздушным движением с использованием многоагентного подхода на основе 8вТ (п.1) и предложенных методов построения и оценки функций рисков и преимуществ (п.2). Проведен обширный вычислительный эксперимент по оценке работы системы ОрВД, в ходе которого доказана эффективность применения методов и программного обеспечения, представленных в работе, для построения перспективной региональной (на первом этапе) интеллектуальной системы ОрВД (на основе концепции свободного полета).

Методы исследования.

Для решения задачи использовались численные методы, методы линейной алгебры, математической статистики, объектно-ориентированного программирования, паттерны проектирования. Существенным образом в диссертации используются результаты работ исследователей ЦАГИ в области вихревой безопасности A.M. Гайфуллина, B.B. Вышинского, В. А. Ярошевского, A.B. Бобылева.

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

1) Исследованы возможности и разработана методология применения теории компромиссных игр для разрешения конфликтов трех видов в воздушном пространстве в многоагентной среде в классе плоских маневров.

2) Разработаны и апробированы с помощью численных экспериментов методы построения функций риска и преимуществ для ВС.

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

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

5) Построены основы теории децентрализованной системы ОрВД, базирующейся на теории компромиссных игр.

Практическая значимость.

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

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

Апробация работы и публикации.

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

1) Юбилейная L научная конференция МФТИ «Современные проблемы фундаментальных и прикладных наук», ноябрь 2007, Долгопрудный.

2) XIX Международная Интернет-ориентированная конференция молодых ученых и студентов по проблемам машиноведения (МИКМУС-2007), декабрь 2007, Москва.

3) Научная конференция «Проблемы машиноведения». Институт машиноведения имени A.A. Благонравова РАН, 12−14 ноября 2008 года, Москва.

4) XVI Международная конференция по вычислительной механике и современным прикладным программным системам (ВМСППС'2009), 2531 мая 2009 г., Алушта.

5) III Международная конференция «Управление развитием крупномасштабных систем MLSD'2009». Институт проблем управления им. В. А. Трапезникова РАН, 5−9 октября 2009 г.

6) XXI Международная Инновационно-ориентированная конференция молодых ученых и студентов «МИКМУС-2009». Институт машиноведения им. A.A. Благонравова РАН, 16−18 ноября 2009.

7) LII Научная конференция МФТИ «Современные проблемы фундаментальных и прикладных наук», 2009, Долгопрудный.

8) VII Всероссийская межвузовская конференция молодых ученых. Санкт-Петербургский государственный университет информационных технологий, механики и оптики, 20−23 апреля 2010 г.

9) VIII Международная конференция по Неравновесным процессам в соплах и струях (NPNJ'2010), 25 — 31 мая 2010 г., Алушта.

10) LIII Научная конференция МФТИ «Современные проблемы фундаментальных и прикладных наук», 2010, Долгопрудный.

11) Научный семинар в ФГУП «Государственный научно-исследовательский институт авиационных систем» (ГосНИИАС), октябрь 2010 г., Москва.

12) XVII Международная конференция по вычислительной механике и современным прикладным программным системам (ВМСППС'2011), 2531 мая 2011 г., Алушта.

13) Научный семинар в ФГУП «Центральный аэрогидродинамический институт имени проф. Н.Е. Жуковского» (ЦАГИ), июнь 2011 г., Жуковский.

14) X Всероссийский съезд по фундаментальным проблемам теоретической и прикладной механики, 24−30 августа 2011 г., Нижний Новгород.

15) V Международная конференция «Управление развитием крупномасштабных систем MLSD'2011». Институт проблем управления им. В. А. Трапезникова РАН, 3−5 октября 2011 г.

16) Российский научно-технический семинар «Состояние и перспективы развития автоматизированных систем планирования использования воздушного пространства в РФ» (ПИВП-2011). Государственный научный центр Российской Федерации ФГУП.

Государственный научно-исследовательский институт авиационных систем (ГосНИИАС)", 22−24 ноября 2011 г.

Основные результаты диссертации опубликованы в 17 статьях, в том числе, в трех статьях [142−144] в журналах из Перечня ВАК РФ, и в прочих журналах и трудах научных конференций[145−158].

Структура и объем диссертации

.

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

Список литературы

включает 158 наименований.

5.6.5 Выводы.

Проведенное экспериментальное моделирование включило несколько тестовых сценариев. Во всех без исключения сценариях рост числа ВС приводил к росту конфликтов, особенно опасных сближений и попаданий в вихревой след. В то же время, увеличение соотношения константы эгоизма к константе альтруизма до некоторого предела приводило к увеличению эффективности работы системы. В целом, моделирование показало простоту, гибкость (различные сценарии) и хорошую производительность приведенного алгоритма плоского маневрирования, действующего в рамках подхода SGT, без существенного снижения показателей безопасности полета в сравнении с другими схемами разрешения конфликтов [59].

Следующими шагами усовершенствования алгоритма могут стать:

1) поиск оптимального отношения константы эгоизма к константе альтруизма и определение набора параметров, от которых это соотношение зависит;

2) использование физически более правдоподобной модели для описания движения ВС (например, с непрерывным диапазоном разрешенных изменений курса);

3) добавление возможности совершения маневров ВС в вертикальной плоскости (например, по алгоритму предотвращения попадания ВС в вихревой след в вертикальной плоскости главы 4) и выбор оптимального маневра смены курса или изменения высоты полета;

4) проверка работы алгоритма на реальных данных (например, суточных данных о прошедших полетах в каком-либо секторе ВД).