Известия РАН. Теория и системы управления, 2020, № 4, стр. 18-27

Введение. В настоящей статье приводится динамическая стохастическая система со случайной скачкообразной структурой (ССС) [1–6], имеющей конечное число возможных состояний. Переходы из одного состояния в другое происходят в случайные моменты времени и управляются двумя противоборствующими сторонами (военными противниками, экономическими или политическими конкурентами), преследующими строго противоположные интересы [1, 3]. При этом каждый из противников располагает конечным числом возможных стратегий (управлений) и руководствуется некоторым своим априорным представлением об управляемом объекте и информацией, которую он получает от своего индикатора структуры, регистрирующего с ошибками текущее состояние структуры объекта.

Ставится задача построения алгоритмов управления противников (“игроков”), состоящая в нахождении оптимальных управлений с обратной связью по состоянию объекта в каждый момент времени k в классе детерминированных зависимостей от показаний индикаторов структуры – на отрезке времени от начального момента до текущего k.

Для решения задачи используется теория стохастического динамического программирования на основе метода динамического программирования Беллмана, байесовская обработка информации и марковские математические модели [1, 3, 7–12]. Применение этих методов позволяет построить алгоритмы, сочетающие точность решения с простотой реализации. Их достоинствами являются: обратная связь управлений с состоянием объекта, комплексирование априорной и апостериорной информации о состоянии объекта и рекуррентная форма алгоритмов, не требующая запоминания всей совокупности наблюдений на отрезке времени, который предшествует текущему моменту. Это особенно важно, например, для реализации в системах управления, навигации и наведения летательных аппаратов при существующих ограничениях по памяти в бортовых цифровых вычислительных машинах [13].

1. Постановка задачи. Дано: рассматривается объект ССС, управляемый двумя игроками, которые преследуют строго противоположные интересы. Структура s_k описывается марковской цепью с конечным числом возможных состояний ${{s}_{k}} = \overline {1,{{n}^{{(s)}}}} $ , где k – текущий момент времени: $k = \overline {0,n} $.

Информация, которой располагают игроки о вероятностях переходов из состояния s_k в состояние ${{s}_{{k + 1}}}$, неодинакова:

где ${{\Theta }_{k}}$, ${{\vartheta }_{k}}$ – управления игроков A и B, имеющие конечное число возможных стратегий: Θ_k = $\overline {1,{{n}^{\Theta }}} $, ${{\vartheta }_{k}} = \overline {1,{{n}^{\vartheta }}} $.

Состояние структуры регистрируется индикаторами с ошибками. Измерения состояния структуры описываются условно-марковскими цепями с конечным числом возможных состояний ${{r}_{k}} = \overline {1,{{n}^{r}}} $ и ${{\rho }_{k}} = \overline {1,{{n}^{\rho }}} $. Условно-марковские цепи заданы условными вероятностями переходов из r_k в ${{r}_{{k + 1}}}$ и из ${{\rho }_{k}}$ в ${{\rho }_{{k + 1}}}$ при фиксированных ${{s}_{{k + 1}}}$, ${{\Theta }_{k}}$, ${{\vartheta }_{k}}$:

Зависимость $\pi _{{k + 1}}^{A}( \cdot )$ от ${{\Theta }_{k}}$ означает, что игрок A может управлять как структурой объекта, так и характеристикой индикатора структуры. Зависимость $\pi _{{k + 1}}^{A}( \cdot )$ от ${{\vartheta }_{k}}$ означает, что игрок B может управлять не только структурой объекта s_k, но и осуществлять информационное противодействие игроку A. Аналогичный смысл имеет зависимость $\pi _{{k + 1}}^{B}( \cdot )$ от ${{\vartheta }_{k}}$ и ${{\Theta }_{k}}$.

Так как интересы игроков строго противоположны, то показатели качества (эффективности) игры для обоих аналогичны:

