Модификации сетей Петри

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

 

- простые сети;

- чистые сети;

- сети, свободные от конфликтов;

- автоматные графы;

- регулярные сети;

- сети свободного выбора;

- ординарные (Ordinary Nets) сети;

- маркированные графы.

 

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

 

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

 

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

 

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

 

введение сдерживающих дуг или понятия области ограничения;

синхронизация срабатывания переходов;

введение приоритетов в срабатывании конкурирующих (конфликтующих) переходов;

введение множества правил срабатывания переходов (типизация переходов и позиций).

 

Наиболее мощным расширением (по возможности адекватно представлять сложные параллельные асинхронные системы с ярко выраженным причинно-следственным характером функционирования) являются F-сети.

 

Методы анализа сетей Петри на основе дерева достижимости

Дерево достижимости представляет множество достижимости сети Петри.

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

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

 

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

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

 

Для сведения дерева к конечному виду используется еще одно средство - символ (бесконечность).

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

 

Анализ свойств с помощью дерева достижимости

 

Безопасность

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

СП безопасна, если все маркировки в дереве достижимости состоят из нулей и единиц.

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

 

Ограниченность

Ограниченность проверяется по дереву достижимости для сети или отдельных позиций.

СП ограничена, если символ отсутствует в дереве достижимости. В противном случае она неограничена.

СП является k ограниченной, если k - наибольшее число,встречающееся в маркировках дерева.

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

 

Сохраняемость

 

Свойство сохраняемости (консервативности) эффективно проверяется с помощью дерева достижтмости.

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

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

 

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

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

 

Достижимость

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

 

Активность

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

 

Моделирование

Моделирование позволяет осуществлять процесс функционирования сети. Для управления процессом функционирования предназначен пункт меню "Модель". Пункт меню Модель включает в себя следующие подпункты:

· Запустить;

 

· Состояние;

· Статистика;

· Режим.

Данный пункт позволяет пользователю управлять моделированием, следить за функционированием сети и определять тот набор информации, который будет выдаваться на экран в процессе функционирования. Информация о функционировании сети может выдаваться в окно редактирования, в окно моделирования и в окно статистики.

Окно редактирования

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

 

В окне редактирования отображаются переходы и позиции сети:

 

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

 

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

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

 

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

Окно размещения сети

Окно размещения сети на экране позволяет производить перемещение по экрану фрагментов сети, а также дает представление об общем виде сети.

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

 

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

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

 

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

Окно моделирования

Окно моделирования открывается при выборе подпункта Запустить пункта Модель главного меню окна редактирования. Окно моделирования содержит текущую информацию о состоянии сети, состав которой определяется пользовантелем в окне Режим моделирования, и кнопки Пуск/Стоп, Начало, Помощь и Выход. В предельном режиме пользователь может отключить вывод в окно любой информации, тогда окно содержит только кнопки.

 

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

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

 

· текущий такт равен 0;

 

· текущее время равно 0;

· очереди переходов пусты;

· текущая маркировка равна начальной маркировке.

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

 

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

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

Окно статистики

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

 

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

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

 

Опции моделирования

Окно опций моделирования содержит две группы опций: Выдавать сообщение и Закрывать окно.

Группа опций Выдавать сообщение определяет при каких условиях остановки моделирования пользователю будет выдаваться сообщение о завершении моделирования:

· По тупиковой ситуации - выдавать сообщение по достижению тупиковой ситуации в сети;

 

· По времени останова - выдавать сообщение по достижению времени останова;

· По такту останова - выдавать сообщение по достижению такта останова;

· По закрытию пользователем - выдавать сообщение по закрытию окна пользователем.

Опции группы "Закрывать окно" определяют, при каких условиях остановки моделирования будет закрываться окно моделирования и, таким образом, завершаться процесс моделирования.

· По тупиковой ситуации - моделирование завершается по достижению тупиковой ситуации в сети;

 

· По времени останова - моделирование завершается по достижению времени останова;

· По такту останова - моделирование завершается по достижению такта останова.

Моделирование всегда завершается при закрытии пользователем окна моделирования.

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

 

При нажатии кнопки Отмена опции не изменяются.

 

Инструментальный набор

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

 

 

- выделения элементов;

- изменения параметров;

- маркировки позиций;

- установки позиции;

- установки перехода;

- рисования дуги;

- удаления элементов.

 

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

Текущий выбранный режим всегда выделяется цветом. В приведенном выше примере выбранным является режим выделения элементов.

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

Дуга сети считается выделенной, если выделены переход и позиция которые она соединяет.

Двойное нажатие левой клавиши мыши в этом режиме помещает данную точку по возможности в центр экрана. Ctrl+двойное нажатие не снимает при этом выделение с элементов.

 

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

Изменение параметров

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

Для того, чтобы поменять нагрузку дуги, подведите указатель мыши к дуге. Нажатие левой клавиши мыши увеличивает нагрузку дуги, нажатие правой клавиши - уменьшает. Нагрузка не может быть равной 0.

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

 

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

Для того, чтобы поменять маркировку позиции, подведите указатель мыши к нужной точке экрана. Нажатие левой клавиши увеличивает значение маркировки, нажатие правой клавиши - уменьшает. Маркировка не может быть меньше нуля.

Когда процесс функционирования сети (моделирования) не запущен, в этом режиме редактируется начальная маркировка сети, в противном случае - текущая маркировка.

Установка позиции

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

 

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

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

 

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

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

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

Для удаления выделенных элементов сети используйте подпункт Удалить пункта Редактор главного меню окна редактирования.