Дерево достижимости сети петри

Задача достижимости. Для данной сети Петри С с маркировкой m и маркировки m‘ определить: ?

Маркировка m" покрывает маркировку m‘, если m" m‘, т.е. . Задача покрываемости. Для данной сети Петри С с начальной маркировкой m и маркировки m‘ определить, существует ли такая достижимая маркировка , такая что m" m‘.

Методы анализа сетей Петри.

Дерево достижимости.

Рис 4.4: Маркированная сеть Петри, для которой строится дерево достижимости.

Дерево достижимости представляет множество достижимости сети Петри. Рассмотрим, например, маркированную сеть Петри на рис. 4.4. Её начальная маркировка – (1, 0, 0). Это – корневая вершина дерева достижимости. Непосредственно достижимые из неё маркировки – это вершины второго уровня и т.д.

Рис 4.5: Первые три шага построения дерева достижимости для сети Петри на рис 4.4.

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

Пассивные маркировки – маркировки, в которых нет разрешенных переходов. Они называются терминальными вершинами. Другой класс маркировок – это маркировки, ранее встречавшиеся в дереве. Они называются дублирующими вершинами; никакие последующие маркировки рассматривать нет нужды – все они будут порождены из места первого появления дублирующей маркировки в дереве. Таким образом, в дереве на рис.4.5 маркировка (0, 1, 1), получившаяся в результате выполнения последовательности , не будет порождать какие-либо новые вершины, поскольку она ранее встречалась в дереве в результате выполнения перехода из начальной маркировки.

Для сведения дерева достижимости к конечному представлению используется еще одно средство. Рассмотрим последовательность запусков переходов σ, начинающуюся в начальной маркировке m и кончающуюся в маркировке m‘ > m,. Маркировка m‘ совпадает с маркировкой m, за исключением того, что имеет некоторые «дополнительные» фишки в некоторых позициях. Теперь, поскольку на запуски переходов лишние фишки не влияют, последовательность σ можно запустить снова, начиная в m‘ и приходя к маркировке m". В общем случае можно запустить последовательность σ n раз, получив в результате маркировку . Следовательно, для тех позиций, которые увеличивают число фишек последовательностью σ, можно создать произвольно большое число фишек, просто повторяя последовательность σ столько, сколько это нужно. В сети Петри на рис. 4.4, например, можно запустить переход столько раз, сколько необходимо для того, чтобы получить произвольное число фишек в р₂. Представим бесконечное число маркировок, получающихся из циклов такого типа, с помощью специального символа ω, который обозначает «бесконечность». Для любого постоянного а определим

. (4.5)

Рис 4.6: Дерево достижимости для сети Петри изображённой на рис 4.4.

Можно показать, что алгоритм построения дерева достижимости заканчивает работу.

Лекция 5.

Анализ сетей Петри (продолжение).

Безопасность и ограниченность.

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

Сохранение.

Если маркировка имеет в качестве маркировки некоторой позиции тогда для того, чтобы сеть была сохраняющей, вес этой позиции должен быть равным 0. Если сеть сохраняющая, существуют взвешенная сумма, обозначим её s, и вектор весов w = (w₁, w₂, . w_n). Для каждой маркировки дерева достижимости имеем

. (5.1)

Если система (5.1) имеет решение, то сеть сохраняющая с весом.

Покрываемость.

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

Последнее изменение этой страницы: 2016-08-14; Нарушение авторского права страницы

На этом шаге мы рассмотрим вопросы, связанные с достижимостью и покрываемостью в сетях Петри .

Определение. Задача достижимости. Для данной сети Петри С = (P, T, I, O) с маркировкой m и маркировки m’ определить: m’ , принадлежащее R(C, m) .

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

Множество достижимости сети Петри представляет собой дерево достижимости. Пусть имеется сеть Петри, представленная на рисунке 1.

Рис.1. Маркированная сеть Петри, для которой строится дерево достижимости

Ее начальная маркировка – (1, 0, 0). В этой начальной маркировке разрешены t 1 и t 2 . Чтобы рассмотреть все множество достижимости, определим новые вершины в дереве достижимости для других достижимых маркировок, получающихся в результате запуска каждого из этих двух переходов. Начальной (корневой) является вершина, соответствующая начальной маркировке. Дуга, помеченная запускаемым переходом, приводит из начальной маркировки к каждой из новых маркировок (рисунок 2).

Рис.2. Первый шаг построения дерева достижимости

Это частичное дерево показывает все маркировки, непосредственно достижимые из начальной маркировки.