где ${{W}_{k}}( \cdot )$ – текущая функция потерь; ${\text{M}}[ \cdot ]$, ${\text{P}}\left[ \cdot \right]$, $\mathop = \limits^\Delta $ – символы соответственно математического ожидания, вероятности и равенства по определению. При этом полагается, что управления ${{\Theta }_{{k - 1}}}$, ${{\vartheta }_{{k - 1}}}$, как было сказано во Введении, детерминированно зависят от наблюдений $r{{{\kern 1pt} }_{{\overline {0,k - 1} }}}$, $\rho {{{\kern 1pt} }_{{\overline {0,k - 1} }}}$.

Поскольку рассматривается задача игрового управления, в которой показатели эффективности игроков (1.3), (1.4) различны, так как основываются на различной информации – r_k и ρ_k, то для того, чтобы подчеркнуть это обстоятельство, в качестве показателя выбраны суммы условных математических ожиданий текущей функции потерь ${{W}_{k}}\left( {{{s}_{k}},{{\Theta }_{{k - 1}}},{{\vartheta }_{{k - 1}}}} \right)$ при фиксированных наблюдениях $r{{{\kern 1pt} }_{{\overline {0,k - 1} }}}$, $\rho {{{\kern 1pt} }_{{\overline {0,k - 1} }}}$ соответственно.

Как следует из (1.3), (1.4), критерии оптимальности ${{J}^{{A*}}},$  ${{J}^{{B*}}}$ определяются выражениями

т.е. игрок A выбирает оптимальную стратегию на отрезке [0, n – 1], добиваясь минимума показателя качества ${{J}^{A}}( \cdot )$ и предполагая, что его противник будет придерживаться стратегии, максимизирующей этот показатель. Противоположным образом действует игрок B, который максимизирует показатель ${{J}^{B}}( \cdot )$ в расчете на стратегию игрока A, минимизирующую этот показатель.

Априорные сведения о начальных значениях вероятностей состояний структуры, которыми располагают игроки, различны: $p_{0}^{A}({{s}_{0}})$ и $p_{0}^{B}({{s}_{0}})$.

Требуется найти: оптимальные управления $\Theta _{k}^{*}(r{{{\kern 1pt} }_{{\overline {0,k} }}},\rho {{{\kern 1pt} }_{{\overline {0,k} }}})$, $\vartheta _{k}^{*}\left( {r{{{\kern 1pt} }_{{\overline {0,k} }}},\rho {{{\kern 1pt} }_{{\overline {0,k} }}}} \right)$ с обратной связью по состоянию объекта в классе детерминированных зависимостей от наблюдений $r{{{\kern 1pt} }_{{\overline {0,k} }}}$, $\rho {{{\kern 1pt} }_{{\overline {0,k} }}}$.

2. Алгоритм игрока A. 2.1. Регулятор структуры. Найдем уравнения регулятора структуры (блока управления), связывающие оптимальное управление с вероятностью состояния структуры.

С учетом специфики поставленной задачи применим подход, разработанный Р. Беллманом и известный как метод динамического программирования [7]. Его обобщения и модификации широко используются для синтеза оптимальных управлений с обратной связью в стохастических системах [8–11].

Обозначим

где $J_{k}^{A}( \cdot )$ – функция оставшихся потерь – показатель качества на отрезке [k, n], в отличие от показателя качества ${{J}^{A}}( \cdot )$ на отрезке [1, n ] , определяемого формулой (1.3).

Представим $J_{k}^{A}( \cdot )$ в виде суммы двух слагаемых: $W_{k}^{A}( \cdot )$ и оставшейся части суммы из (2.1). Тогда на основании (2.1), (2.2) получаем

Обозначив

и применяя операцию $\mathop {\min }\limits_{\Theta {{{\kern 1pt} }_{{\overline {k - 1,n - 1} }}}} \mathop {\max }\limits_{\vartheta {{{\kern 1pt} }_{{\overline {k - 1,n - 1} }}}} $ к обеим частям равенства (2.3), получаем

Формула (2.4) отражает традиционный способ, разработанный Р. Беллманом [7] и используемый всеми авторами, применяющими теорию динамического программирования для оптимизации управления стохастическими системами, например, Р.А. Ховард [8], А.А. Фельдбаум [9], М. Аоки [10], А.Е. Брайсон и Хо Ю Ши [11].

Так как $W_{k}^{A}( \cdot )$ от $\Theta {{{\kern 1pt} }_{{\overline {k,n - 1} }}}$, $\vartheta {{{\kern 1pt} }_{{\overline {k,n - 1} }}}$ не зависит, а

