Раскрашенные (цветные) сети Петри (CPN)

Определение раскрашенных (цветные) сети Петри (C PN)

В последние годы широко используется методология моделирования дискретных систем, основанная на использовании раскрашенных (цветных) сетей Петри – Coloured Petri Net (CPN). Эта методология является обобщением формализма обыкновенных сетей Петри на случай многих видов ресурсов и позволяет более эффективно моделировать сложные системы. На базе методологии CPN разработан специальный язык моделирования – Coloured Petri Net Modelling Language (CPN ML) и созданы соответствующие программные средства.

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

Ниже рассмотрено несколько упрощенное и по возможности нефор-мализованное описание CPN ориентированное на синтаксис языка Паскаль. Полное и строгое описание CPN содержится в книге Курта Йенсена [5].

 

Мультимножества

Одним из важных понятий, используемых в теории раскрашенных сетей Петри, является понятие мультимножества.

Формально мультимножеством  на непустом множестве  называется функция , где  - множество натуральных чисел.

Иными словами, мультимножество  состоит из элементов множества , каждый из которых может быть повторен  раз (  - переменная целого типа). мультимножество может быть представлено в виде кортежа, в котором перечислены входящие в него элементы с указанием их кратности. Указатель кратности – выражение целого типа - ставится перед названием элемента множества и отделяется от него кавычкой. Отсутствие какого либо элемента из  в мультимножестве эквивалентно его присутствию с нулевой кратностью. Формально мультимножество на  можно представить суммой

где  – число появлений (кратность) элемента  в мультимножестве .

Пример. Пусть  – множество элементов и  – мультимножество на . Последняя запись означает, что  состоит из двух элементов , одного элемента , нуля (ни одного) элементов  и  элементов , где  – переменная типа integer.

Рассмотрим операции над мультимножествами.

1. Сложение мультимножеств.

Пусть , .

Тогда .

2. Умножение мультимножества на скаляр.

Пусть  мультимножество,  - скаляр типа integer.

Тогда .

3. Сравнение мультимножеств.

Мы будем говорить, что ,

если .

4. Вычитание мультимножеств. если , то можно определить разность мультимножеств:

.

5. Мощность мультимножества – суммарное число элементов в мультимножестве:

.

Формальное определение CPN

раскрашенная сеть Петри CPN – это кортеж

.                                           (3.1)

Рассмотрим элементы определения (3.1).

1.  - множество дискретных моментов времени (шагов), в которые происходит функционирование сети. Номер шага есть переменная целого типа:

var teta: Integer;.

2.  – конечное множество непустых типов, называемое цветами. Типы имеют общее название  и задаются аналогично тому, как это принято в языках программирования. Например:

; – перечисляемый тип, здесь  - имя цветного множества, , ,  – входящие в него цвета;

; – целый тип;

; – прямое произведение типов.

При описании переменных, используемых в сети, указывают их принадлежность к типу, например:

; ; .

В последнем примере переменная  состоит из пары элементов , где элемент  принадлежит типу , а  – типу .

3.  – конечное множество позиций. Это множество может быть представлено перечисляемым типом:

;                                                          (3.2)

а для работы с ним вводится переменная

.

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

.

Здесь , ,  - переменные указанных в п. 2 цветовых типов, определяющие различные виды ресурсов, а цифры, стоящие перед кавычками – количество фишек соответствующего типа, в позиции .

Совокупность маркировок всех позиций называется маркировкой сети:

.

В языке Паскаль мультимножество, определяющее маркировку позиции, может быть представлено, например, типом – множество, состоящим из записей вида

;                                                                     (3.3)

; ; ;.

Операции над мультимножествами можно определить соответствующими процедурами. Аналогично определяется мультимножество, задающее маркировку сети.

4.  – конечное множество переходов, которое можно представить перечисляемым типом

;                                                             (3.4)

и соответствующей переменной:

.

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

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

В этих выражениях первый элемент указывает начало дуги, второй элемент – конец дуги.

множество  имеет следующую структуру:

,

где дуги  определяются одним из видов выражений:

 или , , .

Поскольку дуги имеют два вида: от позиции к переходу () и от перехода к позиции (), то множество  можно представить в виде суммы непересекающихся множеств:

, ,

где множество  содержит элементы вида , а множество  –элементы вида .

Как и в случае обыкновенных сетей Петри, элементы множеств , , не пересекаются:

.

6.  – узловая функция, которая для каждой дуги  указывает ее исходный и конечный узел. Формально

, , если в множестве  элементу  соответствует выражение . Здесь  - имя узла, от которого начинается дуга,  – имя узла, где она заканчивается.

Рассмотрим один из способов задания этой функции.

Каждая дуга может быть представлена в виде записи. Дуги типа  задаются записью

;                                                                     (3.5)

; ; ;.

Дуги типа  задаются аналогично:

;                                                                  (3.6)

; ; ;.

Множества дуг  и  могут быть представлены перечисляемыми типами:

                                                   (3.7)

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

; .

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

означает, что цвета типа  разрешены для позиций , а цвета типа  разрешены для всех остальных позиций из .

8.  – блокировочная (спусковая) функция, описывающая дополнительные условия, которые должны быть выполнены для срабатывания перехода . Эта функция представляет собой предикат, составленный из переменных, принадлежащих типам цветов . Например, функция

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