Теперь необходимо рассмотреть все маркировки, достижимые из новых маркировок. Из маркировки (1, 1, 0) можно снова запустить t 1 (получая 1, 2, 0) и t 2 (получая (0, 2, 1)); из (0, 1, 1) можно запустить t 3 (получая 0, 0, 1). Это порождает дерево, изображенное на рисунке 3.

Рис.3. Второй шаг построения дерева достижимости

Начиная с трех новых маркировок, необходимо повторить этот процесс, порождая новые маркировки, которые нужно ввести в дерево, как показано на рисунке 4.

Рис.4. Третий шаг построения дерева достижимости

Заметим, что маркировка (0, 0, 1) пассивная; никакой переход в ней не является разрешенным, поэтому никакие новые маркировки из этой пассивной маркировки в дереве порождаться не будут. Кроме того, необходимо отметить, что маркировка (0,1, 1), порождаемая запуском t 3 в (0, 2, 1) была уже порождена непосредственно из начальной маркировки запуском t 2 .

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

Рис.5. Простая сеть Петри с бесконечным деревом достижимости

Дерево представляет все возможные последовательности запусков переходов. Всякий путь в дереве, начинающийся в корне, соответствует допустимой последовательности переходов.

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

Приведение к конечному представлению осуществляется несколькими способами. Прежде всего, необходимо использовать те средства, которые ограничивают введение новых маркировок (называемых граничными вершинами) на каждом шаге. Для этого могут вводиться пассивные маркировки, то есть маркировки, в которых нет разрешенных переходов. Такие пассивные маркировки называются терминальными вершинами . Другой класс маркировок – это маркировки, ранее встречавшиеся в дереве. Такие маркировки называются дублирующими вершинами : никакие последующие маркировки можно не рассматривать – все они будут порождены из места первого появления дублирующей маркировки в дереве. Таким образом, в дереве на рисунке 5 маркировка (0, 1, 1), получившаяся в результате выполнения последовательности t 1 , t 2 , t 3 , не будет порождать какие-либо новые вершины в дереве, поскольку она ранее встречалась в дереве в результате выполнения последовательности t 2 из начальной маркировки.

Каждая вершина может классифицироваться как граничная вершина, терминальная вершина, дублирующая вершина или как внутренняя вершина. Граничными являются вершины, еще не обработанные алгоритмом, а после обработки они могут стать терминальными, дублирующими или внутренними вершинами.

Алгоритм обычно начинается с определения начальной маркировки корнем дерева, т. е. граничной вершиной.

Пусть х – граничная вершина, которую необходимо обработать, тогда

1. если в дереве имеется другая вершина у , не являющаяся граничной, и с ней связана та же маркировка, m(х) = m(у) , то вершина х – дублирующая;
2. если для маркировки m(х) ни один из переходов не разрешен, то х – терминальная вершина;
3. дуга, помеченная t j , направлена от вершины х к вершине у . Вершина х переопределяется как внутренняя, вершина у – становится граничной.

Если все вершины дерева – терминальные, дублирующие или внутренние, то обработка данным алгоритмом останавливается. Определение. Задача покрываемости. Для заданной сети Петри С с начальной маркировкой m и маркировки m’ определить, существует ли такая достижимая маркировка m” принадлежащая R(C, m) , что m” >= m . Маркировка m” покрывает m’ .

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

Мы закончили краткое введение в сети Петри. В заключение приведем небольшой список использованных нами источников.

1. Дружинин В. А. Использование сетей Петри для моделирования технологических процессов / Дружинин В. А., Борде Т. Д. // Радиоэлектроника, информатика, управление. – 1999. – №2. – С. 65-72.
2. Захаров Н. Г. Синтез цифровых автоматов. Учебное пособие / Захаров Н. Г., Рогов В. Н. / Ульяновский гос. техн. ун-т. – Ульяновск, 2003. – 135 с.
3. Кирюшин О.В. Анализ систем с помощью сетей Петри. Учебно-методическое пособие / Кирюшин О.В. / Уфимский гос. нефт. техн. ун-т. – Уфа, 2006. – 18 с.
4. Котов В.Е. Сети Петри: Пер. с англ. / Котов В.Е. – М.: Наука, 1984. – 160 с.
5. Лескин А.А. Сети Петри в моделировании и управлении / Лескин А. А., Мальцев П. А., Спиридонов А. М. – Л.: Наука, 1989. – 133 с.
6. Никулина Н. О. Применение аппарата сетей Петри для моделирования экономических процессов. Методические указания к лабораторным работам по курсу "ЛВС и распределенная обработка данных в банках" / Никулина Н. О., Старцева Е. Б. / Уфимский гос. авиац. техн. ун-т. – Уфа, 2001. – 32 с.
7. Павлова А. В. Математические основы теории систем. Учебное пособие / Павлова Н. О. /Белорусский гос. ун-т информатики и радиоэлектроники. – Минск, 2004. – 84 с.
8. Питерсон Дж. Теория сетей Петри и моделирование систем / Питерсон Дж. – М.: Мир, 1984. – 264 с.
9. Федотов И. Е. Некоторые приемы параллельного программирования. Учебное пособие. / Московский гос. ин-т радиоэлектроники, электроники и автоматики. – Москва, 2008. – 188 с.
10. Сети Петри. Моделирование с помощью сетей Петри [Электронный ресурс] http://www.modelling-process.ru
11. Моделирование (базовый курс) [Электронный ресурс] http://bigor.bmstu.ru
12. Теория информационных технологий и систем. Лекция: Сети Петри [Электронный ресурс] http://www.intuit.ru
13. Моделирование информационных процессов и систем [Электронный ресурс] http://www.best-in-web.narod.ru

