Средства моделирования на основе темпоральных сетей петри для интеллектуальных систем поддержки принятия решений

УДК 007:519.816

СРЕДСТВА МОДЕЛИРОВАНИЯ НА ОСНОВЕ ТЕМПОРАЛЬНЫХ СЕТЕЙ ПЕТРИ ДЛЯ ИНТЕЛЛЕКТУАЛЬНЫХ СИСТЕМ ПОДДЕРЖКИ ПРИНЯТИЯ РЕШЕНИЙ

А.П. Еремеев (eremeev@appmat.ru)

Ю.И. Королев (korolevyu@gmail.com)

Национальный исследовательский университет «МЭИ», Москва

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

Введение

В настоящее время в области информационных технологий можно выделить два класса систем [Ларичев и др., 1987]: OLTP (On-Line Transaction Processing) системы, ориентированные на операционную (транзакционную) обработку данных; DSS (Decision Support Systems - системы поддержки принятия решений) системы, ориентированные на аналитическую обработку данных с целью повышения уровня автоматизации и качества принимаемых решений.

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

На кафедре прикладной математики Национального исследовательского университета «МЭИ» в научной группе, организованной одним из основателей направления «искусственный интеллект» в СССР и России Д.А. Поспеловым, более тридцати лет проводятся исследования по разработке математического и программного обеспечения ИСППР, ориентированных на открытые и динамические предметные области [Башлыков и др., 1994]. При разработке таких систем, типичными представителями которых являются ИСППР РВ для помощи оперативно-диспетчерскому персоналу при мониторинге и управлении сложными техническими системами [Вагин и др., 2001], используются предложенная Д.А. Поспеловым концепция семиотических систем управления [Поспелов, 1981] и аппарат нетрадиционных логик [Вагин и др., 2008].

ИСППР РВ предназначены для помощи ЛПР при мониторинге и управлении сложными объектами и процессами в условиях достаточно жестких временных ограничений. Одной из главных задач таких систем является помощь ЛПР для удержания объекта в штатном режиме функционирования и возвращения его в этот режим при возникновении каких-либо отклонений (аномалий). В работе [Еремеев и др., 2003a] предложено конструировать ИСППР как интегрированные интеллектуальные системы семиотического типа, сочетающие строгие, формальные методы и модели поиска решений с нестрогими, эвристическими методами и моделями, базирующимися на знаниях специалистов-экспертов, моделях человеческих рассуждений, имитационных моделях, неклассических логиках и накопленном опыте.

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

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

1. Цветные сети Петри как инструмент моделирования сложных объектов

Сети Петри (СП) позволяют естественно описывать синхронизацию, параллелизм, конфликт и причинную зависимость, а также наглядно представлять структуру и поведение систем. Основы теории обычных СП изложены, например, в работе [Котов, 1984]. Можно вводить ряд дополнительных правил и условий в алгоритмы моделирования, получая ту или иную разновидность СП. В частности, теория цветных сетей Петри (ЦСП) разрабатывается более 20 лет рабочей группой под руководством профессора Курта Йенсена [Jensen, 1984]. ЦСП – это графоориентированный язык для проектирования, описания, имитации и контроля распределенных и параллельных систем. Графическими примитивами показывается течение процесса, а конструкциями специального языка имитируется необходимая обработка данных. Показано [Jensen, 1984], что для каждой ЦСП можно построить обычную СП, и наоборот. Преимуществом ЦСП перед обычными СП является более компактный и удобный язык моделирования.

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

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

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

ЦСП реального времени (ЦСП РВ) [Szpyrka et al, 2006] являются функциональным подклассом ЦСП, ориентированным на моделирование и анализ систем реального времени. По сравнению с ЦСП, в ЦСП РВ используется другая модель времени и приоритеты переходов, на них наложены некоторые структурные ограничения, что в итоге позволяет разработчикам прямое моделирование элементов.

Чтобы проиллюстрировать главные аспекты ЦСП РВ, приведем в качестве примера модель автоматической остановки поезда. В кабине машиниста каждые 60 секунд загорается световой сигнал, чтобы проверить, контролирует ли он идущий поезд. Если машинист проигнорирует световой сигнал, то через 6 секунд включается звуковой сигнал. Если машинист не дезактивирует его в течение 3 секунд, срабатывает механизм аварийного торможения. Модель ЦСП РВ для данного примера, представленная на рис 1., содержит шесть мест: ContrSyst - элемент, контролирующий систему; Console - консоль в кабине для отображения сигналов; Brake - механизм торможения; Driver -машинист поезда; Timer1 и Timer2- таймеры; и пять переходов: TurnOnLS -включение светового сигнала; TurnOnSS - включение звукового сигнала; TurnOnBrake - запуск механизма торможения; Disactivate - дезактивация машинистом сигналов; Activity - моделирование действий машиниста.

Задана начальная маркировка, начальные значения временных меток равны нулю и опущены. Переход Disactivate имеет приоритет 1, остальные переходы – 0 (опущены на схеме). Весовые и временные выражения дуг разделены знаком @. Если временное выражение равно 0, то оно опущено. Каждая дуга с двумя стрелками заменяет для наглядности пару дуг.

Рис. 1. Модель системы остановки поезда на основе ЦСП РВ

2. Средства моделирования на основе ЦСП РВ с темпоральной логикой

Временные зависимости подразделяются на [Еремеев и др., 2003b]:

количественные (метрические) – когда для представления времени используются количественные меры на временной оси;
качественные – когда используется только относительное положение во времени событий или действий.

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

