известия ран. теория и системы управления, 2014, № 3, с. 27-37
УПРАВЛЕНИЕ В СТОХАСТИЧЕСКИХ СИСТЕМАХ И В УСЛОВИЯХ НЕОПРЕДЕЛЕННОСТИ
удк 681.5
АЛГОРИТМ РАСПОЗНАВАНИЯ СОСТОЯНИЯ СИСТЕМЫ МАССОВОГО ОБСЛУЖИВАНИЯ, ОСНОВАННЫЙ НА ТЕОРИИ СИСТЕМ СО СЛУЧАЙНОЙ СКАЧКООБРАЗНОЙ СТРУКТУРОЙ* © 2014 г. В. А. Болдинов, В. А. Бухалев, А. А. Скрынников
Москва, МАИ (национальный исследовательский ун-т), Московский научно-исследовательский телевизионный институт, ФГУП "ГосНИИАС" Поступила в редакцию 06.11.13 г., после доработки 24.12.13 г.
Рассматривается задача построения алгоритма распознавания состояния системы массового обслуживания на основании неточных наблюдений. Система имеет конечное число состояний, динамика которых описывается условной марковской цепью. Находятся оптимальное и приближенно-оптимальное решения, базирующиеся на теории систем со случайной скачкообразной структурой. В примере с использованием предложенного подхода получен алгоритм приближенно-оптимального распознавания состояния военного объекта, попеременно разрушаемого и восстанавливаемого в ходе боевых действий.
Б01: 10.7868/80002338814030032
Введение. Как показано в [1], исследование систем массового обслуживания (СМО) методами теории систем со случайной скачкообразной структурой (ССС) [2—9] обладает следующими достоинствами. По сравнению с теорией массового обслуживания (ТМО) [10—14] теория систем ССС позволяет существенно расширить класс математических моделей, описывающих СМО, а именно распространить его на динамические стохастические системы с условно-марковской нестационарной структурой.
Вероятностные аналитические алгоритмы исследования СМО, основанные на теории систем ССС, значительно превосходят статистические алгоритмы имитационного моделирования по оперативности, требованиям к электронно-вычислительным машинам, быстродействию и ком-плексированию с реальной аппаратурой. Особенно сильно эти преимущества проявляются в задачах синтеза алгоритмов обработки информации в СМО и других системах со случайной структурой [3—5, 7, 9, 15—19], где ТМО и имитационное моделирование малоэффективны. Одной из таких задач является построение алгоритма распознавания состояния СМО на основании неточных наблюдений.
В терминах теории систем ССС эта задача может быть представлена следующим образом. Состояние дискретной системы ССС — математической модели некоторой СМО — в каждый момент времени к характеризуется вектором [Хк, к = 0, 1, 2, ..., где Хк — вектор фазовых координат, принадлежащий непрерывному или счетному множеству; 8к — скалярный индекс состояния структуры, принадлежащий конечному множеству. Вектор Хк и скаляр 8к — случайные процессы, связанные между собой стохастически или функционально. При этом эволюция вектора [Хк, ^к] представляет собой марковский случайный процесс, однако процессы Хк и Бк, рассматриваемые в отдельности, марковскими не являются. Это обусловлено тем, что состояние одной из компонент вектора [Хк, ^к] в дискретный момент времени к + 1 зависит не только от ее состояния в предыдущий момент времени к, но и от состояния другой компоненты в момент времени к, т.е. эволюция компонент вектора [Хк, ^к] является условно-марковским процессом.
Имеется индикатор структуры, случайный скалярный выходной сигнал которого Ук, также принадлежащий некоторому конечному множеству, дает неточную и, в общем случае, неполную информацию о состоянии структуры объекта Sk. Ставится задача построения алгоритма оптимального распознавания структуры 8к на основании показаний индикатора Ук на отрезке [0, к].
* Работа выполнена при финансовой поддержке РФФИ (грант № 13-08-01191а).
1. Постановка задачи. Динамический объект ССС описывается стохастическим рекуррентным уравнением
Xk+1 = tyk (Sk+1, Xk, Sk, "k), (1.1)
где к — дискретный момент времени, к = 0, 1, 2, ...; Xk — случайный «¿.-мерный вектор фазовых координат объекта; Ек — вектор возмущений — последовательность векторных случайных величин, независимых при разных к, с известной функцией распределения Ф^^), которая служит общим описанием как для непрерывных распределений, например гауссовского, так и для дискретных, например распределения Бернулли; ф^-) — вектор известных детерминированных функций своих аргументов; Sk — случайный скаляр состояний структуры объекта — индекс структуры.
Индекс структуры Sk — условно-марковская цепь с конечным числом состояний, заданная условными вероятностями переходов из состояния sk в состояние sk +1 при фиксированном значении xk:
qk (sk+ll Xk ' Sk) = PSk+1 = Sk+1|Xk = Xk ' Sk = Sk ]' Sk = 1> ns- (1.2)
Выходной сигнал индикатора структуры Yk — условно-марковская цепь, заданная условными вероятностями переходов из состояния yk в состояние yk +1 при фиксированном значении sk +1:
nk+l(Vk+11 Уь sk+1) = pYk+1 = yk+1 Yk = yk, Sk+1 = sk+1]. yk = l ny. (1.3)
В (1.1)—(1.3.) большими буквами Xk, Sk, Sk, Yk обозначены случайные величины, а соответствующими им малыми буквами xk, sk, £,k, yk — детерминированные переменные; = означает равенство по определению; P[] — символ вероятности.
Распределение вероятностей (РВ) уk(xk, sk) представляет собой при фиксированном sk плотность вероятности непрерывнозначного случайного вектора Xk, а при фиксированном xk — ряд распределения вероятностей целочисленной (дискретнозначной) случайной величины Sk.
Известно начальное РВ вектора состояний у0(x0, s0). Требуется найти апостериорные вероятностные характеристики, основанные на наблюдениях y^ = (y0, y1,..., yk): текущее (в момент к) РВ, плотность вероятности (ПВ) фазовых координат, вероятности состояний структуры, математическое ожидание (МО) и корреляционную матрицу (КМ) (ковариацию) ошибки оценивания вектора фазовых координат.
2. Обозначения. Введем следующие обозначения для условных вероятностных характеристик случайных величин Xk, Sk при фиксированных наблюдениях y-^:
Y k (xk, sk) — апостериорное РВ вектора состояния;
Y k+1(xk+1, sk+1) — прогнозируемое на один шаг дискретности РВ вектора состояния;
6k(xk+1|sk+1, xk, sk) — ПВ перехода вектора фазовых координат из состояния xk в состояние xk +1 при фиксированных состояниях структуры sk +1, sk;
fk (xk |sk) — условная апостериорная ПВ вектора фазовых координат при фиксированном sk;
fk (xk+1|sk+1) — условная прогнозируемая ПВ вектора фазовых координат при фиксированном sk+1;
fk (xk) — апостериорная ПВ;
Pk (sk) — апостериорная вероятность состояния структуры sk;
Pk+1(sk+1) — прогнозируемая вероятность состояния структуры sk +1;
sk — оптимальная по критерию максимума апостериорной вероятности апостериорная оценка состояния структуры;
Pk+1(yk+1) — условная вероятность состояния индикатора yk +1 при фиксированных y^;
xk (sk) — условное апостериорное МО вектора Xk при фиксированном sk;
xk+1(sk+1) — условное прогнозируемое МО вектора Xk +1 при фиксированном sk +1;
xk — апостериорное МО вектора Xk;
Rk(sk) — условная апостериорная КМ вектора Xk при фиксированном sk;
Як+1($к+1) — условная прогнозируемая КМ вектора Хк при фиксированном зк + Як — апостериорная КМ вектора Хк.
3. Оптимальный алгоритм. Распределение ук+1(хк+1,5к+1) — апостериорное распределение вектора Хк + ь 8к + х при фиксированных наблюдениях у-ок+ ^ (УокУк+1):
У к+1(хк+1, +1) = У к+1(хк+1, ^к+11 у0к+1) = У к+1(хк+1, як+1Ук+1, уок ). Поэтому на основании формулы Байеса [20] запишем равенство
Уk+l(Xk+l, sk+l) -
Уk+1(xk+1,sk+llyo,k)P[Yk+l - yk+l|Xk+l - xk+1,Sk+1 - Sk+l, Yo>k - yo,k]
PYk+1 - yk+1\Y~k - y~k]
Применив формулу полной вероятности и формулы умножения вероятностей [20], запишем зависимость прогнозируемого распределения у k+1(xk+1, sk+1| yo"k ) на к + 1 шаге от апостериорного Y k (Xk, Sk\yo,k ) на к шаге:
Уk+1(xk+1, Sk+1) = I JSk(xk+1|sk+1, Xk, sk, y0k) X
Sk
x P[Sk+1 = Sk+1|Xk = Xk, Sk = Sk,Yok = yokk J'Y k (Xk, Skboîkk )dXkP-
Здесь и далее j*() dXk — кратный определенный интеграл по всему евклидовому пространству M " изменения вектора хк, а
"s
I (•) = I (•)■
sk sk=1
Используя марковское свойство векторных случайных процессов (Хк, Sk), Yk и обозначения, приведенные в разд. 2, окончательно получаем алгоритм:
г. /„ „ ч nk+1(Fk+1\yk,Sk+1)y k+1(Xk+1,sk+1) /т
yk-nCXk+b Sk+1) =-:—1-:-, (31)
Pk+1(yk+1)
Уk+1(Xk+1, sk+1) = I I 6k(Xk+11 Sk+1, Xk, sk) qk(sk+1|Xk, sk) Yk(Xk, sk) dXk,
k (3.2)
Y o(Xo, So) = Y o(Xo, So).
Нормировочный коэффициент pk+1(yk+1) в (3.1) находится по формуле полной вероятности
Pk+1(yk+1) = I nk+1(yk+l|Уk, sk+l)Jyk+l(Xk+1, sk+l) dXk+l. (3.3)
sk+l
Как показано в [1], ПВ s k() определяется либо формулой
S k (Xk+l|Sk+l, Xk, Sk) = (2n)-"X ||exp{/®T[9k fo+l, Xk, sb % k) - Xk+l]} d® d Ф k (% k), (3^4)
либо эквивалентной ей формулой
6k(Xk+l|Sk+1, Xk, Sk) = |S[9k(SkXk,Sk, %k) - Xk+l] d<MU) M
в зависимости от конкретного вида функций 9k(-), Фk(t,k), где |() dФk(tkk) — кратный интеграл
Стилтьеса, ô[9k(•) - Xk+1] — многомерная дельта-функция Дирака, T — символ транспонирования.
Система функциональных рекуррентных уравнений (3.1)—(3.5) является основой для байесовского алгоритма оптимального распознавания и оценивания состояния системы в любой момент времени по совокупности показаний индикатора структуры на интервале [0, к].
Алгоритм построен по двухэтапной схеме "прогноз—коррекция". На этапе прогноза вычисляется прогнозируемое РВ, связывающее у k+l(Xk+1, Sk+1) с апостериорным у k (Xk, Sk ), а на этапе кор-
рекции вычисляется апостериорное РВ ук+1(хк+1, 3к+1), связывающее его с прогнозируемым у к+1(хк+1,3к+1), с учетом корректирующих показаний индикатора структуры ук +
Зная у к (хк, 3к) можно найти и другие вероятностные характеристики вектора состояния, например:
Рк (¿к) = |у к (Хк, ) Лхк, ¡к (Хк ) = X у к (Хк, ¿к ),
ук — а^тах рк (¿к), (3.6)
3к = 1, «3
хк — ]"хк!к (хк) ^хк,
Кк — !(хк - хк )(хк - хк)Т /к (хк) Лхк.
Формулы (3.1)—(3.6) дают оптимальное решение задачи в рамках представленной математической модели. Однако неизбежное в практических задачах несоответствие математической модели и реального явления, а также ошибки индикаторов структуры зачастую делают нецелесообразным применение оптимальных алгоритмов.
Неплохим компромиссо
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.