Общие понятия о сетях Петри

Перед тем как ввести понятие о сетях Петри следует упомянуть о том, что существуют два направления развития сетей Петри. Первое направление – прикладная теория сетей Петри – связана с применением сетей Петри для моделирования систем, их анализа и анализа результатов. Второе направление – чистая теория сетей Петри – занимается разработкой средств, методов и понятий, необходимых для применения сетей Петри [2].

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

Итак, сеть Петри C является четвёркой , где - конечное множество позиций, n > 0, - конечное множество переходов, m > 0, таких, что . - является входной функций – отображением из переходов в комплекты позиций. - выходная функция – отображение из переходов в комплекты позиций [2].

Пример сети приведён на рис. 1.

Рис. 1. Пример структуры сети Петри

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

Граф G сети Петри – это двудольный ориентированный мультиграф, G = (V,A), где - множество вершин, - комплект направленных дуг, , где и для любой направленной дуги либо , либо .

Доказательства эквивалентности представлений можно найти в [2], а ниже на рис. 2 приведён рисунок сети рис. 1 в графическом представлении.

Рис. 2. Граф сети Петри, соответствующей сети на рис. 1.

Следующим основным понятием, которое мы введём, будет маркировка. Маркировка µ сети Петри – есть отображение множества позиций P в множество неотрицательных целых чисел: [2].

За таким понятием скрывается довольно простая вещь – в каждый кружочек мы можем поместить точку (или несколько), которая будет отражать, грубо говоря, некоторый потенциал данной позиции. Например, промаркируем сеть рис. 1 следующим образом: (1, 0, 0, 2, 1). Здесь число, стоящее на i-й позиции в множестве обозначает количество точек в p_i. Таким образом мы получаем рис. 3.

Рис. 3. Маркировка сети Петри

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

Например, на рис. 3 разрешены переходы t₁, t₃, t₄, а переход t₂ запрещён. Переход t1 разрешён потому, что на входе у него позиция p₁ с одной дугой и имеет одну фишку. Переход t₂ запрещён, так как входящие в него позиции p₂ и p₃ не имеют фишек вообще. Переход t₃ разрешён, так как в него входит посредством двух дуг позиция p₄, имеющая 2 фишки. Переход t₄ разрешён, так как имеет на входе он имеет позицию p₅ с одной фишкой и одной дугой.

Рис. 4. Граф сети после запуска в сети рис.3 перехода t₄

Рис. 5. Граф сети после запуска в сети рис.4 перехода t₁

Можно заметить, что после последовательного выполнения переходов t₄ и t₁ переход t₂ становится разрешённым.

Функция следующего состояния – для сети Петри с маркировкой и переходом t_i определена тогда и только тогда, когда переход t_i разрешён и определяется выражением - где - новая маркировка, получаемая при выполнении перехода t_i. Кроме того следует ввести понятие непосредственно достижимой маркировки. Маркировка непосредственно достижима из µ, если существует t_i такой, что . Далее следует понятие множества достижимости. Множество достижимости R(C, µ) для сети Петри с маркировкой µ есть наименьшее множестве маркировок, такое, что: а) _, б) если и для некоторого t_j , то Например, для сети на рис. 6. Множеством достижимости R(C, µ) является множество: [2].

Рис. 6. Пример сети Петри для иллюстрации понятия множество достижимости

Так как все процессы моделирования усвоения знаний носят вероятностный характер по своей природе, то целесообразно определить стохастическую сеть Петри. Стохастической сетью Петри называется пара где описывает структуру сети, а отображение , где присваивает каждой позиции вектор распределения вероятности наличия фишек [4]. То есть V – набор векторов, отражающих вероятность нахождения фишки в данной точке. При этом номер компоненты вектора отражает количество фишек, а значение компоненты равняется вероятности нахождения такого количества фишек в этой позиции. Проще говоря, V- двухмерный вектор, первая компонента соответствует номеру позиции, вторая компонента отражает вероятность того, что на данной позиции находится j-е количество фишек. Таким образом, размерность вектора количественно равна произведению количества позиций на максимальное число фишек. Соответственно переход t_i в такой сети может быть разрешён тогда и только тогда, когда у вектора вероятностей каждой входной позиции этого перехода имеется компонента, не равная нулю с номером равным или большим числа дуг, соединяющих данную позицию с переходом [4]. Все функции, которые были определены выше для статической сети, теперь носят вероятностный характер. Для описания правил изменения маркировки применяется математический аппарат свёртки матриц Грама.

Пусть сеть имеет вид, представленный на рис. 7:

Рис. 7. Пример сети

И имеет начальную маркировку:

Рис. 8. Маркировка сети рис. 7

Переход t₁ разрешён, так как . После срабатывания перехода t₁ маркировка позиций p₁ и p₂ имеет вид:

Рис. 9. Маркировка сети после выполнения перехода t1

Определим вектор r:

Рис. 10. Вектор r

Найдём матрицу Грама для векторов и r:

Рис. 11. Матрица Грама

Таким образом, маркировка позиции p₃ после перехода будет:

Рис. 12. Маркировка позиции p₃ после выполнения перехода t₁