Методы анализа сетей Петри

Лекция 4.

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

Пример сети Петри и её графа.

C = (P, T, I, O), P = { p ₁, p ₂ p ₃, p ₄, p ₅}, T = { t ₁, t ₂ t ₃, t ₄}

I (t ₁) = { p ₁}, O (t ₁) = { p ₂, p ₃, р ₅},

I (t ₂) = { p ₂, p ₃, p ₅}, O (t ₂) = { p ₅},

I (t ₃) = { p ₃}, O (t ₃) = { р ₄},

I (t ₄) = { p ₄}, O (t ₄) = { p ₂, p ₃}.

Рис 4.1: Пример сети Петри.

Привести пример какой-нибудь маркировки.

Функция следующего состояния.

Состояние, сети Петри определяется ее маркировкой. Запуск перехода изменяет состояние сети. Пространство состояний сети Петри, обладающей n позициями, есть множество всех маркировок, т. е. Nⁿ. Изменение в состоянии, вызванное запуском перехода, определяется функцией изменения d, которую мы назовем функцией следующего состояния: ,

. (4.1)

Достижимость.

Пусть некоторый переход в маркировке m разрешен и, следовательно, может быть запущен. Результат запуска перехода есть новая маркировка m '. Говорят, что m ' является непосредственно достижимой из маркировки m. если существует переход , такой, что . Если m ' непосредственно достижима из m, a m " — из m ', говорят, что m " достижима из m. Можно записать , где σ — последовательность переходов. Определим множество достижимости R (C, m) сети Петри С с маркировкой m как множество всех маркировок, достижимых из m. Маркировка m ' принадлежит R (C, m), если существует какая-либо последовательность запусков переходов, изменяющих m на m '.

Безопасность.

Одно из важнейших свойств сети Петри, которая должна моделировать реальное устройство, — безопасность. Позиция сети Петри является безопасной, если число фишек в ней никогда не превышает 1. Позиция сети Петри C = (P, T, I, O) с начальной маркировкой m является безопасной, если . Сеть Петри безопасна, если безопасны все позиции сети. В первоначальном определении сети Петри были безопасны, поскольку переход не мог быть запущен, если не все из выходных позиций были пусты (а кратные дуги не были разрешены).

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

Если и , тогда добавить к

Если и , тогда добавить к .

Цель введения этой новой позиции — представить условие « пуста». Следовательно, и дополнительны; имеет фишку, только если не имеет фишки и наоборот. Любой переход, удаляющий фишку из должен помещать фишку в , а всякий переход, удаляющий фишку из , должен помещать фишку в .

а) б)

Рис 4.2: а) Опасная сеть Петри; б) Эквивалентная ей безопасная сеть Петри.

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

Сохранение.

Сеть Петри C = (P, T, I, O) с начальной маркировкой m называется строго сохраняющей, если для всех имеет место

. (4.2)

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

Сеть Петри C = (P, T, I, O) с начальной маркировкой m называется сохраняющей по отношению к вектору взвешивания w, w = (w ₁, w ₂,.., w_n), n = | P |, w_i > 0, если для всех

. (4.3)

Строго сохраняющая сеть Петри является сохраняющей по отношению к вектору взвешивания (1,..., 1).

Активность.

Тупик в сети Петри — это переход (или множество переходов), которые не могут быть запущены. В сети Переход называется активным, если он не заблокирован (нетупиковый). Это не означает, что переход разрешен, скорее он может быть разрешенным. Переход t_j сети Петри С называется потенциально допустимым в маркировке m, если существует маркировка , в которой t_j разрешен. Переход активен в маркировке m, если потенциально запустим во всякой маркировке из . Следовательно, если переход активен, то всегда возможно перевести сеть Петри из ее текущей маркировки в маркировку, в которой запуск перехода станет разрешенным.

Для заданной маркировки m можно выделить пять уровней активности.

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

Уровень 1: Переход t_j обладает активностью уровня 1, если он потенциально запустим, т. е. если существует такая , что t_j разрешен в m '.

Уровень 2: Переход t_j; обладает активностью уровня 2, если для всякого целого n существует последовательность запусков, в которой t_j присутствует по крайней мере n раз.

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

