Сети Петри
1. Сети Петри - математический аппарат для
моделирования
Сети Петри - математический аппарат для
моделирования динамических дискретных систем. Описаны в диссертационной работе
Карла Петри "Kommunikation mit Automaten" на соискание степени
доктора наук в 1962 году. Сеть Петри представляет собой двудольный
ориентированный граф, состоящий из вершин двух типов - позиций и переходов,
соединённых между собой дугами. Вершины одного типа не могут быть соединены
непосредственно. В позициях могут размещаться метки (маркеры), способные
перемещаться по сети.
Рис.1 Пример сети Петри. Белыми кружками
обозначены позиции, полосками - переходы, чёрными кружками - метки.
Событие в сети Петри - это срабатывание перехода
в сети, при котором метки из входных позиций этого перехода перемещаются в
выходные позиции. События происходят мгновенно, либо разновременно, при
выполнении некоторых условий.
Сети Петри разрабатывались для
моделирования систем с параллельными взаимодействующими компонентами. Сети
Петри впервые предложил Карл Адам Петри
<#"827064.files/image002.jpg">
Рис.2 Построение сети, в которой каждой позиции
инцидентно не более одной ингибиторной дуги.
Доказательство: В качестве доказательства
рассмотрим следующее преобразование.
Пусть в исходной сети позиции p инцидентны две
ингибиторные дуги - (p, t1) и (p, t2). Преобразуем исходную сеть, заменив в ней
позицию p на две позиции - p1 и p2 с такими же наборами обыкновенных дуг, что и
у исходной позиции p. Добавим ингибиторные дуги (p1, t1) и (p2, t2).
(Пример преобразования изображен на Рис. 2.
Здесь и далее для иллюстрации преобразований мы рассматриваем в качестве
исходной сети (слева) схему, включающую все возможные связи моделируемого
синтаксического элемента с другими компонентами системы. В данном случае
рассматривается позиция и две инцидентные ей ингибиторные дуги, а также полный
набор всевозможных различных связанных с ними элементов. Так, с позицией
связаны два перехода -входной и выходной. С переходами, в которые ведут
ингибиторные дуги, могут быть связаны входные и выходные позиции.)
В качестве результирующей сети (справа)
изображена сеть после преобразований. Переходы и позиции без подписей
соответствуют таким же по расположению переходам и позициям исходной сети.
Начальную разметку получим из исходной разметки
M, поместив в p1 и p2 по M(p) фишек.
Очевидно, что из-за полного совпадения начальной
разметки и набор обычных дуг разметки p1 и p2 всегда будут совпадать.
Теорема 2. Для любой сети Петри с ингибиторными
дугами существует эквивалентная ей сеть, в которой каждому переходу инцидентно
не более одной тингибиторной дуги.
Доказательство: В качестве доказательства
рассмотрим следующее преобразование.
Во-первых, добавим в сеть “выключатель” - новую
позицию key с дугами (key(s), s) и (s, key(s)) для каждого перехода s. Таким
образом, любой переход сети может сработать только тогда, когда в позиции key
есть фишка. В начальной разметке в позицию-выключатель поместим одну фишку.
Пусть в исходной сети переходу t инцидентны две
ингибиторные дуги -(t, p1) и (t, p2). Преобразуем исходную сеть, заменив в ней
переход t на три перехода - t1, t2 и t3. У перехода t1 тот же набор входных
дуг, что и у t, и нет выходных; у перехода t2 - тот же набор выходных дуг, что
и у t, и нет входных; у перехода t3 нет входных дуг, а множество выходных дуг
соответствует множеству входных дуг исходного перехода t. Добавим новую позицию
p (с нулевой начальной разметкой) и три новые дуги - (t1, p), (p, t2) и (p,
t3). Исходные ингибиторные дуги (t, p1) и (t, p2) преобразуем в ингибиторные
дуги (t1, p1) и (t2, p2).
Далее, выключатель key соединим забирающей фишку
дугой (key, t1) с первым переходом t1, возвращающей фишку дугой (t2, key) со
вторым переходом t2и возвращающей фишку дугой (t3, key) с третьим переходом t3.
.
Пример преобразования изображен на Рис. 3
Срабатывание перехода t1 соответствует началу
(попытке) срабатывания перехода t в исходной сети и может произойти только при
отсутствии фишек в p1.
Рис. 3. Построение сети, в которой каждому
переходу инцидентно не более одной ингибиторной дуги этом t2 может сработать
только в случае отсутствия фишек в p2. Срабатыванияt2 и t3 “включают” остальные
переходы. При этом срабатывание t2 соответствует успешному завершению
срабатывания t в исходной сети, а t3 - отмене срабатывания.
сеть петри моделирование дискретный
Очевидно, что множество достижимости построенной
сети совпадает с множеством достижимости исходной сети (без учета разметки
новых позиций, которые могут содержать не более одной фишки).
.
Пример использования ингибиторной дуги
Рис.5.Имитация появления и устранения отказов
путем ввода ингибиторной дуги
Появление и устранение отказов оборудования
Отказ элемента системы является случайным
событием, а его устранение продолжается в течение случайного времени. В переход
между позициями начала P1 иокончания P2 операции вводят ингибиторную дугу,
закрывающую движение маркеров на время появления и устранения отказа (рис. 5).
В нормальном режиме маркеры движутся от позиции
P1 к позиции P2 через переход t1. Среднее число отказов генерируется датчиком
случайных чисел ДСЧ 1. При этом в позициях P3, P4 появляется N маркеров и
переход t1 закрывается ингибиторной дугой. Одновременно маркер из позиции P5
переходит в позицию P6 устранения отказов и задерживается в ней на случайное
время Z устранения отказа, заданное датчикомслучайных чисел ДСЧ 2. После
устранения отказа маркер переходит в позицию P5 и переход t2 открывается для
устранения следующего отказа. Устранение N отказов приводит к открыванию
перехода t2 и продолжению работы.
Список используемых источников
1. Учебный
курс МГТУ им. Баумана “Основы САПР. Моделирование”. Сети Петри. Анализ сетей
Петри
. Сети
Петри на сайте Института автоматики и процессов управления. Исходные тексты
примеров программ, реализующих сети Петри и строгоиерархические сети.
.
Конюх В-Л-Имитационное моделирование динамики автоматизированного производства
// Автоматизация в промышленности. 2008. № 4. C. 14-16.