Лекция о сетях Петри от Шамаля

Сети Петри.

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

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

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

Сети Петри, как правило, рассматриваются с точностью до изоморфизма, то есть имена позиций и переходов являются «связанными» внутри сети и при графическом изображении, вообще говоря, могут не указываться (они необходимы только для ссылок, например, при описании поведения сети):

Определение 1. Сети и , считаются идентичными, если существуют взаимно-однозначные отображения и , такие, что .

Основой определения семантики сетей Петри является функция переходов , в общем случае частичная: Здесь «+» и «-» – знаки операций «сложения» и «вычитания» комплектов: , , где . Функция обобщается на множество кортежей переходов ( ): , . Мно-жество маркировок, достижимых из маркировки , обозначается и определяется так: , а множество всех достижимых в сети маркировок (достижимых из начальной маркировки ) так: . Маркировка называется тупиковой, если для всех не определено, т.е. не выполняется условие . обозначает подмножество всех достижимых тупиковых маркировок в сети. Кортеж переходов называется историей достижения маркировки , если . Множество всех возможных историй достижения маркировки обозначим .

Переходы могут классифицироваться по степени их «активности»:

1. «мертвый» переход (не встречается ни в одной истории достижения маркировок из );

2. «потенциально мертвый» переход (существуют маркировки, ни в одно из продолжений историй достижения которых он не входит);

3. «потенциально живой» переход, который входит в хотя бы одну из историй достижения некоторой маркировки из ;

4. «живой» переход (входит в одно из продолжений любой истории достижения маркировок из );

5. переход, который входит в некоторую историю достижения маркировок из не менее любого заданного числа раз;

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

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

Сеть называется ограниченной, если . Также очевидно, что ограниченные сети могут быть реализованы конечными автоматами.

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

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

• если вершина помечена обобщенной маркировкой, являющейся тупиковой,

• если в некоторой ветви, идущей из корня дерева, повторно встречается одна и та же обобщенная маркировка.

Доказательство конечности дерева достижимости любой сети Петри базируется на следующих леммах.

Лемма 1. В любом бесконечном направленном дереве с конечными степенями вершин существует бесконечный путь, исходящий из корня.

Лемма 2. Всякая бесконечная последовательность натуральных чисел содержит бесконечную неубывающую подпоследовательность.

Лемма 2. Всякая бесконечная последовательность обобщенных комплектов элементов конечного множества (кратности могут иметь значение ) содержит бесконечную неубывающую подпоследовательность.

Доказательство лемм достаточно очевидно, а доказательство теоремы о конечности дерева достижимости проводится от противного.

Другой вариант доказательства базируется на следующей теореме:

Теорема. Для всякого конечного множества не существует бесконечных множеств попарно не сравнимых обобщенных комплектов его элементов.

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

На рис. 1 показан пример сети с заданной начальной маркировкой и построено для нее дерево достижимости.

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

Анализ поведения сетей Петри

Одной из основных задач анализа поведения сетей Петри является задача достижимости маркировок. Из всех возможных вариантов задач такого типа обычно выделяют нижеследующие:

• задача достижимости отдельной маркировки – для заданной маркировки выполняется ?

• задача достижимости подмаркировки – для заданной маркировки и заданного подмножества позиций существует ли маркировка , такая что ?

• задача достижимости нулевой маркировки – достижима ли маркировка , такая что , т.е. ?

• задача достижимости маркировки, нулевой в одной позиции – достижима ли для заданной позиции маркировка , такая что , т.е. ?

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

Другой подход к анализу сетей Петри рассматривает степень активности переходов в сети. Оказывается, что, в частности, является ли заданный переход сети «живым», или является ли сеть «живой» (то есть все ли переходы сети – «живые») – это задачи, которые сводятся к решению проблем достижимости.

Р
ассмотрим примеры моделирования различных параллельных систем с помощью сетей Петри.

Пример 1.

На рис. 3 показана сеть Петри, моделирующая продвижение деталей на конвейере. Каждое рабочее место представлено двумя позициями: – соответствует свободному состоянию, а – соответствует состоянию обработки детали на -м рабочем месте. Переход осуществляет загрузку детали на первое рабочее место, если оно свободно. Переходы представляют перемещение деталей с -го рабочего места на -ое. Эта сеть является безопасной: при всех достижимых маркировках во всех позициях сети не может быть более одной фишки.

Пример 2.

На рис. 4 представлена модель системы из двух одновременно работающих конвейеров, в которой на первом и втором, на втором и третьем, и т.д. используются инструменты, общие для двух конвейеров, что вносит дополнительные ограничения на перемещение деталей в этих конвейерах. Рабочие места в конвейерах 1 и 2 представлены в моделирующей сети, соответственно, позициями «свободно» («занято»): и . Позиция представляет склад «заготовок»; в начальной маркировке в этой позиции фишек ( – количество заготовок), а позиция представляет склад «готовых изделий». Позиции представляют совместно используемые двумя конвейерами инструменты, соответственно, на первом и втором рабочем месте, на втором и третьем, и т.д. Завершение работы конвейеров соответствуют маркировке, в которой эта позиция содержит фишек. Эта сеть, как и сеть на рис. 1, тоже является безопасной.

П
ример 3.