Сеть Петри — математический объект, используемый для моделирования динамических дискретных систем, предложенный Карлом Петри в 1962 году.
Определяется как двудольный ориентированный мультиграф, состоящий из вершин двух типов — позиций и переходов, соединённых между собой дугами. Вершины одного типа не могут быть соединены непосредственно. В позициях могут размещаться метки (маркеры), способные перемещаться по сети. Событием называют срабатывание перехода, при котором метки из входных позиций этого перехода перемещаются в выходные позиции. События происходят мгновенно либо разновременно, при выполнении некоторых условий.
Сеть Петри есть мультиграф, так как он допускает существование кратных дуг от одной вершины графа к другой. Так как дуги являются направленными, то это ориентированный мультиграф. Вершины графа можно разделить на два множества (позиции и переходы) таким образом, что каждая дуга будет направлена от элемента одного множества (позиций или переходов) к элементу другого множества (переходов или позиций); следовательно, такой граф является двудольным ориентированным мультиграфом.
Изначально разрабатывались для моделирования систем с параллельными взаимодействующими компонентами; основные положения теории связи асинхронных компонент вычислительной системы Петри сформулировал в докторской диссертации «Связь автоматов».
Динамика Процесс функционирования сети Петри может быть наглядно представлен графом достижимых маркировок. Состояние сети однозначно определяется её маркировкой — распределением фишек по позициям. Вершинами графа являются допустимые маркировки сети Петри, дуги помечены символом срабатывающего перехода. Дуга строится для каждого возбуждённого перехода. Построение прекращается, когда мы получаем маркировки, в которых не возбуждён ни один переход, либо маркировки, содержащиеся в графе. Отметим, что граф достижимых маркировок представляет собой автомат.
Виды сетей Петри Некоторые виды сетей Петри: Временна́я сеть Петри — переходы обладают весом, определяющим продолжительность срабатывания (задержку). Стохастическая сеть Петри — задержки являются случайными величинами. Функциональная сеть Петри — задержки определяются как функции некоторых аргументов, например, количества меток в каких-либо позициях, состояния некоторых переходов. Цветная (окрашенная, раскрашенная) сеть Петри — метки могут быть различных типов, обозначаемых цветами, тип метки может быть использован как аргумент в функциональных сетях. Ингибиторная сеть Петри — возможны ингибиторные дуги, запрещающие срабатывания перехода, если во входной позиции, связанной с переходом ингибиторной дугой, находится метка. Иерархическая сеть — содержит не мгновенные переходы, в которые вложены другие, возможно, также иерархические, сети. Срабатывание такого перехода характеризует выполнение полного жизненного цикла вложенной сети. WF-сеть. Алгебраическая сеть Петри.
Анализ сетей Петри Основными свойствами сети Петри являются: ограниченность — число меток в любой позиции сети не может превысить некоторого значения ; безопасность — частный случай ограниченности: ; сохраняемость — постоянство загрузки ресурсов: постоянна, где — число маркеров в -той позиции, — весовой коэффициент; достижимость — возможность перехода сети из одного заданного состояния (характеризуемого распределением меток) в другое; живость — возможность срабатывания любого перехода при функционировании моделируемого объекта.
В основе исследования перечисленных свойств лежит анализ достижимости. Методы анализа свойств сетей Петри основаны на использовании графов достижимых (покрывающих) маркировок, решении уравнения состояний сети и вычислении линейных инвариантов позиций и переходов. Применяются также вспомогательные методы редукции, позволяющие уменьшить размер сети Петри с сохранением её свойств, и декомпозицииЗайцев Д. А. Композиционный анализ сетей Петри // Кибернетика и системный анализ. — 2006, № 1. — С. 143—154., разделяющие исходную сеть на подсети.
Универсальная сеть Петри В 1974 году Тилак Аджервала показал, что ингибиторная сеть Петри является универсальной алгоритмической системой. В монографии Котова приведён набросок доказательства, указывающий правила кодирования ингибиторной сетью программы счётчикового автомата Минского. Питерсон приводит примеры других расширенных классов сетей Петри, являющихся универсальной алгоритмической системой: синхронных и приоритетных. Построенная в явном виде универсальная сеть ПетриЗайцев Д. А. Универсальная сеть Петри, Кибернетика и системный анализ, № 4, 2012, с. 24-39. насчитывала несколько тысяч вершин и недавно была уменьшена до 56 вершинZaitsev D.A. Toward the Minimal Universal Petri Net, IEEE Transactions on Systems, Man, and Cybernetics: Systems, 2013, 1- 12..
Бесконечные сети Петри Бесконечные сети Петри были введены для верификации вычислительных решеток и позволяют определять свойства сетей Петри для регулярных структур (линейная, древовидная, квадратная, треугольная, шестиугольная и гиперкубЗайцев Д. А. , Шмелева Т. Р. Верификация коммуникационных структур гиперкуба параметрическими сетями Петри, Кибернетика и системный анализ, № 1, 2010, С. 119—128.) произвольного размера, полученных путём композиции типовых фрагментов.
См. также Системы массового обслуживания Имитационное моделирование Модель акторов Конечный автомат
Примечания
Литература
Мараховский В. Б., Розенблюм Л. Я., Яковлев А. В. Моделирование параллельных процессов. Сети Петри. Курс для системных архитекторов, программистов, системных аналитиков, проектировщиков сложных систем управления. — Санкт-Петербург: Профессиональная литература, АйТи-Подготовка, 2014. — 400 с.
Ссылки Учебный курс МГТУ им. Баумана «Основы САПР. Моделирование». Сети Петри. Анализ сетей Петри Сети Петри на сайте Института автоматики и процессов управления. Исходные тексты примеров программ, реализующих сети Петри и строго иерархические сети.
Категория:Сети Петри