45366 (Синтез комбинацонных схем и конечных автоматов, сети Петри), страница 4

где А – матрица инцидентности графа сети.

Определим понятие маркированной сети Петри – оно является ключевым для любой сети.

Маркировка μ сети Петри C = (P, T, I, O) есть функция:

N = μ(P), N N, (3.2.8)

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

μ = {μ₁, μ₂,…, μ_n} , (3.2.9)

где n = │P │, а μ_i N. Между этими определениями есть связь:

μ_i = μ (p_i) (3.2.10)

На графе маркировка отображается ссответствующим числом точек в каждой позиции. Точки называются маркерами или фишками. Если фишек много (больше трёх), то их количество отображается числом.

Таким образом, маркированная сеть Петри представляет собой пятёрку элементов:

M = (P, T, I, O, μ). (3.2.11)

Пример простейшей сети Петри:

p₁

▪▪▪

t₁ p₃

p₂ ▪

Рисунок 3.2.1 – Пример сети Петри

Правила работы с сетями Петри.

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

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

Проиллюстрируем сказанное на примере уже нарисованной сети Петри. Запустим в ней переход t₁ – он является разрешённым:

p₁

▪

t₁ p₃

▪

p₂ ▪

Рисунок 3.2.2 – Пример запуска перехода сети Петри

Пространство состояний и поведенческие свойства сетей Петри.

Пусть имеется маркированная сеть Петри:

M = (P, T, I, O, μ) (3.2.12)

У неё n позиций. В каждой позиции не более N фишек. Тогда пространство сотояний есть множество всех возможных маркировок сети. Определим δ – функцию следующего состояния.

Если переход t_j разрешён при текущей маркировке μ , то следующая маркировка μ’ определится так:

μ’ = δ (μ, t_j) (3.2.13)

Если переход t_j не разрешён, то δ не определена.

Пусть {t_j0, t_j1,…, t_js} – последовательность запущенных переходов. Тогда ей будет соответствовать последовательность {μ⁰, μ¹,…,μ^s+1}, то есть

μ^k+1 = δ(μ^k, t_jk) (3.2.14)

На основании последнего равенства можно определить понятие непосредственно достижимой маркировки. Для сети C = (P, T, I ,O) маркировка μ’ называется непосредственно достижимой из μ , если существует такой переход t_j T, при котором

μ' = δ(μ , t_j) (3.2.15)

Можно распространить это понятие на множество достижимых из данной маркировок. Определим множество достижимых из μ маркировок R(C, μ) следующим образом:

во - первых, μ R(C, μ);

во - вторых, если μ’ R(C, μ), μ’ = δ(μ , t_j) и μ’’ = δ(μ’, t_k), то и μ’’ R(C, μ).

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

1. Достижимость данной маркировки. Пусть имеется некоторая маркировка μ, отличная от начальной. Тогда возникает вопрос достижимости: можно ли путём запуска определённой поледовательности переходов перейти из начальной в заданную маркировку.

2. Ограниченность. Сеть Петри называется k- ограниченной, если при любой маркировке количество фишек в любой из позиций не превышает k. В частности, сеть называется безопасной, если k равно 1. Кроме того, сеть называется однородной, если в ней отсутствуют петли и одинарной (простой), если в ней нет кратных дуг.

3. Активность. Сеть Петри называется активной, если независимо от дотигнутой из μ₀ маркировки существует последовательность запусков, приводящая к запуску этого перехода.

Реально вводят понятия нескольких уровней активности для конкретных переходов. Переход t_j T называется:

а) пассивным (L0- активным), если он никогда не может быть запущен;

б) L1- активным, если он может быть запущен последовательностью переходов из μ₀ хотя бы один раз;

в) L2- активным, если для любого числа K существует последовательность запусков переходов из μ₀ , при которой данный переход может сработать K и более раз;

г) L3- активным, если он является L2- активным при K → ∞.

1. Обратимость. Сеть Петри обратима, если для любой маркировки μ R(C, μ₀) маркировка μ₀ достижима из μ.

2. Покрываемость. Маркировка μ покрываема, если существует другая маркировка μ’ R(C, μ₀) такая, что в каждой позиции μ’ фишек не меньше, чем в позициях маркировки μ.

3. Устойчивость. Сеть Петри называется устойчивой, если для любых двух разрешённых переходов срабатывание одного из них не приводит к запрещению срабатывания другого.

Существуют два основных метода анализа сетей Петри: матричные и основанные на построении дерева покрываемости.

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

D ^– [i, j] = # (p_i , I(t_j)), (3.2.16)

каждый её элемент равен числу фишек, уходящих из j- й позиции при запуске i- го перехода. Вторая матрица называется матрицей выходов:

D ⁺ [i, j] = # (p_i , O(t_j)), (3.2.17)

каждый её элемент равен числу фишек, приходящих в j- ю позицию при запуске i- го перехода. Определим единичный вектор e[j] размерности m, содержащий нули во всех позициях кроме той, которая соответствует запускаемому в данный момент переходу. Очевидно, что переход разрешён, если μ ≥ e[j]·D ^–. Тогда результат запуска j- го перехода можно описать так:

μ’ = μ + e[j]·D, (3.2.18)

где D = (D ⁺ – D ^–) – матрица изменений. Тогда все сформулированные ранее проблемы сети Петри легко интерпретируются матричными уравнениями вида

μ = μ₀ + σ·D, (3.2.19)

где μ – исследуемая маркировка, σ – вектор, компоненты которого показывают, сколько раз срабатывает каждый переход.

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

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

Ясно, что этот метод хотя и требует утомительного перебора всех возможных маркировок сети, но зато по уже готовому дереву достаточно легко анализировать проблемы достижимости, покрываемости, активности, обратимости сети.

Описав поведенческие свойства и методы анализа, можно перейти непосредственно к анализу конкретной сети Петри.

3.3 Расчёты и полученные результаты

Исходная сеть в виде графа:

p₁ p₆

▪ ▪

t₁ ▪ p₄ t₄

p₂ p₇

t₂ ▪ p₅ t₅

p₃ p₈

t₃ t₆

Рисунок 3.3.1 – Исходная сеть Петри

Для матричного анализа сети найдём её матрицу изменений.

(3.3.1)

(3.3.2)

Матрицу изменений найдём как разность между (3.3.2) и (3.3.1):

(3.3.3)

Таким образом, получив матрицу изменений, можно записать матричное уравнение смены маркировок вида (3.2.19). Вектор начальной маркировки определим так:

μ₀ = (10011100) (3.3.4)

Составим дерево покрываемости маркировок сети.

(10011100) ‘Новая’

t₁ t₄

‘Новая’ ‘Новая’

(01001100) (10010010)

t₂ t₄ t₁ t₅

(00100100) (01000010) (01000010) (10000001)

‘Новая’ ‘Тупик’ ‘Тупик’ ‘Новая’

t₃ t₆

(10011100) ‘Старая’ (10011100) ‘Старая’

Рисунок 3.3.1 – Дерево покрываемости маркировок

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

Граф покрываемости сети выглядит следующим образом:

μ₀

t₃ t₆

10011100

00100100 t₁ t₄ 10000001

t₂ t₅

01001100 10010010