Учебно-материальное обеспечение. 1. Наглядные пособия: Слайды: Формирующий фильтр для марковского случайного процесса

1. Наглядные пособия: Слайды: Формирующий фильтр для марковского случайного процесса. Алгоритм фильтрации Калмана применительно к УЦМ. Алгоритм оптимального управления ЦМ

2. ТСО: ___ Лектор – 2000._______________________________________

3. Приложения: _____ Раздаточный материал.________________________

Введение.

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

Вопрос №1. Общие понятия управляемых цепей Маркова.

Пусть дискретному множеству состояний стохастического объекта управления в дискретные моменты времени соответствует конечное множество решений (управлений) u_i(k) U={1,…,s,…S}. Простейшей моделью, описывающей вероятностно-временной механизм изменения дискретных по состояниям и времени управляемых случайных последовательностей, является управляемая цепь Маркова. Цепь задается вектором вероятностей начальных состояний процесса P (0)={ p_i (0) }, матрицей одношаговых переходных вероятностей P ^u(k/k-1) = {p ^u_ij(k/k-1)}, а также периодом смены состояния марковской цепи (t_k-t_k-1=T). Дискретное состояние объекта управления в любой k-й момент времени, при марковской природе происходящих в нем процессов, определяется состоянием объекта на предыдущем шаге, матрицей вероятностей перехода и диффузионными свойствами шума возбуждения (случайным значением дискретного приращения, компенсирующего нецелочисленную часть прогноза состояния).

Для однородной управляемой марковской цепи вероятность принятия ею i-го состояния на k-м шаге определяется следующей рекуррентным уравнением Маркова:

P_i(k) = , i,j=1,…,I, , (1)

где

.

Здесь вектор начальных вероятностей определяет значения вероятностей принятия процессом x(0) состояния i в нулевой момент времени, при этом если процесс в момент k-1 принял состояние x(k-1) = i, то одношаговая вероятность перехода p_ij(k/k-1) определяет вероятность принятия процессом на следующем шаге k состояния j.

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

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

.

Определим пошаговые вектора вероятностей состояния МЦ, используя уравнения Маркова и Колмогорова-Чепмена.

.

Вначале определяем одношаговые матрицы перехода:

Затем определяем пошаговые вектора вероятностей состояний ЦМ:

Из анализа результатов следует, что значения компонент пошаговых векторов вероятностей достаточно быстро устанавливаются стремясь к так называемым «финальным» вероятностям. Это основное свойство однородных цепей Маркова.

Вопрос№2. Управляемые цепи Маркова с доходами. Функция Беллмана.

Если объект управления в момент времени k находится в состоянии i и при этом было принято решение (управление) u, то он получает доход r_i ^u(k).

В некоторых задачах вместо вектора доходов r^u={r_i^u} задается матрица доходов (потерь) r ^u={r_ij^u}, элементы которой определяются не только с учетом состояния i в котором оказался объект в момент времени k, но и состояния j, в которое объект перейдет на следующем шаге.

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

В случае конечного времени управления k={1,…,K} оптимальная стратегия является марковской, т.е. зависит лишь от состояния x_i(k), в котором находится объект в момент времени принятия решения, а также от значения целевой функции R_i(k,u). Для управляемых цепей Маркова априорное пошаговое значение среднего риска-функции Беллмана , соответствующей k-му шагу и i-му состоянию процесса, определяется следующим прямым рекуррентным соотношением:

R_i(k, ) = (2)

при начальных условиях: .

Для случая задания матрицы доходов задача сводится к задаче с векторными доходами путем усреднения доходов на k-м шаге по строке матрицы с весами, равными вероятностям появления соответствующих номеров состояния УМЦ.

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

Рассмотрим применение трех основных методов решения поставленной задачи: итерационного алгоритма Ховарда; алгоритма линейного программирования и алгоритма динамического программирования.

Итерационный алгоритм Ховарда.

Пусть U-множество стратегий управления . При этом -вектор управлений, i-й элемент которого является решением, принимаемым в состоянии i в момент k. Процесс смены состояний цепи определяется в основном матрицей одношаговых переходов P (k/k-1)= p^u_ij(k/k-1), а результатом перехода цепи в состояние j на следующем k-м шаге под воздействием управления служит доход, который получает цепь находясь в этом состоянии r^u_i. Все доходы объединены в вектор доходов , а средний суммарный за бесконечное время доход является ограниченным и имеет вид:

