Граф достижимых маркировок сети Петри

Формализованное описание УП на языке сетей Петри прежде всего используется для анализа процесса, выявления его свойств, обнаружения и устранения недопустимых состояний. К числу таких состояний, наиболее характерных для параллельных процессов с разделяемыми ресурсами, относятся тупиковые состояния, в которых процесс прекращает развитие, не достигнув своего конечного состояния. Причины возникновения тупикового состояния могут быть различны — это и некорректно составленная структура параллельно-последовательного процесса, и неправильное распределение ФР, и недопустимое взаимодействие процедур процесса с ЛР. Поскольку возникновение тупиковых состояний в УП приводит к преждевременной остановке технологического процесса, выявление и устранение тупиков является одной из основных задач начального этапа проектирования УА.

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

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

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

Очевидно, наличие символа ω в графе достижимых маркировок свидетельствует о том, что число различных маркировок может быть бесконечным, несмотря на конечное число вершин графа. Сеть Петри, для которой получен такой граф, является неограниченной. Если сеть Петри ограничена и символ ω отсутствует в графе ее достижимых состояний, то эта сеть задает систему с конечным числом состояний. Именно к таким системам относится рассматриваемый нами УА, поэтому сеть Петри, описывающая УП, реализуемый в УА, должна иметь конечное число состояний.

Граф достижимых маркировок сети Петри N будем обозначать G_N. В вершине графа G_N, соответствующей маркировке M _i, будем выписывать те позиции сети Петри, которые содержат метки при этой маркировке, и те переходы, которые при этом активизированы. Если активизированные переходы входят в параллельные участки процесса, т. е. могут быть реализованы одновременно, в вершине графа G_N они связываются знаком конъюнкции. Активизированные переходы, входящие в альтернативные ветви, соединяются знаком дизъюнкции. Если позиция а _μ в маркировке M_i имеет более одной метки, число этих меток указывается в виде верхнего индекса этой позиции.

Поскольку каждая маркировка сети Петри определяет состояние рассматриваемой системы, можно считать, что вершина M _i графа достижимых маркировок сети Петри соответствует состоянию S _i процесса, задаваемого этой сетью. Для каждого процесса задается начальное и конечное состояния; если процесс является циклическим, то выделяется состояние, после которого процесс повторяется. В общем случае может быть несколько начальных и конечных состояний. Начальное состояние соответствует начальной вершине графа G_N, конечное — его терминальной вершине. Состояние процесса, не являющееся конечным, но не допускающее дальнейшего его развития, является тупиковым. Вершина графа G_N, соответствующая тупиковому состоянию, характеризуется тем, что при наличии меток в основных внутренних позициях сети Петри нет ни одного активизированного перехода.