автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.11, диссертация на тему:Автоматизация деятельности авиадиспетчера: подход на основе исполняемых спецификаций

МОСКОВСКИЙ ИНЖЕНЕРНО-ФИЗИЧЕСКИЙ ИНСТИТУТ

РГ6 од

«I

до/.

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

ИВАНЕЦ Сергей Владимирович:

Автоматизация деятельности авиадиспетчера: подход на основе исполняемых спецификаций

05.13.11 - Математическое и программное обеспечение вычислительных машин, комплексов, систем и сетей

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

Автор:

Москва - 1994

Работа выполнена в Московском ордена Трудового Красного Знамени инженерно-физическом институте.

Научный руководитель:

кандидат технических наук, доцент Ильинский Н.И.

Официальные оппоненты:

доктор технических наук, профессор

Я.А.Хетагуров, кандидат технических наук П.А.Шаглий.

Ведущая организация - Государственный научно-исследовательский институт "Аэронавигация" (ГосНИИ "Аэронавигация").

Защита диссертации состоится 25 мая 1994г. в 16.00 на заседании специализированного Совета Д053.03.04 в Московском инженерно-физическом институте по адресу: 1 15409, Москва, Каширское ш., 31.

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

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

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

Ученый секретарь специализированного Совета

А.Д.Модяев

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

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

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

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

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

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

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

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

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

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

1. Исследование особенностей функционирования сложных систем на примере системы УВД в районе аэродрома.

2. Выявление наиболее "узких мест" диспетчерского обеспечения УВД и возможностей их устранения.

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

данных с учетом накладываемых ограничений.

4. Построение формальной модели системы текущего планирования воздушного движения в аэродромном районе.

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

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

Методы исследования, применявшиеся при решении поставленных задач, основаны на использовании аппарата логики 1-го порядка, теории сложности, методологии системного подхода.

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

1. Впервые обоснована необходимость и поставлена задача автоматизированного поиска бесконфликтных планов при движении ВС в аэродромной зоне.

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

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

б) интерпретацию модели как системы исполняемых спецификаций;

в) исследование модели с позиций теории сложности, декомпозиция ее на фрагменты в соответствии с их

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

3. Поставлена задача и разработана модель движения воздушного судна вдоль гладкой траектории в аэродромной зоне.

4. Разработано алгоритмическое и программное обеспечение системы планирования воздушного движения, предназначенное для исполнения в операционной среде UNIX System V на различных ЭВМ, поддерживающих ее.

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

Реализация результатов работы. Научные и практические результаты, изложенные в диссертации, использованы в научно-экспериментальной работе по Государственному заказу Департамента воздушного транспорта Министерства транспорта Российской Федерациии (договор N 1513/92-335 3 0) а также в плановой госбюджетной НИР в МИФИ по теме "Разработка системы оптимального планирования" (договор N 91-3-022-500) и внедрены в ГосНИИ "Аэронавигация" и АДЦ "Минеральные Воды", что подтверждено соответствующими актами о внедрении.

Апробация работы. Основные результаты работы апробированы на Всесоюзном семинаре по логическому программированию (Новосибирск, п. Листвянка, 1990), Всесоюзном семинаре по систолическому программированию

<

(Львов, 1991), Second Russian Conference on Logic Programming (С.-Петербург, 1991), семинаре "Аппаратная поддержка интеллектуальных систем. Параллелизм в интеллектуальных системах" в рамках Ассоциации искусственного интеллекта (Москва, 1992).

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

Структура и объем работы. Диссертация состоит из введения, 4 глав, заключения, выводов и библиографического указателя литературы. Работа изложена на 183 страницах машинописного текста, иллюстрирована 24 таблицами, 34 рисунками. Библиографический указатель включает 167 источников, в том числе 100 отечественных и 67 зарубежных авторов.

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

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

Формальная постановка задачи определяет в качестве исходных данных состояние воздушного пространства В В: С-> Н хТ,

где С - множество всех контрольных точек зоны, Н -множество дискретных значений высот, Т - множество дискретных значений времен в некотором интервале планирования. Отношение В определяет доступность для движения ВС различных эшелонов (высот) в различные моменты времени над каждой контрольной точкой аэродромной зоны.

Также исходными данными служат множество различных маршрутов полета М (плоскостных), проходящих через контрольные точки зоны, и множество воздушных судов в, рассматриваемых в заданном интервале планирования.

Задача данного исследования заключается в определении отображения /Я ; В х М х в -> Р, где Р - множество планов полетов всех ВС. При этом V д е в Эр с Р : 8(Р), О(р). Под безопасностью 5(Р) понимается согласованность и отсутствие потенциальных конфликтов во всей совокупности принятых ранее планов. Физическая осуществимость 0(р) включает такие факторы, как непрерывность функции скорости, соответствие скорости и ускорения летно-техническим характеристикам ВС и требованиям комфортности полета и т.п.

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

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

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

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

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

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

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

В связи с этим предлагается, абстрагируясь вначале от таких характеристик сложности, как пространственная и временная, получить наиболее простое решение, используя исчисление предикатов 1-го порядка. Язык предикатов обладает рядом характерных особенностей, которые могут быть эффективно использованы при построении модели системы УВД. К таким особенностям относятся:

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