то из (2.4) следует рекуррентное уравнение для $J_{k}^{{A*}}( \cdot )$: где

Аргумент $r{{{\kern 1pt} }_{{\overline {0,k - 1} }}}$ у всех функций здесь и далее опущен для простоты записи. Его наличие обозначено символами “$\widehat {}$”, “$\widetilde {}$” и пр.

Вероятность $\sigma _{k}^{A}({{r}_{k}})$ находится по формуле полной вероятности

а $W_{k}^{A}( \cdot )$, как следует из (2.2), – по формуле где $\tilde {p}_{k}^{A}({{s}_{k}})\mathop = \limits^\Delta {\text{P}}[{{s}_{k}}|r{{{\kern 1pt} }_{{\overline {0,k - 1} }}}]$ – вероятность состояния структуры s_k, прогнозируемая на один шаг дискретности вперед и определяемая по формуле полной вероятности где $\hat {p}_{{k - 1}}^{A}({{s}_{{k - 1}}})\mathop = \limits^\Delta {\text{P}}[{{s}_{{k - 1}}}|r{{{\kern 1pt} }_{{\overline {0,k - 1} }}}]$ – апостериорная вероятность состояния структуры ${{s}_{{k - 1}}}$.

Пара минимаксных управлений, согласно (2.5), (2.8), (2.9), определяется формулой

где $\Theta _{{k - 1}}^{*}$ – оптимальное управление игрока A, a $\vartheta _{{k - 1}}^{A}$ – предполагаемое игроком A оптимальное управление игрока B, основанные на показаниях индикатора структуры $r{{{\kern 1pt} }_{{\overline {0,k - 1} }}}$, принадлежащего игроку A.

Рекуррентные уравнения (2.5)–(2.10) описывают алгоритм регулятора структуры игрока A. Выходными сигналами регулятора являются управления $\Theta _{k}^{*}$, $\vartheta _{k}^{A}$, входным сигналом – апостериорная вероятность $\hat {p}_{k}^{A}({{s}_{k}})$, которая определяется алгоритмом классификатора структуры (в блоке обработки информации).

2.2. Классификатор структуры.  Апостериорная  вероятность состояния структуры $\hat {p}_{k}^{A}({{s}_{k}})$, согласно формуле Байеса, обобщенной на класс ССС [1, 2], и формуле полной вероятности, определяется рекуррентными уравнениями

В целом, оптимальный минимаксный информационно-управляющий алгоритм игрока A описывается замкнутой системой рекуррентных уравнений (2.5)–(2.12), в которой уравнения регулятора (2.5)–(2.10) решаются в “обратном времени” ($k = n,n - 1,\; \ldots ,\;1$) при “начальных” условиях $\tilde {J}_{{n + 1}}^{{A*}} \equiv 0$, а уравнения классификатора (2.11)–(2.12) – в “прямом времени” ($k = 0,1,\; \ldots ,\;n - 1$) при начальных условиях $\tilde {p}_{0}^{A} = p_{0}^{A}({{s}_{0}})$.

3. Алгоритм игрока B. Аналогичный информационно-управляющий максиминный алгоритм игрока B описывается уравнениями (2.5)–(2.12), в которых производятся следующие замены:

индекс “A” $ \to $ индекс “$B$”; ${{r}_{k}} \to {{\rho }_{k}}$; $\Theta _{k}^{*} \to \Theta _{k}^{B}$; $\vartheta _{k}^{A} \to \vartheta _{k}^{*}$, где $\vartheta _{k}^{*}$ и $\Theta _{k}^{B}$ – максиминные управления: $\vartheta _{k}^{*}$ – оптимальное управление игрока B, а $\Theta _{k}^{B}$ – предполагаемое игроком $B$ оптимальное управление его противника A, основанные на показаниях индикатора структуры $\rho {{{\kern 1pt} }_{{\overline {0,k} }}}$, принадлежащего игроку B.

3.1. Регулятор структуры. С учетом выполненных преобразований алгоритм регулятора структуры игрока B будет иметь вид:

