ИТМиВТ - Институт точной механики и вычислительной техники С. А. Лебедева РАН
Институт точной механики и вычислительной техники им. С. А. Лебедева РАН - научно-исследовательский институт в области информационных технологий, вычислительной техники и микроэлектроники
English
Главная страница Контактная информация Карта сайта и поиск
Об институте Решения Проекты Образование

Подчиненные сети Петри в задачах логического управления

Клепиков В.И., к.т.н.,
ФГУП «ИТМиВТ им.С.А. Лебедева РАН»

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


Subordinate Petri Nets in Tasks of Logical Control

V.Klepikov, PhD,
Institute of Precise Mechanics and Computer Engineering (IPMCE),
Russian Academy of Science

Subordinate Petri Nets (SPN) technology was introduced for simulation and programming the tasks of logical control. The effectiveness of SPN was demonstrated for description and simulating of processes characterizing by properties of subordination one to others. The mechanism of transformation of SPN to common Petri Nets with inhibitory links was proposed. SPN is used in IPMCE for FPGA development and software design and coding.

Введение

Качество функционального описания и моделирования дискретного процесса или системы зависят от того, насколько явно выбранный инструмент моделирования отражает их свойства и особенности поведения. Общим фундаментом практически всех известных моделей дискретных процессов и систем являются теория автоматов и теория сетей Петри [1,2], которые нашли свое развитие и в языке UML, диаграммы состояний и взаимодействия которого играют одну из ключевых ролей в процессе проектирования и моделирования управляющих систем [3].

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

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

Основные положения аппарата ПСП

Формально ПСП определяется [4] как «девятка» N = (P, T, Q, I+, I-, O, G, V, μo), где

  1. P = {p1,p2, …, pn} — конечное множество позиций;
  2. T = {t1,t2, …, tm} — конечное множество переходов (множества позиций и переходов не пересекаются — P ∩ T = Ø);
  3. Q = {q1,q2, …, qr} — конечное множество маркеров;
  4. I+ : T → 2p, I- : T → 2p, O : T → 2p — отображения множества всех переходов в множества позиций [1], задающие для каждого перехода tj множества входных разрешающих I+(tj), входных запрещающих I-(tj) и выходных O(tj) позиций;
  5. G : Q → 2p — отображение множества маркеров в множества позиций, задающее для каждого маркера qk область его действия G(qk), т. е. подмножество позиций, в которых может находиться маркер qk;
  6. V = {v1,v2, …, vm} — конечное множество весовых коэффициентов, определяющее для каждого перехода tj, j = 1,…,m, действительное число vj;
  7. μo = { μo 1, μo 2, …, μo r} — начальная маркировка сети — набор позиций, в которые помещены маркеры в начальный момент.


[1] 2p — множество всех подмножеств множества  P.

ПСП со входом будем называть тройку NI = (N, X, σ), где

  • N — ПСП;
  • X — множество состояний входа;
  • σ : T → 2x — функция, которая переходам tj сети (не обязательно всем) ставит в соответствие подмножество состояний σ(tj) входа  X.

Изображаются ПСП ориентированным графом, в котором позиции pi обозначены прямоугольниками, а переходы tj — жирными черточками. Рядом с переходом укажем его весовой коэффициент (опущенный коэффициент по умолчанию равен единице) и входную функцию, если она определена для данного перехода. Маркеры qk покажем в виде точек с соответствующими обозначениями, а области действия различных маркеров отделим пунктирными линиями. От позиций к переходам проведем дуги со стрелками (разрешающие связи) или с точками (запрещающие связи); из переходов в позиции могут вести только дуги со стрелками. В начальной маркировке каждый маркер qk помещается в позицию μo k.

Состояние сети определяется ее текущей маркировкой, т. е. размещением маркеров по позициям. Если в текущей маркировке каждая из входных разрешающих позиций перехода tj содержит маркер, а кроме того, все запрещающие позиции этого перехода маркеров не содержат, и состояние входа удовлетворяет условию σ, то этот переход считается активным. Активный переход активизирует каждую из своих выходных позиций, причем степень активизации A(pi) позиции pi равна максимальному по абсолютной величине весовому коэффициенту для всех активных переходов, которым данная позиция служит в качестве выходной. Каждый маркер qk сети может перемещаться из одной позиции в другую в пределах области G(qk) своего действия, и его текущее положение определяется тем, активность какой позиции в пределах G(qk) максимальна в данный момент, т.е. Ұpi Є G(qk), (A(pw) > A(pi)) → μ/ k = pw.

