20. Агрегативный подход

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

Определение 2.1   Агрегатом называется следующая математическая модель:
\begin{displaymath}{A~~=~~\Bigl\{~~T~,~~Z~,~~X~,~~\Gamma~,~~Y~, ~~H ~,~~G ~~\Bigr\},~~}\end{displaymath} (2)

где $T=[0,T_f] \subset R$ -- интервал моделирования (обычно конечный) Z -- множество состояний (фазовое пространство), $z=(z_1,z_2,\ldots,z_l),$ где $z_1,\ldots z_l$ -- фазовые координаты. $\{z(t)\}$ -- фазовые траектории $\{ z(0)\}$ -- множество начальных состояний X -- множество входных сигналов ( $x=[x^{(1)},\ldots,x^{(l)}],$ где l - число "входных контактов", каждый из которых принимает сигналы своего типа). Моменты прихода входных сигналов определяются через временную последовательность $\{t_j\}, t_j\in T$. Последовательность событий $<t_j, x_j>, x_j\in X$ называется последовательностью приема входных сигналов $\Gamma$ - множество управляющих (особенных) сигналов ( $g=[g^{(1)},\ldots,g^{(r)}],$ где r - число "особенных входных контактов") Моменты прихода управляющих сигналов определяются через временную последовательность $\{\tau_i\},$ $\tau_i\in T$. Последовательность событий $<\tau_i, g_i>, g_i\in \Gamma$ называется последовательностью приема управляющих сигналов Y -- множество выходных сигналов. Моменты выдачи выходных сигналов определяются через временную последовательность $\{\xi_k\}, \xi_k\in T$, в которой каждый элемент $\xi_k$ соответствует моменту пересечения фазовой траектории z(t) границы некоторого множеcтва из системы множеств $\{Z_y\}$, определенной на пространстве состояний Z заданием набора предикатов над Z. Последовательность событий $<\xi_k, y_k>, y_i\in Y$ называется последовательностью выдачи выходных сигналов $H = \{ V_x, V_g,V_{gx}, W, U \}$ - оператор переходов, который определяет текущее состояние по предистории: z(t) = H[z(0),t]. Vx, Vg, Vgx -- операторы формирования новых начальных условий при приеме очередного входного, управляющего сигналов и одновременного их приема соответственно (Vg формирует новое поведение, Vx формирует только новые значения параметров); W -- оператор формирования новых начальных условий (как и Vx, только значений параметров) в момент выдачи выходного сигнала; U -- оператор поведения на временных интервалах между событиями $G = G_{?} \cup G_{!}$ -- оператор выходов, G? -- оператор проверки условия выдачи выходного сигнала, G! -- генератор выходного сигнала: y(t) = G[z(0),t]

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

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

Замечание 2.2   Определение 2.2.1 описывает более узкий класс динамических систем, чем определение 2.1.1, в нем текущее состояние определяется не последовательностью внешних сигналов, а последним управляющим и последним входным (выходным) сигналом.

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

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

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


Среди агрегатов выделяются некоторые подклассы, для которых возможно более простое решение задачи моделирования. Классификация агрегатов определяется по виду оператора U. Непример, кусочно-линейным агрегатом называется агрегат у которого пространство cостояний Z определенным образом структурировано 2 и оператор U линейный. К типичным примерам кусочно-линейных агрегатов можно отнести вероятностный автомат, математическую модель системы массового обслуживания или систему ОДУ, представленную конечно-разностными уравнениями.


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


Другой формализм описания поведения непрерывно-дискретных систем был предложен В.М.Глушковым в 1973 году ([3]) и реализован в системе моделирования НЕДИС. Формализм включает в себя математическую модель непрерывно-дискретной системы, язык спецификации, а также набор процедур и функций реализации моделирующего алгоритма. В противоположность агрегативному подходу, моделирующий алгоритм В.М.Глушкова базируется на дискретном событийном подходе к моделированию сложных систем.

Определение 2.3   Непрерывно-дискретной системой называется следующая математическая модель:
\begin{displaymath}{S~~=~~\Bigl\{~~T~,~~P~,~~e~,~~E~,~~K~,~~F~~\Bigr\},~~}\end{displaymath} (3)