где $W_{k}^{B}( \cdot )\mathop = \limits^\Delta W_{k}^{B}(\hat {p}_{{k - 1}}^{B}({{s}_{{k - 1}}}),{{\Theta }_{{k - 1}}},{{\vartheta }_{{k - 1}}})$, $\tilde {J}_{{k + 1}}^{{B*}}( \cdot )\mathop = \limits^\Delta \tilde {J}_{{k + 1}}^{{B*}}(\hat {p}_{{k - 1}}^{B}({{s}_{{k - 1}}}),{{\Theta }_{{k - 1}}},{{\vartheta }_{{k - 1}}})$.

3.2. Классификатор структуры. Алгоритм классификатора структуры игрока $B$ описывается уравнениями:

4. Пример. Рассмотрим задачу оптимизации управления ССС объекта с двумя состояниями как частный случай общей постановки задачи из разд. 1.

Дано: структура объекта, индикаторы структуры и критерии оптимальности описываются следующими выражениями:

1) для игрока A:

2) для игрока B:

где ${{W}_{k}}( \cdot )$ – текущая функция потерь: где $\delta ({{s}_{k}},1)$ – символ Кронекера; $\lambda = {\text{const}}$, $\mu = {\text{const}}$, $\lambda \in (0,1)$, $\mu \in (0,1)$.

Вероятностью перехода ${{q}_{k}}$ управляет игрок A, а вероятностью ${{g}_{k}}$ – игрок B.

Согласно (2.2), (2.8), (4.7),

откуда следует содержательный смысл критериев оптимальности (4.3), (4.6): игрок A минимизирует вероятность первого состояния структуры, ограничивая свои усилия по переводу структуры из первого состояния во второе и предполагая, что противник будет максимизировать эту вероятность; игрок B максимизирует ту же самую вероятность, предполагая, что игрок A будет ее минимизировать. При этом игрок B также старается ограничить свои усилия по переводу структуры из второго состояния в первое (так как $max( - \mu {{g}_{{k - 1}}}) = min(\mu {{g}_{{k - 1}}})$). Весовые коэффициенты $\lambda $ и $\mu $ характеризуют приоритетность соответствующих частных показателей в общем показателе качества.

Как видно из (4.1), каждый из игроков располагает двумя возможными режимами управления: “экономный” – ${{q}_{{min}}}$, ${{g}_{{min}}}$ и “энергичный” – ${{q}_{{max}}}$, ${{g}_{{max}}}$.

Требуется найти: оптимальные алгоритмы управления игроков в виде детерминированных зависимостей от показаний их индикаторов структуры $r{{{\kern 1pt} }_{{\overline {0,k} }}}$ и $\rho {{{\kern 1pt} }_{{\overline {0,k} }}}$.

Решение. Синтез оптимальных информационно-управляющих алгоритмов игроков A и B осуществляется методом игрового оптимального управления системами ССС.

Информационно-управляющий алгоритм игрока A.

Алгоритм управления игрока A состоит из регулятора и классификатора структуры.

Регулятор структуры игрока A. На основании (2.9), (4.8) получаем

где

Будем искать решение уравнения (2.5) в виде

где $\psi _{k}^{A}$, $m_{k}^{A}$ – неопределенные параметры.

Из (2.6), (2.9), (4.10), (4.11) следует

Оптимальные значения ${{q}_{{k - 1}}}$, ${{g}_{{k - 1}}}$, согласно (2.10), (4.9)–(4.11), определяются формулой

где

Из (4.13), (4.14) следует

Подставив (4.11)–(4.13) в (2.5), получаем

где

Приравнивая коэффициенты при $\hat {p}_{{k - 1}}^{A}(1)$ в левой и правой частях уравнения (4.17), получаем рекуррентное уравнение для ψ_k:

откуда следует и с учетом (4.14), (4.18) получаем рекуррентное уравнение для $\varepsilon _{k}^{A}\mathop = \limits^\Delta \lambda {\text{/}}\lambda _{k}^{A} = \mu {\text{/}}\mu _{k}^{A}$:

Пороговые значения $\lambda _{k}^{A}$, $\mu _{k}^{A}$ вычисляются по формулам