В качестве примера на рисунке 1 приведена ПСП, для которой: P={p1,…,p10}, T={t1, …,t13}, Q={q1,q2,q3}, G(q1)={p1, p2,p3}, G(q2)={p4, p5,p6}, G(q3)={p7,p8,p9,p10}, V={1,3,1,2,1,1,1,3,1,1,1,1,—3}, μo={p1,p4,p7}.

Работа ПСП складывается из элементарных циклов, каждый из которых состоит из двух шагов. На первом шаге производится проверка активностей всех переходов сети. При этом в текущей маркировке μ последовательно для каждого перехода tj проверяется наличие маркеров во всех входных разрешающих позициях I+(tj) Є μ, отсутствие маркеров во всех входных запрещающих позициях I-(tj) ∩ μ = Ø и принадлежность текущего состояния входа множеству σ(tj). Если эти условия выполняются, то переход считается активным, и всем его выходным позициям pi, активность A(pi) которых по абсолютной величине меньше весового коэффициента этого перехода, присваивается новое значение активности, равное весовому коэффициенту перехода Ұpi Є O(tj), (| v(tj) | ≥ A(pi)) → A(pi) = v(tj). Отметим, что в начале элементарного цикла активности всех позиций равны нулю, поэтому по его окончании, т. е. при проходе по всем переходам, каждой позиции будет назначена активность, соответствующая максимальному по абсолютной величине значению ее входного (активного) перехода.

На втором шаге формируется новая маркировка сети μ/, для чего в области действия каждого маркера G(qk) отыскивается позиция с наибольшей положительной активностью, и маркер qk помещается в эту позицию: Ұpi Є G(qk), (A(pw) > A(pi)) → μ/k = pw. Если при этом все позиции области действия маркера qk имеют нулевую или отрицательную активность, то положение маркера в текущем элементарном цикле не изменяется: Ұpi Є G(qk), (A(pi) ≤ 0) → μ/k = μk. Если же две или более позиций в области действия маркера имеют одинаковую положительную активность, то маркер помещается в одну из них произвольным образом, в зависимости от алгоритма реализации сети.

Рисунок 1. Пример ПСП

Рисунок 1. Пример ПСП

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

Синхронизирующий переход tj может иметь входные разрешающие и запрещающие позиции из различных автоматов, а выходные позиции — только в тех автоматах, в которых он имеет входные разрешающие позиции.

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

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

Для иллюстрации работы ПСП рассмотрим работу сети [4], представленной на рисунке 1. В этой сети — три автомата — N1, N2, N3. Переходы t2, t3 — синхронизирующие, t4 — переключающий, t8 — удерживающий, t13 — блокирующий, остальные переходы принадлежат соответствующим переходам и являются собственными.

В исходной маркировке и при отсутствии входных сигналов X1 и X2 активен лишь переход t2, и, как следствие, позиция p7 будет иметь активность A(p7), равную его весовому коэффициенту A(p7) = v2 = 3. Остальные позиции сети будут иметь нулевую активность Ұpi, (i ≠ 7) → A(pi) = 0. Позиция p7 уже содержит маркер, поэтому маркировка сети не изменяется.

При появлении входного условия X7 станет активен переход t4, и это изменит активность позиции p8 : A(p8) = 1. Маркировка же сети при этом не изменится, т. к. активность позиции p7 будет выше активности позиции p8, и маркер q3 останется в позиции p7.

При появлении X1 переход t1 активизирует позицию p3 (A(p3) = 1), в нее из позиции p1 (A(p1) = 0) перемещается маркер q1, и активность позиции p3 снова становится нулевой (A(p3) = 0). Переход t4 становится активным, а переход t2 — неактивным, благодаря чему активности позиций p2, p6 и p9 будут равны 2, активности остальных позиций будут нулевыми. Следующим шагом в указанные позиции переместятся, соответственно, маркеры q1, qи q3, причем q3 переместится в позицию p9 независимо от наличия условия X7, т. к. вес перехода t9 меньше веса перехода t4.

