Сеть Петри

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

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

Определяется как двудольный ориентированный мультиграф, состоящий из вершин двух типов — позиций и переходов, соединённых между собой дугами. Вершины одного типа не могут быть соединены непосредственно. В позициях могут размещаться метки (маркеры), способные перемещаться по сети. Событием называют срабатывание перехода, при котором метки из входных позиций этого перехода перемещаются в выходные позиции. События происходят мгновенно либо разновременно, при выполнении некоторых условий.

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

Изначально разрабатывались для моделирования систем с параллельными взаимодействующими компонентами; основные положения теории связи асинхронных компонент вычислительной системы Петри сформулировал в докторской диссертации «Связь автоматов»^[1].

ДинамикаПравить

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

Виды сетей ПетриПравить

Некоторые виды сетей Петри:

Временна́я сеть Петри — переходы обладают весом, определяющим продолжительность срабатывания (задержку).
Стохастическая сеть Петри — задержки являются случайными величинами.
Функциональная сеть Петри — задержки определяются как функции некоторых аргументов, например, количества меток в каких-либо позициях, состояния некоторых переходов.
Цветная (окрашенная, раскрашенная) сеть Петри — метки могут быть различных типов, обозначаемых цветами, тип метки может быть использован как аргумент в функциональных сетях.
Ингибиторная сеть Петри — возможны ингибиторные дуги, запрещающие срабатывания перехода, если во входной позиции, связанной с переходом ингибиторной дугой, находится метка.
Иерархическая сеть — содержит не мгновенные переходы, в которые вложены другие, возможно, также иерархические, сети. Срабатывание такого перехода характеризует выполнение полного жизненного цикла вложенной сети.
WF-сеть.
Алгебраическая сеть Петри.

Анализ сетей ПетриПравить

Основными свойствами сети Петри являются:

Пример траектории в сети Петри.

ограниченность — число меток в любой позиции сети не может превысить некоторого значения $\text{[math]}$ $\text{[math]}$ $K$ ;
безопасность — частный случай ограниченности: $\text{[math]}$ $\text{[math]}$ $K=1$ ;
сохраняемость — постоянство загрузки ресурсов: $\text{[math]}$ $\text{[math]}$ $\sum A_{i}N_{i}$ постоянна, где $\text{[math]}$ $\text{[math]}$ $N_{i}$ — число маркеров в $\text{[math]}$ $\text{[math]}$ $i$ -той позиции, $\text{[math]}$ $\text{[math]}$ $A_{i}$ — весовой коэффициент;
достижимость — возможность перехода сети из одного заданного состояния (характеризуемого распределением меток) в другое;
живость — возможность срабатывания любого перехода при функционировании моделируемого объекта.

В основе исследования перечисленных свойств лежит анализ достижимости. Методы анализа свойств сетей Петри основаны на использовании графов достижимых (покрывающих) маркировок, решении уравнения состояний сети и вычислении линейных инвариантов позиций и переходов. Применяются также вспомогательные методы редукции, позволяющие уменьшить размер сети Петри с сохранением её свойств, и декомпозиции^[2], разделяющие исходную сеть на подсети.

Универсальная сеть ПетриПравить

В 1974 году Тилак Аджервала показал, что ингибиторная сеть Петри является универсальной алгоритмической системой. В монографии Котова приведён набросок доказательства, указывающий правила кодирования ингибиторной сетью программы счётчикового автомата Минского. Питерсон приводит примеры других расширенных классов сетей Петри, являющихся универсальной алгоритмической системой: синхронных и приоритетных. Построенная в явном виде универсальная сеть Петри^[3] насчитывала несколько тысяч вершин и недавно была уменьшена до 56 вершин^[4].

Бесконечные сети ПетриПравить

Бесконечные сети Петри были введены для верификации вычислительных решеток и позволяют определять свойства сетей Петри для регулярных структур (линейная, древовидная, квадратная, треугольная, шестиугольная и гиперкуб^[5]) произвольного размера, полученных путём композиции типовых фрагментов.

См. такжеПравить

ПримечанияПравить

↑ Питерсон, 1984, стр. 11 «1.3. Зарождение теории сетей Петри».
↑ Зайцев Д. А. Архивная копия от 1 апреля 2022 на Wayback Machine Композиционный анализ сетей Петри // Кибернетика и системный анализ. — 2006, № 1. — С. 143—154.
↑ Зайцев Д. А. Архивная копия от 1 апреля 2022 на Wayback Machine Универсальная сеть Петри, Кибернетика и системный анализ, № 4, 2012, с. 24-39.
↑ Zaitsev D.A. Архивная копия от 1 апреля 2022 на Wayback Machine Toward the Minimal Universal Petri Net, IEEE Transactions on Systems, Man, and Cybernetics: Systems, 2013, 1- 12.
↑ Зайцев Д. А. Архивная копия от 1 апреля 2022 на Wayback Machine, Шмелева Т. Р. Верификация коммуникационных структур гиперкуба параметрическими сетями Петри, Кибернетика и системный анализ, № 1, 2010, С. 119—128.

ЛитератураПравить

Питерсон Дж. Теория сетей Петри и моделирование систем. — М.: Мир, 1984. — 264 с.
Котов В. Е. Сети Петри. — М.: Наука, 1984. — 160 с.
Слепцов А. И., Юрасов А. А. Автоматизация проектирования управляющих систем гибких автоматизированных производств / Б. Н. Малиновский. — Киев: Техніка, 1986. — 160 с.
Ачасова С. М., Бандман О. Л. Корректность параллельных вычислительных процессов. — Новосибирск: Наука, 1990. — 253 с.
Мараховский В. Б., Розенблюм Л. Я., Яковлев А. В. Моделирование параллельных процессов. Сети Петри. Курс для системных архитекторов, программистов, системных аналитиков, проектировщиков сложных систем управления. — Санкт-Петербург: Профессиональная литература, АйТи-Подготовка, 2014. — 400 с.

СсылкиПравить

Учебный курс МГТУ им. Баумана «Основы САПР. Моделирование». Сети Петри. Анализ сетей Петри
Сети Петри на сайте Института автоматики и процессов управления.
Исходные тексты примеров программ, реализующих сети Петри и строго иерархические сети.

[_d4fad3dce2a86a6a-1] Питерсон, 1984, стр. 11 «1.3. Зарождение теории сетей Петри».

[2] Зайцев Д. А. Архивная копия от 1 апреля 2022 на Wayback Machine Композиционный анализ сетей Петри // Кибернетика и системный анализ. — 2006, № 1. — С. 143—154.

[3] Зайцев Д. А. Архивная копия от 1 апреля 2022 на Wayback Machine Универсальная сеть Петри, Кибернетика и системный анализ, № 4, 2012, с. 24-39.

[4] Zaitsev D.A. Архивная копия от 1 апреля 2022 на Wayback Machine Toward the Minimal Universal Petri Net, IEEE Transactions on Systems, Man, and Cybernetics: Systems, 2013, 1- 12.

[5] Зайцев Д. А. Архивная копия от 1 апреля 2022 на Wayback Machine, Шмелева Т. Р. Верификация коммуникационных структур гиперкуба параметрическими сетями Петри, Кибернетика и системный анализ, № 1, 2010, С. 119—128.

[1]

[2]

[3]

[4]

[5]