WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

загрузка...
   Добро пожаловать!

Pages:     | 1 || 3 |

Производя линеаризацию динамики объектов относительно номинальных движений, приходим к следующей линейной дифференциальной игре:

= F, t [0, T ], x, y R2, u P, v Q, = -(F - u)/P, (5) x(T ), y(T ) = y(T ) - x(T ).

= v, Здесь x вектор положения первого (догоняющего) игрока, y вектор положения второго (убегающего) игрока, P постоянная времени, характеризующая инерционность отработки управления первого игрока. Множества P и Q, ограничивающие управления первого и второго игроков, являются эллипсами:

2 u2 u2 v1 v1 P = u R2 : + 1, Q = v R2 : + 1.

2 A2 BP A2 BE P E Полуоси AP, BP, AE, BE параллельны координатным осям и вычисляются на основе ограничений aP, aE на ускорения игроков и косинусов углов (P )nom и (E)nom. Момент окончания T игры фиксирован. Платой является геометрическое расстояние между объектами в момент окончания. Первый игрок минимизирует функцию платы, второй максимизирует.

Структура задачи такова, что в ней появляются множества уровня функции цены, имеющие узкие шейки, строение которых принципиально разнится для случаев, когда скорость преследователя больше скорости убегающего и когда меньше. Для второго случая множества, близкие к критическому, имеют весьма сложное строение в районе узкой Рис. 2: Множество уровня с узкой шейкой, близкое к критическому (внутреннее темное), и большее множество уровня (внешнее прозрачное) Рис. 3: Увеличенный фрагмент с узкой шейкой шейки. Здесь и далее критическим называем множество уровня функции цены с непустыми t-сечениями на [t0, T ], имеющее на (t0, T ) одно или более t-сечений с пустой внутренностью. На рис. 2 приведен вид двух множеств уровня: близкого к критическому и большего. Видно, что большее множество уровня имеет гладкую границу. Это означает, что именно около узкой шейки сосредоточены нерегулярности функции цены (рис. 3). Чтобы правильно отразить их, нужны очень аккуратные вычисления в районе узкой шейки. Кроме того, потребовались хорошие средства визуализации трехмерных максимальных стабильных мостов.

Соответствующие программы были разработаны в 1997-2000 гг. в секторе компьютерной визуализации отдела системного обеспечения ИММ УрО РАН В.Л.Авербухом, А.И.Зенковым, Д.А.Юртаевым.

Вычислительные качества программы проверялись и на других примерах, относящихся, как и система (5), к классу игр, которые называются обобщенный контрольный пример Л.С.Понтрягина 11,12. Среди прочих был подобран и просчитан следующий пример:

- 0.025 + 1.3 x = u, + y = v, (6) x, y R2, u P, v Q, x(T ), y(T ) = y(T ) - x(T ).

Ограничения на управления игроков были взяты в виде одинаковых эллипсов 2 v1 vP = Q = v R2 : + 1.

1.52 1.На рис. 4 приведен общий вид множества уровня функции цены, обладающего двумя узкими шейками. Отмечены моменты обратного времени, соответствующие узким шейкам. Множество уровня построено для значения c = 1.2 функции платы.

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

Никольский М.С. Первый прямой метод Л.С.Понтрягина в дифференциальных играх. М: Изд-во Моск. ун-та, 1984.

Чикрий А.А. Конфликтно управляемые процессы. Киев: Наукова Думка, 1992.

Рис. 4: Игра (6): общий вид множества уровня функции цены с двумя узкими шейками Геометрической разностью (разностью Минковского) множеств A и B называют13,14 совокупность элементов пространства, вдвигающих множество B в множество A при помощи алгебраической суммы:

A - B = {x : B + x A}.

Вообще говоря, если сложить геометрическую разность двух множеств с множеством-уменьшаемым, то получим лишь подмножество множестваХадвигер Г. Лекции об объеме, площади поверхности и изопереметрии.

М: Наука, 1966.

Понтрягин Л.С. Линейные дифференциальные игры, 1 // Докл. АН СССР, №6, Т.174, 1967. C. 1278–1280.

уменьшаемого:

B + (A - B) A.

Если же множества A и B таковы, что в предыдущем соотношении имеет место равенство, т.е.

B + (A - B) = A, то говорят, что множество A полностью выметается множеством B (множество B полностью выметает множество A). Понятие полного выметания введено в работе П.Б. Гусятникова и М.С. Никольского15.

