ИЗВЕСТИЯ РАН. ТЕОРИЯ И СИСТЕМЫ УПРАВЛЕНИЯ, 2015, № 2, с. 56-67
УПРАВЛЕНИЕ В СТОХАСТИЧЕСКИХ СИСТЕМАХ ^^^^^^ И В УСЛОВИЯХ НЕОПРЕДЕЛЕННОСТИ
УДК 681.5
ИНФОРМАЦИОННО-УПРАВЛЯЮЩИЙ АЛГОРИТМ СИСТЕМЫ МАССОВОГО ОБСЛУЖИВАНИЯ, ОСНОВАННЫЙ НА ТЕОРИИ СИСТЕМ СО СЛУЧАЙНОЙ СКАЧКООБРАЗНОЙ СТРУКТУРОЙ* © 2015 г. В. А. Болдинов, В. А. Бухалёв, С. П. Прядкин, А. А. Скрынников
Москва, МАИ (национальный исследовательский ун-т), Московский научно-исследовательский телевизионный институт, Радиотехнический институт им. акад. А.Л. Минца, ФГУП "ГосНИИАС" Поступила в редакцию 29.07.14 г., после доработки 27.08.14 г.
Рассматривается задача построения информационно-управляющего алгоритма системы массового обслуживания. Система имеет конечное число состояний, динамика которых описывается условной марковской цепью, и наблюдается с помощью индикаторов, работающих с ошибками. Находятся оптимальное и приближенно-оптимальное решения, основанные на теории систем со случайной скачкообразной структурой. В качестве примера рассматривается задача синтеза приближенно-оптимального алгоритма распознавания состояния и управления авианалетами на военный объект, попеременно разрушаемый и восстанавливаемый в ходе боевых действий авиации.
Б01: 10.7868/80002338815010023
Введение. Как показано в [1, 2], анализ и распознавание состояния системы массового обслуживания (СМО) методами теории систем со случайной скачкообразной структурой (ССС) [3—12] обладает следующими достоинствами. По сравнению с теорией массового обслуживания (ТМО) [13—17] теория систем ССС позволяет существенно расширить класс математических моделей, описывающих СМО, распространив его на динамические стохастические системы, фазовые координаты и структура которых представляют собой взаимосвязанные случайные процессы.
Особенно наглядно и очевидно эти процессы проявляются при стохастической оптимизации управления СМО по терминальному критерию, где возникает необходимость решения стохастической двухточечной краевой задачи (СДКЗ) с применением метода динамического программирования Беллмана [18] и баейсовской обработки информации [19].
В терминах теории систем ССС эта задача может быть представлена следующим образом. Состояние дискретной системы ССС — математической модели некоторой СМО — в каждый момент времени к характеризуется вектором [Хк, ], к = 0, п, где Хк — вектор фазовых координат, принадлежащий непрерывному множеству; 8к — скалярный индекс состояния структуры, принадлежащий конечному множеству; Хк и 8к — взаимосвязанные условно-марковские процессы, а вектор состояния [Хк, Бк ] — марковский процесс. Неточная и, в общем случае, неполная информация о состоянии структуры поступает от индикатора, случайный скалярный выходной сигнал которого Ук также принадлежит конечному множеству.
Ставится задача построения алгоритма оптимального распознавания структуры 8к и управления ею по терминальному критерию эффективности на основании показаний индикатора Ук при
всех к = 0, п.
1. Постановка задачи. Динамический объект ССС описывается стохастическим рекуррентным уравнением
Хк+1 = ф к Хк, Бк, Е к), к = 0~п, (1.1)
где к — дискретный момент времени, Хк — случайный ях-мерный вектор фазовых координат объекта; Нк — вектор возмущений — последовательность векторных случайных величин, независи-
* Работа выполнена при финансовой поддержке РФФИ (грант № 13-08-01191а).
мых при разных к, с известной функцией распределения Фк(£,к); фк(-) — вектор известных детерминированных функций своих аргументов; Бк — случайный скаляр состояний структуры объекта. В свою очередь индекс структуры Бк — управляемая условно-марковская цепь с конечным числом состояний, заданная условными вероятностями переходов из состояния Бк в состояние Бк+1 при фиксированных значениях фазовых координат Хк и управления &к:
Як 5+1\хк, *к, 0к) = Р[^к+1 = +Х = хк, Б к = ; © к = 0 к 1. = 1, и,, (1.2)
где ©к = 1, и0 — дискретная случайная скалярная величина — сигнал управления структурой. Известно начальное распределение вероятностей (РВ) у0(х0, 50) общего начального вектора состояния системы (1.1)—(1.2).
Выходной сигнал индикатора структуры Ук — условно-марковская цепь, заданная условными вероятностями переходов из состояния Ук в состояние 7к+1 при фиксированном значении индекса структуры Бк+1:
Пк+1(Ук+1 I Ук, 5к+1) = Р7к+1 = Ук+1 I = У к'; Бк+1 = 5 к+1] 1 Ук = 1, Пу. (1.3)
В (1.1)—(1.3) прописными буквами Хк, Бк, Ек, Ук, ©к обозначены случайные величины, а соответствующими им строчными буквами хк, 5к, 2, к, ук, 0 к — детерминированные переменные. При этом = означает равенство по определению, а Р[] — символ вероятности.
Требуется найти управления ©к, к = 0, и, в классе их детерминированных зависимостей от всех имеющихся наблюдений (управление с обратной связью):
©к =0к (%), ± (71,..., 7к)
где 0к(У0~к) — функция управления, оптимальная в смысле минимума аддитивного показателя качества (показателя эффективности, функционала потерь),
1 = М
^ШХк, Бк, ©к_1)
к=1
где М[-] — символ математического ожидания (МО); Жк(хк, 5к, 0к_1) — текущая функция потерь на к-м шаге.
2. Обозначения. Введем следующие обозначения для условных вероятностных характеристик случайных величин Хк, Бк при фиксированных наблюдениях у^-* или У0_к-!:
" " — символ апостериорной характеристики, например, /к(•) = М[/к(•) | У0-*1;
" " — символ характеристики, прогнозируемой на один шаг дискретности вперед, например, /*(•) = М[/к(•) I У0—1 ];
ук(хк, 5к) и ук(хк, 5к) — апостериорное и прогнозируемое РВ вектора состояний соответственно;
/к(хк\,к) и /к+1(хк+1 | 5к+1) — апостериорная и прогнозируемая условные плотности вероятностей (ПВ) Хк и Хк+1 при фиксированных % +1 соответственно;
рк( 5к) и рк+1( 5к+1) — апостериорная и прогнозируемая вероятности состояний зк и 5к+1 соответственно;
хк( 5к) и хк+1( 5к+1) — апостериорное и прогнозируемое условные МО Хк и Хк+1 при фиксированных % 5к+1 соответственно;
Як( 5к) и Лк+1( 5к+1) — апостериорная и прогнозируемая условные ковариации (ковариационные матрицы — КМ) при фиксированных % +1 соответственно;
6к(хк+1\,к+1, хк, 5к) — ПВ перехода из хк в хк+1 при фиксированных % 5к+1, определяемая формулой
е к (хк+11 Эк+1, хк, 5к) -
= (2п)-Пх Цехр{/ют[фк(5к+1, Хк, Эк, \к) - Хк+1]} йюйФк - (2.1)
- ]*5[фк(э к+1, хк, Эк, ^ к ) хк+1] й Ф к,
где ¡() йФк(2,к) — кратный интеграл Стилтьеса; 8[фк(•) - хк+1] — многомерная дельта-функция Дирака; Т — символ транспонирования;
Р к+1(Ук+1) — прогнозируемая вероятность состояния индикатора ук+1; Ц^к — прогнозируемое МО текущей функции потерь; Jk — функционал оставшихся потерь на отрезке [к, п]; J* — оптимальное значение функционала Jk.
3. Оптимальный алгоритм. Оптимальный информационно-управляющий алгоритм состоит из двух взаимосвязанных блоков: блока обработки информации и блока управления структурой ("регулятора"). Он основан на обобщении метода динамического программирования Беллмана в сочетании с байесовским подходом на класс систем ССС.
Регулятор описывается рекуррентным уравнением с конечным условием, полученным с помощью метода динамического программирования Беллмана [18] применительно к классу систем ССС [8, 10] (см. Приложение):
Jk* = ш1п_[№к(0к_1) + Ял к = птг, J:+l - 0, (3.1)
0к -1 е 1, п0
где Jkk+1 — МО функционала Jk+1(Yk) по случайному аргументу Ук,
= X Jk+l(yk )р к (Ук, 0к-1); (3.2)
Ук
Щ (0к-1) = X ¡^к (хк, Эк, 0 к-1) У к (хк, Эк, 0к-1) йхк, (3.3)
Р к (у к, 0 к-1) = X Пк (Ук1Ук-1, Эк ) ¡У к(хк, Эк, 0 к-1) йхк, (3.4) У к (хк, Эк, 0 к-1) = X ¡8 к-1(хк I Эк, хк-1, Эк-\У1к-1(эк I хк-1, Эк-1, 0 к-1) У к-1(хк-1, Эк-1) йхк-1,
(3.5)
к = 1, п, yо(*о, »o) = YO(XQ, SQ).
Оптимальные функции управления определяются в процессе решения уравнения (3.1) по формуле
ÖtiO^) = arg mmj^k(0к_i) + /*ц], к = ~n. (3.6)
9к -1 e 1, ne
Так как функции Жк(-) и 7*+1, согласно (3.2)—(3.5), выражаются через апостериорные РВ Yк-1(хк_1, »к_1), то в результате получаем управление с обратной связью — детерминированную зависимость 0*_1 от yк_1(хк_1, sk_1), записываемую в память ЭВМ и используемую затем в процессе работы информационно-управляющего алгоритма.
В (3.1)—(3.6) и далее j"() dxk — кратный определенный интеграл по всему евклидову пространству изменения вектора xk, тогда как суммирования выполняются по всем значениям соответствующих дискретнозначных переменных
П Пу
X(•) = X () X(•) = X (•).
»к »к = 1 у к у к = 1
»к-1
Алгоритм обработки информации описывается основанными на байесовской обработке информации [19] применительно к классу систем ССС [5, 10] рекуррентными уравнениями (см. Приложение):
У^ 1 (хк 1 ^ 1 б*) = ПкЭк^к+1(Хк+ь Эк+1' б*) (3 7)
Рк+1(Ук+1, б*)
У к+1(Хк+1, ^к+1, 0*) = X |бк (Хк+1^к+1, Хк, (^к+1|Хк, Sk, 0*)у к (Хк, Зк^Хк, (3.8)
Рк+1(Ук+1, 0*) = Xпк+1(Ук+1|Ук,Эк+1)|ук+1(Хк+1, Зк+1, 0*) dХk+1 (3.9)
с начальным условием у0(х0, з0) = у0(х0, з0). Здесь к = 0, п - 1, а оптимальное управление 0* определяется по (3.6).
Информационно-управляющий алгоритм работает следующим образом: на каждом шаге к = 0, п -1 из памяти ЭВМ извлекается значение 0* {ук(Хк, эк)} ,которое, согласно (3.7)—(3.9), и с учетом показаний индикатора структуры ук+1, ук переводит объект управления из состояния, характеризуемого РВ у*(Хк, эк), в состояние, характеризуемое РВ у*(Хк+1, зк+1).
4. Приближенно-оптимальный алгоритм. Основной недостаток оптимального решения заключается в трудностях программной реализации функциональных рекуррентных уравнений для плотностей вероятностей, связанных с ограничениями по памяти и быстродействию ЭВМ. А вот потенциальное достоинство оптимальных алгоритмов — их точность — в значительной степени утрачивается в силу несоответствия математической модели, используемой при синтезе, и реального явления, а также неточной и неполной априорной и апостериорной информации о параметрах и состоянии системы.
По этим причинам во многих прикладных задачах целесообразно применение приближенно-оптимальных алгоритмов, которые бы практически незначительно уступали оптимальным в точности, но зато существенно превосходили последних в простоте реализации.
В настоящей статье рассматривается два спосо
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.