9.  – функция, задающая выражения на дугах . Эта функция для каждой дуги  определяет мультимножество, состоящее из элементов, описанных в множестве цветов . Мы будем говорить, что это мультимножество помечает дугу. Введение в CPN функции  является развитием понятия кратности дуг в формализме обыкновенных СП.

Рассмотрим примеры задания функции .

- дуга  помечается двумя фишками типа ;

- дуга  помечается двумя фишками типа , если переменная  и одной фишкой типа , если .

- дуга  помечается одной фишкой типа , если , иначе не помечается.

- дуга  помечается одной фишкой типа  состоящей из типов  и  (см. пример в п. 2 определения), если  и не помечается в противном случае.

Отсутствие выражения для какой-либо дуги означает, что дуга не помечена.

9.  - функция инициализации сети CPN. Эта функция по аналогии с обыкновенными СП задает начальную маркировку (разметку) сети , т.е. для каждой позиции  указывает цветовое мультимножество, обозначаемое .

Например, ; ;  - начальные маркировки позиций;  - начальная маркировка сети.

Функционирование CPN

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

Мы будем говорить, что переход  может сработать, если выполняется условие:

.                                (3.8)

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

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

Во второй скобке записано условие отсутствия блокировки перехода  (см. п. 8 определения).

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

Изменение маркировки узла  при осуществлении шага работы CPN рассчитывается по формуле:

.                              (3.9)

В выражении (4.21) все слагаемые являются мультимножествами, и вычисления производятся в соответствии с правилами сложения и вычитания мультимножеств. Знаки суммирования мультимножеств используются в формуле по причине, которая уже пояснена выше: каждая пара узлов может быть связана несколькими дугами, а каждая дуга  помечена отдельным выражением .

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

Пример. Приведем описание простой CPN, схема которой и начальная маркировка приведены на рисунке 3.1 а.

                                       

                          а)                                                   б)

Рисунок 3.1 Раскрашенная сеть Петри и
эквивалентная ей обыкновенная СП

 

· Множества цветов:

; .

· Переменные:

; .

· Множество позиций:

.

· Множество переходов:

.

· Множество дуг , , , , ,

; ;

; ;

· Цветовая функция

· Блокировочная функция отсутствует:

.

· функция , задающая выражения на дугах:

;

· функция инициализации , задающая начальную маркировку ; ; .

 

Ниже приведено полное дерево маркировок рассмотренной сети.

 

 

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

В позицию  при срабатывании перехода пересылается та фишка, которая была извлечена из  при срабатывании перехода. Начальная маркировка – 3 фишки цвета  в позиции , по одной фишке всех цветов в позиции .

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

Эквивалентная рассмотренной CPN обыкновенная сеть Петри приведена на рисунке 3.1 б.

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

Расширения CPN

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

Ниже мы рассмотрим одно важное расширение CPN, значительно расширяющее их моделирующие возможности: CPN с временным механизмом

Существует ряд задач моделирования, в которых необходимо учитывать не только последовательность событий, но и время их наступления, а также продолжительность. Для этой цели предусмотрено расширение возможностей раскрашенных сетей Петри путем введения временного механизма (так называемых timed CPN [10]). В несколько упрощенном виде сущность такого расширения описана ниже.

А. В модель системы вводятся часы, показывающие глобальное время . Обычно это время считается дискретным, т.е. означает номер такта, выдаваемого тактовым генератором системы моделирования. Глобальное время  отличается от времени , которое содержится в определении (4.13), поскольку  есть номер шага работы CPN, а  изменяется независимо от работы сети.

Б. Ресурсы, перемещаемые в сети (фишки) могут получить временные метки. Такие ресурсы, в общем виде, задаются мультимножествами с временными метками (timed multi-sets), однако мы эту теорию не рассматриваем. Отметим лишь, что при описании множества цветов добавляются пометки timed, а переменные соответствующего типа снабжаются знаками @ (по-английски читается at, т.е. «во время»). Это означает, что переменная привязана к глобальному времени. После значка @ в квадратных скобках указывается значение глобального времени, в течение которого возможно использование данных фишек при срабатывании переходов, для которых они являются входными. При этом запись вида @[500] говорит о том, что фишка «включается» в момент  и далее готова для работы в сети, а запись @[500, 600] означает, что фишка может использоваться в диапазоне глобального времени .

Приведем пример.

;

;

;

.

Возможное значение мультимножества определяемого переменной :

.

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

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

Рисунок 3.2 Фрагмент CPN с временными метками

Пусть в сети на рисунке 3.2 начальная маркировка такова:

, .

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

, .

 

3.1.5 Сравнение формализмов обыкновенных и
раскрашенных сетей Петри

Подведем некоторые итоги данного раздела. Мы кратко рассмотрели теорию сетей Петри в двух вариантах:

· формализм классических или обыкновенных СП (РТ – сетей в терминологии К. Йенсена);

· формализм раскрашенных сетей Петри - CPN.

Нетрудно убедиться в том, что формализм описания структуры и функционирования CPN справедлив и для обыкновенных СП. При этом пункты 1, 3, 4 и 10 совпадают с описанием в разделе 2.1.1; цветовое множество всего одно и имеет единственный цвет; описание связей между узлами вместо матриц  и  следует задавать множеством дуг , узловой функций  и выражениями на дугах . Функция  тривиальна и поэтому не нужна, а функция  всегда истинна.

Правила срабатывания и изменения маркировок (3.8) и (3.9) при сделанных предположениях совпадают соответственно с (2.6) и (2.7).

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