Динамика сетей Петри в пространстве состояний.

 

Динамика сети описывается следующим рекуррентным уравнением:

 

M_k = M_k-1+A*U_k, k=1, 2, 3,…. (5.1)

 

Для вычисления управляющего вектора U_k необходимо определить те переходы t_j, которые срабатывают при маркировании M_k-1. Если t_j срабатывает, то u_j=1 и произведение A*U_k даёт число меток, добавляемых в позицию P _i в каждом такте.

Условие срабатывания перехода t_j и выработки u_j=1 представляется логическим уравнением:

 

i [m(P _i) ≥ I(t _j,P _i)] (u _j =1), (5.2)

 

которое управляет действиями t_j.

Для генерирования диаграммы состояний сети Петри достаточно использовать (5.1), (5.2). В теории сетей Петри иногда исходят из того, что не указывают порядок срабатывания переходов, если вектор U задаёт возбуждение нескольких из них в одном и том же такте k. Так в примере при построении дерева достижимости в состоянии M₀ вектор управления U₁*=(1,0,1), что указывает на возбуждение первого и третьего переходов. При срабатывании t₁ сеть перейдёт в состояние M₁=(0,1,1,1), при t₃ в состояние M₅=(2,2,0,0). Однако, если следовать (5.1), то диаграмма состояний сети имеет вид рис. 5.22в. Итак, если полагать, что все возбуждённые переходы срабатывают вместе, то динамику сети можно представить уравнением (5.1). Если исходить из того, что возбуждённые переходы могут срабатывать только порознь, то уравнение состояний сети будет иметь

в)

б)

a)

другой вид.

 

P

P

t

t

t

P

-1

A:

-1

-1

I:

O:

 

I: T x P → {0,1} - функция следования;

O: P x T → {0,1} - функция предшествования.

 

Рис. 5.22. Построение диаграммы состояний сети

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

Свободное движение сети. В реальных ВС имеется вполне определённый способ управления сменой состояний и присутствует такой фактор как время, что позволяет уточнить уравнение (5.2). Если времена срабатывания переходов одинаковы, то динамика системы моделируется уравнениями (5.1), (5.2), поскольку такая сеть является синхронной. Этих уравнений недостаточно для моделирования асинхронных процессов, для которых времена срабатывания различны.

В этом случае процедуру продвижения меток в сети следует производить в асинхронном времени, введя в модель часы. Если в синхронных системах достаточно вести отсчёт тактов, то в асинхронных необходимо в каждом из тактов определять момент наступления очередного. Интервал времени между тактами k и k +1 определяется временем наступления срабатывания одновременно одного или нескольких переходов.

Вынужденное движение сети. Уравнение (5.1) отражает свободное движение сети из начального состояния M₀. Вынужденное движение сети определяется вектором-функцией W(t), компоненты которого W_i(t) описывают приход меток в позиции P_i во времени; W(t) может задаваться в моменты дискретного времени k, наступление которых устанавливается моментами переключения состояния сети или внутренними часами.

Уравнение вынужденного движения сети Петри имеет вид:

 

M_k = M_k-1+A*U_k + W_k (5.3)

 

Таким образом, введённая здесь последовательность W_k описывает внешний источник меток, представленных входной лентой.

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

Последовательность W_k предназначена для отображения взаимодействий в структурированных сетях, она может отображать последовательные наборы данных, управляющих команд и т. д. Очевидно, что в любом состоянии системы компоненты вектора маркировки не могут быть отрицательными, то есть M_k≥0, V_k. Учитывая последнее, из (5.1) получаем M_k-1+A*U_k≥0.

Последовательность маркирований (5.1) можно выразить через начальную маркировку M₀ и вектор счёта срабатываний:

 

S = { }; j = 1, 2, 3, …, m. (5.4)

Элемент s_j указывает, какое число раз срабатывает переход t в последовательности маркирований, ведущей от M₀ к Мк.

Учитывая уравнение (5.4), из выражения (5.1) получаем:

 

M_k = M₀ + A*S. (5.5)

 

Введя вектор изменения маркирования ΔM = M_k – M₀, из уравнения (6) получим:

 

A*S = ΔM. (5.6)

 

К нахождению решений данного уравнения сводятся различные задачи практики. Все его возможные решения можно получить одним из методов решения задач целочисленного программирования.