где -коэффициент переоценки доходов, принимающий значение из интервала (0…1);

матрица одношаговых переходных вероятностей, при этом P^d(0)= I;

I -единичная матрица размера .

Итерационный алгоритм включает следующие этапы:

1. Определение начального вектора управлений и вектора доходов.

На этом этапе выбирают произвольный вектор управлений для i-х начальных состояний цепи и определяют соответствующие им установившиеся значения доходов

.

2. Оценка возможностей улучшения решения

На данном этапе, используя полученные ранее значения доходов R_i(u_i=s), i=1,…,I, ищут наличие такого элемента u_i= множества U, для которого выполняется условие:

Если такое управление найдено, то оно считается доминирующим для состояния i, если условие не выполнено, то возвращаемся к шагу 1. Затем аналогичные операции выполняются для других состояний цепи.

Алгоритм линейного программирования.

Сформулируем задачу отыскания оптимальных управлений состояниями марковской цепи как задачу линейного программирования. Введем понятие суммарного среднего дохода:

где первый член в выражении -векторный доход, получаемый цепью на нулевом шаге при условии принятия стратегии управления d(1), а P(0)= I- единичная матрица размера I*I.

Далее введем начальное распределение состояний цепи {p₁(0),…,p_i(0),…,p_I(0)} и совместную вероятность принятия решения u_i=s,если процесс находится в состоянии i в момент времени k:

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

x_j^s= .

Тогда стандартная задача линейного программирования имеет вид:

,

при ограничениях

В качестве начальной стратегии обычно выбирают стратегию, обеспечивающую максимум r_i^s по всем состояниям цепи.

Частным случаем решения этой ЗЛП является стационарная стратегия, которая каждому i-му состоянию цепи ставит в соответствие одну переменную x_j^s, а следовательно одно управляющее воздействие u_j^s.

Двойственная к предыдущей задача имеет вид

при ограничениях

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

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

-процесс обнаружения сигнала на входе приемника;

-процесс поступления заявок пользователя на услуги сети связи;

-процесс управления маршрутами прохождения сообщений (пакетов);

-процесс управления алгоритмами обработки сигналов и алгоритмами множественного доступа в сетях связи;

-процесс управления резервами сетей связи.

Пример решения задачи оптимизации стратегии управления ремонтом ПЭВМ на основе УМЦ.

Пусть с периодичностью один час проводится анализ технического состояния ПЭВМ и принимается решение о необходимости ее ремонта. Если машина на k-м шаге находится в исправном состоянии, то доход от ее работы составляет 3 у.е. При этом ремонт не проводится, а вероятность остаться ПЭВМ в работоспособном (первом) состоянии на следующем шаге равна 0,7, а вероятность перейти в неработоспособном состоянии равна 0,3.

Если машина отказала (второе состояние) на k-м шаге, то ее можно отремонтировать двумя способами: ускоренным и обычным. Ускоренный ремонт требует затрат в 2 у.е. и обеспечивает переход в первое состояние с вероятностью 0,6. Второй, обычный способ требует затрат 1 у.е. и обеспечивает переход в состояние 1 с вероятностью 0,4. Таким образом, для первого состояния ПЭВМ имеется один вариант управления - ремонта не проводить , а во втором состоянии ПЭВМ возможных управлений два: проводить ускоренный ремонт, либо - обычный .

Аппроксимация описанного процесса УМЦ позволяет задать ее в следующем виде:

Вектор вероятностей начальных состояний

Матрицы одношаговых переходных вероятностей для различных векторов управлений:

Период смены состояния: УМЦ T_c=1 час;

Множество возможных вариантов векторов управлений на каждом шаге:

Вектора доходов на k-м шаге при принятом на k-1-м шаге векторе управлений имеют вид:

= ;

.

1. Вначале найдем решение итерационным алгоритмом.

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

R₁=1380/91, R₂=880/91.

На втором этапе улучшения решения получаем:

r₂²+ ,

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

Применяя вновь процедуру определения доходов, найдем

R₁=1110/73; R₂=710/73,

что дает оптимальную стационарную стратегию

Среднее значение дохода цепи при равновероятных состояниях составляет:

R = [0,5; 0,5] =910/73.

B. Проведем теперь поиск решения алгоритмом линейного программирования. Для начального распределения вероятностей состояний цепи P(0)=(0,5;0,5) и заданных исходных данных:

получаем следующую задачу линейного программирования:

