311

Оптимальное управление и дифференциальные игры

О НЕКОТОРЫХ СПОСОБАХ ОБРАБОТКИ И

ХРАНЕНИЯ ИНФОРМАЦИИ ПРИ РЕШЕНИИ ЗАДАЧ

ДИНАМИЧЕСКОЙ ОПТИМИЗАЦИИ НА ЗАДАННОМ

ОТРЕЗКЕ ВРЕМЕНИ

Токманцев Т.Б.1

e-mail: [email protected] Рассмотрим задачу оптимального управления системой:

x(t) = f (t, x, u), x[t0 ] = x0, u P, (1) где t [0, T ] – время, x Rn – фазовый вектор системы, управляющий параметр u выбирается из заданного компакта P Rm.

Функционал платы имеет вид It0, x0 (x(·), u(·)) = min {(, x()) + g(t, x(t), u(t))dt}, (2) [t0,T ] t где x(·) = x(·; t0, x0, u(·)) : [t0, T ] Rn – траектория движения динамической системы (1), стартующей из начальной точки (t0, x0 ) [0, T ] Rn под воздействием управления u(·) : [t0, T ] P. Оптимальный результат (цена) V (t0, x0 ) определяется соотношением V (t0, x0 ) = inf It0, x0 (x(·; t0, x0, u(·)), u(·)). (3) u(·)Ut Символом Ut0 обозначается множество всех допустимых управлений – измеримых функций u(·) : [t0, T ] P, называемых программами.

Предполагается, что исходные данные удовлетворяют следующим условиям. Функции f (t, x, u) и g(t, x, u) определены и непрерывны на [0, T ] Rn P вместе со своими частными производными f /t, f /xi, g/t, g/xi, i = 1, n, и липшицевы относительно t и x. Функция (t, x) определена и непрерывна на R Rn вместе со своими частными производными /t, /xi, i = 1, n.

Предполагается, что множества Arg min [ p, f + g] состоят (f,g)F (t,x) (f 0 (t, x, p), g 0 (t, x, p)), из единственного элемента где F (t, x) = {(f (t, x, u), g(t, x, u)) : u P }.

1

Работа выполнена при финансовой поддержке РФФИ (проект 05–01–00609), гранта Президента РФ по поддержке ведущих научных школ (проект НШ– 8512.2006.1) 312 Труды XXXVIII Молодежной школы-конференции Как известно [1], функция цены (3) является минимаксным решением следующей задачи Коши с дополнительными ограничениями:

V (t, x)/t + H(t, x, Dx V (t, x)) = 0, (4) (t, x) [0, T ] Rn, V (T, x) = (T, x), V (t, x) (t, x), V (t, x) V (t, x) где Dx V (t, x) =. При сделанных предполоx1,..., xn жениях существуют классические характеристики уравнения Беллмана (4) ((·), p(·), z (·)):

x d = Dp H(t, x, p), x dt dp = Dx H(t, x, p), dt (5) d z = p, Dp H(t, x, p) H(t, x, p), dt x(T, y) = y, p(T, y) = Dy (T, y), z (T, y) = (T, y), где параметр y Rn, H(t, x, p) = min[ p, f (t, x, u) + g(t, x, u)].

uP Предлагается следующая аппроксимация функции цены:

j V (ti, x) = min{(ti, x), min zi } = j : xj x i (6) ti+ {(ti, x), V (ti+1, xj ) + g 0 (, xj ( ), pj ( ))d }, min i+1 j j : xi x ti где [ti, ti+1 ] [0, T ], Qi+1 – сетка по x Rn в момент t = ti+1, xj (ti+1 ) = y j Qi+1, pj (ti+1 ) y V (ti+1, y j ), z j (ti+1 ) = V (ti+1, y j ), j j j j j j xi = x (ti ), pi = p (ti ), zi = z (ti ). Параметр аппроксимации 0. Алгоритм и его оценки подробно изложены в [2] и [3].

Оценка численной аппроксимации. Введем разбиение отрезка времени [0, T ] с шагом t: N = {t0, t1,..., tN = T }. Численная аппроксимация функции цены (6) осуществляется посредством попятной процедуры интегрирования характеристической системы с помощью метода Эйлера. Полученный результат V (ti, xj ) отлича- i ется от точного значения функции цены в точках текущей сетки на величину Оптимальное управление и дифференциальные игры где константы C1 > 0, C2 > 0, F > 0 вычислены по входным данным задачи (1)–(2), а (·) g (t, x, ·).