Пусть f скалярная функция аргумента x и Mc = {x : f(x) c} ее множество уровня, соответствующее константе c. Будем говорить, что функция обладает свойством уровневого выметания, если для любой пары констант c1 < c2 в случае непустоты множества уровня Mc этой функции оно полностью выметает множество уровня Mc.

Результатом второй главы является следующая Теорема. Пусть непрерывная квазивыпуклая функция платы (·) дифференциальной игры (2) обладает свойством уровневого выметания:

для любых двух констант c1 < c2 ее множество уровня Mc (если оно непусто) полностью выметает множество уровня Mc.

Тогда соответствующие множества уровня Wc и Wc функции 1 цены V (·) игры (2) обладают аналогичным свойством: для каждого момента t [t0, T ] такого, что сечение меньшего множества уровня Wc (t) непусто, сечение Wc (t) полностью выметает сече1 ние Wc (t) большего множества уровня.

Обоснование теоремы базируется на рекуррентном правиле пересчета (3), (4), записанном на языке множеств:

W(ti) = W(ti+1) + · P(ti) - · Q(ti).

Таким образом, для того, чтобы проверить наличие полного выметания сечения Wc (t) сечением Wc (t) множеств уровня в некоторый мо2 Гусятников П.Б., Никольский М.С. Об оптимальности времени преследования // Докл. АН СССР, Т. 168, № 3, 1969. С. 518–521.

мент t, в предположении о полном выметании множества Mc множеством Mc, следует проверить сохранение этого свойства при операциях алгебраической суммы, геометрической разности и при предельном переходе с измельчением шага сетки по времени.

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

Лемма (2.5.1). Пусть множества A и B таковы, что множество A полностью выметается множеством B, т.е. A = B + (A - B). Тогда для любого множества P имеем (A + P ) = (B + P ) + (A + P ) - (B + P ).

Лемма (2.5.2). Пусть выпуклые компакты A, B R2 таковы, что множество A полностью выметается множеством B. Тогда для лю бого выпуклого компакта Q R2 такого, что B - Q =, имеем (A - Q) = (B - Q) + (A - Q) - (B - Q).

Отметим, что первая из этих лемм верна в пространстве любой размерности и для любых множеств A, B, P (от них не требуется ни выпуклость, ни замкнутость, ни ограниченность). Вторая же лемма специфична для пространства R2, что показывается соответствующими контрпримерами.

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

Типы сингулярных поверхностей описаны в книге Р.Айзекса Дифференциальные игры. Исходя из вариантов поведения оптимальных движений (другими словами, обобщенных характеристик уравнения Гамильтона–Якоби–Беллмана–Айзекса), выделяют следующие виды сингулярных поверхностей: рассеивающие, универсальные/фокальные, экивокальные, поверхности переключения. Необходимые условия, характеризующие тот или иной тип сингулярной поверхности, получены P. Bernhard16 и А.А. Меликяном17. В работах A.W. Merz, J. Lewin, J.G. Olsder, J. Shinar исследованы сингулярные поверхности, возникающие в конкретных задачах. Автору неизвестны работы, посвященные численным алгоритмам глобального построения сингулярных поверхностей в дифференциальных играх.

В диссертации предложена следующая схема построения сингулярных поверхностей. В процессе нахождения очередного сечения W(ti) максимального стабильного моста W на границе W(ti) выделяются сингулярные точки, которые классифицируются и связываются с точками на границе W(ti+1) ранее построенного в обратном времени сечения W(ti+1). В итоге после построения рассматриваемого стабильного моста имеем совокупность сингулярных линий на его границе. Сингулярные поверхности строятся на основе набора сингулярных линий, снятых с системы мостов (множеств уровня функции цены).

Таким образом, первичными являются сингулярные линии на границе множеств уровня.

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

Для случая скалярных управлений сингулярными оказываются точки на границе сечения W(ti), для которых конус внешних нормалей содержит нормали отрезков вектограмм P(ti) и Q(ti) игроков.

Bernhard P. Singular Surfaces in Differential Games: an Introduction // Differential Games and Applications. Springer-Verlag, Berlin, 1977. pp. 1–33.

Melikyan A.A. Generalized Characteristics of the First Order PDEs: Applications in Optimal Control and Differential Games. Burkhuser, Boston, 1998.

Классификация типа сингулярности основана на анализе дополнительных меток, которые присваиваются векторам, описывающим строение положительно-однородной кусочно-линейной функции (·, ti) (3), и затем проходят сквозь процесс построения выпуклой оболочки этой функции. Для выделения сингулярных точек некоторых типов дополнительно требуется анализ негладкости соответствующих вершин многоугольника W(ti). Вершина называется гладкой, если ее конус внешних нормалей имеет раствор меньше заданного порога.

