Software & Systems

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

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

Цветные сети Петри как средство моделирования процессов в ИСППР РВ

ИСППР РВ в общем случае является динамической нестационарной нелинейной системой. При выборе математической модели для моделирования таких систем необходимо учитывать эти свойства, а также необходимость отображать не только закономерности функционирования, но и структурные характеристики системы. Для выявления конструктивных закономерностей системы необходимо добиться максимальной визуальной выразительности. Поэтому в качестве базовой модели была выбрана одна из графоориентированных сред моделирования – ЦСП [3].

Формально ЦСП определяется в виде кортежа N=(Σ, P, T, A, N, C, G, E, I), где Σ – непустое конечное множество типов (цветов), определяющее значения данных, операций и функций, которые можно использовать в сетевых выражениях (то есть в выражениях дуг, защитных функций и функций инициализации), каждое такое множество имеет по крайней мере один элемент; P – непустое конечное множество мест; T – непустое конечное множество переходов; A – конечное множество дуг (места, переходы и дуги описываются множествами P, T, A, которые должны быть конечными и попарно непересекающимися; требование конечности множеств позволяет избежать ряда технических проблем, например, таких, как возможность бесконечного числа дуг между двумя узлами); N: A→(P×T)È(T×P) – узловая функция, ставящая в соответствие каждой дуге пару, первый элемент которой является узлом источника, а второй – узлом назначения (допускается наличие нескольких дуг между одними и теми же узлами, поэтому A определяется как отдельное множество); C: P→Σ – функция типа, помечает каждое место p типом C(p) (это означает, что каждый токен p должен иметь значение типа С(р)); G – защитная функция: ∀t∈T: (Γ(G(t))⊆Bool, Γ(ν(G(t)))⊆Σ), ставящая в соответствие каждому переходу t логическое выражение, в котором все переменные имеют типы, принадлежащие множеству Σ (при создании графа ЦСП защитные выражения, всегда возвращающие истину, опускаются); E – функция выражений дуг, ∀a∈A: (Γ(E(a))⊆C(P(a)), Γ(ν(E(a)))⊆Σ), ставящая в соответствие каждой дуге выражение типа C(P(a)) (это означает, что результат вычисления каждого выражения дуги должен быть типа того места, откуда выходит или куда входит эта дуга); I – функция инициализации, ∀p∈P: (Γ(I(p))⊆C(p), ставящая в соответствие каждому месту выражение типа C(p).

В работе [3] показано, что для каждой ЦСП можно построить обычную СП и наоборот. Однако на практике ЦСП представляют собой более компактный и удобный язык моделирования, чем обычные СП.

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

Определим ЦСП РВ как кортеж N=(Σ, P, T, A, C, G, I, EM, ES, M0, S0), где Σ – непустое конечное множество непустых типов (множество цветов); P – непустое конечное множество мест; T – непустое конечное множество переходов, PÇT=Æ; A⊆ ⊆(P×T)È(T×P) – конечное множество дуг; C: P→Σ – функция типа; G – защитная функция: "tÎT: (Γ(G(t))⊆Bool, Γ(ν(G(t)))⊆Σ); I: T→NÈ{0} – функция приоритетов; EM – функция весовых выражений дуг, ∀aÎA: (Γ(EM(a))⊆C(P(a)), Γ(ν(EM(a)))⊆Σ); ES – функция временных выражений дуг, "aÎA: (Γ(ES(a))⊆Q+È{0}, Γ(ν(ES(a)))⊆Σ); M0 – начальная маркировка, M0(p)⊆2C(p); S0: P→Q – начальное значение функции временных меток.

Временные метки в ЦСП РВ ассоциируются с местами. Положительное значение временной метки описывает, как долго токен в соответствующем месте будет недоступным для любого перехода. Токен доступен для перехода, если значение временной метки меньше либо равно нулю. Например, равенство метки трем означает, что возраст токена – три временные единицы (возраст токена необходим для его участия в переходе). Для иллюстрации главных аспектов ЦСП РВ приведем модель автоматической остановки поезда [4]. В кабине машиниста каждые 60 секунд за- горается световой сигнал, чтобы проверить, контролирует ли он идущий поезд. Если машинист проигнорирует этот сигнал, через 6 секунд включается звуковой сигнал. Затем, если машинист не деактивирует его в течение 3 секунд, срабатывает механизм аварийного торможения.

Соответствующая ЦСП РВ представлена на рисунке 1.

Данная ЦСП РВ содержит шесть мест и пять переходов.

Множество мест P={ContrSyst, Timer1, Console, Brake, Driver, Timer2} – соответственно элемент, контролирующий систему; таймер, моделирующий ежеминутный запуск; консоль в кабине для отображения сигналов; механизм торможения; машинист поезда; таймер, моделирующий действия машиниста.

Множество переходов T={TurnOnLS, TurnOn­SS, TurnOnBrake, Disactivate, Activity} – соответственно включение светового сигнала; включение звукового сигнала; запуск механизма торможения; деактивация машинистом сигналов; моделирование действий машиниста.

Задана начальная маркировка, начальные значения временных меток равны нулю и опущены. Переход Disactivate имеет приоритет 1, остальные переходы – 0 (опущены на схеме). Весовые и временные выражения дуг разделены знаком @. Если временное выражение равно 0, оно опущено. Каждая дуга с двумя стрелками заменяет для наглядности пару дуг. Начальное состояние сети M0=(safe, on, (off, off), off, active, on); S0=(0, 0, 0, 0, 0, 0). Анализ свойств сети может осуществляться с помощью маркировки узлов графа и меток дуг. Каждая метка дуги представляет собой пару, состоящую из перехода в некоторой подстановке и течения времени. Второй элемент пары можно рассматривать как вес дуги, определяющий время, затраченное на переход от одного состояния к другому.

Качественные временные зависимости и использование темпоральной логики

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

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

Временной интервал X – упорядоченная пара (X-, X+), такая, что X-

Обозначим Int множество всех временных интервалов, а переменную, определяющую интервал, ассоциирующийся с местом p, будем обозначать именем этого места. Для корректного оперирования временными интервалами переопределим некоторые элементы ЦСП РВ [7]. Представим ЦСП РВ с поддержкой логики Аллена в виде кортежа N=(Σ, P, T, A, C, G, I, EM, ES, M0, S0), где Σ – непустое конечное множество непустых типов (множество цветов); P – непустое конечное множество мест; T – непустое конечное множество переходов, PÇT=Æ; A⊆(P×T)È(T×P) – конечное множество дуг; C: P→Σ – функция типа; G – защитная функция: ∀tÎT: (Γ(G(t))⊆Bool, Γ(ν(G(t)))⊆ΣÈInt); I: T→NÈ{0} – функция приоритетов; EM – функция весовых выражений дуг, ∀aÎA: (Γ(EM(a))⊆C(P(a)), Γ(ν(EM(a)))⊆ΣÈInt); ES – функция временных выражений дуг, ∀aÎA: (Γ(ES(a))⊆Q+È{0}, Γ(ν(ES(a)))⊆ΣÈInt); M0 – начальная маркировка, M0(p)⊆2C(p); S0: P→Q – начальное значение функции временных меток.

Модель системы остановки поезда на основе данного аппарата представлена на рисунке 2.

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

Разработка инструментария и практическое моделирование

Компьютерное моделирование ИСППР РВ актуально для теоретических исследований и для практического применения. Создание соответствующего инструментария представляет серьезную проблему, так как среда разработки должна поддерживать концепцию реального времени, а также достаточную универсальность разрабатываемых моделей. Инструментальный комплекс G2 (Gen­sym Corp., США) удовлетворяет данным требованиям [8] и является объектно-ориентированной интегрированной средой для разработки и сопровождения приложений − интеллектуальных систем РВ. В отличие от систем, ориентированных на какую-то одну методологию или на конкретную предметную область, G2 интегрирует в себе множество взаимодополняющих методов искусственного интеллекта, что упрощает и ускоряет процесс разработки приложений. Программные продукты, разработанные с помощью G2, не зависят от аппаратного обеспечения и полностью переносимы. Возможность простого манипулирования графическим представлением объектов и составление схем, являющихся отображением технологических цепочек или алгоритмов обработки данных, обеспечивают базовые средства для построения проблемно-ориентированных языков визуального программирования и разработки достаточно эффективного инструментария для систем РВ на основе ЦСП РВ с поддержкой темпоральной логики Аллена.

В качестве примера рассмотрим модель сис- темы остановки поезда, созданной в среде G2 (рис. 3). На переходах деактивации стоят защитные функции оценки истинности атомарных формул логики Аллена: Driver d LightSig на переходе DisactLS; Driver d SoundGig на переходе DisactSS. Переход DisactLS сработает, если место Driver станет удовлетворять условию доступности перехода Activity в тот момент, когда место LightSig удовлетворяет условию доступности перехода DisactLS; аналогично для перехода DisactSS. Важно, чтобы приоритет перехода DisactSS был выше приоритета DisactLS, иначе неизбежно возникнет конфликт приоритетов при реагировании машиниста в момент включенных звукового и светового сигналов. Значения защитных функций переходов вычисляются через внешние функции G2, определенные разработчиком.

Моделирование поведения машиниста осуществляется путем корректировки временного выражения дуги Activity–Driver. Существуют три варианта поведения машиниста относительно системы: 1) если машинист реагирует на сигнал в течение первых 6 секунд, срабатывает переход DisactLS, световой сигнал LightSig выключается, а звуковой SoundSig не успевает включиться по переходу TurnOnSS; 2) при реагировании машиниста в период с 7-й до 9-й секунды включительно срабатывает переход DisactSS, выключая оба сигнала LightSig и SoundSig; 3) после срабатывания на 9-й секунде перехода TurnOnBr момент реакции машиниста становится несущественным – переходы деактивации сработают, однако механизм торможения Brake к этому моменту будет уже запущен.

