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

ВВЕДЕНИЕ

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

– конечных автоматов,

– сетей Петри,

– нейронных сетей.

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

Для изучения и работы с моделируемыми системами важным инструментом благодаря своей способности описывать различные классы параллельных, дискретных, асинхронных, распределенных и недетерминированных систем является сеть Петри. Она обеспечивает наглядное описание их функционирования и обладает качественным программным и математическим аппаратом для анализа [1][2].

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

МАТЕРИАЛЫ И МЕТОДЫ

Теория сетей Петри развивается в двух основных направлениях:

– формальная теория сосредоточена на определении и создании понятий, методов и способов работы с сетями;

– прикладная теория включает разработку методов анализа и моделирования с использованием сетей Петри [5].

Классический способ определения сети Петри (PN). Традиционно сети Петри можно задать в аналитическом, графическом или матричном виде.

Аналитический способ задания сетей Петри. Сеть Петри состоит из двух компонентов:

– собственно сети, которая определяется структурой сети;

– маркировкой позиций (мест) сети, с помощью которой определяется функционирование сети [6][7].

Структура сети представляет собой 4-кортеж (P, T, I, O) и является двудольным (направленным) мультиграфом, дуги которого соединяют узлы двух непересекающихся множеств:

множества позиций P, представляющих собой состояния

P = {p₁, p₂, ..., p_i, p_n},

множества переходов T, показывают действия

T = {t₁, t₂, ..., t_i, t_n}.

Переходы и позиции, соединенные дугами f_k, делятся на два типа: направленные от позиции к переходам (p – t), а также от переходов к позициям (t – p). Таким образом, формально сеть Петри представляется как совокупность множеств:

N = (P, T, F),

здесь P – множество позиций,

T – множество переходов,

F – множество дуг сети, причем F(p – t) ⋃ F(t – p),

где F(p – t) – множество дуг, ведущих от позиций к переходам,

F(t – p) – множество дуг, ведущих от переходов к позициям.

При таком представлении функционирование сети представляется как взаимодействие позиций и переходов в ней.

РЕЗУЛЬТАТЫ И ИХ ОБСУЖДЕНИЕ

Рассмотрим для переходов t_j следующие функции:

– ввода I(t_j): T → P (отображение из множества переходов в комплекты позиций);

– выхода O(t_j): T → P (отображение из множества переходов в комплекты позиций). Таким образом, в этом случае для перехода t_j → T определяются входные I(t_j) и выходные O(t_j) позиции сети, то есть позиция p_i будет входной позицией перехода t_j, если p_i ∈ I(t_j) и будет выходной позицией этого перехода, если p_i ∈ O(t_j).

Определим для позиций p_i следующие функции:

– ввода I(p_i): P → T (отображение из множества позиций в комплекты переходов);

– выхода O(p_i): P → T (отображение из множества позиций в комплекты переходов). Таким образом, в этом случае для позиции t_i ∈ P определяются входные I(p_i) и выходные O(p_i) переходы сети, то есть переход t_j будет входным переходом позиции p_i, если t_i ∈ I(p_i) и будет выходным переходом этой позиции, если t_i ∈ O(p_i).

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

В таком случае сеть Петри можно представить 4-кортежем (P, T, I, O).

Пример:

Задана структура сети Петри C = (P, T, I, O, M), где

P = {p₁, p₂, p₃, p₄, p₅} – множество мест (позиций) сети,

T = {t₁, t₂, t₃, t₄} – множество переходов сети,

I – функция входа: I(t₁) = {p₁},

I(t₂) = {p₁, p₃, p₅},

I(t₃) = {p₃},

I(t₄) = {p₄},

O – функция выхода: O(t₁) = {p₂, p₃, p₅},

O(t₂) = {p₅},

O(t₃) = {p₄},

O(t₄) = {p₂, p₃}.

Приведенная выше структура сети Петри состоит из пяти позиций, четырех переходов и тринадцати дуг.

Графический способа задания сетей Петри. Таким образом, сеть Петри можно представить как двудольный мультиграф, дуги которого соединяют вершины двух непересекающихся множеств (P и T). Вершины P множества P изображают кружками, а вершины t_j ∈ T – полочками. Дуги этого мультиграфа всегда направлены либо из вершин множества P к вершинам множества T, либо наоборот – из вершин множества T к вершинам множества P.

Рассмотренная ранее в примере 1 структура сети Петри представлена на рисунке (рис. 1).  