где $T = \{t_i\}, t_i\in R_{\geq 0}$ -- дискретная модель времени P -- множество классов процессов e -- множество классов событий (причин мгновенной смены поведения и структуры системы) E -- множество алгоритмов классов событий (подготовительных дискретных действий при переходе к новому поведению системы). К элементарным действиям относятся пассивизация, активизация, порождение и уничтожение процессов, изменение значений переменных процесса и запись в календарь планирования событий отметки о будущем событии $K = \{ <t_i,e_i>,~L \}$ -- календарь планирования событий, в который записываются отметки о событиях отдельными объектами и с помощью которого описывается динамика системы. Планирование события подразумевает явное задание момента его наступления или задание условия L его наступления через предикат (планирование события по условию) F -- список уравнений, характеризующих локальные поведения процессов во временных интервалах между событиями Структура процесса и его поведение описывается следующей математической моделью:
\begin{displaymath}{P~~=~~\Bigl\{~~X~,~~Y~,~~V_s~,~~V_d~,~~B~~\Bigr\},~~}\end{displaymath} (4)

где X, Y -- каналы входа и выхода Vs -- множество статических переменных процесса, которые задаются алгебраическими выражениями и могут меняться только при исполнении алгоритмов событий Vd -- множество "переменных-функций" - динамических переменных, которые задаются дифференциальными уравнениями из множества F B -- тело процесса, содержащее описания его всевозможных поведений

Замечание 2.3   Изменение значений переменных-функций является механизмом смены поведения объекта и системы в целом. Порождение и удаление процессов соответствует динамическому созданию и удалению экземпляров классов и является механизмом смены структуры системы.

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

Теорема 2.1   Непрерывно-дискретная модель В.М.Глушкова представима А-комплексом с моделью каналов связей типа "кажный с каждым".

Действительно, можно представить процесс непрерывно-дискретной системы В.М.Глушкова агрегатом:

\begin{displaymath}{A_P~~=~~\Bigl\{~~T~,~~Z~,~~X~,~~\Gamma~,~~Y~, ~~H ~,~~G ~~\Bigr\},~~}\end{displaymath} (5)


в котором $T\subseteq R_{\geq 0}$ -- дискретная модель времени расширяется до непрерывной $Z = V^{(P)}_s \cap V^{(P)}_d$ -- фазовое пространство суть область значений переменных процесса P $X = e_1\subset e$ -- множество входных сигналов суть подмножество событий непрерывно-дискретной модели, алгоритмы которых E(e1) содержат операции изменения значений переменных Vs данного процесса $\Gamma = e_2\cap e_{Init},~e_2\subset e$ -- множество управляющих сигналов суть подмножество событий непрерывно-дискретной модели, алгоритмы которых E(e2) содержат операции смены поведения и структуры (активизация, пассивизация, порождение, удаление, присвоение значений переменным Vd) данного процесса, плюс сигнал eInit, соответствующий событию начального запуска системы, в алгоритм которого входит инициализация переменных всех процессов, и в частности данного (для динамически порождаемого процесса определим например $E_{Init}=\{ Z:=0 \}$) $Y = e(L) \subset e$ -- множество выходных сигналов суть подмножество событий непрерывно-дискретной модели, планируемых по условию, для которых в L входят переменные данного процесса. Список этих условий определяет разбиение фазового пространства Z на систему подмножеств $\{Z_y\}$. $H = \{V_x, V_g, W, U\}$ -- оператор глобального поведения процесса P, в котором $V_x=\{E(e_1)\}, V_g=\{E(e_2)\}$ -- алгоритмы событий множеств e1 и e2 соответственно; $W =\{E(e_L)\}$ -- алгоритмы событий множества eL; $U = F^{(P)} (V^{(P)}_d) \cap F_{Idle}$ -- все возможные локальные поведения процесса P из списка F плюс дополнительно введенная функция FIdle, описывающая "никакое" поведение процесса до запуска, после удаления или в период его пассивности в непрерывно-дискретной модели (например, можно определить $F_{Idle} = \{Z=const\}$). $G = G_{?} \cap G_{!}$ -- оператор выходов, в котором G? есть оператор проверки условий L(P), G! -- генератор выдачи сигналов типа активизации, пассивизации и пр. для других процессов. Фактически, оператор Gчастично выполняет функции процесса-монитора в непрерывно-дискретной модели В.М.Глушкова. Всю непрерывно-дискретную систему можно представить А-комплексом с моделью каналов связей типа "кажный с каждым", в котором число агрегатов соответствует максимальному числу процессов с учетом порождаемых во время функционирования. Из данного построения видно, что множества входных, выходных и управляющих сигналов агрегата включают в себя описание всех возможных классов событий, приводящих к смене поведения и структуры непрерывно-дискретной системы и событие начального запуска и не содержат никаких других сигналов. Это означает, что каждому событию некоторого процесса непрерывно-дискретной системы соответствует единственное особое состояние соответствующего агрегата, и, следовательно, каждой цепочке событий непрерывно-дискретной системы соответствует единственная последовательность особых состояний, порождаемая А-комплексом, и никаких других последовательностей не порождается. Таким образом, непрерывно-дискретная система может быть описана в терминах агрегативного направления, хотя, очевидно, при переходе от модели В.М.Глушкова к агрегативной системе теряется наглядность описания динамики системы, так как возможность динамического изменения структуры системы заменяется на фиксированную структуру системы с максимальным числом элементов.

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

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