Проведем симуляцию при 9-секундной задержке реакции машиниста. В начальный момент параллельно срабатывают два независимых перехода TurnOnLS и Activity, изменив состояние сети на новое. Далее в течение 6 секунд ни один переход не становится допустимым, а по истечении этого времени срабатывает переход TurnOnSS, меняя цвет токена в месте SoundSig (рис. 4). Через 3 секунды после этого становятся допустимыми два перехода: TurnOnBr и DisactSS, но, поскольку изначально приоритет последнего был установлен более высоким, сработает переход деактивации. При этом поменяются токены в местах LightSig и SoundSig, что не позволит сработать переходу TurnOnBr. Далее в течение 51 секунды система останется стабильной, а единственным изменением будет непрерывное уменьшение временных меток с установленным шагом в 1 секунду. Затем модель вернется к исходному состоянию и сработают переходы при таймерах. Изменяя значение временной метки дуги Activity–Driver, можно исследовать и другие возможные варианты работы системы.

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

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

Литература

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

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

3.     Jensen K., Coloured Petri Nets. Basic concepts, analysis methods and practical use, 1992–1997, Vol. 1–3.

4.     Szpyrka M., Szmuc T., Integrated approach to modeling and analysis using RTCPnets, IFIP Intern. Federation for Information Proc., NY, 2006, Vol. 227, pp. 115–120.

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

