Автоматика и телемеханика, № 1, 2023
Стохастические системы
© 2023 г. А.Н. ТАРАСОВ1 (tarrapid@gmail.com),
В.М. АЗАНОВ, канд. физ.-мат. наук (azanov59@gmail.com),
А.И. КИБЗУН2, д-р физ.-мат. наук (kibzun@mail.ru)
(Московский авиационный институт)
ОБ ОДНОЙ ЗАДАЧЕ ОПТИМАЛЬНОГО УДЕРЖАНИЯ
ТРАЕКТОРИЙ ДИСКРЕТНОЙ СТОХАСТИЧЕСКОЙ
СИСТЕМЫ В ТРУБКЕ
Исследуется задача оптимального управления стационарной линейной
стохастической системой с дискретным временем, скалярным неограни-
ченным управлением, аддитивным шумом и критерием вероятности пре-
бывания ее траекторий в заданной окрестности нуля. С использованием
метода динамического программирования и двусторонних оценок функ-
ции Беллмана находится аналитическое выражение оптимального управ-
ления для двух шагов по времени и субоптимального управления для
произвольного горизонта управления. Эффективность найденного управ-
ления проверяется на модельном примере.
Ключевые слова: дискретные системы, стохастическое оптимальное
управление, вероятностный критерий, метод динамического програм-
мирования, функция Беллмана, стационарные системы, неограниченное
управление.
DOI: 10.31857/S0005231023010038, EDN: LUDTND
1. Введение
Исследование задач оптимального управления стохастическими система-
ми с критериями вероятности выполняются с 1960-х гг. для широкого спек-
тра прикладных областей: аэрокосмической [1-5], робототехнической [6-10],
экономической [11-12], биомедицинской [13] и др. [14]. Под критерием ве-
роятности понимается вероятность выполнения некоторых ограничений на
вектор состояния, часто характеризующих точность системы управления [1].
Интерес к таким постановкам вызван практическими требованиями, предъ-
являемыми к системам управления, формализованными в виде вероятност-
ных ограничений [1, 3, 4] и задачами определения множеств стохастической
1 Работа выполнена при финансовой поддержке Российского фонда фундаментальных
исследований в рамках научного проекта №20-31-90056 (Разделы 1, 2, 3, 4.1).
2 Работа выполнена при финансовой поддержке гранта Российского научного фонда
63
достижимости [2, 6-8], жизнеспособности [15] (в англоязычной литературе
stochastic viability) и поглощений [16].
Задачи с критерием максимума вероятности пребывания системы в трубке
траекторий исследовались в [2, 6-10, 13-15, 19-21]. В [6-10, 13-15] исследован
случай дискретного времени, для которого получены условия оптимальности
в форме метода динамического программирования (МДП), на основе которо-
го предложен ряд алгоритмов, позволяющих решить задачу стохастической
достижимости, где сами множества достижимости строятся с помощью ап-
проксимации поверхности уровня функции Беллмана. В [19] для линейной
системы с дискретным временем получены условия логарифмической вогну-
тости функции Беллмана и с использованием “разомкнутого управления”, яв-
ляющегося программным, предложен алгоритм аппроксимации поверхностей
уровня функции Беллмана. В [9, 10] для широкого класса систем предложен
численный метод поиска оптимального управления в классе полиномов, ос-
нованный на сведении исходной задачи к так называемой проблеме моментов
(см., например, [21]). В [21] найдены двусторонние оценки функции Беллмана
и предложен алгоритм поиска субоптимального управления, основанный на
ее нижней границе. Преимущество данного алгоритма заключается в отсут-
ствии необходимости решения уравнения Беллмана, а наличие явного соотно-
шения определения точности субоптимального управления [21] обеспечивает
возможность его практического применения.
В настоящей статье исследуется задача оптимального удержания траекто-
рий линейной системы с дискретным временем, скалярным неограниченным
управлением и случайным шумом в канале управления в заданной окрест-
ности нуля по вероятностному критерию. С использованием [21] находятся
явные выражения для поверхностей уровня 1 и 0 функции Беллмана и дву-
сторонние границы функции Беллмана. С использованием нижних границ
получено аналитическое выражение для субоптимального управления. Пока-
зано, что для траекторий системы, лежащих на поверхностях уровней 1 и 0
функции Беллмана, данное управление является оптимальным. Рассмотрен
пример управления системой второго порядка. Для системы второго поряд-
ка показано, что поверхности уровня 1 и 0 обладают свойствами частичной
стационарности.
2. Постановка задачи
В статье рассматривается задача оптимального управления линейной сто-
хастической системой с дискретным временем и аддитивным случайным шу-
мом
{
xk+1 = Axk + Buk + Cξk,
(1)
k = 0,N,
x0 = X,
где xk ∈ Rn вектор состояния, uk ∈ R скалярное управляющее воздей-
ствие, ξk случайное возмущение со значениями на R, N горизонт управ-
64
ления, A ∈ Rn×n матрица системы, B = (0, . . . , b)T , b ∈ R и C = (0, . . . , c)T ,
c ∈ R.
В качестве критерия рассматривается функционал вероятности
(
)
(2)
Pϕ (u(·)) = P max
∥Λxk+1∥∞ ≤ ϕ
,
k=0,N
где матрица Λ ∈ Rn×n и скаляр ϕ ∈ R представляют собой параметры множе-
ства удержания F = {x ∈ Rn : ∥Λx∥∞ ≤ ϕ}, а ∥x∥∞ = maxi∈1,n |xi| l1-норма
вектора, где x = (x1, . . . , xn)T .
В отношении системы (1) и функционала (2) введем предположения:
1. Известна полная информация о векторе состояния xk; данный факт
позволяет строить управление в классе функций uk = γk (xk), где
γk : Rn → R некоторая измеримая функция;
2. Начальное состояние x0 = X является случайным вектором со значе-
ниями в Rn и с известным распределением PX ;
3. Управлением называется набор функций u (·) = (γ0 (·) , . . . , γN (·))T ∈ U,
классом допустимых управлений называется множество U = U0 × . . . ×
× UN, где Uk множество измеримых функций γk (·);
4. Случайные величины ξk, k = 0, N , имеют распределение с финитной
плотностью вероятности fξk (t), supp [fξk (t)] = [mξ - ǫ; mξ + ǫ], где mξ =
= M[ξk], ǫ > 0, причем fξk (t) симметрична относительно mξ, а компо-
ненты вектора (X, ξ0, . . . , ξN )T независимы;
5. Матрица Λ = diag [λ1, . . . , λn] ∈ Rn×n является диагональной и положи-
тельно определенной, а ϕ > 0.
Рассматривается задача
(3)
Pϕ (u(·)) → max ,
u(·)∈U
физический смысл которой поиск позиционного управления, максимизи-
рующего вероятность пребывания траекторий системы (1) в прямоугольном
параллелепипеде F в течение заданного промежутка времени {1, . . . , N + 1}.
Вопросы оптимального управления с критериями в форме (2) в более об-
щем случае рассмотрены в [21, 23], где, в частности, получены условия опти-
мальности в форме МДП и найдены двусторонние границы функции Беллма-
на, на основе которых предложен способ построения субоптимального управ-
ления. Приведем отдельные теоретические положения работ [21, 23], для их
дальнейшего использования при решении задачи (3).
3. Метод динамического программирования
и двусторонние оценки функции Беллмана
Введем обозначения:
fk (xk,uk,ξk) = Axk + Buk + Cξk, Φk (x) = ∥Λx∥∞ .
65
Рассмотрим функцию Беллмана
Bk (x) =
(
)
=
sup
P max Φi+1 (xi+1 (xk, γk (·) , . . . , γi (·) , ξk, . . . , ξi)) ≤ ϕxk = x
γk(·)∈Uk,...,γN (·)∈UN
i=k,N
В соответствии с [23] уравнения динамического программирования для зада-
чи (3) имеют вид
(4)
γ∗k (x) = arg maxMξk [IF (x) Bk+1 (fk (x,u,ξk
))] ,
u∈R
(5)
Bk (x) = supMξk [IF (x)Bk+1 (fk (x,u,ξk
))] , k = 0, N,
u∈R
(6)
BN+1 (x) = IF
(x) ,
где Mξk [·] математическое ожидание по распределению случайной вели-
чины ξ, а IF индикаторная функция множества F.
Известно [23], что если существует решение u∗ (·) = (γ∗0 (·) , . . . , γ∗N (·)) за-
дач (4)-(6), то оно является оптимальным управлением в задаче (3). Важно
отметить, что решение уравнений (4)-(6) вызывает большие трудности, даже
если анализировать относительно простые задачи. Для задачи оптимального
удержания траекторий дискретной стохастической системы в трубке общего
вида с помощью поверхностей уровня 1 и 0 функции Беллмана были полу-
чены двусторонние оценки функции правой части уравнения МДП, функции
Беллмана и функции оптимального значения вероятностного критерия.
На данном фундаменте был предложен алгоритм приближенного поиска
оптимального управления [21], который при определенных условиях дает точ-
ное решение. Для описания алгоритма используются поверхности уровня 1
и 0 функции Беллмана
Ik = {x ∈ Rn : Bk (x) = 1} , Ok = {x ∈ Rn : Bk (x) = 0}
и множество Bk = Rn \ {Ik ∪ Ok}. Для удобства введем обозначение F =
= Rn \ F. Нетрудно видеть, что из определения введенных множеств спра-
ведливо, что
Bk (x) = 1,
x∈Ik,
Ik ∪ Bk ∪ Ok = Rn,
Bk (x) ∈ (0,1) ,
x∈Bk,
Bk (x) = 0,
x∈Ok.
В [21] были получены рекуррентные соотношения, не зависящие от функ-
ции Беллмана и позволяющие найти явный вид для поверхностей Ik, Ok и
множества Bk. Благодаря этому были получены условия для оптимальности
управления для xk ∈ Ik ∪ Ok и найдены двусторонние оценки функции Белл-
мана, на базе которых предлагается алгоритм для поиска субоптимального
управления для задачи (3).
66
(
)
Рассмотрим стратегию u (·) =
γ0 (·),... ,γN (·) , где uk = γk (xk), которая
на каждом шаге k максимизирует нижнюю оценку функции правой части
уравнения динамического программирования
γ
(x) = arg maxPξk (fk (x, u, ξk) ∈ Ik+1) ,
k
u∈R
Ik = Fk ∩ {x ∈ Rn : ∃u ∈ R : Pξ
(7)
(fk (x,u,ξk) ∈ Ik+1) = 1}, k = 0,N,
k
IN+1 = F.
Для предложенной стратегии из [21] следует, что стратегия является опти-
мальной при xk ∈ Ik ∪ Ok, k = 0, N и для любых xk ∈ Rn при k = N, а также
там приведено выражение для нахождения оценки точности субоптималь-
ной стратегии u (·). Воспользуемся теоретическими результатами настоящего
раздела для решения задачи (3).
4. Решение задачи
4.1. Аналитическое решение для двух шагов по времени
Воспользуемся методом динамического программирования, найдем реше-
ние задач (4)-(6) для k = N и положим x = xN , u = uN . Из выражений (5)
и (6) следует
BN (x) = maxM[IF (x) IF (fN (x,u,ξN ))] =
u∈R
= max{IF (x)P(∥Λ(Ax + Bu + CξN)∥∞ ≤ ϕ)} .
u∈R
Поскольку матрица Λ является диагональной, Λ = diag [λ1, . . . , λn], и для всех
i = 1,n - 1 выполнено eTiΛb = eTiΛc = 0, где ei-орт координатной оси, то по-
следнее выражение примет вид
{
(
)
eT
BN (x) = max
IF (x) I(-∞,ϕ] max
ΛAx
×
i
u∈R
i=1,n-1
}
(
)
×P
eT
Λ(Ax + Bu + CξN)≤ϕ
=
n
{
(
)
maxP
eTnΛ (Ax + Bu + CξN )≤ϕ
,
x∈F∩F′,
= u∈R
0,
x ∈F∩F′,
где
{
}
eT
≤ϕ
F′ = x ∈ Rn : max
i
ΛAx
i=1,n-1
67
Рассмотрим задачу стохастического программирования в первой ветви по-
следнего выражения. Целевая функция может быть преобразована следую-
щим образом:
(
)(
)
h = sign
eTn ΛC
ϕ - eTnΛAx - eTnΛBu - eTnΛCmξ
,
∫
h
(
)
P
eT
Λ(Ax + Bu + CξN)≤ϕ
= f˚ξ
(t) dt → max,
n
N
u∈R
−h
где fξ (t)
плотность распределения центрированной случайной величи-
N
ныξN = ξN - mξ. Поскольку f˚ (t) является четной функцией, указаннаяξ
N
задача стохастического программирования в соответствии с [24, с. 244] име-
ет детерминированный эквивалент, аналитическое решение которого u∗ =
(
)-1 (
)
=-
eTnΛB
eTnΛAx + eTnΛCmξ
. Подставляя найденное решение в целевую
функцию, находим функцию Беллмана на шаге k = N:
(
)
(8)
BN (x) = IF∩F′ (x) P
eTnΛCξ
N
≤ϕ
и решение задачи (3) при k = N
(
)
)-1 (
γ∗N (x) = -
eTnΛB
eTnΛAx + eTnΛCmξ
Заметим, что функция (8) равна единице только в случае
eTnΛCε≤ϕ,поэто-
му поверхность уровня 1 функции Беллмана на шаге k = N непуста только
в случае выполнения этого неравенства и равна
{
≤ϕ,
F∩F′,
eTnΛCε
IN =
∅
иначе.
(
)
Аналогично с учетом P
eTnΛCξ
N
≤ϕ
= 0 находим выражение для поверх-
ности уровня 0:
ON = F ∪ F′.
Найдем теперь оптимальное управление и функцию Беллмана для k = N -1.
Используя (4) и (8), запишем цепочку равенств
[
]
BN-1 (x) = maxM IF (x)BN (fN-1 (x,u,ξN-1))
=
u∈R
[
(
)]
= max
M IF (x)IF∩F′ (fN-1 (x,u,ξN-1))P
eTnΛCξ
N
≤ϕ
=
u∈R
{
(
(
)
{
= max
IF∩F′ (x)P
eT
Λ (Ax + Bu + CξN-1),
eTnΛCξ
N
≤ ϕ P max
n
u∈R
}
)}
eT
max
ΛA (Ax + Bu + CξN-1)
≤ϕ
i
i=1,n-1
68
Введем в рассмотрение матрицу
(
ΛN =
eT1ΛA, eT2ΛA,... , eTn-1ΛA, eTnΛ)T , ΛN ∈ Rn×n.
Тогда выражение для функции Беллмана при k = N - 1 можно представить
в виде
BN-1 (x) =
(
)
= IF∩F′ (x)P
eTnΛCξ
N
≤ ϕ maxP(∥ΛN (Ax + Bu + CξN-1)∥∞ ≤ ϕ) .
u∈R
Ниже в доказательстве утверждения 1 будет показано, что решение задачи
стохастического программирования в правой части последнего выражения
имеет вид
c
γ∗N-1 (x) = arg maxP(∥ΛN (Ax + Bu + CξN-1)∥∞ ≤ ϕ) = cN-1 (x) -
mξ,
u∈R
b
а функция Беллмана равна
(
)
(
)
c
(9)
BN-1 (x) = IF∩F′ (x)P
eTnΛCξ
N
≤ϕ P
ξN-1 ≤ rN-1 (x)
,
b
где функции cN-1 : Rn → R, rN-1 : Rn → R имеют вид
(
)
)
1
1(
cN-1 (x) =
ϕN-1 (x) + ϕN-1 (x)
,
rN-1 (x) =
ϕN-1 (x) - ϕN-1 (x)
,
2
2
а функции ϕN-1 : Rn → R и ϕN-1 : Rn → R имеют вид
(
)
sign
eTiΛN B
ϕ - eTiΛNAx
ϕN-1 (x) = min
,
i=1,n
eTiΛN B
(
)
-sign
eTiΛNB
ϕ - eTiΛNAx
ϕN-1(x)=max
i=1,n
eTiΛN B
Найдем поверхность уровня 1 функции Беллмана для k = N - 1:
{
≤ϕ,
F ∩ F′ ∩ ΔIN-1,
eTnΛCε
IN-1 =
∅
иначе,
где
{
}
(
)-1
ΔIN-1 = x ∈ Rn :
eTnΛNB
eTnΛN Cε ≤ rN-1 (x)
=
{
(
= x∈Rn :2
eTnΛN B
)-1 eTnΛN Cε + max-sign(eiΛN B)ϕ-eiΛN Ax
≤
i=1,n
eTiΛNB
(
)
}
sign
eTiΛNB
ϕ - eTiΛNAx
≤ min
=
i=1,n
eTiΛNB
69
{
(
)
c
-sign
eTjΛN B
ϕ-eTjΛNAx
=
x∈Rn :2
ε+
≤
b
eTjΛNB
(
)
}
sign
eTiΛNB
ϕ - eTiΛNAx
≤
,
∀i, j ∈ {1, . . . , n}
=
eTiΛNB
= {x ∈ Rn : ∥ΛN-1x∥∞ ≤ ϕ} ,
где матрица ΛN-1 ∈ RnN-1×n, nN-1 = n (n - 1) /2, составлена следующим об-
разом:
(
)T
ΛN-1 = eT1ΛN-1, eT2ΛN-1,... ,eTn
ΛN-1
,
N -1
p-я строка eTpΛN-1, p = 1, nN-1, определяется выражением
(
)T
(
)
T
aj
ϕ
ai
N-1
N-1
eTpΛN-1 =
(
)
-
,
biN-1
bj
ε+ sign(biN-1) + sign(bjN-1) ϕ
N-1
где
c
ε=2
ε,
b
biN-1 = eTiΛNB,
(
)T
aiN-1
= eTiΛNA,
aiN-1 ∈ Rn, biN-1 ∈ R,
ε∈ [0,+∞),
а индексы i и j связаны с p системой
p = (n - 1)i + j - 1
i, j ∈ {1, . . . , n} ,
i < j.
Поскольку для всех x ∈ Rn выполнено rN-1 (x) > 0, то с учетом (9) поверх-
ность уровня 0 функции Беллмана на шаге k = N - 1 имеет вид
ON-1 = F ∪ F′.
Поиск функции Беллмана и оптимального управления на шагах k = 0, N - 2
затруднен.
(
)
управление γ0 (·) , . . . , γN-2 (·) и нижнюю границу функции Беллмана.
4.2. Субоптимальная стратегия на шагах k = 0, N - 2
Воспользуемся теоремой 1 и найдем поверхность уровня 1 функции Белл-
мана, ее нижнюю границу и субоптимальное управление на шагах k =
= 0, N - 2.
70
Утверждение 1. Пусть выполнено
bi
(10)
max
max
≤2ϕ(ε)-1 ,
k
k=0,N-2 i∈1,nk+1+n
где параметры nk+1, bik и ε определены ниже. Тогда справедливы утвержде-
ния:
1.
Поверхности уровня 1 функции Беллмана при k = 0, N - 2 имеют вид
(11)
Ik = F ∩ F′ ∩ ΔIk,
где
ΔIk = {x ∈ Rn : ∥Λkx∥∞ ≤ ϕ} ,
матрица Λk ∈ Rnk×n, где
nk =1
(nk+1 + n) (nk+1 + n - 1) , k = 0, N - 2,
2
nN-1 =1
n(n - 1),
2
(
имеет вид Λk =
eT1Λk, eT2Λk,... ,eTnk Λk
)T, где каждая p-я строка, p =
= 1, nk, определяется соотношениями
(
)T
(
)T
aj
ϕ
aik
k
(12)
eTpΛk =
(
)
-
,
bik
bj
ε+ sign(bik) + sign(bjk) ϕ
k
c
ε=2
ε,
b
bik = eTiΛk+1B,
(
(13)
aik
)T = eTi Λk+1A,
(
Λk+1 =
Λk+1, eT1ΛA,... ,eTn-1ΛA, eTnΛ)T ,
aik ∈ Rn, bik ∈ R, ε∈ [0,+∞),
Λk ∈ R(nk+n)×n,
причем индексы i и j связаны с p системой
p = (i - 1)(nk+1 + n) + j - 1,
(14)
i, j ∈ {1, . . . , nk+1 + n} ,
i<j.
2.
Решения задачи стохастического программирования
(7) при k =
= 0, N - 2 имеют вид
c
(15)
γk (x) = ck (x) -
mξ,
b
71
нижняя граница функции Беллмана равна
(
)
c
Bk (x) = IF∩F′ (x)P
ξ
,
k
≤ rk (x)
b
где функции ck : Rn → R, rk : Rn → R имеют вид
(
)
)
1
1(
ck (x) =
ϕk (x) + ϕ
(x)
,
rk (x) =
k
ϕk (x) - ϕk (x)
2
2
и функции ϕk : Rn → R и ϕ
: Rn → R определяются выражениями
k
(
)
(
)T
sign
bik
ϕ-
aik
x
ϕk (x) = min
,
i=1,nk+1+n
bi
k
(
)
(
)T
-sign
bik
ϕ-
aik
x
ϕ
(x) = max
k
i=1,nk+1+n
bi
k
3. Поверхности уровня 0 функции Беллмана при k = 0, N - 2 имеют вид
(16)
Ok = F ∪ F′.
4. Верхняя граница функции Беллмана при k = 0, N - 2 равна
(
)
c
ξ
(17)
Bk (x) = IF∩F′ (x) P
k
≤ rN-1 (x)
b
Доказательство утверждения 1 вынесено в Приложение.
Замечание. Если bik = 0 или bjk = 0 из п.1 утверждения 1, то вектор
строка, определяемая выражением (12), исключается из Λk.
Как видно из п. 1 утверждения 1, условие (25) является необходимым для
непустоты поверхностей уровня 1 функции Беллмана на шагах k = 0, N - 2.
Заметим, что из п. 1 следует, что число строк nk матрицы Λk квадратич-
но растет с каждым шагом обратного времени k = 0, N - 2. Субоптималь-
ное управление (31) представляет собой кусочно-линейную функцию состоя-
ния с максимальным числом линейных участков, равных nk. Заметим так-
же, что верхняя граница функции Беллмана для всех k = 0, N - 2 с точно-
стью до случайной величины ξk совпадает с функцией Беллмана на шаге
k = N - 1 (23), а поверхности уровня 0 стационарны.
5. Пример 1. Управление системой второго порядка
5.1. Описание системы
Рассмотрим систему (1) для случая n = 2, описывающую движение мате-
риальной точки
rk+1 = rk + vkh,
(18)
vk+1 = vk + ukh + ξk,
r0 = X,v0 = V,
72
где rk, vk
координата положения и скорость в k-й момент времени,
ξk ∼ U[mξ - ǫ,mξ + ǫ] случайные возмущения на шаге k, для которых вве-
дены допущения, описанные в разделе 2, k = 0, N . Роль управляющего воз-
действия uk выполняет ускорение.
Во введенных в разделе 2 обозначениях получаем
)
(rk
(1 h)
(0)
(0)
xk =
, A=
B=
, C =
vk
0
1
h
1
и установим значения для параметров системы: N = 6, h = 1, ϕ = 1, 2, ǫ = 0,7,
mξ = 0 и Λ = diag [1,1].
5.2. Поверхности уровня 1 функции Беллмана
Перед тем, как перейти к численному эксперименту, важно отметить,
что для случая двумерной системы получается установить факт стационар-
ности поверхностей уровня 1 функции Беллмана для шагов k = 0, N - 2.
Рассмотрим шаг k = N. Используя результаты раздела 4.1, находим ΛN =
(
)T
=
eT1ΛA, eT2Λ
∈R2×2.
Рассмотрим шаг k = N - 1. Используя результаты раздела 4.1, получаем
(
)T
nN-1 = n(n - 1)/2 = 1 и ΛN-1 =
eT1ΛN-1
∈ R1×n, где
((
)T
(
)T)
ϕ
a1
a2
N-1
N-1
eT1ΛN-1 =
(
)
-
,
ε+
sign(b1N-1) + sign(b2N-1)
ϕ b1N-1
b2
N-1
(
ε=2
eT2B
)-1 eT2Cε ,
biN-1 = eTiΛNB,
(
)T
aiN-1
= eTiΛNA,
aiN-1 ∈ Rn, biN-1 ∈ R,
ε∈ [0,+∞).
Упростим выражения для параметров aiN-1 и biN-1 с учетом вида матри-
цы ΛN и eT2ΛeT1 = 0, eT1ΛeT2 = 0:
(
(eT1ΛA)
(eT1ΛA)
a1N-1
)T = eT1
A = eT1ΛAA, b1N-1 = eT1
B = eT1ΛAB,
eT2Λ
eT2Λ
(
)T
(eT1ΛA)
(eT1ΛA)
a2N-1
=eT2
A = eT2ΛA, b2N-1 = eT2
B = eT2ΛB,
eT2Λ
eT2Λ
(
(
)T
)T
a1
eT1ΛAA
eT1AA
eT1AA
a2
eT2ΛA
eT2A
N-1
N-1
=
=
=
,
=
=
,
b1N-1
eT1ΛAB
eT1AB
eT1AeT2B
b2N-1
eT2ΛB
eT2B
(
)T
(
)T
(
)
)
a1
a2
eT1AA
eT2A
eT1A
A
(eT1AeT1
1
N-1
N-1
-
=
-
=
-eT
=
·
eT1A.
2
b1N-1
b2N-1
eT1AeT2B
eT2B
eT1AeT2
eT2B
eT1AeT2
eT2B
73
Из этих выражений получаем выражение для матрицы ΛN-1:
)
(
)T
ϕ
(eT1AeT1
1
ΛN-1 =
λN-1eT1A
,
λN-1 =
(
)
,
ε+
sign(b1N-1) + sign(b2N-1)
ϕ eT1AeT
eT2B
2
где λN-1 ∈ R, λN-1 = 0. Таким образом, из утверждения 1 получаем, что
множество ΔIN-1 равно
{
}
{
}
≤ϕ
ΔIN-1 =
x ∈ R2 : ∥ΛN-1x∥∞ ≤ ϕ
=
x∈R2 :
eT1ΛN-1x
Рассмотрим шаг k = N - 2. Воспользуемся утверждением 1 и найдем зна-
чения параметров управления
1
nN-2 =
(nN-1 + 2) (nN-1 + 1) = 3,
2
(
)T
(
)
T
aj
ϕ
ai
N-2
N-2
eTpΛN-2 =
(
)
-
,
ε+ sign(biN-1) + sign(bjN-1) ϕ
biN-2
bj
N-2
(
ε=2
eT2B
)-1 eT2Cε ,
biN-2 = eTiΛN-1B,
(
)T
aiN-2
= eTi ΛN-1A,
(
)T
ΛN-1 =
ΛN-1, eT1ΛA, eT2Λ
,
aiN-2 ∈ R2, biN-2 ∈ R,
ε∈ [0,+∞),
ΛN-1 ∈ R3×2,
где индексы i и j связаны с p системой
p = i · 3 + j - 4,
i, j ∈ {1, 2, 3} ,
i<j.
Нетрудно видеть, что выполнены равенства
(19)
a2N-2 = a1N-1, a3N-2 = a2N-1, b2N-2 = b1N-1, b3N-2 = b2N-1,
(
(
(
)T
)T
)T
a1
λN-1eT1AA
eT1AA
a2
a1
N-2
N-2
N-1
(20)
=
=
=
=
b1N-2
λN-1eT1AB
eT1AB
b2N-2
b1
N-1
С учетом (19) строка p = 1 (i = 1, j = 2) матрицы ΛN-2 оказывается нулевой,
поскольку
(
)T
(
)T
a1
a2
N-2
N-2
-
= (0, 0) .
b1N-2
b2
N-2
74
k = 0, ..., N
1,0
0,5
0
-0,5
-1,0
-1,0
-0,5
0
0,5
1,0
r
Рис. 1. Поверхность уровня 1 функции Беллмана при k = 0, . . . , N.
Аналогично получаем, что строки p = 2 (i = 1, j = 3) и p = 3 (i = 2, j = 3)
матрицы ΛN-2 совпадают, так как выполнено
(
(
(
)T
(
)T
)T
)T
a1
a3
a2
a3
N-2
N-2
N-2
N-2
-
=
-
,
b1N-2
b3N-2
b2N-2
b3
N-2
и равны eT1ΛN-1 в силу (19) и (21). Таким образом матрица ΛN-2 принимает
вид
(
)T
ΛN-2 =
(0, 0) , eT1ΛN-1, eT1ΛN-1
,
откуда получаем, что множество ΔIN-2 равно
{
}
{
}
ΔIN-2 =
x ∈ R2 : ∥ΛN-2x∥∞ ≤ ϕ
=
x∈R2 :
eT1ΛN-1x
≤ϕ
= ΔIN-1.
Отсюда по индукции заключаем, что для всех k = 0, N - 2 выполнено
ΔIk = ΔIN-1,
и, следовательно, для указанных шагов поверхности уровня 1 функции Белл-
мана совпадают. Используя описанный выше результат и п. 3 утверждения 1,
получаем, что поверхности уровня 1 и 0 функции Беллмана для шагов k =
= 0r, N - 2 стационарны. В качестве примера на рис. 1 построена поверхность
уровня 1 функции Беллмана для системы (18).
Далее рассмотрим численный эксперимент, используя результаты, приве-
денные в разделах 4.1 и 4.2, для системы (18) с целью анализа полученного
решения.
75
5.3. Численный эксперимент
Положение системы в начальный момент времени не фиксируется, а гене-
рируется из равномерного распределения. Для положения r0 и скорости v0
системы из распределения U[-1, 1, 1, 1]. Важно отметить, что носители слу-
чайных величин r0 и v0 подобраны таким образом, чтобы генерировать точки
внутри и вне множества удержания. Выполним симуляцию M = 100 траек-
торий rk(i), vk (i) и uk(i), k = 0, N , i = 1, M стохастической системы.
На рис. 2 отображена каждая траектория системы отдельно. Графики под-
тверждают, что удается удержать систему для случаев, когда начальное со-
стояние системы находится внутри и вне множества удержания, причем начи-
ная с шага 3 траектории системы проходят близко к началу координат. При
этом заметно, что часть траекторий rk(i) и vk(i) до второго шага лежат вне
множества удержания, но после все траектории лежат строго внутри множе-
ства удержания.
Для анализа управления, предложенного в разделе 4 (далее вероят-
ностного управления), сравним его с LQG (Linear quadratic Gaussian control)
управлением с единичной матрицей Q и критериальной функцией J(u(·)) =
∑N+1
=M[
xTk xk].
k=0
На левом графике рис. 3 изображены зависимости оценки вероятност-
ного критерия от параметра ϕ при использовании вероятностного (пунк-
тирная линия) и LQG (жирная линия) управлений. Для оценки критери-
альной функции выполняется симуляция M = 1000 траекторий rk(i), vk(i)
и uk(i), k = 0,N, i = 1,M стохастической системы при заданном ϕ и ис-
пользуется частотная оценка для критерия. Из графика видно, что при
ϕ ∈ [0,1) ∪ (1,35, +∞] значения критериальных функций совпадают, а на от-
резке [1, 1,35] для основной части точек ϕ оценка вероятности удержания
траекторий системы больше для вероятностного управления.
На правом графике рис. 3 изображены зависимости оценки критериальной
функции J(u(·)) от первой координаты начального состояния x10 при исполь-
зовании вероятностного (пунктирная линия) и LQG (жирная линия) управле-
rk(i)
vk(i)
uk
2
2
1
1
1
0
0
0
-1
-1
-1
-2
-2
0
2
4
6
0
2
4
6
0
2
4
6
k
k
k
Рис. 2. Изменения траекторий системы rk(i), vk(i) и uk(i).
76
Pf(u)
J(u(·))
1,0
1,0
0,8
0,8
0,6
0,6
0,4
0,4
0,2
Probability control
Probability control
0,2
LQG control
LQG control
0
0
1,0
1,1
1,2
1,3
-2
-1
0
1
2
1
f
x0
Рис. 3. Значение критериальных функций Pϕ(u(·)) и J(u(·)) для вероятност-
ного и LQG управлений.
ний и фиксированной второй координате начальных условий x20 на уровне 0,5.
Из графика видно, что значения критериальных функций очень близки, но
кривая для LQG критерия всегда проходит немного ниже кривой для веро-
ятностного критерия.
6. Заключение
В статье рассмотрена задача оптимального удержания линейной системы
с дискретным временем, скалярным неограниченным управлением и случай-
ным шумом в канале управления в заданной окрестности нуля по вероят-
ностному критерию. Найдены аналитические выражения для поверхностей
уровня 1 и 0 функции Беллмана и ее двусторонних границ. На основе ниж-
ней границы получено явное соотношение для субоптимального управления,
являющегося оптимальным, если состояния системы принадлежат поверх-
ностям уровня 1 и 0. Эффективность найденного управления проверена на
модельной задаче. Для частного случая системы второго порядка доказано
свойство частичной стационарности поверхностей уровня 1.
ПРИЛОЖЕНИЕ
Доказательство утверждения 1. Предположим, что на некотором
шаге k + 1, где k = 0, N - 2, поверхность уровня 1 функции Беллмана имеет
вид Ik+1 = F ∩ F′ ∩ ΔIk+1,
ΔIk+1 = {x ∈ Rn : ∥Λk+1x∥∞ ≤ ϕ} ,
где Λk+1 ∈ Rnk+1×n, а nk+1 ∈ N, nk+1 ≥ n некоторое целое число. Восполь-
зуемся п. 1 теоремы 1 и найдем поверхность уровня 1 на шаге k:
{
(
{
})
}
Ik = F ∩
x ∈ Rn: ∃u ∈ R: P
[Ax + Bu + Cξk] ∈
F ∩ F′ ∩ ΔIk+1
=1
=
{
(
{
})
}
=F∩F′ ∩
x ∈ Rn: ∃u ∈ R: P
[Ax + Bu + Cξk] ∈
F′n ∩ F′ ∩ ΔIk+1
=1
,
77
{
}
≤ϕ
где F′n =
x∈Rn :
eTnΛx
. Введем обозначения
{
}
Ik+1 =
F′n ∩ F′ ∩ ΔIk+1
=
{
}
}
{
eT
eT
= x ∈ Rn : max
n
Λx, max
i
ΛAx
, ∥Λk+1x∥∞
≤ϕ
i=1,n-1
Введем в рассмотрение матрицуΛk+1 ∈ R(nk+1+n)×n,
(
)T
Λk+1 =
Λk+1, eT1ΛA,... ,eTn-1ΛA, eTnΛ
Тогда справедливо
{
}
Ik+1 = x ∈ Rn :
Λ
k+1x
≤ϕ ,
∞
а выражение для поверхности уровня 1 функции Беллмана на шаге k имеет
вид
{
(
)
}
Ik = F ∩F′ ∩ x ∈ Rn : ∃u ∈ R : P
Λ
k+1 (Ax+Bu+Cξk)
≤ϕ =1
=
∞
{
(
)
}
= F ∩ F′ ∩ x ∈ Rn : maxP
Λ
k+1 (Ax + Bu + Cξk)
≤ϕ =1 .
u
∞
Рассмотрим задачу стохастического программирования
(
)
(Π.1)
P
Λ
k+1 (Ax + Bu + Cξk)
≤ ϕ → max,
∞
u
которая позволит найти явный вид поверхности уровня 1, нижнюю грани-
цу функции Беллмана и стратегию (3) на шаге k = 0, N - 2. Преобразуем
целевую функцию (П.1) с учетом обозначений (12)-(14)
(
)
(Π.2) P
Λ
k+1 (Ax + Bu + Cξk)
≤ϕ =
∞
(
)
= P max
eTi Λ
k+1 (Ax + Bu + Cξk)≤ϕ
=
i=1,nk+1+n
(
)
(
)T
= P max
aik
x+biku+cikξk≤ϕ
=
i=1,nk+1+n
(
(
)
(
)T
(
)
(
)T
-sign
bi
ϕ-
aik
x
cik
sign
bik
ϕ-
aik
x
k
=P
≤u+
ξk ≤
,
bik
bik
bi
k
)
∀i = 1,nk+1 + n
,
78
где cik = eTi Λk+1C. Заметим, что для любого i = 1, nk+1 + n выполнено cik/bik =
= eTnC/eTnB. Тогда последнее выражение для целевой функции принимает вид
(
)
eTnC
(Π.3) P ϕk (x) ≤ u +
ξk ≤ ϕk (x)
=
eTnB
(
)
)
1(
1(
eTnC
=P
-
ϕk (x) - ϕ
(x)
+
≤u+
ξk ≤
k
ϕk (x) + ϕk (x)
2
2
eTnB
)
(
)
)
1
1(
≤
ϕk (x) - ϕ
(x)
+
=
k
ϕk (x) + ϕk (x)
2
2
)
(
T
C
n
= Pu + e
ξk - ck (x)
rk (x)
=
≤
eTnB
)
(
T
C
eTnC
n
ξ
= Pu + e
k +
mξ - ck (x)
rk (x)
≤
eTnB
eTnB
Поскольку плотность распределения f˚ (t) центрированной случайной вели-ξ
k
чиныξk является четной функцией, то задача (П.1) имеет решение
c
(Π.4)
u∗ = γk (x) = ck (x) -
mξ,
b
а оптимальное значение целевой функции определяется выражением
(
)
(
)
c
ξ
(Π.5)
P
Λ
k+1 (Ax + Bu∗ + Cξk)
≤ϕ =P
k
≤ rk (x)
∞
b
Запишем преобразованный вид поверхности уровня 1 функции Беллмана на
шаге k
{
(
)
}
c
ξ
Ik = F ∩ F′ ∩ x ∈ Rn : P
k
≤ rk (x)
=1
=
b
{
}
c
=F∩F′ ∩ x∈Rn :
ε ≤ rk (x)
=
b
{
}
c
= F ∩ F′ ∩ x ∈ Rn : ϕk (x) + 2
ε ≤ ϕk (x)
=
b
{
(
)
(
)T
-sign
bik
ϕ-
aik
x
= F ∩ F′ ∩ x ∈ Rn : max
+
i=1,nk+1
bi
k
(
)
(
)T
}
c
sign
bik
ϕ-
aik
x
+2
ε ≤ min
=
b
i=1,nk+1+n
bi
k
79
{
(
)
(
)T
-sign
bik
ϕ-
aik
x
=F∩F′ ∩
x∈Rn :
+
bi
k
(
)
(
)T
j
j
}
sign b
ϕ- a
x
k
k
+ε≤
,
∀i, j ∈ {1, . . . , nk+1
+ n}
=
j
b
k
{
(
)
(
)T
-sign
bik
ϕ-
aik
x
=F∩F′ ∩ x∈Rn :
+
bi
k
(
)
(
)T
j
j
}
sign b
ϕ- a
x
k
k
+ε≤
,
∀i, j ∈ {1, . . . , nk+1
+ n}
j
b
k
Видно, что для Ik = ∅ необходимо, чтобы
(Π.6)
max
bik
≤2ϕ(ε)-1 .
i∈1,nk+1+n
С учетом (П.4) получаем
{
(
)
(
-sign
bik
ϕ-
aik
)T x
Ik = F ∩ F′ ∩ x ∈ Rn :
+ε≤
bi
k
(
)
(
)T
j
j
}
sign b
ϕ- a
x
k
k
≤
,
∀i, j ∈ {1, . . . , nk+1
+ n},i < j
=
j
b
k
(
)T
{
(
)T
aj
ϕ
ai
k
k
=F∩F′ ∩ x∈Rn :
(
)
-
x ≤ ϕ,
bik
) + sign(bjk) ϕ
bjk
ε+ sign(bk
}
∀i, j ∈ {1, . . . , nk+1 + n} , i < j
= F ∩ F′ ∩ {x ∈ Rn : ∥Λkx∥∞ ≤ ϕ} =
= F ∩ F′ ∩ ΔIk.
Для завершения доказательства п. 1 достаточно убедиться, что на шаге k =
= N -1 поверхность уровня 1 функции Беллмана имеет вид (11), что следует
из раздела 4.1.
П. 1 утверждения 1 доказан.
П. 2 утверждения 2 следует из (П.4) и (П.5).
Предположим, что на некотором шаге k + 1, k = 0, N - 2 поверхность
уровня 0 функции Беллмана имеет вид Ok+1 = F ∪ F′. Воспользуемся п. 2
теоремы 1 и найдем поверхность уровня 0 на шаге k
80
{
(
)
}
(Π.7) Ok = F ∪
x∈Rn
: ∀u ∈ R : Pξk
[Ax + Bu + Cξk]∈F∪F′ =1
=
{
(
)
}
=F∪F′ ∪ x∈Rn
: ∀u ∈ Uk : Pξk
[Ax + Bu + Cξk] ∈ F ∪ F′
=1
,
n
где F′n = Rn \ F′n (см. доказательство п. 1 утверждения 1). Нетрудно видеть,
что
{
(
)
}
x ∈ Rn : ∀u ∈ R : Pξ
[Ax + Bu + Cξk] ∈ F ∪ F′n
=1
= ∅,
k
откуда с учетом (П.7) заключаем, что Ok = F ∪ F′, и поскольку данное ра-
венство выполнено для k = N - 2, то оно выполнено и для всех k = 0, N - 2.
П. 3 утверждения 1 доказан.
П. 4 утверждения 1 следует из (9), (10) и п.3 утверждения 1.
Утверждение 1 доказано.
СПИСОК ЛИТЕРАТУРЫ
1.
Малышев В.В., Кибзун А.И. Анализ и синтез высокоточного управления лета-
тельными аппаратами. М.: Машиностроение, 1987.
2.
Lesser K., Oishi M., Erwin R. Stochastic reachability for control of spacecraft relative
motion // Proc. IEEE Conf. Dec. and Ctrl. 2013. P. 4705-4712.
3.
Кан Ю.С. Оптимизация управления по квантильному критерию // АиТ. 2001.
№ 5. C. 77-88.
Kan Y.S. Control Optimization by the Quantile Criterion // Autom. Remote Con-
trol. 2001. V. 62. No. 6. P. 746-757.
4.
Азанов В.М., Кан Ю.С. Синтез оптимальных стратегий в задачах управле-
ния стохастическими дискретными системами по критерию вероятности // АиТ.
2017. № 6. C. 57-83.
Azanov V.M., Kan Yu.S. Design of Optimal Strategies in the Problems of Discrete
System Control by the Probabilistic Criterion // Autom. Remote Control. 2017.
V. 78. No. 6. P. 1006-1027.
5.
Кузьмин В.П., Ярошевский В.А. Оценка предельных отклонений фазовых ко-
ординат динамической системы при случайных возмущениях. М.: Наука, 1995.
6.
Soudjani S., Abate A. Probabilistic reach-avoid computation for partially degenerate
stochastic processes // IEEE Trans. Autom. Ctrl. IEEE Trans. Autom. Ctrl., 2014.
V. 59. No. 2. P. 528-534.
7.
Summers S., Lygeros J. Verification of discrete time stochastic hybrid systems: A
stochastic reach-avoid decision problem // Automatica. 2010. V. 46. No. 12. P. 1951-
1961.
8.
Vinod A., Oishi M. Scalable underapproximation for the stochastic reach-avoid prob-
lem for highdimensional LTI systems using Fourier transforms // IEEE Lett.-Contr.
Syst. Soc. 2017. V. 1. No. 2. P. 316-321.
9.
Jasour A.M., Aybat N.S., Lagoa C.M. Semidefinite Programming For Chance Con-
strained Optimization Over Semialgebraic Sets // SIAM J. Optimization. 2015.
V. 25. No. 3. P. 1411-1440.
81
10.
Jasour A.M., Lagoa C.M. Convex constrained semialgebraic volume optimization:
Application in systems and control. arXiv:1701.08910, 2017.
11.
Григорьев П.В., Кан Ю.С. Оптимальное управление по квантильному критерию
портфелем ценных бумаг // АиТ. 2004. №2. С. 179-197.
Grigor’ev P.V., Kan Y.S Optimal Control of the Investment Portfolio with Respect
to the Quantile Criterion // Autom. Remote Control. 2004. V. 65. No. 2. P. 319-336.
12.
Бунто Т.В., Кан Ю.С. Оптимальное управление по квантильному критерию
портфелем ценных бумаг с ненулевой вероятностью разорения // АиТ. 2013.
№ 5. С. 114-136.
Bunto T.V., Kan Y.S. Quantile criterion-based control of the securities portfolio
with a nonzero ruin probability // Autom. Remote Control. 2013. V. 74. No. 5.
P. 811-828.
13.
Maidens J.N., Kaynama S., Mitchell I.M., Oishi M.M., Dumont G.A. Lagrangian
methods for approximating the viability kernelin high-dimensional systems // Au-
tomatica. 2013. V. 49. No. 7. P. 2017-2029.
14.
Kariotoglou N., Raimondo D.M., Summers S., Lygeros J. Astochastic reachability
framework for autonomous surveillance withpan-tilt-zoom cameras // Proc. Euro-
pean Ctrl. Conf. 2011. P. 1411-1416.
15.
Doyen L., De Lara M. Stochastic viability and dynamic programming // Systems
and Control Letters. 2010. V. 59. No. 10. P. 629-634.
16.
Кибзун А.И., Иванов С.В., Степанова А.С. Построение доверительного множе-
ства поглощения в задачах анализа статических стохастических систем // АиТ.
2020. № 4. С. 21-36.
17.
Азанов В.М., Кан Ю.С. Двухсторонняя оценка функции Беллмана в задачах
стохастического оптимального управления дискретными системами по вероят-
ностному критерию качества // АиТ. 2018. № 2. С. 3-18.
Azanov V.M., Kan Yu.S. Bilateral Estimation of the Bellman Function in the Prob-
lems of Optimal Stochastic Control of Discrete Systems by the Probabilistic Perfor-
mance Criterion // Autom. Remote Control. 2018. V. 79. No. 2. P. 203-215.
18.
Азанов В.М., Кан Ю.С. Усиленная оценка функции Беллмана в задачах стоха-
стического оптимального управления с вероятностным критерием качества //
АиТ. 2019. № 4. С. 53-69.
Azanov V.M., Kan Yu.S. Refined Estimation of the Bellman Function for Stochas-
tic Optimal Control Problems with Probabilistic Performance Criterion // Autom.
Remote Control. 2019. V. 90. No. 4. P. 634-647.
19.
Vinod A.P., Oishi M.M. Stochastic reachability of a target tube: Theory and com-
putation // Automatica. 2021. V. 125.
20.
Афанасьев В.Н., Колмановский В.Б., Носов В.Р. Математическая теория кон-
струирования систем управления. М.: Высш. шк., 2003.
21.
Азанов В.М.,Тарасов А.Н. Двусторонняя оценка функции Беллмана в задаче оп-
тимального удержания траекторий дискретной стохастической системы в трубке
по критерию вероятности // АиТ. 2020. № 10. C. 93-117.
Azanov V.M., Tarasov A.N. Probabilistic criterion-based optimal retention of tra-
jectories of a discrete-time stochastic system in a given tube: bilateral estimation of
the Bellman function // Autom. Remote Control. 2020. V. 81. P. 1819-1839.
22.
Konrad Schmudgen. The moment problem. Vol. 9. Springer, 2017.
82
23. Азанов В.М., Кан Ю.С. Об оптимальном удержании траектории дискретной
стохастической системы в трубке // АиТ. 2019. № 1. С. 38-53.
Azanov V.M., Kan Yu.S. On Optimal Retention of the Trajectory of Discrete
Stochastic System in Tube // Autom. Remote Control. 2019. V. 80. No. 1. P. 30-42.
24. Кан Ю.С., Кибзун А.И. Задачи стохастического программирования с вероят-
ностными критериями. М.: ФИЗМАТЛИТ, 2009.
Статья представлена к публикации членом редколлегии М.М. Хрусталевым.
Поступила в редакцию 24.02.2022
После доработки 16.05.2022
Принята к публикации 28.07.2022
83