Далее, маркировка сети изменяется в соответствии с активизацией собственных переходов автоматов. Работа автомата N3, однако, находится под контролем автоматов N1 и N2. Так, при попадании маркера q2 в позицию p6, маркеру q3 блокирующим переходом t13 будет запрещен доступ в позицию p7. При попадании маркера qв позицию p5 с одновременным наличием условия X9 маркер q3 удерживающим переходом t8 будет переведен в позицию p10, откуда сможет выйти только при активизации перехода t2 маркерами q1 и q2, когда последние попадут, соответственно, в позиции p1 и p4.

Соотношения аппаратов СП и ПСП

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

Варианты преобразования переключающего перехода проиллюстрированы на Рисунке 2. В исходной ПСП (Рисунок 2a) активен переход tj, в результате срабатывания которого активными станут позиции pi1, pik и p1/. Позиция p1 потеряет маркер, а позиция pm — сохранит его.

Эквивалентная СП может быть получена (Рисунок 2b) путем построения r переходов tjf, f=1..r, где r в общем случае равно произведению количества позиций автоматов N1..Nk, r = n1*…*nk. Входными для переходов tfj являются как входные позиции перехода tj (p1…pm), так и все возможные комбинации позиций автоматов N1..Nk. Множество выходных позиций переходов tjf состоит из позиций, являющихся выходными для перехода tj, и тех входных позиций перехода tj, которые содержатся в автоматах, не имеющих выходных позиций этого перехода. Это означает, что в результате срабатывания перехода tjf в СП S установится новая маркировка μ/S, совпадающая с маркировкой μ/N/S/N).

Рисунок 2. Преобразование переключающего перехода ПСП в эквивалентную СП. a) – исходная ПСП; b), c) – эквивалентные СП

Рисунок 2. Преобразование переключающего перехода ПСП в эквивалентную СП.
a) — исходная ПСП; b), c) — эквивалентные СП.

Другой путь получения эквивалентной СП для переключающего перехода ПСП заключается в построении для каждого автомата Ni набора переходов, равного количеству позиций автомата, из которых выполняется переключение. Так, на рисунке 2c переходы tjf и tjr заменены парами переходов tjf1, tjf2 и tjr1, tjr2. Применим и комбинированный подход, как, например, на рисунке 2c сохранен переход tj1, хотя для него изменяется состав выходных позиций за счет появления перехода tj/.

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

Рисунок 3. Преобразование удерживающих переходов ПСП в эквивалентную СП

Рисунок 3. Преобразование удерживающих переходов ПСП в эквивалентную СП.
a) — исходная ПСП; b) — эквивалентная СП.

Преобразование в СП блокирующего перехода ПСП (Рисунок 4a) демонстрируется на рисунке (Рисунок 4b). Переход tx является блокирующим для позиции pz, т. е. если позиция px содержит маркер, то маркеры из позиций p1… pn не могут перейти в позицию pz. Функция блокировки реализуется в СП с помощью переходов с запрещающими связями. Однако использование блокирующего перехода ПСП позволяет выполнять проектирование автомата Nz без учета возможных внешних его связей.

Рисунок 4. Преобразование блокирующего перехода ПСП в эквивалентную СП.

Рисунок 4. Преобразование блокирующего перехода ПСП в эквивалентную СП.
a) — исходная ПСП; b) — эквивалентная СП.

Заключение

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

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

  1. Лазарев В.Г., Пийль Е.И. Синтез управляющих автоматов, М., «Энергия», 1970, 400с.
  2. Питерсон Дж. Теория сетей Петри и моделирование систем: Пер. с англ. М.: Мир, 1984.
  3. Рамбо Дж., Блаха М. UML 2.0 Объектно-ориентированное моделирование и разработка. 2-е изд. — СПб.: Питер, 2007. — 544 с.: ил.
  4. Клепиков В.И., Сосонкин В.Л. Структурированные нейроподобные сети как средство моделирования дискретных процессов. // АиТ. 1998, № 1, с. 147—154.
  5. Сосонкин В.Л., Клепиков В.И. Принцип подчиненного управления в логических системах управления // Приборы и системы управления. 1995, № 12, с. 16—18.

 

Авиакосмическое приборостроение, № 8, 2007 г.

Оригинал статьи PDF, 355 Кб

© 1948—2016 «ИТМиВТ»
Версия для печати Контактная информация