УДК 656.2:519 | (РГУПС) |
ПРОГНОЗИРОВАНИЕ ПОВЕДЕНИЯ ЖЕЛЕЗНОДОРОЖНЫХ СИСТЕМ НА ОСНОВЕ ПАРАЛЛЕЛЬНОГО АНАЛИЗА ДЕРЕВА ДОСТИЖИМОСТИ МОДЕЛИРУЮЩЕЙ СЕТИ ПЕТРИ
Введение
Сети Петри (СП), описанные в [1] и в [2], являются инструментом для математического моделирования и исследования сложных систем, состоящих из множества взаимодействующих друг с другом компонентов. Наибольшее применение сети Петри нашли в области разработки аппаратного и программного обеспечения параллельных распределённых систем. Однако они могут быть весьма полезными во многих других областях, в частности, в области прогнозирования и планирования эффективной работы железнодорожных систем. Под железнодорожными системами здесь понимаются железнодорожные станции, узлы или участки. При этом наиболее подходящим представляется метод анализа моделирующих СП на основе дерева достижимости СП, которое описывает, в частности, множество всех достижимых состояний системы из заданного начального состояния.
Даже незначительное увеличение размера СП приводит к существенному увеличению размера её дерева достижимости. Это означает, что с ростом размера СП значительно возрастают вычислительные расходы по памяти (необходимой для хранения дерева достижимости), а также по времени анализа дерева достижимости. Достаточно детализированные модели железнодорожных систем в виде СП характеризуются большим размером. Поэтому задача распараллеливания анализа дерева достижимости таких СП является актуальной.
В этой статье показывается, как можно моделировать сетями Петри железнодорожные системы, и какие их свойства можно прогнозировать на основе дерева достижимости моделирующей СП. Описывается алгоритм построения дерева достижимости СП и излагаются принципы распараллеливания процесса его анализа.
1. Основные понятия сетей Петри
Пусть мультимножество ¾ это множество, допускающее вхождение произвольного числа экземпляров (в том числе и 0) одного и того же элемента (в [1] используется термин комплект).
Сеть Петри N является четверкой N=(P, Т,I,O), где
· P={p1, p2,...,pn} — конечное множество позиций, n³0;
· T={t1, t2,...,tm} — конечное множество переходов, m³0;
· I: T ® P* — входная функция, сопоставляющая переходу мультимножество позиций;
· О: T ® P* — выходная функция, сопоставляющая переходу мультимножество позиций.
Графы сетей Петри. Наиболее наглядным представлением СП является её графическое представление, которое представляет собой двудольный, ориентированный мультиграф [1]. Граф СП обладает двумя типами узлов: кружок O, представляющий позицию СП; и планка ¾, представляющая переход СП (здесь используется прямоугольник). Ориентированные дуги этого графа (стрелки) соединяют переход с его входными и выходными позициями. При этом дуги направлены от входных позиций к переходу и от перехода к выходным позициям.
Маркировка — это размещение по позициям СП фишек, изображаемых на графе СП точками. Маркировка m сети Петри N=(P, T,I, О) есть функция, отображающая множество позиций P в множество неотрицательных целых чисел Nat. Маркировка m может быть также определена, как n-вектор m=<m(p1),m(p2),…,m(pn)>, где n=êPê и m(pi) – количество фишек в позиции pi, для всех 1£i£n.
СП выполняется посредством запусков переходов. Запуск перехода возможен, если он разрешен, т. е. если каждая из его входных позиций содержит число фишек не меньшее, чем число дуг, ведущих из этой позиции в переход.
Пусть функции ^#: P´T®Nat и #^: T´ P ®Nat, задающие кратность входных и выходных дуг перехода сответственно. Для произвольных позиций pÎP и перехода tÎТ значение ^#(p,t) совпадает с кратностью дуги, ведущей из p в t, если такая дуга существует, и с нулём, в противном случае. Значение #^(t,p) совпадает с кратностью дуги, ведущей из t в p, если такая дуга существует, и с нулём, в противном случае.
Запуск разрешённого перехода tÎT из каждой своей входной позиции pÎI(t) удаляет ^#(p,t) фишек, а в каждую свою выходную позицию p’ÎO(t) добавляет #^(t,p’) фишек. Переход t в сети Петри с маркировкой m может быть запущен всякий раз, когда он разрешен и в результате запуска перехода t образуется новая маркировка m', определяемая, как m'(p)= m(p) – ^#(p,t) + #^(t,p), для всех pÎP. Такая маркировка m' называется непосредственно достижимой из маркировки m. Если m' получается из µ последовательным запуском нескольких разрешённых переходов, то m' называется достижимой из m маркировкой.
2. Моделирование работы железнодорожных систем на примере железнодорожной станции
Пусть система «железнодорожная станция» (ЖС) включает в себя конечное число N приёмо-отправочных путей. В неё с северного и южного (чётного и нечётного) направлений могут прибывать поезда, а также – отправляться по этим же направлениям. Прибывший поезд может быть принят на один из свободных путей.
Для построения модели системы ЖС в виде сети Петри выделим в ней следующие условия:
· поезд прибывает с северного направления (обозначим это условие через Сin);
· поезд прибывает с южного направления (Юin);
· поезд отправился в с северном направлении (Сout);
· поезд отправился в южном направлении (Юout);
· на k-том (где 1£k£N) пути находится поезд (Пk);
· на k-том пути нет поезда (НПk).
С этой же целью в системе ЖС выделим следующие события:
· поезд, прибывший с северного направления, принимается на k-й путь (СПk);
· поезд, прибывший с южного направления, принимается на k-й путь (ЮПk);
· поезд отправляется с k-го пути в северном направлении (ОСk);
· поезд отправляется с k-го пути в южном направлении (ОЮk).
В таблице 1 определяются пред - и постусловия этих событий.
Таблица 1
Пред - и постусловия событий для системы ЖС
Событие | Предусловия | Постусловия |
СПk ЮПk ОСk ОЮk | Сin, НПk Юin, НПk Пk Пk | Пk Пk Сout Юout |
Сеть Петри, моделирующая систему ЖС, представлена на рис. 1. В этой сети частичная маркировка соответствует состоянию системы ЖС, в котором по одному поезду прибывает с северного и южного направлений, в северном направлении отправился поезд, первый путь свободен, а N-й путь занят.
Рис. 1. Сеть Петри, моделирующая железнодорожной станции ЖС
Детализация и уточнение моделирующей сети Петри для системы ЖС может быть продолжена.
3. Анализ сетей Петри, моделирующих железнодорожные системы
Моделирование систем сетями Петри, прежде всего, обусловлено необходимостью проведения глубокого исследования их поведения. Для проведения такого исследования необходимы методы анализа свойств самих сетей Петри. Этот подход предполагает сведения исследования свойств реальной системы к анализу определённых свойств моделирующей СП. Здесь приведём только некоторые свойства СП и продемонстрируем их практическое значение для железнодорожных систем.
Необходимо отметить, что все эти свойства анализируются относительно начального состояния системы, задаваемого начальной маркировкой СП. Таким образом, одна и та же модель железнодорожной системы в виде СП может быть использована для исследования её поведения при различных начальных условиях, отражающих, например, различные количества и расположение находящихся в ней поездов.
3.1. Свойства
Ограниченность. Пусть k – неотрицательное целое число.
Позиция pÎP сети Петри N=(P,Т,I,O) c начальной маркировкой m является k-ограниченной, если m’(p)£k для любой достижимой маркировки m’ÎR(N,m). Позиция называется ограниченной, если она является k-ограниченной для некоторого целого значения k. Сеть Петри ограниченна, если все ее позиции ограниченны. Свойство ограниченности позиций моделирующей СП для участковой станции может гарантировать, в частности, что на этой станции количество составов, ожидающих локомотивы для отправки, не превышает заданной границы.
Безопасность. Позиция pÎP сети Петри N=(P,Т,I,O) c начальной маркировкой m является безопасной, если она является 1-ограниченной. Сеть Петри безопасна, если безопасны все позиции сети. Свойство безопасности определённых позиций моделирующей СП может гарантировать свойства железнодорожной системы такого типа, как, например, следующее свойство. На одном пути станции или на одном блокучастке участка дороги никогда не оказывается более одного поезда одновременно.
Сохранение. Сеть Петри N=(P,Т,I,O) с начальной маркировкой m является сохраняющей, если для любой достижимой маркировки m’ÎR(N,m) справедливо следующее: 
m’(p) = m(p). Свойство сохранения позволяет устанавливать, что количество некоторого ресурса остаётся постоянным в системе во время её функционирования, например, количество локомотивов на участке их оборота. Это свойство может также рассматриваться по отношению только к некоторому подмножеству множества P.
Достижимость. Для заданной сети Петри с маркировкой m и маркировкой m’ требуется определить: достижима ли m’ в сети N из начальной маркировки m, т. е. справедливость m’ÎR(N,m). На основе решения этой задачи для СП, моделирующей работу железнодорожной системы, можно, в частности, устанавливать, достижимо ли заданное нежелательное или аварийное состояние в этой системе.
Эквивалентность. Сеть Петри N=(P,Т,I,O) с начальной маркировкой m и сеть Петри N’=(P`,Т`,I`,O`) с начальной маркировкой m` эквивалентны, если справедливо R(N,m)=R(N`,m`).
Сети Петри присуще некоторое поведение, которое определяется множеством её достижимых маркировок или множеством её возможных последовательностей запусков переходов. Интересной с практической точки зрения является задача оптимизации (изменения) сети Петри без изменения её поведения. Изменение означает, в частности, удаление пассивных переходов (которые никогда нельзя запустить), или пассивных позиций (которые никогда не могут быть маркированы). Оптимизация может состоять, в частности, в увеличении параллелизма, что для моделируемой железнодорожной системы может означать увеличение её пропускной способности. Для железнодорожных систем такая оптимизация также может приводить к более эффективному использованию ресурсов системы, к уменьшению расходов по её эксплуатации.
Метод дерева достижимости, вообще говоря, позволяет устанавливать более сложные соотношения между элементами маркировки СП, описывающие различные взаимозависимости количеств ресурсов (вагонов локомотивов и составов), находящихся в различных частях железнодорожной системы.
3.2. Дерево достижимости сети Петри
Один из основных методов анализа СП основан на использовании дерева достижимости [1, 2], представляющего все достижимые маркировки и все возможные последовательности запусков переходов.
При построении дерева достижимости для обозначения бесконечного множества значений маркировки позиции используется символ w. Так же используются следующие ниже операции над w, определяемые для любого постоянного a.
w - а = w; w + а = w; а < w; w £ w.
Алгоритм построения дерева достижимости. Каждая вершина дерева достижимости классифицируется алгоритмом или как граничная вершина, терминальная вершина, дублирующая вершина, или как внутренняя вершина. Алгоритм начинает работу с определения начальной маркировки корнем дерева и граничной вершиной. Один шаг алгоритма состоит в обработке граничной вершины. Пусть х –- граничная вершина, тогда её обработка заключается в следующем:
1. Если в дереве имеется другая вершина y, не являющаяся граничной, и с ней связана та же маркировка, m[x]=m[y], то вершина х становится дублирующей.
2. Если для маркировки m[х] ни один из переходов не разрешен, то x становится терминальной.
3. В противном случае, для всякого перехода tÎT, разрешенного в m[х], создаётся новая вершина z дерева достижимости. Маркировка m[z], связанная с этой вершиной, определяется для каждой позиции pÎP следующим образом:
3.1. Если m[х](p)=w, то m[z](p)=w.
3.2. Если на пути от корневой вершины к x существует вершина y с m[y]<m’ (где m’ – маркировка, непосредственно достижимая из m[х] посредством запуска перехода t) и m[y](p)<m’(p), то m[z](p)=w. (В этом случае последовательность запусков переходов, ведущая из маркировки m[y] в маркировку m’, может неограниченно повторяться и неограниченно увеличивать значение маркировки в позиции p.) В противном случае m[z](p)=m’(p).
4. Строится дуга с пометкой t, направленная от вершины x к вершине z. Вершина х становится внутренней, а вершина z – граничной.
Такая обработка алгоритмом граничных вершин продолжается до тех пор, пока все вершины дерева не станут терминальными, дублирующими или внутренними. Затем алгоритм останавливается.
В качестве примера на рис. 2 изображена маркированная сеть Петри, а на рис. 3 – дерево достижимости.
Рис. 2. Сеть Петри
Рис. 3. Дерево достижимости сети Петри, представленной на рис. 2
На основе метода дерева достижимости, в частности, разрешимы проблемы безопасности и ограниченности, сохранения (существует разрешающий алгоритм) [1, 2]. Если в дереве достижимости СП отсутствует символ w, то свойства достижимости и эквивалентности также разрешимы на его основе. Разрешающие алгоритмы основаны на переборе вершин дерева достижимости.
4. Параллельный анализ дерева достижимости
Изложенный в предыдущем разделе алгоритм построения дерева достижимости СП показывает, что верхней границей числа вершин в дереве достижимости высоты n является величина (|T|n + |T|n-1 + … +|T| + 1) , где |T| ¾ количество переходов СП. Таким образом, даже незначительное увеличение числа переходов в сети приводит к существенному увеличению размера её дерева достижимости. Это в свою очередь означает, что с ростом размера СП значительно возрастают вычислительные расходы по памяти (прежде всего необходимой для хранения маркировок, соответствующих вершинам дерева достижимости), а также по времени анализа дерева достижимости.
Достаточно детализированные модели железнодорожных систем в виде СП характеризуются большим размером. Поэтому задача распараллеливания процесса анализа дерева достижимости таких СП является актуальной. Так как разрешающие алгоритмы свойств СП основаны на простом переборе вершин дерева достижимости, то эти алгоритмы легко распараллеливаются. При этом, как правило, достаточно разбить дерево достижимости на поддеревья примерно одинакового размера и распределить по отдельным процессам, а каждый процесс должен реализовывать применение разрешающего алгоритма к своему поддереву. Основное время взаимодействия таких процессов потребляется при распределении дерева достижимости по процессам.
Параллельный анализ дерева достижимости можно разбить на три этапа:
1. Один из процессов, обозначим его P, строит дерево достижимости и распределяет его по процессам.
2. Каждый процесс анализирует своё поддерево.
3. Процесс P собирает от всех процессов информацию о результатах анализа их поддеревьев и формирует общий результат.
Литература
1. Дж. Питерсон. Теория сетей Петри и моделирование систем.¾ М.: Мир, 1984. – С. 263.
2. Сети Петри. – М.: Наука, 1984. – С. 157.