max [3x₁¹-x₂¹-x₂²],

при ограничениях

0,37 x₁¹-0,54 x₂¹-0,36 x₂² =0,5,

-0,27 x₁¹ +0,64 x₁¹ +0,46 x₂² =0,5,

x₁¹ , x₂¹ , x₂² 0,

для которой оптимальное решение имеет вид:

x₁¹=410/73, x₂² =320/73, x₂¹ =0,

а целевая функция равна

3. Используем метод динамического программирования Беллмана для определения оптимальной стратегии управления состоянием УМЦ на интервале двух шагов от начального состояния.

Шаг № 1. Перепишем выражение (2) в векторном виде:

, (2а)

R(0)=0.

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

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

Это означает, что при нахождении ПЭВМ в первом (исправном) состоянии на нулевом шаге ремонт не проводится, а при втором (неисправном) состоянии ПЭВМ предпочтение следует отдавать обычному способу ее ремонта.

Шаг № 2. В отличие от первого шага, прогноз максимального значения вектора доходов на втором шаге осуществляется с учетом управлений, допустимых на первом шаге и принятых на нулевом шаге, т.е. уже для четырех возможных ситуаций (стратегий управления):

Как видно из поэлементного сравнения векторов доходов, максимальным из них является доход, полученный при реализации стратегии управления d₄, которая и является оптимальной на двух начальных шагах работы ПЭВМ.

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

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

Вопрос №3. УЦМ с зашумленными наблюдениями за их состоянием.

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

Постановка задачи оптимизации управляемой цепи Маркова в этих условиях изменяется следующим образом. Имеется система уравнений состояния и наблюдения, описывающая вероятностно-временные изменения случайных параметров объекта управления и условия наблюдения за их состоянием:

x(k+1)= C^T(k+1) (3)

где строка возможных состояний процесса x(k);

i=1,…,I- номер состояния дискретного процесса, для которого выполняется условие (4);

-специальные индикаторы состояния моделируемых последовательностей.

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

где (k+1,k)= = матрица вероятностей перехода процесса из одного состояния в другое на соседних шагах;