Обратное утверждение получить также просто.

Теорема 2.2   Произвольная агреративная система может быть описана в терминах непрерывно-дискретной модели.

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

Замечание 2.6   Здесь имеется ввиду формальная эквивалентность математичаских моделей, но не систем моделирования, использующих эти модели в качестве вычислительных моделей. Действительно, систему НЕДИС и любую систему моделирования агрегативного направления нельзя считать эквивалентными из-за разницы в используемых методах моделирования локальных поведений исследуемой системы. Несмотря на присутствие в агрегаливном направлении определения агрегата общего вида 2.2.1, в вычислительных системах моделирования этого направления используются конечно-разностные методы (и фактически только класс кусочно-линейных агрегатов); в этом смысле система В.М.Глушкова применима для более широкого класса непрерывно-дискретных систем.

Гибрибное направление исследования непрерывно-дискретных систем возникло в начале 90-х годов на базе современной методологии спецификации и верификации сложных дискретных систем и систем реального времени, разработанной в теории теактивных систем ([10], [11]). Основатели гибридного направления (А.Пнуэли, Д.Харел), вводя в базовую дискретную модель реактивной системы некоторые характеристики непрерывного поведения, определяют таким образом новый класс сложных систем, который они называют "гибридной реактивной системой" ([7], [8] ). До 1992 года основной акцент в этом направлении был сделан на проблемах спецификации (построения компактного представления математической модели) непрерывно-дискретных систем в рамках дискретного подхода и аксиоматического доказательства некоторых качественных поведенческих свойств. С появлением метода символьной верификации для систем реального времени ([9]), появилась надежда автоматизировать верификацию гибридных систем. В 1995-96 году создана система HyTech автоматической верификации гибридных систем, основанная на символьной верификации ([12]). Исследование поведения гибридной системы сводится к статическому качественному анализу поведенческих свойств, без использования поточечного численного моделирования глобального поведения системы.

Определение 2.4   Гибридной системой называется следующая конструкция:
\begin{displaymath}{H~~=~~\Bigl\{~~S~,~~X~,~~E~,~~F~, ~~\phi ~~,~~\psi ~~,~~\lambda ~~\Bigr\},~~}\end{displaymath} (6)

