Сети Петри

 

Сети Петри – это аппарат для моделирования динамических дискретных систем. Динамическая система - это система, состояние которой изменяется с течением времени. В настоящее время сети Петри применяются в основном в моделировании [7].

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

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

Сеть Петри определяется как четверка < Р, Т, I, O>, где Р и Т - конечные множества позиций и переходов, I и O - множества входных и выходных функций. Другими словами, сеть Петри представляет собой двудольный ориентированный граф, в котором позициям Р соответствуют вершины, изображаемые кружками, а переходам Т - вершины, изображаемые утолщенными черточками; функциям I соответствуют дуги, направленные от позиций к переходам, а функциям О - дуги, направленные от переходов к позициям.

В сетях Петри вводятся объекты двух типов: динамические, которые изображаются метками (маркерами) внутри позиций, и статические, которые соответствуют вершинам сети Петри.

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

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

 

Рис 12. Фрагмент сети Петри

Правила срабатывания переходов (рис. 12) конкретизируют следующим образом: переход срабатывает, если для каждой из его входных позиций выполняется условие N_i > = K_i, где N_i - число маркеров в i-й входной позиции, K_i - число дуг, идущих от i-й позиции к переходу; при срабатывании перехода число маркеров в i-й входной позиции уменьшается на K_i, а в j-й выходной позиции увеличивается на М_j где М_j - число дуг, связывающих переход с j-й позицией.

На рис. 12 показан пример распределения маркеров по позициям. Для срабатывания перехода эту маркировку можно записать в виде (2, 1, 3, 1) или (2131). После срабатывания перехода маркировка принимает вид (0, 0, 0, 4).

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

Рис. 13. Конфликтная ситуация.

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

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

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