Соответственно принятому подходу могут быть сформулированы этапы разработки, а также факторы,

принимаемые при этом во внимание.

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

м = <у, о, Рт, и о, и, р, г>,

где V - множество всех переменных модели, О - предметная область, задающая допустимые значения всех переменных из V, Рт - множество ш-местных предикатов, использованных в модели, I. - множество унарных и бинарных пропозициональных связок, О - множество используемых кванторов, и - множество вспомогательных знаков, Я" -множество формул, составляющих модель, Z - правило вывода.

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

Так был получен практически готовый к исполнению программный код в стиле языков логического программирования, в частности ПРОЛОГа, что позволило решить проблему интеллектуальной сложности системы.

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

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

Качественно иное решение состоит в анализе структуры временной сложности задачи и определении подзадачи, обуславливающей "узкое место". С учетом особенностей

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

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

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

решения, что, в свою очередь, снимает проблему временной сложности.

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

В результате экспериментальных исследований получено, что прототип в состоянии одновременно обрабатывать информацию более чем о 130 ВС. При отсутствии потенциальных конфликтов время, требуемое для построения плана полета одного ВС, находится в линейной зависимости от общего их числа и не превышает 1.5 с для 100 одновременно рассматриваемых ВС. Для потока ВС, содержащего конфликты, рост времени расчета в зависимости от общего числа ВС носит экспоненциальный характер. Непрерывная подмодель и другие меры по оптимизации модели, направленные на сокращение перебора при вычислениях, позволили существенно удлинить пологий участок экспоненты. Время обслуживания в 2 с достигается лишь при общем числе ВС, превышающем 80-90. Полученные количественные характеристики покрывают

потребности практически всех аэропортов СНГ и многих крупных аэропортов мира.

Решение серии тестовых задач показало, что для 6 ВС 3-х различных типов, прибывающих в течение 11 мин, с 3-х направлений и образующих до 10 ситуаций потенциального конфликта, система успешно строит планы полетов, полностью согласующиеся с летно-техническими характеристиками соответствующих ВС. При выполнении полетов по этим планам все ВС будут разделены требуемыми нормами эшелонирования. Отклонения от запланированного времени прибытия, связанные с разрешением конфликтных ситуаций, для всех ВС в сумме составили менее 2-х мин.

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

Система реализована на языке С в операционной среде UNIX System V с использованием сетевых протоколов и библиотек XWindows. Программная реализация СПЛАВ основана на принципах взаимодействия "клиент - сервер", принятых в ряде стран в качестве промышленного стандарта.

Операционная среда UNIX позволила удовлетворить требование совместимости с программным обеспечением многих современных систем УВД. Кроме того, UNIX

обеспечила универсальность и мобильность разработки. Благодаря использованию библиотек Х\Мпс1о\У5 оказалось возможным построить высококачественный пользовательский интерфейс, соответствующий международным стандартам. Технология "клиент - сервер" и протоколы Х\ЛЛпс1о\¥з придали гибкость конфигурации системы.

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

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

3. Определено, что построенная в рамках логики исчисления предикатов модель может быть непосредственно интерпретирована как исполняемые спецификации или код в стиле языков логического программирования.

4. Исследованы вопросы временной сложности задачи. Предложены два подхода к проблеме сокращения перебора

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

5. На основе полученных исполняемых спецификаций построен прототип системы управления воздушным движением на языке логического программирования ПРОЛОГ.

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

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

8. Научные и практические результаты работы внедрены в ГосНИИ "Аэронавигация" и АДЦ "Минеральные Воды", что подтверждено соответствующими актами о внедрении.

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

работах:

[ 1 j Иванец С.В. Язык программирования и параллельный компьютер //Международный компьютерный журнал НовИнТех. - 1991. - N1. - С. 7-11.

[2] Ivanets S., Ilinsky N.r Krylov M. WAM Specification for Parallel Execution on SIMD Computer //Proc. Russian Conference on Logic Programming, 2 Ann. Conf., St.Peterburg, Russia, September 11-16, 1991. - P. 232-239.

[3] Разработка системы оптимального планирования. Математическая модель движения воздушных судов в районе аэродрома: (Промежуточный). Тема 91-3-022-500; 02.9.30. 000220 /Рук. темы Ильинский Н.И.; Отв. исп. Иванец С.В. - М.: МИФИ, 199 1. - 26 с.

[4] Ivanets S., Ilinsky N., Krylov M. Towards Parallel WAM //Proc. The European Workshops on Parallel Computing "From Theory to Sound Practice", Barcelona (Sitges), Spain, March 23-24, 1992.- P. 297-305.

[5] Ivanets S., Ilinsky N., Krylov M., Timohin S. Optimum Flight Planning System for Aerodrome Zone //Proc. International Logic Programming Conference, Budapest, Hungry, June 2125, 1993. - P. 317-318.

Л-34074 от 10.04.94

Зак. 1089, тир. 100

Типография ЦБ РФ