6.     Allen J.F., Maintaining knowledge about temporal intervals, Communications of the ACM, 1983, Vol. 26, no. 11, pp. 832–843.

7.     Еремеев А.П., Королев Ю.И. Средства моделирования на основе темпоральных сетей Петри для интеллектуальных систем поддержки принятия решений / КИИ-2012: тр. 13-й нац. конф. по искусственному интеллекту с междунар. участием (16–20 октября 2012 г., Белгород, Россия). Белгород: Изд-во БГТУ. 2012. Т. 3. С. 105–112.

8.     Еремеев А.П., Гречкина П.В., Чибизова Н.В. Конструирование интеллектуальных систем поддержки принятия решений на основе инструментального комплекса G2: учеб. пособие. М.: Издат. дом МЭИ, 2012. 92 с.

Referenses

1.     Bashlykov A.A., Eremeev A.P., Ekspertnye sistemy pod­derzhki prinyatiya resheny v energetike [Decision support expert systems in power engineering], Moscow, Izdatelstvo MEI, 1994.

2.     Vagin V.N., Eremeev A.P., Journal of Computer and Systems Sciences International, 2001, no. 6, pp. 114–123.

3.     Jensen K., Coloured Petri nets. basic concepts, analysis methods and practical use, Springer-Verlag, 1992–1997, Vol. 1–3.

4.     Szpyrka M., Szmuc T., Software Engineering Techniques: Design for Quality, IFIP Int. Federation for Information Proc. NY, 2006, Vol. 227, pp. 115–120.

5.     Eremeev A.P., Kurilenko I.E., Intellektualnye sistemy. Kollektivnaya monografiya [Intelligent systems. Multi-author book], Vol. 4, Moscow, Fizmatlit, 2010, pp. 222–252.

6.     Allen J.F., Communications of the ACM, 1983, Vol. 26, no. 11, pp. 832–843.

7.     Eremeev A.P., Korolev Y.I., Trudy XIII nats. konf. po is­kusstvennomu intellektu s mezhdunar. uchastiem KII-2012 [Proc. of XIII national conf. on artifical intelligence with int. participants], Belgorod, Izd-vo BGTU, 2012, Vol. 3, pp. 105–112.

8.     Eremeev A.P., Grechkina P.V., Chibizova N.V., Konstru­irovanie intellektualnykh sistem podderzhki prinyatiya resheny re­alnogo vremeni na osnove instrumentalnogo kompleksa G2: ucheb. posobie [Decision support intelligent systems design based on G2 instrumental complex: study guide], Moscow, Izd. dom MEI, 2012.