Формальное определение ЦСП РВ с использованием темпоральной логики Аллена приведено в работе [Еремеев и др., 2011]. Модель системы остановки поезда, построенная с помощью данного аппарата, представлена на рис. 2. Переход к логике Аллена привел к сужению множества цветов и разбиению сети на две несвязные подсети, одна из которых определяет работу механизма аварийного торможения, а другая моделирует действия машиниста. Формулы логики Аллена применены в данном случае как защитные функции переходов DisactLS и DisactSS, обозначающих своевременную реакцию ЛПР (машинист) на световой и звуковой сигнал соответственно. Главным преимуществом в данном случае является возможность задавать не конкретное время реакции, как в случае ЦСП РВ, а интервалы, на которых машинист может дезактивировать систему и каждый из которых определяет дальнейшее поведение модели. Таким образом, включение в модель аппарата интервальных темпоральных логик позволило адекватно отразить неопределенность, присущую задаче.

Рис. 2. Модель системы остановки поезда на основе ЦСП РВ с темпоральной логикой

Компьютерное моделирование в ИСППР РВ актуально как для теоретических исследований, так и для практического применения. Создание инструментария для решения подобных задач представляет серьезную проблему, прежде всего потому, что среда разработки должна поддерживать концепцию РВ, а также из-за уникальности разрабатываемых моделей. Отметим, что некоторые современные системы, в частности, G2 - инструментальный комплекс конструирования систем РВ (Gensym Corp., США) позволяют реализовывать подобные проекты. G2 является объектно-ориентированной интегрированной средой для разработки и сопровождения приложений – ИС РВ, использующих базы знаний. В отличие от систем, ориентированных на какую-то одну методологию или на конкретную предметную область, G2 интегрирует в себе множество взаимодополняющих методов искусственного интеллекта, что упрощает и ускоряет процесс разработки приложений и позволяет делать их достаточно универсальными [Еремеев и др., 1998]. Эти особенности позволили разработать в данной среде достаточно эффективный инструментарий для моделирования систем на основе ЦСП РВ, в том числе, с поддержкой темпоральной логики Аллена. Модель системы остановки поезда, созданная средствами G2, приведена на рис.3.

Рис. 3. Модель системы остановки поезда в среде G2

Результаты работы планируется использовать для создания прототипа ИСППР РВ для оперативно-диспетчерского персонала энергоблока в плане исследований НИУ «МЭИ» по тематике разработки методов, моделей и базовых инструментальных программных средств конструирования ИСППР РВ для мониторинга и управления сложными объектами типа объектов энергетики и транспортных систем.

Благодарности. Исследования выполняются при финансовой поддержке РФФИ (проекты № 11-01-00140, 12-07-00508).

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

[Башлыков и др., 1994] Башлыков А.А., Еремеев А.П. Экспертные системы поддержки принятия решений в энергетике. – М.: Издательство МЭИ, 1994.

[Вагин и др., 2001] Вагин В.Н., Еремеев А.П. Некоторые базовые принципы построения интеллектуальных систем поддержки принятия решений реального времени. – Известия РАН. Теория и системы управления, 2001, № 6.

[Вагин и др., 2008] Вагин В.Н., Еремеев А.П. Исследования и разработки кафедры прикладной математики по конструированию интеллектуальных систем поддержки принятия решений на основе нетрадиционных логик. – Вестник МЭИ. 2008. № 5.

[Емельянов и др., 1998] Емельянов В.В., Ясиновский С.И. Введение в интеллектуальное имитационное моделирование сложных дискретных систем и процессов. Язык РДО. – М.: «АНВИК», 1998.

[Еремеев и др., 1998] Еремеев А.П., Чибизова Н.В. Проектирование экспертных систем реального времени на основе инструментального комплекса G2. Методологические указания – М.: Издательство МЭИ, 1998.

[Еремеев и др., 2003a] Еремеев А.П., Тихонов Д.А., Шутова П.В. Поддержка принятия решений в условиях неопределенности на основе немарковской модели. – Известия РАН. Теория и системы управления, 2003, № 5.

[Еремеев и др., 2003b] Еремеев А.П., Троицкий В.В. Модели представления временных зависимостей в интеллектуальных системах поддержки принятия решений. – Изв. РАН. Теория и системы управления, 2003, № 5.

[Еремеев и др., 2010] Еремеев А.П., Куриленко И.Е. Средства темпорального вывода для интеллектуальных систем реального времени. – Интеллектуальные системы. Колл. монография. Вып. 4. – М.: Физматлит, 2010.

[Еремеев и др., 2011] Еремеев А.П., Королев Ю.И. Применение модифицированных сетей Петри при создании интеллектуальных систем поддержки принятия решений. – Интегрированные модели и мягкие вычисления в искусственном интеллекте. Сб. научных трудов VI-й Международной научно-практической конференции (Коломна, 16-19 мая 2011 г.). В 2-х томах. Т2. – М.: Физматлит, 2011.

[Котов, 1984] Котов В.Е. Сети Петри – М.: Наука, 1984.

[Ларичев и др., 1987] Ларичев О.И., Петровский А.В. Системы поддержки принятия решений. Современное состояние и перспективы их развития. Итоги науки и техники. Сер. Техническая кибернетика. Т.21. – М. ВИНИТИ, 1987.

[Поспелов, 1981] Поспелов Д.А. Логико-лингвистические модели в системах управления. – М.: Энергоиздат, 1981.

[Allen, 1983] Allen J.F. Maintaining knowledge about temporal intervals // Communications of the ACM, v. 26, n. 11, 1983.

[Jensen, 1984] Jensen K. Colored Petri Nets. Basic Concepts, Analysis Methods and Practical Use // Springer-Verlag Berlin Heidelberg New York, 1997.

[Szpyrka et al, 2006] Szpyrka M., Szmuc T. Integrated approach to modelling and analysis using RTCPnets // IFIP International Federation for Information Processing, vol. 227, New York, 2006.