Определение сети Петри

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

Сетью называют формальный объект вида (P, T, E), где:

P - непустое множество элементов сети (позиции);

T - непустое множество элементов сети (переходы);

P Ç T = Æ;

E Í (P´ T) È (T´ P) - отношение инцидентности, причем:

· любой элемент сети инцидентен хотя бы одному элементу другого типа (связность);

· в сети не содержится пар позиций, инцидентных одному и тому же переходу:

" p₁, p₂ Î P: (I(p₁) = I(p₂)) Ç (O(p₁) = O(p₂)) ® (p₁ = p₂).

Графически сеть представляется двудольным орграфом с двумя типами вершин (рис. 1): p_iÎ P, i=1(1)|P|; t_j Î T, j=1(1)|T|. Вершины p_iÎ P и t_j Î T связаны дугой (p_i, t_j), ориентированной из p_i в t_j, если (p_i, t_j) Î P ´ T. Вершины p_iÎ P и t_j Î T связаны дугой (t_j, p_i), ориентированной из t_j в p_i, если (t_j, p_i) Î (T ´ P).

Сети Петри. Формально сеть Петри представляет собой сеть с особым способом маркированными позициями и дугами.

C = (P, T, E, W, M), где

(P, T, E) - сеть;

W: E ® N \0, N - множество натуральных чисел, 0 - ноль;

M: P ® N.

Маркировка сети состоит в присвоении ее элементам (позициям p_i Î P и дугам e_ij, e_ji Î E численных значений (меток, маркеров).

Маркировку позиций удобно представлять в виде вектора

M₀ = (M₀(p₁), M₀(p₂),..., M₀(p_{½ p½} ),

где M₀(p_i) - число, которым отмечается позиция p_i Î P при ее маркировке. Маркировка M₀ задает исходное состояние сети.

Маркировка дуг устанавливает кратность каждой дуги сети: W(e_ij), W(e_ji) - натуральные числа (не ноль), задающие кратность дуг e_ij Î (P ´ T) и e_ji Î (T ´ P), инцидентных переходу t_j Î T соответственно по входу и выходу этого перехода.

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

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

Выполнение сети Петри. В сети Петри всегда срабатывает только возбужденный переход. Переход t_j Î T возбужден в состоянии M =(M(p₁), M(p₂),..., M(p_{½ p½} ) сети, заданном текущей маркировкой ее позиций, если

" р_i Î I(t_j): M(p_i) ³ W(p_i, t_j), (p_i, t_j)= e_ij Î (P ´ T) Ì E.

Таким образом, возбужденным в состоянии M оказывается всякий переход t_j Î T, имеющий в каждой своей входной позиции p_i Î I(t_j) метку M(p_i), большую (равную) кратности W(p_i, t_j) дуги (p_i, t_j), инцидентной этой входной позиции перехода.

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

Если в состоянии M сети оказываются возбужденными два или большее число переходов, то выполняется всегда только какой-то один из них. При этом вероятности выбора любого из этих переходов равны. Выполнение возбужденного перехода - неделимый акт. При срабатывании перехода в сети совершаются нормативные изменения ее состояния. Эти изменения производятся одномоментно с выполнением перехода. Они заключаются в назначении новой разметки M⁺ входных I(t_j) и выходных O(t_j) позиций выполняемого перехода:

" p_i Î I(t_j): M⁺ (p_i) = M(p_i) - W(p_i, t_j);

" p_i Î O(t_j): M⁺(p_i) = M(p_i) + W(t_j, p_i,);

" p_i Ï (I(t_j) È O(t_j)): M⁺ (p_i) = M(p_i), p_i Î P.

После разметки по указанным правилам сеть имеет новое состояние

M⁺ = (M⁺ (p₁), M⁺ (p₂),..., M⁺ (p_{½ P½} )).

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

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

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

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

Тупики в сетях Петри. Возможны такие сети Петри, в которых имеются переходы, никогда не получающие возбуждения. Они - " лишние" в сети. Их удаление не внесет каких-либо искажений в процесс выполнения сети. Другая ситуация, при которой происходит " выключение" перехода, связана с тупиковым состоянием сети.

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

Достижимость на сетях Петри. Если обозначить через M(C) множество достижимых от M₀ маркировок позиций сети, а знак ® использовать для записи отношения непосредственной достижимости

M_k M_k+1, k=1, 2, 3,...,

которым выражается факт перехода текущей маркировки M_k в следующую за ней непосредственно маркировку M_k+1, возникающую при срабатывании перехода t_j Î T, тогда с помощью тройки символов можно определить динамику сети Петри: Q = (M₀ , ®, M(C)).

Всякому возможному варианту выполнения сети будет отвечать определенная последовательность срабатываний переходов s = (t_j1, t_j2,.., t_jk,..) и связанная с ней последовательность маркировок сети

M₀ M₁ M₂ M_k.

Транзитивное бинарное замыкание отношения непосредственной достижимости маркировок задает бинарное отношение достижимости на сетях Петри. Маркировка M_k достижима от M_r, если в сети существует какая-либо последовательность s, в результате выполнения которой маркировка M_r перейдет в M_k:

M_r M_k, M_r, M_k Î M(C) Ì N ^{½ P½} .

Функционирования производственного модуля

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

1 - входная позиция станка; 2 - выходная позиция станка; 3 - накопитель заготовок в таре; 4 - промышленный робот (ПР); 5 - трансробот - манипулятор (ТМ); 6 - место комплектации; 7 - склад готовых деталей и заготовок в таре.

Сеть Петри формально задается матрицей инциденций

+ 1, p_i Î O(t_j), p_i Î P, t_j Î T;

a_ji = – 1, p_i Î I(t_j), p_i Î P; t_j Î T;

0, иначе.

В столбцах P₁ и P₁₃ матрицы R записаны значения (±1), что для матриц не правильно. Возникновение таких значений связано с наличием в сети контуров t_j, p_i, t_j, j=1, 3, 6 и t_j, p_i, t_j, j=7, 8, 10. Выходом из такого положения является представление R в виде составной матрицы R = R^- - R⁺ , R^- = (r^-_ji ), R⁺ = (r⁺_ji).