Удачи в освоении и использовании сетей Петри!

Дерево достижимости представляет множество достижимости сети Петри. Рассмотрим, например, маркированную сеть Петри на рис. 3.6. Начальная маркировка ее – (1, 0, 0). В этой начальной маркировке разрешены два перехода: t₁ и t₂. Поскольку мы хотим рассмотреть все множества достижимости, определим новые вершины в дереве достижимости для (достижимых) маркировок, получающихся в результате запуска каждого из этих двух переходов. Дуга, помеченная запускаемым переходом, приводит из начальной маркировки к каждой из новых маркировок (рис. 3.7). Корневой (начальной) является вершина, соответствующая начальной маркировке. Это (частичное) дерево показывает все маркировки, непосредственно достижимые из начальной маркировки.

Рис. 3.6. Маркированная сеть Петри Рис. 3.7. Первый шаг построения дерева достижимости

Теперь необходимо рассмотреть все маркировки, достижимые из новых маркировок. Из маркировки (1, 1,0) можно снова запустить t₁ ( получая (1, 2, 0)) и t₂ (получая (0, 2, 1)); из (0, 1, 1) можно запустить t₃ (получая (0, 0, 1)). Это порождает дерево, изображенное на рис. 3.8. Начиная с трех новых маркировок, необходимо повторить этот процесс, порождая новые маркировки, которые нужно ввести в дерево, как показано на рис. 3.9. Заметим, что маркировка (0, 0, 1) пассивная; никакой переход в ней не является разрешенным, поэтому никакие новые маркировки из этой пассивной маркировки в дереве порождаться не будут. Кроме того, необходимо отметить, что маркировка (0, 1, 1), порождаемая запуском t₃ в (0, 2, 1), была уже порождена непосредственно из начальной маркировки запуском t₂.

Рис. 3.8. Второй шаг построения дерева Рис. 3.9. Третий шаг построения дерева

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

Приведение к конечному представлению осуществляется несколькими способами. Нам необходимо найти те средства, которые ограничивают введение новых маркировок (называемых граничными вершинами) на каждом шаге. Здесь могут помочь пассивные маркировки – маркировки, в которых нет разрешенных переходов. Эти пассивные маркировки называются терминальными вершинами. Другой класс маркировок – это маркировки, ранее встречавшиеся в дереве. Такие дублирующие маркировки называются дублирующими вершинами; никакие последующие маркировки рассматривать нет нужды – все они будут порождены из места первого появления дублирующей маркировки в дереве. Таким образом, в дереве на рис. 3.9 маркировка (0, 1, 1), получившаяся в результате выполнения последовательности t₁t₂t₃, не будет порождать какие-либо новые вершины в дереве, поскольку она ранее встречалась в дереве в результате выполнения последовательности t₂ из начальной маркировки.

Для сведения дерева достижимости к конечному представлению используется еще одно средство. Рассмотрим последовательность запусков переходов σ, начинающуюся в начальной маркировке μ и кончающуюся в маркировке μ’, μ’ > μ. Маркировка μ’ совпадает с маркировкой μ, за исключением того, что имеет некоторые «дополнительные» фишки в некоторых позициях, т. е. μ’ = μ + (μ’ – μ) > 0. Теперь, поскольку на запуски переходов лишние фишки не влияют, последовательность σ можно запустить снова, начиная в μ’, приходя к маркировке μ". Так как действие последовательности переходов σ добавило μ’ – μ фишек к маркировке μ, она добавит также μ’ – μ фишек и к маркировке μ’, поэтому μ” = μ’ + (μ’ – μ) или μ” = μ + 2(μ’ – μ). В общем можно запустить последовательность σ n раз, получив в результате маркировку μ + n(μ’ – μ). Следовательно, для тех позиций, которые увеличивают число фишек последовательностью σ, можно создать произвольно большое число фишек, просто повторяя последовательность σ столько, сколько это нужно. В сети Петри на рис. 4.7, например, можно запустить переход t₁ столько раз, сколько необходимо для того, чтобы получить произвольное число фишек в р₂.

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