Q(k+1,k, матрица интенсивностей перехода процесса ;

диагональные члены матрицы интенсивностей;

T_с – период смены состояний цепи;

I – единичная матрица соответствующей размерности;

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

G(k)= diag -матрица диффузии процесса x(k);

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

матрица спектральных плотностей мощности процесса ;

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

Порядок определения вектора компенсирующих последовательностей в выражении (6.) подробно рассмотрен в работе[ ].

Наряду с уравнениями состояния (3-6) полная математическая модель случайного процесса обычно содержит уравнение наблюдения за его состоянием следующего вида:

-процесс наблюдения за процессом x(k);

H(k)- матрица наблюдения, элементы которой определяют способ преобразования измерений в значения процесса x(k);

вектор непрерывнозначных гауссовских последовательностей (шумов наблюдения) со средним, равным нулю и ковариационной матрицей M ;

матрица спектральных плотностей мощности процесса .

Апостериорное пошаговое значение критерия оптимальности-функции Беллмана при этом становится условным по наблюдениям за состоянием объекта управления и имеет следующий вид:

R(k, )= при начальных условиях

R(0,x(0)=i)= 0.

Следует отметить, что знак математического ожидания в критерии оптимальности (среднем доходе) означает усреднение значения целевой

функции как по значениям переменных состояния объекта управления, так и по значениям наблюдений за ними z(k).

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

-этап стохастического оптимального оценивания состояния объекта управления;

-этап оптимизации детерминированных управляющих воздействий (решений) на основе полученных на первом этапе оценочных значений переменных состояния объекта.

Этап стохастической оценки состояния объекта управления может быть выполнен на основе алгоритмов оценивания (интерполяции, фильтрации, экстраполяции), оптимальных в смысле минимума среднеквадратической ошибки оценивания (МСКО).

Можно показать [ ], что для случая принятой модели состояния и наблюдения (3-7) текущая оценка состояния процесса x (k) может быть найдена на основе рекуррентного алгоритма Калмана, обеспечивающего непосредственную оценку его стохастических индикаторов:

, (8)

откуда непосредственно следует и оценка состояния обьекта

где оценки процесса и стохастических индикаторов его состояния на k+1-м шаге;

-предсказанное значение оценки вектора индикаторов на k+1-й шаг;

измерение, предсказанное на основе прежней оценки на k+1- й шаг;

-матрица коэффициентов усиления фильтра Калмана;

-невязка измерения значения процесса x(k).

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

где R(k+1)- ковариационная матрица шумов наблюдения;

ковариационная матрица (дисперсий) ошибок оценивания, определяемая следующим выражением:

(10.)-ковариационная матрица оценки с начальным условием = .

Для установившегося режима работы фильтра выражения (8,9,10.) принимают вид:

K=P₂H^TR^-1;(11.)

P^*= P P₂P^T+ GVG^T;(12.)

P₂()= ,(12б.)

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

С учетом полученных оценочных значений параметров состояния объекта выражение (7) для критерия оптимальности может быть записано в виде:

R =

при начальных условиях

R(0, (0))= 0.

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

u^опт = ()^T.

Вопрос № 4. Матричные игры на основе УЦМ.

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

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

Пусть в игре принимают участие спутниковая линия связи и система радиоподавления вероятного противника. Пусть заданы множества допустимых управлений как со стороны линии связи {u(k)} , так и со стороны радиоподавления {v(k)} , а также соответствующая каждому i-му состоянию первого игрока платежная матрица-матрица средних одношаговых доходов . Кроме того, вероятностно-временные изменения состояния линии связи x(k) описываются управляемой марковской цепью следующего вида:

Указанные исходные данные позволяют сформулировать следующие три игровые задачи:

A. Задача поиска чистых стратегий игры {u_s(k);v_r(k)} с использованием незашумленного канала наблюдения за состоянием линии связи x(k)=i.

Используя критерий среднего байесовского риска в форме функции Беллмана и опираясь на теорему о минимаксе [ ], найдем решение игры (в чистых стратегиях) следующего вида:

,

R_i(0)=0,

где -оптимальные для случая игры в «чистых» стратегиях решения относительно управлений в линии связи и в системе радиоподавления соответственно.

Поиск оптимального решения начинается с решения максиминной части задачи, где осуществляется выбор r-й стратегии противника, соответствующей минимальному элементу матрицы доходов линии связи. Соответствующий этому элементу столбец матрицы доходов определяет область поиска управления u_s(k), максимизирующего доход линии в условиях воздействия v_r(k). Затем решается минимаксная часть задачи, где вначале выбирается s-я стратегия линии связи, максимизирующая доход в ней, а затем в рамках строки матрицы, соответствующей стратегии u_s(k), ищется стратегия противника v_r(k), минимизирующая доход . Если при найденных из решения обоих частей задачи стратегиях управления оказываются выполненными условия равенства значений максимина и минимакса целевой функции, то они являются решением данной игры в чистых стратегиях. Если равенство не достигнуто, то решение игры ищут в смешанных стратегиях.

B. Задача поиска смешанных стратегий игры с использованием незашумленного канала наблюдения за состоянием линии.

В отличие от предыдущей задачи здесь выбор стратегий управления как со стороны линии связи, так и со стороны подавления осуществляется с некоторыми вероятностями соответственно. При этом если для i-го состояния первого игрока один из элементов его вектора вероятностей управлений равен единице , а все остальные его элементы равны нулю, это означает выбор чистой стратегии u_s.

Критерий оптимальности выбора вероятностных (рандомизированных) стратегий в данном случае имеет следующий вид:

,

R_i(0)=0,

где оптимальные для случая смешанных стратегий вектора вероятностей применения стратегий управления со стороны линии связи {u_s (k)} и радиоподавления {v_r (k)} соответственно.

Как следует из теоремы о минимаксе для седловой точки верхняя и нижняя цены игры равны среднему доходу линии связи на k-м шаге, т.е.

.

C. Задача поиска смешанных стратегий игры при зашумленном канале наблюдения за состоянием линии связи.

Данный случай требует дополнительного задания уравнений состояния и наблюдения для УЦМ (для переменной x(k)), а также использованием в качестве критерия оптимальности апостериорного байесовского риска [ ]. Использование в этой ситуации принципа разделения [ ] обеспечивает переход к оценочным значениям переменных состояния в критерии оптимальности, что позволяет записать его в следующем виде:

,

R_i(0)=0,

где оценка состояния линии связи, являющаяся условным по наблюдениям z(k) средним и определяемая соотношением (8);

оптимальные для случая смешанных стратегий вектора вероятностей применения стратегий управления со стороны линии связи {u_s (k)} и радиоподавления {v_r (k)} соответственно.

Заключение.

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