Сети Петри

1.Сети Петри - математический аппарат для моделирования

Сети Петри - математический аппарат для моделирования динамических дискретных систем. Описаны в диссертационной работе Карла Петри "Kommunikation mit Automaten" на соискание степени доктора наук в 1962 году. Сеть Петри представляет собой двудольный ориентированный граф, состоящий из вершин двух типов - позиций и переходов, соединённых между собой дугами. Вершины одного типа не могут быть соединены непосредственно. В позициях могут размещаться метки (маркеры), способные перемещаться по сети.

Рис.1 Пример сети Петри. Белыми кружками обозначены позиции, полосками - переходы, чёрными кружками - метки.

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

Сети Петри разрабатывались для моделирования систем с параллельными взаимодействующими компонентами. Сети Петри впервые предложил Карл Адам Петри <#"justify">2.Сети с ингибиторными дугами

Одним из самых известных расширений класса сетей Петри являются сети Петри с ингибиторными дугами. Это сети, в которых кроме обычных дуг могут присутствовать так называемые ингибиторные, обозначаемые стрелками с наконечниками в виде черных точек (Рис. 2).

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

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

Рис.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.

По построению после срабатывания перехода t1 может последовать только одно из двух срабатываний: t2 или t3 (все остальные переходы выключены).

Рис. 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.

Больше работ по теме: