Алгоритм построения оптимальной стратегии в нелинейной дифференциальной игре с использованием конволюты

Основы теории дифференциальных игр с нулевой суммой заложены в работах Р. Айзекса. [1], Л.С. Понтрягина. [2], Н.Н. Красовского [3] и др. В настоящее время разработаны различные алгоритмы, вычисляющие цепу игры, и оптимальные стратегии управления [4-6]. Для линейных дифференциальных игр с выпуклым целевым множеством современные методы используют алгоритмы вычисления игровых множеств достижимости через опорные функции этих множеств. Если дифференциальная игра, нелинейна, то игровые множества, достижимости становятся невыпуклыми, аппарат опорных функций становится неприменимым. В работе [7] для нелинейной дифференциальной игры с липшицевой функцией платы предложен алгоритм построения ква-зиоптимальной стратегии управления с помощью пошагового минимакса.

В настоящей работе предлагается алгоритм построения квазиоптимальной (или е -оптимальной) стратегии управления для нелинейной дифференциальной игры на. фиксированном отрезке времени с целевым множеством. Алгоритм использует попятную конструкцию построения игровых множеств достижимости. В двумерном случае эти множества, могут быть построены с помощью алгоритма, близкого к алгоритму построения конволюты суммы Минковского двух многоугольников [10,11].

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

I.    Постановка задачи

Рассмотрим динамическую систему, описываемую дифференциальным уравнением

x ( t ) = a ( t, x ( t ) , u ( t )) + b ( t, x ( t ) , v ( t )) , t E [0 , 9 ] , (1 . 1)

на фиксированном отрезке времени [0 ,9 ], г де t — время, x ( t ) Е R n — фазовый вектор системы, управление первого игрока u ( t ) и второго игрока v ( t ) подчинены ограничениям

u ( t ) E P, v ( t ) E Q Vt E [0 ,9 ] .      (1-2)

Предполагается, что заданы компактные множества. P. Q ii непрерывные функции a : [0 ,9 ] х х R ⁿ х P ^ R n ii b : [0 ,9 ] х R ⁿ х Q ^ R n Кроме того, вектограммы a ( t,x,P ) = {a ( t,x,u ) : u E P}, b ( t, x, Q ) = {b ( t, x,v ) : v E Q} выпуклы при всех t E E [0 ,9 ], x E R n . Пусть также задано компактное множество M С R n , которое будем называть целевым, или терминальным.

Пусть для какой-то начальной позиции x ( t 0) = = x о E R n ii каких-то номеримых управлений u: [0 ,9 ] ^ P. v [0 ,9 ] ^ Q абсолютно непрерывная функция x : [0 ,9 ] ^ R n почти всюду на отрезке [0 ,9 ] удовлетворяет уравнению (1.1). Если в конечный момент времени выполняется x ( 9 ) E E M, то будем говорить, что в игре имеет место поимка. Если в конечный момент времени выполняется x ( 9 ) E M, то будем говорить, что в игре имеет место уклонение. Цель первого игрока, состоит в поимке, цель второго игрока. — в уклонении.

Расстоянием от точки x E R n до множества Y С R n называется величина

% ( x,Y ) = inf [x - y\\ . y ∈ Y

(1.3)

Будем говорить, что в конечный момент времени имеет место е-поимка. если % ( x ( 9 ) ,M ) 6 е.

‘Работа выполнена при поддержке РФФИ, грант 10-01-00139а, ФЦП «Научные и научно-педагогические кадры инновационной России» и АВЦП «Развитие научного потенциала высшей школы».

Будем предполагать, что функции a : [0 , в ] х х R n х P ^ R n ii b : [0 ,в ] х R n х Q ^ R n удовлетворяют следующим условиям Липшица:

||a ( t 1 ,x i ,u i) - a ( t 2 ,x 2 ,u 2) W 6

6 La|t 1 ^—t 2 1 + Lxwx 1 ^—x 2 1 1+ Luwu 1 ^—u 2 1 1

Vt 1 ,t 2 E [0 ,в ] , x 1 ,x 2 E R n, u 1 ,u 2 E P ; (1 . 4) Wb ( t 1 ,x 1 ,v 1) - b ( t 2 ,x 2 , v 2) W 6

• ⁶ Lbt 1 ^— t 2 I ⁺ L^XWx 1 ^{— x} 2 ^{W +} Lv ^Wv 1 ^{— v} 2 ^W

Vt 1 ,t 2 E [0 ,в ] , x 1 ,x 2 E R n, v 1 , v 2 E Q ;   (1 . 5)

Wa ( t,x,u ) W 6 Ca Vt E [0 ,в ] , x E R n, u E P ; (1 . 6) Wb ( t, x, v ) W 6 Cb Vt E [0 ,в ] , x E R n, v E Q. (1 . 7)

Обозначим

C = Ca + Cb, L = La + LX.      (1.8)

II.    Стратегии и законы управления

Пусть задано число t 0 E [0 , в ]. Множеством U [ t 0 ,в ] допустимых реализаций управления первого игрока, называется множество всех измеримых функций u : [ t 0 , в ] ^ P. Множеством V [ t 0 , в ] допустимых реализаций управления второго игрока. называется множество всех измеримых функций v : [ t 0 , в ] ^ Q.

Пусть заданы число t 0 E [0 , в ) и начальное состояние x ( t 0) = x 0. Пусть T = {т Д ^ =0 — разбиение отрезка. [ t 0 , в ] : t 0 = т 0 < т 1 < ••• < TI = = в. Кусочно-постоянной стратегией первого игрока, соответствующей разбиению T , будем называть набор функций uT = {u Str : R n ^ P}I =0¹. Движением, соответствующим начальному состоянию x ( t 0) = x 0, разб!гению T, стратегии первого игрока uT и допустимой реализации управления v E V [ t 0 , в ]. будем называть функцию x : [ t 0 , в ] ^ ^ R n , определяемую из пошагового уравнения

x ( t ) = a ( t, x ( t ) , uT ^r( x ( Ti ))) + b ( t, x ( t ) , v ( t )) , (2.9)

которое должно выполняться при почти всех t E E [ Ti,Ti +1] и всех i E 0 , I — 1. При этом начальная позиция для отрезка [ т 0 ,т 1] равна x 0, а начальная позиция x ( Ti ) для отрезка. [ TiT +1] совпадает с конечной позицией x ( Ti ) отрезка [ Ti- 1 ,Ti ].

В силу принятых предположений при заданных начальной позиции x ( t 0) = x 0, разбггении T, стратегии первого игрока uT и допустимой реализации управления v E V [ 1 0 , в ] движеиие x ( • ) существует и единственно. Обозначим его следующим образом:

x m^ot( t,t 0 ,x 0 ,T,uT,v ) = x ( t ) Vt E [ 1 0 ,в ] . (2.10)

Аналогично определяются кусочно-постоянная стратегия второго игрока vsStr, соответствующая разбиеншо T. и движение xmot(t, 10, x0,T,u, vsStr). соответствующее начальной позиции x(10) = x0, разбиению T, допустимой реализации управления первого игрока u E U [10, в] и кусочно-постоянной стратегии второго игрока v^tr.

Будем говорить, что кусочно-постоянная стратегия uTr гарантирует е-поимку для начального состояния x ₀, если для любой реализации управления v E V [0 , в ] выполняется

% ( x m^ot( в, 0 , x 0 , T, uT, v ) , M ) 6 е. (2.11)

Будем говорить, что кусочно-постоянная стратегия vsStr гарантирует уклонение для начального состояния x0, если для любой реализации управления u EU [0, в] выполняется xmot( в, 0 ,x 0, T, u, vTtr) E M.       (2.12)

Пара кусочно-постоянных стратегий ( uT, v^ tr) называется е-оптимальной, если для любого начального состояния x 0 E R n выполняется хотя бы одно из условий:

• 1)    стратегия uT гарантирует е -поимку или

• 2)    стратегия v^ tr гарантирует уклонение.

III.    Алгоритм вычисления стратегии управления

Зафиксируем натуральное число I и рассмотрим равномерное разбиение T = {Ti}I =₀ отрезка [0 , в ]. цде Ti = ir. i E 0 , I . Шаг т = в/I разбиения T будем также называть параметром дискретизации по времени.

Для любого множества S С R n и любого индекса i E 0 , I — 1 определим множества

AiS = {x E R n : 3u E P : x + Ta ( Ti,x,u ) E S}, (3 . 13)

BiS = {x E R n : Vv E Q : x + Tb ( Ti,x,v ) E S}. (3 . 14)

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

Суммой и разностью Минковского множеств X С R n yY с R n называются соответственно множества.

X + Y = {x + y : x E X, y E Y},

.                                         (3.15)

X — Y = {x E R n : x + Y С X}.

Заметим, что если функции a ( t,x,u ) и b ( t,x,v ) не зависят от фазового вектора x, то одношаговые операторы достижимости выражаются через операции Минковского. Действительно, пусть a ( t, x, u ) = a ( t,u ). b ( t,x,v ) = b ( t,v ). Тогда, согласно равенствам (3.13), (3.14) имеем

AiS = S + ( —Ta ( Ti,P )) , BiS = S — Tb ( Ti, Q ) .

(3.16)

Для любого числа R >  0 чс)хз B r обозначим замкнутый шар с центром в нуле и радиусом R:

B r = {ж Е R n : ||ж| | 6 R}. (3.17)

Пусть У — класс зтожеств в R n. с которым работают алгоритмы. Примером класса У может служить класс многоугольников в R².

В параграфе V будут рассмотрены алгоритмы, которые для каждого множества S Е У и для каждого индекса i Е 0 , I — 1с некоторыми погрешностями вычисляют множества AiS, BiS. Учитывая эти погрешности, будем предполагать, что реально для каждого множества S Е У вычисляются множества AiS, BiS класса У, удовлетворяющие условиям

Ai ( S — B _E a ) с AiS C Ai ( S + B _E a ) ,     (3.18)

Bi ( S — B ев ) с BiS C Bi ( S + B _EB ) ,    (3.19)

где числа ед, e_B определяют погрешности этих алгоритмов.

Опишем метод, который для любых множества. S C У. пилокса. i Е 0, I — 1 и вылора ж Е AiS позволяет определить вектор ui = ui(ж, S) Е Р такой, что ж + та(тi,ж,Ui) Е S + BEu.       (3.20)

Зафиксируем номер i Е 0 , I — 1 и точку ж Е AiS. Тогда в силу соотношения (3.18) имеем ж Е Ai ( S + + B _EA ). Поэтому согласно равенству (3.13) существует такой вектор и Е Р, что ж + та ( т_i,ж,u ) Е Е S + B _EA . Это означает, что

( S + B _EA — ж ) П ( та ( т_i,ж, Р )) = 0 .

Аппроксимируем множество та(тi,ж,P) многогранником 1b такт к что Р C та (тi,ж,P) C Р + + B5P. Приблизим шар BEu вписанным в него многогранником BEu. Задача нахождения управ ления при этом сведется к поиску пересечения двух многогранников S + BEu — ж и Р, что легко осуществить алгоритмически. Число eu > ед подберем таким образом, чтобы пересечение этих двух многогранников было заведомо непусто. Это возможно, так как реальные множества S + BEA — — ж и та(тi,ж,P) имеют непустое пересечение, а погрешность, вносимую приближениями шара, и вектограммы, мы компенсируем увеличением радиуса шара BEu, прибавляемого к множеству S.

Аналогичным методом для любых множества. S C У. индокса, i Е 0, I — 1 и вок тора, ж Е Rn \ (BiS) найдем вектор vi = vi(ж, S) Е Q такой, что ж + тЬ(Ti,ж,Vi) Е (Rn \ S) + Bev .       (3.21)

Здесь числа eu и ev определяют погрешности соответствующих алгоритмов.

Зафиксируем некоторые векторы и* Е Р, v* Е Е Q и положим Ui(ж,S) = и* при ж Е AiS, vi(ж,S) = v* при ж Е BiS. Тем самым при всех i Е 0, I — 1 определены функции

Ui : R n х У m Р,    vi : R n x У m Q. (3.22)

Обозначим

0    2 ^µ LC x      L^tb ^¶

^A u = ^{т      +} Lb Ca ⁺      ,

/                    t {           (3.23)

A V = т ² ( LC + LXCb + La } ,

A u = ^A U ^{+ e}B ^{+ (1 + т}Д) ) ^eu,

^A v = ^A V ^{+ e}A ^{+ (1 + т}Lx ) ^ev.

Пусть имеются алгоритмы, которые для любого множества. S Е У вычисляют множества. D_uS Е У. D_vS Е У такие, что

S -^∗ B∆ u + εD ⊂ DuS ⊂ S -^∗ B∆ u ,

S + B_A v C DvS C S + Ba „ + e d ,

(3.25)

где число e_D определяет погрешность этих алгоритмов.

Зафиксируем положительное число е.

Определим множества М^¹ Е У, MI Е У так, что

М + B e - e m C MU C М + B E,      (3.26)

М C MI C М + B EM.       (3.27)

Здесь число е_м Е (0 , е ) определяет погрешность начальной аппроксимации.

Двигаясь в сторону уменьшения индекса i и используя алгоритмы параграфа. V, вычислим наборы игровых множеств достижимости {М^¹}!^. {МЕ}I- 0¹:

М“ = AiBiDuMi +1 ,         (3.28)

М1 = BiAiDv МЕ+1.         (3.29)

Для любых i Е 0 , I — 1 11 ж Е R n. используя функции (3.22) и игровые множества, достижимости М“, МЦ, вычисленные алгоритмами параграфа. V, определим

Ui ( ж )= и i ( ж,BiDuMi+1 ) ,       (3.30)

vi ( ж ) = vi ( ж, AiDvМ¹ ₊₁) .        (3.31)

Теорема 3.1. Пусть ж ₀ Е М01, стратегия иT = = {u_i}i =o определена соотношением (3.30). Тогда стратегия иТ^Т гарантирует е -поимку на отрезке [0 , Э ] для иачалык:>го состояния ж (0) = ж q.       □

Теорема 3.2. Пусть ж 0 Е R n \ МQv, стратегия vT tr = {v_i}I = 7 _Q¹ определена соотношением (3.31). Тогда стратегия v^ tr гарантирует уклонение на отрезке [0 , Э ] для иачалык:>го состояния ж (0) = ж 0. □

Определим числа.

C 1 = 2 Сь +

+ в ^ lc + LXCb + LXCa + 2 La + 2 Lb) ,

(3 . 32)

^Е о — ⁽ C 1 ^T + ² E m +

+ (3 e a + 3 e b + 2 E d + 2 e _u + 2 ev ) I ) . (3 . 33)

Теорема 3.3. Пусть e >  e 0. Тогда пара кусочно-постоянных стратегий ( иT, v^ tr) является Е -оптимальной.                              □

• IV.    Доказательство теорем 3.1-3.3

Лемма 4.1. Для любых множества S С С R ”. индокса, i е 0 , I — 1 и 4iюла 5 >  0 операторы (3.13), (3.14) удовлетворяют соотношениям

AiS + B 5 С Ai ( S + B_a+ TLa ) 5 ) ,       (4.34)

BiS + B 5 С Bi ( S + B(1+ TLX ) 5 ) .       (4.35)

¤

Доказательство. Пусть x е AiS + B 5. Тогда существует вектор у е AiS такой, что ky — xk 6 6 5. В силу равенства (3.13) существует вектор и е P такой, что у + та ( т^у,и ) е S. Отсюда, в силу соотношения (1.4) получаем включение x + + та ( т_i,x, и ) е S + B(1+ _t l x ) 5. Следовательно, x е Ai ( S + B(1+ _TLa ) 5 ), что доказывает включение (4.34). Включение (4.35) доказывается аналогично.                                        ■

Для любых t 0 е [0 , в ] ,1 1 е [ t 0 , в ] ,x 0 е R n,u е ей [ t 0 ,t 1] ,v е V [ t 0 ,t 1] обозначим

X ( t,t 0 ,x 0 ,u,v ) — x ( t ) Vt е [ t 0 ,t 1] ,       (4.36)

где x : [ t 0 ,t 1] ^ R n — решение задачи Коши

±( t ) — а ( t, x ( t ) , u ( t ))+ b ( t, x ( t ) ,v ( t )) , t е [0 , в ] , (4 . 37)

с начальным условием x ( t 0) — x 0.

Проводя рассуждения, близкие к доказательству леммы 5.1 из [8], получаем следующую лемму.

Лемма 4.2. Пусть заданы числа т е (0,в), t0 е [0, в — т ]. вок тор x 0 е Rn и Фу1 ikiiiiii и е ей [ t о ,t о + т ], v е V [ t о ,t о + т ]. Пусть xu — x0 +

t0+τ j а(tо, xо, и(t)) dt, t0

(4.38)

x 1 — X ( t о + т,t о ,x о ,u,v ) .        (4.39)

Тогда существует вектор vо е Q такой, что вектор xuv — xu + тЬ (t о ,xu,v о)         (4.40)

удовлетворяет неравенству

I I xuv — x 1 k 6 A U,             (4.41)

где число A U определено равенством (3.23).    □