3. Для всякого перехода t_j Т, разрешенного в μ[х] (т.е. δ(μ[х], t_j) определено), создать новую вершину z дерева достижимости. Маркировка μ[z], связанная с этой вершиной, определяется для каждой позиции р_i следующим образом:

б) Если на пути от корневой вершины к х существует вершина y с
μ[y]

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

Найденное значение является границей числа фишек для заданной позиции. Если граница для всех позиций не превышает 1, сеть безопасна.

На рис. 3.13 демонстрируется использование дерева достижимости для определения ограниченности.

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

Рис. 3.13. Определение ограниченности для сети Петри с помощью дерева достижимости.

Свойство сохранения эффективно проверяется с помощью дерева достижимости. Так как дерево достижимости конечно, для каждой маркировки можно вычислить взвешенную сумму. Если сумма одинакова для каждой достижимой маркировки, сеть – сохраняющая по отношению к данному весу. Если суммы не равны сеть – несохраняющая.

При оценке сохранения необходимо быть внимательным с символом ω. Если маркировка имеет ω в качестве маркировки позиции p_i, тогда для того, чтобы сеть была сохраняющей, вес этой позиции должен быть равным 0. Напомним, что символ ω представляет бесконечное множество значений. Так как все веса неотрицательны, вес должен равняться либо нулю (тем самым означая, что число фишек в данной позиции не важно), либо быть положительным. Если вес положителен, то сумма будет разной для двух маркировок, различающихся в своей ω-компоненте. Следовательно, если какая-либо маркировка с ненулевым весом равна ω, сеть — несохраняющая.

Эти рассуждения относятся к сохранению по отношению к определенному взвешиванию. Сеть Петри является сохраняющей, если она сохраняющая по отношению к некоторому вектору w, w_i > 0. Дерево достижимости можно использовать для определения того, является сеть сохраняющей или нет, путем нахождения вектора весов w (если он существует). Заметим прежде всего, что для того, чтобы сеть Петри была сохраняющей по отношению к положительному вектору весов, она должна быть ограниченной. Как было указано выше, неограниченная позиция должна иметь нулевой вес, что недопустимо в сети с положительным вектором весов. (Если мы хотим допустить нулевые компоненты, нужно просто установить веса всех неограниченных позиций равными нулю и рассматривать после этого только оставшиеся компоненты.) Теперь, если сеть сохраняющая, существуют взвешенная сумма, обозначим ее s, и вектор весов
w = (w₁, w₂, . w_n). Для каждой маркировки μ[х] дерева достижимости имеем

Это равенство определяет для k вершин дерева достижимости совокупность из k линейных уравнений с n + 1 неизвестными. Добавим к ним ограничения:
w_i > 0, i = 1, . n, в результате чего определим ограничения для вектора весов.

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

Последняя задача, которую можно решить с помощью дерева, достижимости, – задача покрываемости. В задаче покрываемости мы хотим для данной маркировки μ’ определить, достижима ли маркировка μ" ≥ μ’. Данная задача решается проверкой дерева достижимости. Строим для начальной маркировки μ дерево достижимости. Затем ищем любую вершину х с μ[х] ≥ μ’. Если такой вершины не существует, маркировка μ’ не покрывается никакой достижимой маркировкой; если она найдена, μ[х] дает достижимую маркировку, покрывающую μ’.

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

Рис. 3.14. Сеть Петри Рис. 3.15. Дерево достижимости сети Петри

Упражнения

2. Построить дерево достижимости для сети Петри на рис. 3.5 и определить тип вершин.

3. Построить дерево достижимости и проверить на безопасность сети Петри с рис.2.14, рис.2.15, рис. 2.16.

4. Построить дерево достижимости и проверить, будет ли сеть Петри с рис.3.9 сохраняющей.

5. Построить дерево достижимости для сети Петри на рис. 3.5 и определить, будет ли покрываемы вершины (1, 1, 1, 0), (0, 1, 1, 0), (1, 1, 0, 0).

6. Построить дерево достижимости для сети Петри на рис. 3.5 и проверить, будет ли достижимы вершины (1, 3, 0, 0) и (0, 0, 1, 0).

Дата добавления: 2016-04-11 ; просмотров: 5143 ; ЗАКАЗАТЬ НАПИСАНИЕ РАБОТЫ