Учитывая, что $\hat {p}_{k}^{A}(2) = 1 - \hat {p}_{k}^{A}(1)$, алгоритм (4.16) удобно записать в виде

Алгоритм регулятора игрока A изображен на рис. 1.

Классификатор структуры игрока A. Апостериорные вероятности $\hat {p}_{k}^{A}(1)$, $\hat {p}_{k}^{A}(2)$ вычисляются в классификаторе структуры, уравнения которого (2.11), (2.12) принимают вид

Информационно-управляющий алгоритм игрока B. Алгоритм описывается уравнениями, подобными уравнениям алгоритма игрока A, в которых произведены изменения, соответствующие замене минимакса на максимин:

Физический смысл полученных оптимальных регуляторов структуры: если вероятность состояния структуры, нежелательного для игрока (s_k = 1 – для игрока A и ${{s}_{k}} = 2$ – для игрока B), превышает некоторый порог ($\lambda _{k}^{*}$ – для игрока A и $\mu _{k}^{*}$ – для игрока B), то включается “энергичный” режим управления (${{q}_{{max}}}$ – для игрока A и ${{g}_{{max}}}$ – для игрока B), повышающий вероятность перехода в желаемое для данного игрока состояние структуры (${{s}_{k}} = 2$ – для игрока A и ${{s}_{k}} = 1$ – для игрока B).

Если же вероятность нежелательного состояния структуры меньше указанного порога, то включается “экономный” режим управления, при котором вероятность переходов минимальна (${{q}_{{min}}}$ – для игрока A и ${{g}_{{min}}}$ – для игрока B).

Кроме оптимальных управлений $q_{k}^{*}$ и $g_{k}^{*}$ каждый игрок определяет предполагаемое оптимальное управление своего противника ($\hat {g}_{k}^{A}$ или $\hat {q}_{k}^{B}$) на основании показаний своего индикатора структуры ($r{{{\kern 1pt} }_{{\overline {0,k} }}}$ или $\rho {{{\kern 1pt} }_{{\overline {0,k} }}}$). Эти оценки необходимы в качестве входных данных для классификаторов структуры.

Приближенно-оптимальные регуляторы структуры. Полученные алгоритмы можно существенно упростить, если в уравнениях (4.19), (4.25) приближенно заменить $q_{k}^{*}$, $\hat {q}_{k}^{B}$, $g_{k}^{*}$, $\hat {g}_{k}^{A}$ их некоторыми средневзвешенными значениями:

где ${{\tilde {\lambda }}_{k}} = \lambda {\text{/}}{{\varepsilon }_{k}}$, ${{\tilde {\mu }}_{k}} = \mu {\text{/}}{{\varepsilon }_{k}}$.

Подставив (4.27) в (4.19), (4.25), получаем рекуррентное уравнение

В установившемся режиме из (4.28) следует

Как видно из (4.28)–(4.30), приближенные пороговые значения ${{\tilde {\lambda }}_{k}}$, ${{\tilde {\mu }}_{k}}$ вычисляются на основании только априорных данных и не зависят от показаний индикаторов структуры, что значительно упрощает практическую реализацию алгоритмов.

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

Рассмотренная задача представляет собой игру с неполной информацией и ненулевой суммой и не имеет седловой точки вследствие различной информированности игроков о результатах игры. Прежде всего это объясняется различными показаниями индикаторов структуры ${{r}_{k}} \ne {{\rho }_{k}}$, откуда следует $\hat {p}_{k}^{A}({{s}_{k}}) \ne \hat {p}_{k}^{B}({{s}_{k}})$, $\Theta _{k}^{*} \ne \Theta _{k}^{B}$, $\vartheta _{k}^{*} \ne \vartheta _{k}^{A}$. Поэтому седловая точка игры отсутствует даже в том случае, когда противники располагают одинаковой априорной информацией (${{q}^{A}}( \cdot ) = {{q}^{B}}( \cdot )$, $\tilde {p}_{0}^{A}({{s}_{0}}) = \tilde {p}_{0}^{B}({{s}_{0}})$), а текущая функция потерь ${{W}_{k}}( \cdot )$ сепарабельна относительно управлений игроков q_k, g_k.