Лемма 4.3. Пусть стратегия первого игрока. иT^r — {ui}f = 7 o определяется соотношением (3.30), i е 0 ,I — 1. x о е M^u. v е V [ 14,14 +1]. x 1 — — x m^ot( 14,14 +1 , x о , T, и T^r ,v ). To гда x 1 е Mi+1. □

Доказательство. Определим функцию и е ей [ т_i, T_i +1] формулой

и ( t )— Ui ( x о) vt е [ Ti,Ti +1] .          (4.42)

Тогда справедливо равенство (4.39), где t _о — т_i.

Из включения xо е Mi1 и равенства (3.28) получаем xо е AiBiDUMi1+1. Отсюда, и из соотношений (3.20), (3.30) следует включение xо + + та(Ti,xо,Ui(xо)) е BiDuMi+1 + BEu. Поэтому согласно равенству (4.42) получаем, что вектор xu, определяемый формулой (4.38), удовлетворяет включению xu е BiDuMi+1 + вeu.        (4.43)

Так как согласно включениям (3.25) имеем DuMi+1 С Mi+1 — Вди. то BiDuMi+1 С С Bi(Mi+1 — Вди) и в силу включений (3.19) получаем бiDuMi+1 С Bi(Mi+1 — Вди + ВЕв). Используя соотношение (4.35), (4.43), получаем xu е BiDuMi+1 + Вeu С

С Bi ( Mi +1 — Вд и + В ев ) + В eu С Bi S, (4 . 44) где

S — Mi +1 — Вд и + В ев + В(1+ TLx ) eu •   (445)

В силу леммы 4.2 существует вектор v _о е Q такой, что для вектора x_uv — x_u + тЬ ( т_i,x_u,v _о) справедливо неравенство (4.41). Из соотношений (3.14), (4.44) следует включение x_uv е е S. Отсюда в силу неравенства (4.41) и равенства (4.45) получаем включение x 1 е S +Вдо — — Mi+1 — Вд u + В ев + (1+ TLx ) eu +Д U■ ПоЭТОМу согласно равенству (3.24) справедливо включение x 1 е Mi+1.        '                               ■

Проводя рассуждения, аналогичные доказательству леммы 4.3, получаем следующую лемму.

