Journal influence
Bookmark
Next issue
Realization of intelligent systems of real time on the basis of the Petri nets with support of temporal dependences
The article was published in issue no. № 3, 2013 [ pp. 88-94 ]Abstract:The apparatus of color Petri nets in respect of its use in intelligent systems of real time is considered. Petri nets allow to describe naturally synchronization, overlapping, the conflict and causal dependence, and also visually to represent a structure and behavior of difficult technical or organizational systems. However, an essential drawback of classical Petri nets is complexity of modeling real time systems when it is necessary to consider a factor of time and temporal dependences. New expansion – color Petri nets with support of Allen’s temporal logic, allowing to model both quantitative, and qualitative temporary delays is offered. This logic is characterized by sufficient expressiveness and existence of polynomial algorithms of a conclusion that its practical application in intelligent systems like intelligent decision support systems of real time allows. The description and the example of use of the developed basic software for this class of Petri nets is given.
Аннотация:Рассматривается использование аппарата цветных сетей Петри в интеллектуальных системах реального времени. Сети Петри позволяют естественно описывать синхронизацию,параллелизм, конфликт и причинную зависимость, а также наглядно представлять структуру и поведение сложной технической или организационной системы. Однако существенным недостатком классических сетей Петри является сложность моделирования функционирования систем реального времени, когда необходимо учитывать фактор времени и временные (темпоральные) зависимости. Предлагается новое расширение – цветные сети Петри с поддержкой темпоральной логики Аллена, позволяющие моделировать как количественные, так и качественные временные зависимости. Данная логика характеризуется достаточной выразительностью и наличием полиномиальных алгоритмов вывода, что позволяет применять ее в системах типа интеллектуальных систем поддержки принятия решений реального времени. В работе даны описание и пример использования разработанного базового программного средства для данного класса сетей Петри.
Authors: Eremeev, A.P. (eremeev@appmat.ru) - National Research University “MPEI” (Professor), Moscow, Russia, Ph.D, (korolevyu@gmail.com) - , Russia | |
Keywords: temporal dependences, colored Petri nets, decision support, intelligent system of real time |
|
Page views: 7507 |
Print version Full issue in PDF (13.63Mb) Download the cover in PDF (1.39Мб) |
Средства моделирования и анализа сложных параллельных и распределенных систем, в том числе систем реального времени, характерными представителями которых являются интеллектуальные системы поддержки принятия решений (ИСППР) реального времени (РВ), вызывают большой интерес [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, TurnOnSS, 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-
Модель системы остановки поезда на основе данного аппарата представлена на рисунке 2. Применение логики Аллена привело к сужению множества цветов Σ и разбиению сети на две несвязанные подсети, одна из которых определяет работу механизма аварийного торможения, а другая моделирует действия машиниста. Формулы логики Аллена применены в данном случае как защитные функции переходов DisactLS и DisactSS, обозначающих своевременную реакцию человека (ЛПР) на световой и звуковой сигналы соответственно. Главным преимуществом в данном случае является возможность задавать не конкретное время реакции, как в случае ЦСП РВ, а интервалы, на которых машинист может деактивировать систему и каждый из которых определяет дальнейшее поведение модели. Таким образом, включение в модель аппарата интервальных темпоральных логик позволило отразить неопределенность, присущую задаче, что является одним из основополагающих принципов в ИСППР РВ. Разработка инструментария и практическое моделирование Компьютерное моделирование ИСППР РВ актуально для теоретических исследований и для практического применения. Создание соответствующего инструментария представляет серьезную проблему, так как среда разработки должна поддерживать концепцию реального времени, а также достаточную универсальность разрабатываемых моделей. Инструментальный комплекс G2 (Gensym 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 к этому моменту будет уже запущен.
В представленной работе исследованы временные подклассы сетей Петри в применении к моделированию процессов в ИСППР, включая ИСППР РВ. Предложено расширение подкласса ЦСП РВ в плане поддержки темпоральной логики Аллена с возможностью моделирования как количественных, так и качественных временных задержек. Исследована возможность моделирования сетей Петри с временными ограничениями в инструментальной среде конструирования интеллектуальных систем реального времени 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 podderzhki 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 iskusstvennomu 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., Konstruirovanie intellektualnykh sistem podderzhki prinyatiya resheny realnogo 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. |
Permanent link: http://swsys.ru/index.php?id=3565&lang=en&page=article |
Print version Full issue in PDF (13.63Mb) Download the cover in PDF (1.39Мб) |
The article was published in issue no. № 3, 2013 [ pp. 88-94 ] |
Back to the list of articles