где S -- конечное множество локаций X -- конечное множество вещественных переменных E -- конечное множество дуг. Дуга есть кортеж $e = < s, a, \phi_е, \lambda^{(s')}, s'> \in E$, $s,s'\in S$ - исходная и целевая локации для дуги e, $a\in \Sigma, \Sigma$ - алфавит меток переходов (алфавит событий) $\phi$ - множество предикатов над X, описывающих условия перехода по дугам E $\lambda$ - множество начальных значений переменных множества X для каждой локации F -- оператор локального поведения внутри каждой локации (система дифф. включений, дифф. уравнений или аналитических функций) $\psi$ -- множество предикатов над X, описывающих область значений переменных Х в локациях $s\in S$ (инвариант в s)

Cостоянием гибридной системы называется вектор значений переменных $x\in X$, к которому для удобства иногда приписывается локация $s\in S$, к которой этот вектор относится (т.е.для которой $\phi_s(x) = True$). Поэтому часто состоянием гибридной системы называется пара $<s,x>, s \in S,x\in X$.

Определение 2.5   Математической моделью, описывающей поведение гибридной системы, является система переходов:
\begin{displaymath}{\Sigma~~=~~~~\Bigl\{~~T~,~~Q~,~Q_0~~,~Q_F~~,~~\to~~\Bigr\},~~}\end{displaymath} (7)

где $T=\{t_i\}$ -- бесконечная упорядоченная несходящаяся временная последовательность Q -- пространство состояний (в смысле определения состояния гибридной системы), Q0, QF -- множество начальных и конечных состояний, определяемых специальными предикатами над X "$\to$" -- отношение перехода между состояниями, которое определяется двумя правилами:


$\bullet~~$ дискретный переход при фиксированном времени (становится возможным как только $\phi(X_0)=True$)

${<s_0, a, \phi, v, s_1>~\in~E,~~~~\phi(X_0)=Т,~~~~X_1\in \lambda^{(s)}(X_0)}\over {<s_0, X_0>~ \rightarrow^a~ <s_1, X_1>}$
$\bullet~~$временной переход - увеличение времени внутри локации с преобразованием непрерывных переменных (время относительное)

${X_1=F_s(X_0, t),~~~~ \forall~ t', ~0 \leq t' \leq t, \psi_s(~F_s(X_0, t')~)}\over {<s , X_0>~ \rightarrow^t~ <s , X_1>}$

Моделирование глобального поведения системы переходов заключается в построении множества вычислений -- бесконечных цепочек пар <si, ti>, таких что: 1) $s_0 \in Q_0, t_0 = 0$ 2) $\forall~ i\geq 0,~s_i\rightarrow^{t_i}s_i, и \exists a~:~s_i\rightarrow^{a}s_{i+1}$Следующая теорема отражает тот факт, что гибридная система общего вида может быть интерпретирована как агрегат:

Теорема 2.3   Математическая модель гибридной системы эквивалентна модели агрегата.

Действительно, система переходов $\Sigma$ гибридной системы

\begin{displaymath}{H~~=~~\Bigl\{~~S~,~~X~,~~E~,~~F~, ~~\phi ~~,~~\psi ~~,~~\lambda ~~\Bigr\},~~}\end{displaymath} (8)


может быть представлена агрегатом

\begin{displaymath}{A^*~~=~~\Bigl\{~~T^*~,~~Z^*~,~~X^*~,~~\Gamma^*~,~~Y^*~, ~~H^*~,~~G^*~~\Bigr\},~~}\end{displaymath} (9)


в котором $T^* = [ 0; \infty )$ -- модель времени расширяется до непрерывной Z* = X -- фазовым пространством является область значений вещественных переменных системы H, $z=(x_1,x_2,\ldots,x_l)\in Z,$ фазовые координаты суть переменные системы H. $\{z(0)\}^* = Q_0$-- множество начальных состояний $X^* = \{X_0\}$ -- множество входных сигналов вырождается в единственный сигнал запуска агрегата (который инициализирует случайным образом некоторое начальное состояние из Q0) $\Gamma^* = 0$ -- управляющие сигналы отсутствуют Y* = (y1,y2) -- выходными сигналами являются вектора с компонентами $y_1\in S, y_2\in T$ ( компоненты элементов сценариев гибридной системы) $H^* = \{W, U\}$ -- оператор переходов, в котором W -- оператор, описывающий преобразование вектора переменных при дискретном переходе по дуге (в момент выдачи выходного сигнала), соответствует оператору инициализации $\lambda$ гибридной системы: $z(t+0) = \lambda_{z(t)}$ U -- функция, описывающая непрерывные изменения в интервалах между моментами выдачи выходных сигналов (то есть в некоторой локации $s\in S$), соответствует F: $z(t) = F_s [z(t_i+0),t], t\in [t_i,t_{i+1})$ $G = G_{?} \cup G_{!}$, где G? -- оператор проверки принадлежности z(t) некоторому множеству из семейства $\{Z_y\}$. Разбиение Z на подмножества Zy эквивалентно введению предикатов $\phi,\psi$ гибридной системы H и разбиению пространства состояний на локации S, G! -- генератор выходного сигнала. Способ разбиения пространства состояний на семейство $\{Z_y\}$и соответствующее множество выходных сигналов определяет взаимно однозначное соответствие между начальной точкой в вычислении гибридной системы и особым состоянием агрегата, соответствующем приему сигнала запуска системы, и между каждой другой точкой в вычислении гибридной системы и особым состоянием, определяемым выдачей соответствующего выходного сигнала. Таким образом, из данного построения видно, что множество последовательностей особых состояний, порождаемых агрегатом, и множество вычислений габрадной системы эквивалентны.

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

Замечание 2.8   Определение инициализации $\lambda$ в виде интервала $\lambda = [\alpha,\beta]$ может быть представлено как введение вероятности в систему -- значение x(t*+0) после перехода является случайной величиной с равновероятным законом распределения в интервале $[\alpha,\beta]$. Однако, в большой степени использование вероятности в гибридных системах отсутствует.

Как и в агрегатативном, так и в гибридном направлении выделяются отдельные классы гибридных систем. Так, например, линейной гибридной системой называется такая гибридная система в которой используются только линейные предикаты и у которой все локальные поведения F могут быть описаны линейными уравнениями (например, F : X=X0 + A t). Именно для этого класса гибридных систем применимы основные результаты символьного подхода теории реактивных систем. Можно установить соответствие между классом линейных гибридных систем и классом кусочно-линейных агрегатов.


Теоремы 2.2.1, 2.2.2, 2.2.3 позволяют утверждать, что представленные выше математические модели описывают (с учетом замечаний 2.2.6, 2.2.7, 2.2.8) один и тот же класс сложных систем и демонстрируют различные подходы к моделированию и анализу сложных систем, поведение которых укладывается в схему, изображенную на рис.1. Во всех подходах предлагаемые модели рассматриваются как расширение базовой (непрерывной или дискретной) модели, поэтому поведение непрерывно-дискретной системы представляется в них с разных точек зрения и с разными, иногда противоположными, акцентами. Любой подход имеет свои ограничения в реализации, которые сведены в таблицу 1, и, следовательно, применим для моделирования и анализа только некоторых подклассов непрерывно-дискретных систем. Нам кажется наиболее выразительным и информативным определением для этого класса систем является определение событийно-управляемой иерархической динамической системой переменной структуры ([15]):

Определение 2.6 (элемент системы)   Элементом событийно-управляемой иерархической системы переменной структуры называется совокупность базовых понятий:
\begin{displaymath}{E~~=~~\Bigl\{~~T~,~~Z~,~~X~,~~Y~,~~F~, ~~e~,~~Act ~~\Bigr\},~~}\end{displaymath} (10)

где $T = t_d: N\to R_{\geq 0}$ -- последовательность временных отсчетов $Z = D_1\times\ldots\times D_n$ -- множество значений переменных состояний X -- множество входных переменных (каналов входа) Y -- множество выходных переменных (каналов выхода) F -- множество допустимых локальных поведений e -- множество причин смены поведения (событий) Act -- множество допустимых дискретных операций

Определение 2.7 (рекурсивное определение)   Событийно-управляемой иерархической системой переменной структуры называется пара:
\begin{displaymath}{S~~=~~\Bigl\{~~Time~,~~\Sigma~~\Bigr\},~~}\end{displaymath} (11)

где $Time=R_{\geq 0}$ -- модель времени $\Sigma$ -- модель объекта,являющегося: (i) элементом (ii) элементом, в котором хотя бы одно локальное поведение заменено на $\Sigma$ (iii) параллельной композицией объектов $\Sigma$ с определенной на ней моделью каналов связей
Last modified: Tuesday, 24 July 2012, 11:49 PM