Лемма 4.4. Пусть стратегия второго игрока. v^ tr — {vilaZ c¹ определяется соотношением (3.31), i е 0 ,1 — 1, x о е Miv, и е U [ Ti,Ti +1], x 1 — — x m^ot( Ti,Ti +1 ,x о ,T,u,vT ^tr). Тогда x 1 / Mi’ ₊₁. □

Доказательство теоремы 3.1. Используя лемму 4.3, индукцией по индексу i е 0 , I — 1 получаем включения x m^ot( t _о ,т_i,x _о ,Т,иTr,v ) е е Mi^u. Отсюда в силу соотношения (3.26) имеем x m^ot( t о , e,x о ,Т,иT,v ) е M + В _e. Следовательно, выполнено неравенство (2.11).                 ■

Доказательство теоремы 3.2. Используя лемму 4.4, индукцией по индексу i е 0 , I — 1 получаем включения x m^ot( t _о ,т_i,x _о , Т, u,vT^t ) е R n \Mi¹. Отсюда, в силу соотношения (3.27) приходим к соотношению (2.12).                            ■

Доказательство теоремы 3.3. Используя неравенство е >  е 0 и повторяя с некоторыми изменениями доказательство теоремы 3 из [8], получаем включение M0 С M0, которое вместе с теоремами 3.1, 3.2 доказывает е -оптимальность пары стратегий ( uT, vT^T).

V.    Алгоритм вычисления одношаговых операторов достижимости в двумерном случае

Для любых i е 0 , I — 1, S С R ” определим множество

AiS = [ ( x — та ( Ti,x,P )) .      (5.46)

x ∈ S

Лемма 5.5. Пусть выполнено неравенство tL X <  1. Тогда, для лгобого множества. S С R n и любого индекса i е 0 , I — 1 справедливы включения

AiS С Ai ( S + B Lcт 2) ,       (5.47)

AiS С A ( S + B Lxcaт 2) .       (5.48)

¤

Доказательство. Зафиксируем множество S С R n и ин деке i е 0 , I — 1. Пл "сть x е AiS. Тогда, существуют векторы у е S, и е P такие, что x = = у — та ( т_i,y,u ). Следователыю. ky — xk 6 С_ат. kx + та ( Ti,x,u ) — yk = тЦа ( ri,x,u ) — а ( т^у, u ) Ц 6 6 LXCaT2, t. e. x е Ai ( S + B Lxca_T 2), что доказывает включение (5.47).

Докажем включение (5.48). Пусть x е AiS. Тогда, согласно равенству (3.13) существует вектор и е P такой, что x + та ( Ti,x,u ) е S . В силу неравенства. tL X <  1 отображение F ( у ) = x + та ( т_i,y,u ) является сжимающим и, значит, имеет неподвижную точку у о е R n: у о = F ( у о). т. е. у о = x + + та ( т^у о , и ). Следователыю. ky ₀ — xk 6 С_ат. kx + та ( Ti,x,u ) — у о | | = т Ца ( ri,x,u ) — а ( т,у о ,и ) Ц 6 6 LxCaT 2. Поэтому у о е S + B LxCaT 2, x = у о — — та ( т^у о ,и ) е Ai ( S + B LacaT 2)•                ■

Далее будем предполагать, что размерность фазового вектора n = 2 и для любых t е [0 ,д ], x е R² вектограммы а ( t, x, P ) 11 b ( t, x, Q ) являются выпуклыми многоугольниками или отрезками. Будем также предполагать, что игровые множества, достижимости и дополнения к ним связны. В качестве класса множеств У, с которым работают алгоритмы, будем рассматривать множество многоугольников с длинами сторон, не превосходящими заданного числа h, которое будем называть параметром дискретизации по пространству.

Напомним определения. Пусть задан набор точек ак е R2, к = 1, m, причем ак+1 = ак для любого к е 1, m — 1. Упорядоченный набор отрезков {[а 1, а2], [а2 ,а3],.. ., [ат- 1, ат]} называется ломаной Г(а 1,..., ат), то^1ки ак называются вершинами, а отрезки [ак ,ак+1] — звеньями этой ломаной. Для одной точки а е R2 поло жим Г( а) = = {а}. Ломаная Г(а 1,..., ат) называется замкнутой. если ат = а 1. Ломаная Г(а 1,..., ат) называется простой замкнутой, если m > 1, ат = а 1 и из того, что z е [aj ,aj+1] С [ак ,ак+1]. 1 6 j < к < m следует, что к = j + 1 11 z = ак. Многоугольником называется ограниченное замкнутое связное множество S С R2 такое, что его границей dS является простая замкнутая ломаная. Вершинами многоугольника S называются вершины ломаной dS.

Заметим, что для любой замкнутой ломаной Y С R² ее дополнение R² \ y состоит из конечного числа, пепересекающихся областей, одна, из которых неограничена. Дополнение к этой неограниченной области называется доменом y ^и обозначается domain y- Легко видеть, что домен любой замкнутой ломаной y С R² является замкнутым ограниченным связным множеством, причем y С С domain y и д (domain y ) С y- Граница домена замкнутой ломаной y называется внешним контуром, y ¹¹ обозиачается ext y: ext y = д (domain y )•

Алгоритм вычисления внешнего контура замкнутой ломаной y = Г( x 1 , ...,x_k ,x 1) состоит из следующих шагов.

Шаг 1. Найдем вершину xi 0 (1 6 i _о 6 к ), наименьшую в смысле лексикографического порядка;

ПОЛОЖИМ i = i о.

Шаг 2. Если на отрезке [ xi,xi +1] нет точек пересечения с другими звеньями ломаной y (кроме соответствующих концов соседних звеньев), то добавляем отрезок [ xi, xi +1 ] в контур ext y и увеличиваем индекс i 11 а 1 (по м<эдулто к ). Иначе находим z — точку самопересечения y, лежащую на [ xi, xi +1], ближайшую к точке xi. Добавлявм отрезок [ xi,z ] в контур ext y- Находим V — множество концов всех звеньев ломаной y, проходящих через точку z . Среди всех вершин xj е V \ {xi, z} находим ту. для которой угол между векторами xi — z и xj — — z, отсчитываемый против часовой стрелки, минимален. Добавляем отрезок [ z,xj ] в контур ext y. Полагаем i = j.

Шаг 3. Если i = i _о, выход. Иначе переходим к шагу 2.

Направлением ненулевого вектора x е R2 называется единичный вектор -^|^. Правым перпендикуляром для ненулевого вектора x е R2 называется единичный вектор x^, полученный путем поворота, по часовой стрелке направления вектора. x на у гол 2. Для любых двух ненулевых векторов а е R2 11 b е R2 че) >ез angle( а, b) обозначим множество всех ненулевых векторов, направления которых получаются путем вращения единичного вектора, против часовой стрелки от направления а до направления Ь. Через (а, b) будем обозначать скалярное произведение векторов a = (a 1, a2) и b = = (b 1, b2): ha, bi = a 1 b 1 + a2b2- Нормальным конусом выпуклого множества X С R2 в точке xо е дХ называется множество

N ( x 0 ,X ) = {р е R² : hp,xi 6 hp,x 0 i V x е X}.

В силу леммы 5.5 для вычисления одношаговых операторов достижимости Ai достаточно с заданной точностью вычислять множества AiS, определяемые формулами (5.46). Рассмотрим алгоритм приближенного вычисления множеств AiS, использующий конволюту.

Понятие конволюты многоугольников введено в [9] и состоит в следующем. Пусть имеются два многоугольника: X с вершинами xi и У с вершинами yj, пронумерованными против часовой стрелки. Коиволютой многоугольников X и У называется упорядоченный набор отрезков вида [ xi + yj,xi +1 + yj ]. г,тс xi +1 - xi е angle(( yj -- yj- 1) , ( yj +1 — yj ))■ ^a также отрезков вида. [ xi + + yj,xi + yj +1]. где вектор yj ₊i - yj е angle(( xi -- xi- 1) , ( xi +1 - xi )). В [10], [11] описан алгоритм, позволяющий построить конволюту двух многоугольников и извлечь из нее сумму Минковского этих многоугольников. Заметим, что если функция a ( t,x,u ) не заш iciit от x. то согласно формуле (5.46) множество AiS является суммой Минковского (см. (3.16)). Адаптируем алгоритм из [10] к задаче приближенного вычисления множеств AiS в предположении связности рассматриваемых множеств и их дополнений.

Зафиксируем произвольный индекс i е 0 , I - 1. Для любого x е  R² обозначим G ( x )  =

= -Ta ( Ti,x,P ). Пусть mik жоуголышк S с длинами сторон 6 h задан набором вершин x 1 ,... ,x_s. пронумерованных против часовой стрелки. Границей многоугольника S является простая замкнутая ломаная дS = Г( x 1 ,...,x_s,x_s +1). г,де xs +1 = x 1. max ||xj +1 - xj| | 6 h. Для любого j е 1 , s обозна- j ∈ 1 ,s чим nj = ( xj +1 - xj ) ^± — правый перпендикуляр к j -му звену ломаной dS. положим n о = ns. Для каждого j е 1 , s рассмотрим g j,..., g³_m j — пронумерованные против часовой стрелки все вершины многоугольника G ( xj ) такие, что

N ( g”m, G ( xj )) П angle( nj- 1 ,n ) = 0 , m е 1 ,mj.

Конволютой для задачи (5.46) будем называть замкнутую ломаную

C ( S, G ) = Г( x 1 + g 1 ,...,x 1 +

• ^{+    g} _m i , ^x 2 ^{+ g} 1 , . . . , ^x 2 ^{+ g} _m 2 , . . . , ^x s ⁺

• +    g s,...,xs + gm _s ,x 1 + g 1) .

Определим многоугольник AiS как домен конволюты C ( S, G ):

AiS = domain( C ( S, G )) .

Используя описанный выше алгоритм вычисления внешнего контура, найдем границу многоугольника AiS: д ( AiS ) = ext( C ( S,G )). Тем самым мы определим вершины многоугольника AiS.

Лемма 5.6. Пусть выполнено неравенство tL X <  1. Тогда для любого i е 0 , I - 1 справедливы включения

д ( AiS ) С AiS + B 2 h, д ( AiS ) С AiS + B 2 h. □

Доказательство. Зафиксируем произвольные i е 0 , I - 1 1i y е д ( AiS ). Пусть отрезок [ y 0 ,y 1 ] является звеном конволюты, содержащим точку y. Поскольку y 0 и y 1 — соседние вершины конволюты, то согласно ее определению существуют x о и x 1 — совпадающие или соседние вершины многоугольника. S такие, что yj е xj + G ( xj ). j = 0 , 1. Так как G ( x ) = -Ta ( Ti,x,P ). то существуют векторы и 0 , и 1 е P такие, что yj = xj - Ta ( Ti,xj,Uj ). j = 0 , 1. Поскольку ||x 0 -x 1 1 6 h. то согласно соотношению (1.4) вектор y 2 = x 0 - Ta ( Ti, x о , и 1) удовлетворяет неравенствам ||y 1 - y 2 1 6 h (1 + tL X ) < <  2 h. Так как векторы y 0 и y 2 содержатся в выпуклом множестве x 0 + G ( x 0), то в этом множестве содержится весь отрезок [ y 0 ,y 2]. Отсюда из включения y е [ y 0 ,y 1] 11 иеравеиства ||y 1 - y 2 1 <  2 h следует. что y е x о + G ( x о) + B2 h С AiS + B2 h. Таким образом, получено первое из доказываемых включений. Доказательство второго включения опускаем в силу его громоздкости. ■

Лемма 5.7. Пусть в R ” заданы ограниченные множества. S 1 11 S 2. дS 1 С S 2 + B 5. пусть число 5 >  0 таково, что множество R ⁿ \ ( S 2 + B 5 ) связно. Тогда S 1 С S 2 + B 5. □

Доказательство. Так как множества S 1 и S 2 ограничены, то существует точка z е R ⁿ: z е ( S 1 U US 2)+B 5. Предположим, что доказываемое включение не выполнено. Тогда существует точка x е е S 1 \ ( S 2 + B 5 ). Поскольку множество R ⁿ \ ( S 2 + + B 5 ) связно и содержит точки x е S 1 11 z е S 1. то существует точка y е ( дS 1) \ ( S 2 + B 5 ), что противоречит условию дS 1 С S 2 + B 5. ■

Замечание. Условие связности множества. R ⁿ \ ( S 2 + B 5 ) в лемме 5.7 существенно. Действительно, рассмотрим в R² множества

S 1 = { ( x,y ) : x ² + y ² 6 1 },

S 2 = { (cos ^, sin ^ ): ^ е [0; 2 n - 5 ] }.

Тогда при 5 е (0; 1) все условия леммы 5.7 кроме связности множества R ⁿ \ ( S 2 + B 5 ) выполнены, но включение S 1 С S 2 + B 5 не справедливо.

Лемма 5.8. Пусть S — многоугольник с длинами сторон, не превосходящими числа h, i е 0 , I - 1. мнойсества R² \ ( AiS + B _{2 h} ) 11 R² \ ( Ai ( S - B _{4 h} )+ B _{2 h} ) связны и пусть выполнено неравенство tL X <  1. Тогда справедливы включения (3.18) при е а =4 h + U X C _X t 2. □

Доказательство. В силу лемм 5.6, 5.7 справедливы включения

AiS С AiS + B 2 h,           (5.49)

Ai ( S — B 4 h ) С Ai ( S — B 4 h ) + B 2 h.     (5.50)

Используя включения (4.34), (5.49) и лемму 5.5, получаем

AiS С Ai ( S + B LaCaT 2) + B 2 h С

С Ai ( S + B LxCaT 2+2 h (1+ TLa )) С Ai ( S + B _EA). (5 . 51)

Аналогично включению (4.34) для любого множества. S С R² и лтобого числа. 5 >  0 имеем

AiS ⁺ B 5 ^С Ai ⁽ S ⁺ B (i+ TLa ) 5 ) .

Следовательно,

Ai ( S — B 4 h ) + B 2 h С

С Ai ( S — B 4 h + B 2 h (1+ tl x )) С AiS.

Отсюда, используя включение (5.50) и лемму 5.5, приходим к соотношениям

Ai ( S — B _ЕА ) = Ai ( S — B 4 h + LaCaT 2) С

^С Ai ^{( S} — B 4 h + LxCaT ^{2 + B} LaCaT ² ) ^С

С Ai ( S — B 4 h ) С AiS. (5 . 52)

Включения (5.51), (5.52) дают (3.18).           ■

Алгоритм, аналогичный описанному выше, позволяет вычислить множества BiS, приближающие множества BiS. Повторяя с некоторыми изменениями рассуждения, проведенные при доказательстве леммы 5.8, получаем, что в предположении связности соответствующих множеств справедливы включения (3.19) при е_в = 4 h + + LXCbT ². Подставляя эпi выражения для ед. ев в формулу (3.33), находим теоретическую оценку общей погрешности алгоритма. Получен-пая оценка, показывает, что параметр дискретизации по пространству h должен быть выбран существенно меньше параметра, дискретизации по времени т.