Одна из основных проблем при реализации алгоритма состоит в проверке условия xj x. В случае одномерного фазового пространства эта проблема решается сортировкой по координате x и сравнением соседних точек. В двумерном фазовом пространстве эта проблема превращается в самостоятельную задачу задачу геометрического поиска.

Для решения этой задачи предлагается следующая схема. Сечения характеристик в моменты времени ti разбиения отрезка [0, T ] сохраняются в бинарном дереве структуре данных, представляющей собой граф, где есть выделенный узел корень и нет циклов. У корня два соседа потомки, каждый из которых представляет собой, в свою очередь, корень поддерева. На дереве задан лексикографический порядок (x1, y1 ) < (x2, y2 ) x1 < x2 ((x1 = x2 ) (y1 < y2 )).

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

Рис. 1: Бинарное дерево с лексикографическим порядком В нашем случае нужно учитывать то, что компоненты x характеристик не будут совпадать точно, а с некоторой погрешностью. Для того, чтобы это учитывать, вводится положительный параметр. Если расстояние между сечениями проекций характеристик, представляющих собой точки в фазовом пространстве, меньше, мы считаем компоненты совпадающими. Если при добавлении новой характериТруды XXXVIII Молодежной школы-конференции стики в дерево мы находим уже добавленную характеристику, расстояние до которой меньше, мы производим операцию по слиянию:

выбираем минимум значений z этих двух характеристик и запоминаем сопряженные переменные p.

После реализации этой схемы оказалось, что нужно также учитывать расстояния между ближайшими характеристиками, даже не совпадающими так как аппроксимация функции цены строится вдоль характеристик, при разбегании характеристик образуются области, на которой функции цены не построена. Чтобы это исправить, нужно находить места в сетке Qi, где ближайшие характеристики отстоят далеко друг от друга и заполнять их. Для этого используется метод диаграммы Вороного (многоугольников Дирихле) [4].

Для каждой точки xj0 строится многоугольник, содержащий точi ки пространства, лежащие ближе к этой точке, чем к остальным точкам xj. Используя для хранения диаграммы Вороного структуру данных реберный список с двойными связями, можно быстро найти всех ближайших соседей данной точки множества.

Рис.2 Диаграмма Вороного Рис.3 Реберный список Если какая-то соседняя точка лежит дальше некоторого параметра, то промежуток между ними надо заполнить. Пусть это будут точки x1 и x2. Мы возвращаемся на предыдущий момент вреi i мени ti+1 и строим выпуклую оболочку сопряженных переменных co{1, p2 }. Затем производим дискретизацию этого множества pi+1 i+ {p1,..., pm } и выпускаем новые характеристики из точек (1,p1,i+1 ),...,(1,pm,i+1 ) и (2,p1,i+1 ),...,(2,pm,i+1 ).

Кроме этого, диаграмма Вороного может применяться для лучОптимальное управление и дифференциальные игры шей визуализации графика функции цены. Соединив точки, лежащие по разные стороны ребер диаграммы Вороного, мы получим триангуляцию этого множества. Триангуляцию можно использовать для рисования графика функции и, вычислив нормали, для освещения этого графика.

Список литературы [1]. Subbotin A.I. Generalized Solutions of First Order of PDEs:The dynamical Optimization Perspectives. Boston: Birkhauser, 1995.

[2]. Субботина Н.Н., Токманцев Т.Б. Алгоритм построения минимаксного решения уравнения Беллмана в задаче Коши с дополнительными ограничениями // Динамические системы: моделирование, оптимизация и управление. Труды Института математики и механики УрО РАН, 2006. Т. 12. № 1. С. 208–215.

[3]. Субботина Н.Н., Токманцев Т.Б. Численная аппроксимация минимаксного решения уравнения Беллмана в задаче Коши с дополнительными ограничениями // Проблемы теоретической и прикладной математики: Труды 37-й Региональной молодежной конференции. Екатеринбург: УрО РАН, 2006. С.357–361.

[4]. Препарата Ф., Шеймос М. Вычислительная геометрия: Введе- ние. М: Мир, 1989. 480 с.