Сети Петри

/

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

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

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

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

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

Сети Петри - инструмент моделирования

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

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

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

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

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 -- отмене срабатывания.

сеть петри моделирование дискретный

Очевидно, что множество достижимости построенной сети совпадает с множеством достижимости исходной сети (без учета разметки новых позиций, которые могут содержать не более одной фишки).

3. Пример использования ингибиторной дуги

Рис.5.Имитация появления и устранения отказов путем ввода ингибиторной дуги

Появление и устранение отказов оборудования

Отказ элемента системы является случайным событием, а его устранение продолжается в течение случайного времени. В переход между позициями начала P1 иокончания P2 операции вводят ингибиторную дугу, закрывающую движение маркеров на время появления и устранения отказа (рис. 5).

В нормальном режиме маркеры движутся от позиции P1 к позиции P2 через переход t1. Среднее число отказов генерируется датчиком случайных чисел ДСЧ 1. При этом в позициях P3, P4 появляется N маркеров и переход t1 закрывается ингибиторной дугой. Одновременно маркер из позиции P5 переходит в позицию P6 устранения отказов и задерживается в ней на случайное время Z устранения отказа, заданное датчикомслучайных чисел ДСЧ 2. После устранения отказа маркер переходит в позицию P5 и переход t2 открывается для устранения следующего отказа. Устранение N отказов приводит к открыванию перехода t2 и продолжению работы.

Список используемых источников

1. Учебный курс МГТУ им. Баумана “Основы САПР. Моделирование”. Сети Петри. Анализ сетей Петри

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

3. Конюх В-Л-Имитационное моделирование динамики автоматизированного производства // Автоматизация в промышленности. 2008. № 4. C. 14-16.