=Paper=
{{Paper
|id=Vol-1825/p34
|storemode=property
|title= Мультиагентная программная система взаимодействия управляемых динамических объектов (Multi-agent software system of dynamic objects interaction)
|pdfUrl=https://ceur-ws.org/Vol-1825/p34.pdf
|volume=Vol-1825
|authors=Sagit S. Valeev,Yuliya.V. Zigangirova
}}
== Мультиагентная программная система взаимодействия управляемых динамических объектов (Multi-agent software system of dynamic objects interaction)==
https://ceur-ws.org/Vol-1825/p34.pdf
Мультиагентная программная система взаимодействия
управляемых динамических объектов
С.С. Валеев Ю.В. Зигангирова
vss@mail.ru julia.zigangirova@mail.ru
Уфимский государственный авиационный технический университет (Уфа)
Аннотация
Рассматриваются распределённые вычислительные системы, воз-
никающие при взаимодействии бортовых вычислительных ком-
плексов управляемых динамических объектов в конфликтных си-
туациях (на примере систем предупреждения столкновений воз-
душных судов). Обсуждаются вопросы обеспечения эффективного
взаимодействия систем при решении совместных задач. Предлага-
ется рассматривать данную задачу с точки зрения мультиагентного
подхода.
Ключевые слова: управляемый динамический объект, распреде-
лённая вычислительная система, бортовой вычислительный ком-
плекс, мультиагентная система, конфликтная ситуация, воздушное
судно.
1 Введение
Рассматриваются распределённые вычислительные системы, возникающие в момент взаимодействия бор-
товых вычислительных комплексов управляемых динамических объектов. При этом они представляют
собой обособленные сложные технические объекты, имеющие средства взаимодействия с другими подоб-
ными объектами. Примером могут служить воздушные суда (ВС).
В рассматриваемом случае, предполагается, что управляемые динамические объекты способны незави-
симо от других объектов изменять своё положение в пространстве, что в ряде случае может привести к
возникновению конфликтных ситуаций. Процесс разрешения конфликтной ситуации представляет собой
процесс принятия решения на основе известного набора данных: прежде всего, данных о геометрической
конфигурации модели конфликтной ситуации и динамических характеристиках управляемых динамиче-
ских объектов, участвующих в решении задачи преодоления конфликтной ситуации. При решении задачи
принятия решений необходимо использование значительных вычислительных ресурсов специализирован-
ных бортовых вычислительных комплексов, включающих в себя как аппаратные средства сбора данных и
обеспечения взаимодействия систем, так и соответствующие программные комплексы.
2 Актуальность вопроса
Вопросы обеспечения эффективного взаимодействия управляемых динамических объектов и, в частно-
сти, воздушных судов в процессе разрешения конфликтных ситуаций представляет актуальную научно-
техническую задачу, так как ошибки в этом процессе могут повлечь гибель людей.
Copyright c by the paper’s authors. Copying permitted for private and academic purposes.
In: G.A. Timofeeva, A.V. Martynenko (eds.): Proceedings of 3rd Russian Conference "Mathematical Modeling and Information
Technologies" (MMIT 2016), Yekaterinburg, Russia, 16-Nov-2016, published at http://ceur-ws.org
269
Несмотря на то, что известны решения, позволяющие избежать большого числа авиационных проис-
шествий (бортовые системы предупреждения столкновений), по данным Федеральной службы государ-
ственной статистики [3], а также по данным базы авиационных происшествий Aviation Safety Network [4]
ежегодно в мире происходит около 30-40 происшествий, в которых в среднем погибает 1000 человек и с
каждым годом их количество возрастает. При этом, согласно тем же источникам, процент столкновений
ВС в воздухе составляет до 10-12 от общего числа авиационных происшествий.
Одной из основных причин столкновений самолётов в воздухе можно назвать несовершенство процессов
взаимодействия и согласования между системами предупреждения столкновений (катастрофа на Боден-
ским озером тому подтверждение). Несмотря на большое количество работ, связанных с совершенство-
ванием данных систем и лежащих в её основе алгоритмов, основная часть из них связана с вопросами
управления воздушными судами при разрешении конфликтных ситуаций [5] и задачами планирования
траекторий маневрирования [6]. Известные же работы по изучению процессов взаимодействия (прежде
всего, с точки зрения мультиагентного похода) описывают взаимодействие абстрактных объектов и не
учитывают специфику предметной области [7].
3 Система разрешения конфликтных ситуаций между динамическими объек-
тами
Для разрешения конфликтных ситуаций между ВС используются так называемые Системы предупрежде-
ния столкновений самолётов в воздухе (Traffic Alert and Collision Avoidance System, TCAS). Эти системы
представляют собой бортовые вычислительные комплексы, которые позволяют наблюдать за ближним
воздушным пространством ВС, идентифицировать наличие других объектов в этой зоне, анализировать
информацию о взаимном расположении, и в случае обнаружения потенциальной угрозы столкновения,
выдавать предупреждение пилотам [1]. Если расстояние между ВС оказывается меньше интервала без-
опасного эшелонирования [2], система предупреждения столкновений просчитывает и выдаёт пилотам ре-
комендацию по маневрированию.
Рис. 1: Структура бортового комплекса для разрешения конфликтных ситуаций
Бортовой комплекс TCAS для разрешения конфликтных ситуаций между ВС имеет структуру, пока-
занную на рисунке 1, и включает в себя следующие блоки: вычислительный блок и соответсвующее ему
программное обеспечение (включающие также некоторую базу данных), блок индикации выработанных
решений (дисплей, звуковое оповещение). Для функционирования комплекса также необходимы блок сбора
данных (антенны и сенсоры) и блок передачи данных (транспондер ADS-B).
Взаимодействие TCAS при разрешении конфликтной ситуации осуществляется с помощью специального
оборудования – приёмоответчика, или транспондера (англ. transponder, от transmitter-responder). Процесс
взаимодействия систем (упрощённая структура обмена сообщениями в виде диаграммы последовательно-
стей «as is») показан на рисунке 2.
Дескрипторы UF, DF обозначают соответственно сообщения по каналу связи «вверх» (сообщения-
запросы) и по каналу связи «вниз» (сообщения-ответы). В зависимости от значения дескриптора раз-
270
личают сообщения наблюдения (UF = 0, DF = 0), сообщения отслеживания траекторий (UF = 20, DF =
20) и координационные сообщения (UF = 16, DF = 16).
Рис. 2: Упрощённая структура обмена сообщениями в виде диаграммы последовательностей «as is»
После обнаружения конфликтной ситуации каждая из систем просчитывает и вырабатывает некоторый
сценарий по её разрешению. В ряде случаев, из-за отсутствия объективной информации о состоянии управ-
ляемых динамических объектов и состоянии внешней среды, выработанные сценарии могут различаться,
следовательно, возникает необходимость их согласования.
Как известно, в настоящее время согласование решений между TCAS происходит по жёсткому алго-
ритму и представляет собой простое подтверждение получения сообщения со сценарием разрешения кон-
фликтной ситуации и выбор первого выработанного сценария [1]. В данной работе предлагается перейти
от жёстких программных алгоритмов к мультиагентному взаимодействию [8], [9]. Тогда рассматриваемые
системы можно представить в виде интеллектуальных агентов, принимающих совместные решения. При
этом возникает задача обеспечения их эффективного взаимодействия.
При согласовании решений между агентами могут быть использованы различные концепции выработки
совместных решений. Например, в соответствии с принципом пригодности процесс согласования должен
включать процедуру подтверждения получения сообщения со сценарием разрешения конфликтной ситуа-
ции. В качестве общего решения в мультиагентной системе принимается сценарий, обеспечивающий дости-
жение заданных характеристик системы в рамках известных ограничений. При этом основным критерием
эффективности является время, необходимое для выработки совместного решения.
В рамках же принципа оптимальности из всех допустимых стратегий выбирается та, которая приводит
к наилучшим значениям характеристик системы, то есть критерием выбора сценария является некоторый
271
показатель его эффективности.
4 Предлагаемое решение
В работе рассматривается реализация взаимодействия агентов в соответствии с принципом адаптивного
поведения в условиях влияния различных факторов неопределённости, что предполагает изменение правил
выработки совместного решения при различных конфликтных ситуациях.
Рис. 3: Упрощённая структура обмена сообщениями в виде диаграммы последовательностей «to be»
В нашем случае алгоритмы взаимодействия программных агентов, во-первых, должны включать ре-
шение задачи оптимизации рекомендаций по некоторому критерию и соответствующей дополнительной
координации, а во-вторых, должны предусматривать возможность изменения критериев поиска оптималь-
ного решения в зависимости от текущей ситуации: использовать либо критерий, учитывающий временя
выработки решения, либо – критерий, учитывающий эффективность решения (сценария) по заданным
показателям.
Однако в таком случае, если в качестве критерия оптимизации выбрать некоторый критерий эффек-
тивности предлагаемого сценария разрешения конфликтной ситуации, то процесс согласования не может
состоять в принятии первого выработанного решения. (Далее будем считать, что такой критерий известен
и задан.) Таким образом, здесь возникает необходимость так изменить процедуры обмена сообщениями
(протокол), чтобы стало возможным решение задачи оптимизации рекомендации.
272
Необходимо понимать, что включение в структуру диалога дополнительных итераций влечёт за собой
увеличение времени принятия решения, следовательно, в ряде случаев применение систем предупреждения
столкновений, построенной в строгом соответствии с концепцией оптимальности, не желательно.
Например, в случае внезапного обнаружения конфликтной ситуации, то есть существенного дефици-
та времени, необходимо максимально быстро выработать любое допустимое решение. И наоборот, в нор-
мальных условиях возможно выбрать сценарий разрешения конфликтной ситуации, подразумевающий
выполнение более эффективного манёвра. Поэтому предлагается реализация системы предупреждения
столкновений в соответствии с концепцией адаптивного поведения, что означает, что правило выбора ре-
шения может изменяться при изменении некоторых условий [10].Следовательно, алгоритмами системы
предупреждения столкновений должна быть предусмотрена возможность в зависимости от текущей ситу-
ации изменять критерий поиска решения: либо использовать критерий времени выработки решения, либо
– критерий его эффективности.
На рисунке 3 наглядно показана упрощённая структура диалога при выборе решения по некоторому кри-
терию его эффективности в виде диаграммы последовательностей «to be». Суть предлагаемых изменений
заключается во введении в процесс разрешения конфликтной ситуации этапа оптимизации рекомендаций
(в соответствии с заранее определённым критерием) и соответствующей дополнительной координации.
В этом случае после выработки некоторой предварительной рекомендации система предупреждения
столкновений отправляет координационный запрос, содержащий информацию об этой рекомендации, дру-
гой системе. Она, в свою очередь, отправляет аналогичный запрос первой, после чего происходит решение
оптимизационной задачи в соответствие с заранее определённым критерием эффективности.
В процессе разрешения конфликтной ситуации между двумя ВС данная задача фактически сводится к
сравнению двух сценариев и выбору наилучшего. Поскольку сравнение представляет собой простую задачу,
имеющую единственное решение, то согласование полученных двумя системами результатов возможно по
правилу первого выработанного решения.
Для возможности осуществления взаимодействия систем в соответствии с предложенной структурой
диалога 2 необходимо внести изменения в форматы сообщений протоколов СПС. Данные сообщения ча-
стично рассматривались работе [10], где были сделаны выводы о возможности внесения дополнительных
информационных битов.
5 Заключение
Рассматривается мультиагентная программная система взаимодействия управляемых динамических объ-
ектов. Обсуждаются особенности архитектуры распределённой вычислительной системы, формируемой
при взаимодействии бортовых вычислительных комплексов управляемых динамических объектов в кон-
фликтных ситуациях (на примере систем предупреждения столкновений воздушных судов). Предлагается
решение задачи обеспечения эффективного взаимодействия систем на базе модифицированного протокола
взаимодействия в распределенной вычислительной системе.
Список литературы
[1] ICAO Doc 9574. Airborne Collision Avoidance System (ACAS) Manual. Montreal, International Civil
Aviation Organization, 2006.
[2] ICAO Doc 9574. Manual on Implementation of a 300 m (1 000 ft) Vertical Separation Minimum
Between FL 290 and FL 410 Inclusive. Montreal, International Civil Aviation Organization, 2006.
[3] Rossija v cifrah. 2015: Kratkij statisticheskij sbornik. Moskva, Rosstat, 2015. (in Russian) = Россия в
цифрах. 2015: Краткий статистический сборник. Москва, Росстат, 2015.
[4] Aviation Safety Network: Statistics. Aviation Safety Network. URL: http://aviation-
safety.net/statistics/(02.04.2016).
[5] S. I. Kumkov, S. G. Pjatko. Zadacha obnaruzhenija i razreshenija konfliktnyh situacij
v avtomatizirovannoj sisteme upravlenija vozdushnym dvizheniem. Nauchnyj vestnik «NII
Ajeronavigacii», 12:35-45, 2013. (in Russian) = С. И. Кумков, С. Г. Пятко. Задача обнаружения и
разрешения конфликтных ситуаций в автоматизированной системе управления воздушным дви-
жением. Научный вестник «НИИ Аэронавигации», 12:35-45, 2013.
273
[6] D. Sislak. Agent-based Approach to Air-Traffic Modeling, Simulation and Collision Avoidance.
Collection of Articles with Commentary. Prague, 2013.
[7] S. S. Parondzhanov. Modeli, metody i programmnye sredstva organizacii vzaimodejstvija
intellektual’nyh agentov. Avtoref. dis. kand. tehn. nauk: 05.13.11. Moskva, 2008. (in Russian) = С. С.
Паронджанов. Модели, методы и программные средства организации взаимодействия интеллек-
туальных агентов. Автореф. дис. канд. техн. наук: 05.13.11. Москва, 2008.
[8] Yu. V. Ayguzina , S. S. Valeev. Multiagent approach for. collision avoidance systems in aviation. Vestnik
UGATU, 18(5):15-19, 2014.
[9] Yu. V. Ayguzina , S. S. Valeev. Multiagent approach for collision avoidance systems. Proceedings of the
2nd International Conference «Information Technologies for Intelligent Decision Making Support» and
the Intended International Workshop «Robots and Robotic Systems», Ufa, vol. 8, pp. 8-11, 2014.
[10] S. S. Valeev, Ju. V. Zigangirova. Protokoly vzaimodejstvija dinamicheskih sistem dlja razreshenija
konfliktnyh situacij. Materialy 3-ej mezhdunarodnoj konferencii «Informacionnye tehnologii
intellektual’noj podderzhki prinjatija reshenij 2015», Ufa:102-106, 2015. С. С. Валеев, Ю. В. Зиганги-
рова. Протоколы взаимодействия динамических систем для разрешения конфликтных ситуаций.
Материалы 3-ей международной конференции «Информационные технологии интеллектуальной
поддержки принятия решений 2015», Уфа:102-106, 2015.
274
Multi-agent software system of dynamic objects interaction
Sagit S. Valeev
Ufa State Aviation Technical University (Ufa, Russia)
Yuliya.V. Zigangirova
Ufa State Aviation Technical University (Ufa, Russia)
Abstract. Distributed computing systems arising in interaction between on-board computer systems of
controlled dynamic objects in conflict situations are considered (in case of aircraft collision avoidance systems).
The issues of effective communication between systems are discussed. It is proposed to consider this problem
from the perspective of multiagent approach.
Keywords: controlled dynamic object, distributed computing system, on-board computer system, multiagent
system, conflict situation, aircraft.
275