Для случая строго выпуклых ограничений обнаружение особых точек основано на поиске негладких вершин построенного сечения W(ti). Найденные точки связываются с точками на предыдущем сечении W(ti+1). Точки считаются соответствующими, если их конусы внешних нормалей пересекаются. Классификация сингулярных точек основана на анализе развития конуса. Если в обратном времени конус раскрывается, точка помечается как рассеивающая. Если конус сужается, точка помечается как фокальная. Если конус поворачивается (необязательно сохраняя величину раствора), то точка помечается как экивокальная.

Приведем результаты построения сингулярных поверхностей в игре конфликтно-управляемый осциллятор :

1 = x2 + v, 2 = -x1 + u, t [0, 8], (7) |u| 1, |v| 0.9, (x1, x2) = x2 + x2.

1 Рисунок 5 показывает два ракурса системы сингулярных поверхностей для игры (7) в исходных координатах x1, x2. Сингулярные поверхности разного типа отмечены соответствующими цифровыми выносками. В пояснении к выноскам добавочные слова за первого игрока означают, что на соответствующей поверхности скачком меняется управление первого игрока. При этом оптимальное управление второго игрока одно и то же по разные стороны вблизи от поверхности. Добавочные слова за обоих игроков означают скачкообразное изменение оптимального управления каждого игрока.

Обратное время на рис. 5 идет справа налево. Вблизи начала обратРис. 5: Два ракурса системы сингулярных поверхностей для задачи конфликтно-управляемый осциллятор (7): 1 поверхность переключения за первого игрока, 2 поверхность рассеивания за второго игрока, 3 экивокальная поверхность, 4 поверхность рассеивания за обоих игроков ного времени видны огрехи восстановления рассеивающей поверхности.

На поверхностях нанесена сетка связей соответственных точек: одно семейство линий, вертикальное, показывает связи между точками, снятыми с разных мостов в один и тот же момент времени; другое семейство, продольное связи между точками, снятыми с одного моста.

Видно, как некоторые линии сетки, идущие вдоль мостов, сходятся к центру. Это объясняется тем, что отдельные мосты обрываются; при этом размеры их сечений уменьшаются.

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

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

После проверки алгоритма построения и классификации сингулярных поверхностей на различных вариантах классических примеров материальная точка на прямой и конфликтно-управляемый осциллятор были исследованы сингулярные поверхности в других задачах.

Был, в частности, обнаружен пример, названный кнопка. Соответствующая дифференциальная игра описывается соотношениями 1 = x1 + 2x2 + v1, |u| 1, (v1, v2)T Q, (8) 2 = x2 + u + v2, (x1, x2) = x2 + x2.

1 Общий вид характерного максимального стабильного моста в исходных координатах x1, x2 приведен на рис. 6. Стабильный мост просчитан для случая, когда множество Q было выбрано в виде отрезка {|v1| 0.9, v2 = 0}. Значение платы было взято равным c = 7.0.

Рис. 6: Общий вид характерного множества уровня функции цены для игры (8) Обрыв моста произошел в момент = 6.9 обратного времени.

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

Структура сингулярных поверхностей в этом примере типична: начальные лепестки рассеивающей поверхности за второго игрока и поверхности переключения за первого сливаются затем в экивокальную поверхность, которая в центре у оси времени переходит в рассеивающую поверхность за обоих игроков.

Рассматриваемый пример был использован для исследования зависимости строения сингулярных поверхностей от параметров игры. Для одного и того же интервала значений платы c [0.5, 7.0] было просчитано шесть вариантов игры с различным размером и ориентацией отрезка Q ограничения на управление второго игрока. Были взяты два размера отрезка Q: отрезок длины 1.8 случай сильного первого игрока и отрезок длины 2.2 случай слабого первого игрока. (В первом случае длина отрезка Q меньше длины отрезка P, а во втором больше.) Для каждого из этих случаев просчитывалось три варианта с различным вариантом положения отрезка Q. Он брался с серединой в начале координат, но с разной ориентацией:

а) отрезок Q на горизонтальной оси v1:

2 Q = {v2 = 0} {v1 + v2 l2};

б) отрезок Q на биссектрисе первого и третьего координатных углов:

2 Q = {v1 = v2} {v1 + v2 l2};

в) отрезок Q на вертикальной оси v2:

2 Q = {v1 = 0} {v1 + v2 l2}.

Здесь l половина длины отрезка Q, равная, соответственно, 0.9 или 1.1.

Pages:     | 1 || 3 |






© 2011 www.dissers.ru - «Бесплатная электронная библиотека»