Задание сетей Петри матричным способом. Для задания инцидентности вершин сети Петри эффективно применение матриц. Иными словами, сеть Петри задают двумя матрицами Q и  R, имеющими n столбцов (по числу вершин позиций p_ε) и  k строк (по числу вершин переходов t_j) (рис. 2).   

Элементами матриц являются нули и единицы, которые отражают значения элементов q_jε и r_jε, заданные выражениями.

Элемент q_jε равен единице, если есть дуга от вершины позиции p_ε к вершине перехода t_j, и равен нулю в случае отсутствия дуги.

Элемент r_jε равен единице, если имеется дуга от вершины перехода t_j к вершине позиции p_ε, и равен нулю в случае отсутствия дуги.

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

Маркировка и функционирование сетей Петри. Функционирование сети Петри, с одной стороны, определяется маркировкой сети: присвоением фишек позициям, количеством и расположением их, а с другой стороны – разработанной методикой изменения маркировки позиций и правилами срабатывания переходов.

Функционирование сети Петри можно определить как процесс присвоения фишек позициям, количество и расположение которых будут меняться. Маркировка сети Петри определяется как отображение множества позиций P в множество неотрицательных целых чисел.

μ : P → N,

где i – метки, P – позиции, N – целые числа.

Маркировка сети Петри может быть определена как вектор M:

M = (μ₁, μ₂, ..., μ_i, ..., μ_n),

где n = |P|, каждое μ_i ∈ N, i = 1, ..., n.

Маркированная сеть Петри представляет собой 5-кортеж (P, T, I, O, M).

Зададим начальную маркировку сети Петри, структура которой рассмотрена в примере 1 на рисунке (рис. 1). Маркировка M₀ = (1,1,0,0,1) означает, что фишки поставлены в позициях 1, 2 и 5. Маркированная сеть Петри примет вид, показанный на рис. 3.

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

Этот процесс будет осуществляться до тех пор, пока не останется ни одного разрешенного перехода, после чего функционирование сети прекращается.

Рассмотрим сеть Петри, заданную графически (рис. 4), начальная маркировка которой M₀ = (1,1,0,0,1). Данная маркировка открывает только один переход – T₁.

Результатом запуска перехода T₁ будет сеть с маркировкой (рис. 5).

Структура матрично-предикатного представления сетей Петри. Сеть Петри можно представить в виде блок-схемы (рис. 6).

Сеть Петри является двудольным (направленным) мультиграфом G(A, E) ,

где A = P ⋃ T – множество вершин,

E – инцидентор, задающий взаимосвязь вершин. Под этим понимаем связь между элементами, когда вершина инцидентна ребру.

Любой граф может быть представлен в матрично-предикатном виде. Представим матрицу этого графа G(A, E) в виде квадратной матрицы, состоящей из четырех частей (рис. 7).  

P = ‖p_i‖ – подматрица вершин-позиций;

T = ‖t_i‖ – подматрица вершин-переходов;

 – подматрица, представляющая часть инцидентора, описывающего переход из состояния позиций сети Петри в состояние переходов;

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

Часть P матрицы M_И (рис. 8) – это диагональная матрица, представляющая собой несвязный граф, который задает множество позиций сети Петри.  

С помощью этой части матрицы M_И осуществляется маркировка сети Петри, которая осуществляется присвоением фишек i позициям (рис. 9).

Маркированная сеть Петри представляет собой 5-кортеж (P, T, I, O, M).

Часть T матрицы M_И (рис. 10) – это диагональная матрица, представляющая собой несвязный граф, который задает множество переходов сети Петри.

Часть E_PT матрицы M_И (рис. 11) – это часть инцидентора, представляющая истинные значения предиката (диагональные элементы матрицы M_И определяются трехместным предикатом PiμiPi или TjμjTj_, а для задания недиагональных ненулевых элементов матрицы M_И трехместный предикат доопределяется двумя местами, определяющими кратности дуг этих входов и выходов), который связывает конкретные позиции сети (матрица P) с соответствующими переходами сети (матрица T).

Часть E_TP матрицы M_И (рис. 12) – это часть инцидентора, представляющая истинные значения предиката, который связывает конкретные переходы сети (матрица T) с соответствующими позициями сети (матрица P).

Подставим в матрицу M_И значения частей P, T, E_PT, E_TP и получим обобщенную матрицу, приведенную на рисунке (рис. 13).

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

ЗАКЛЮЧЕНИЕ

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