Формирование сложных связей с помощью сетей Петри

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

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

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

Полученная сеть Петри представлена на Рис. 2. Созданная модель синтезирована из предположения, что условия возникновения событий всегда выполняются. В силу этого предположения не требуется вводить новые позиции, которые соответствуют набору условий выполнения событий t1−1, t1−2, t2, …, t6−1, t6−2, t7.

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

Рис. 2. Синтезированная сеть Петри.

Основными методами анализа свойств достижимости являются:

построение дерева достижимости;

метод матричных уравнений.

Для синтезированной сети Петри (Рис. 2.) дерево достижимости представлено на рис. 3. Из основных свойств сетей Петри для сложных связей могут использоваться следующие: живость — отсутствие тупиковых состояний, исключая выходное (целевое) состояние сложной связи; безопасность — метки вершин включают только «0» и «1», что означает отсутствие зацикливаний; правильность — сеть безопасна и живая; пассивность переходов — переходу не соответствует ни одной дуги графа.

Методы матричных уравнений. Альтернативным по отношению к определению сети Петри PN в виде (S, T, I, O) является определение сети Петри PN в виде двух матриц Dи D+, представляющих входную и выходную функции I и O. Каждая из матриц Dи D+ имеет m = ¦T¦ строк (по одной на переход и n = ¦S¦ столбцов (по одному на позицию). Матричный вид сети Петри PN = (S, T, I, O) задаётся парой (D, D+), где.

D[k, i] = ^#(si, tk) — кратность дуги, ведущей из позиции pi в переход tk;

D+[k, i] = #^(si, tk) — кратность дуги, ведущей из перехода tk в позицию si, для произвольных 1? k? m, 1? i? n.

Рис. 3. Дерево достижимости для синтезированной сети Петри

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