Уровень 4: Переход t_j обладает активностью уровня 4, если для всякой существует такая последовательность запусков σ, что t_j разрешен в .

Переход, обладающий активностью уровня 0, называется пассивным. Переход, обладающий активностью уровня 4, называется активным. Сеть Петри обладает активностью уровня i, если каждый ее переход обладает активностью уровня i.

В качестве примера, иллюстрирующего уровни активности, рассмотрим сеть Петри на рис. 4.3. Переход t ₀ не может быть запущен никогда; он пассивен. Переход t ₁ можно запустить точно один раз; он обладает активностью уровня 1. Переход t ₂ может быть запущен произвольное число раз, но это число зависит от числа запусков перехода t ₃. Если мы хотим запустить t ₂ пять раз, мы запускаем пять раз t ₃ затем t ₁ и после этого пять раз t ₂. Однако, как только запустится t ₁ (t ₁ должен быть запущен до того, как будет запущен t ₂), число возможных запусков t ₂ станет фиксированным. Следовательно, t ₂ обладает активностью уровня 2, но не уровня 3. С другой стороны, переход t ₃ можно запускать бесконечное число раз, и поэтому он обладает активностью уровня 3, но не уровня 4, поскольку, как только запустится t ₁, t ₃ больше запустить будет нельзя.

Рис 4.3: Пример различной степени активности переходов.

Задачи достижимости и покрываемости

Задача достижимости. Для данной сети Петри С с маркировкой m и маркировки m ' определить: ?

Маркировка m " покрывает маркировку m ', если m " m ', т.е. . Задача покрываемости. Для данной сети Петри С с начальной маркировкой m и маркировки m ' определить, существует ли такая достижимая маркировка , такая что m " m '.

Методы анализа сетей Петри.

Дерево достижимости.

Рис 4.4: Маркированная сеть Петри, для которой строится дерево достижимости.

Дерево достижимости представляет множество достижимости сети Петри. Рассмотрим, например, маркированную сеть Петри на рис. 4.4. Её начальная маркировка – (1, 0, 0). Это – корневая вершина дерева достижимости. Непосредственно достижимые из неё маркировки – это вершины второго уровня и т.д.

Рис 4.5: Первые три шага построения дерева достижимости для сети Петри на рис 4.4.

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

Пассивные маркировки – маркировки, в которых нет разрешенных переходов. Они называются терминальными вершинами. Другой класс маркировок – это маркировки, ранее встречавшиеся в дереве. Они называются дублирующими вершинами; никакие последующие маркировки рассматривать нет нужды – все они будут порождены из места первого появления дублирующей маркировки в дереве. Таким образом, в дереве на рис.4.5 маркировка (0, 1, 1), получившаяся в результате выполнения последовательности , не будет порождать какие-либо новые вершины, поскольку она ранее встречалась в дереве в результате выполнения перехода из начальной маркировки.

Для сведения дерева достижимости к конечному представлению используется еще одно средство. Рассмотрим последовательность запусков переходов σ, начинающуюся в начальной маркировке m и кончающуюся в маркировке m ' > m,. Маркировка m ' совпадает с маркировкой m, за исключением того, что имеет некоторые «дополнительные» фишки в некоторых позициях. Теперь, поскольку на запуски переходов лишние фишки не влияют, последовательность σ можно запустить снова, начиная в m ' и приходя к маркировке m ". В общем случае можно запустить последовательность σ n раз, получив в результате маркировку . Следовательно, для тех позиций, которые увеличивают число фишек последовательностью σ, можно создать произвольно большое число фишек, просто повторяя последовательность σ столько, сколько это нужно. В сети Петри на рис. 4.4, например, можно запустить переход столько раз, сколько необходимо для того, чтобы получить произвольное число фишек в р ₂. Представим бесконечное число маркировок, получающихся из циклов такого типа, с помощью специального символа ω, который обозначает «бесконечность». Для любого постоянного а определим

. (4.5)

Рис 4.6: Дерево достижимости для сети Петри изображённой на рис 4.4.

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