Моделирование управления маневрирующими объектами в условиях конфликта тема автореферата и диссертации по механике, 01.02.01 ВАК РФ

РОССИЙСКАЯ АКАДЕМИЯ НАУК ИНСТИТУТ ПРОБЛЕМ МЕХАНИКИ

На правах рукописи

<—тт

УТЕМОВ Александр Евгеньевич

МОДЕЛИРОВАНИЕ УПРАВЛЕНИЯ

МАНЕВРИРУЮЩИМИ ОБЪЕКТАМИ В УСЛОВИЯХ КОНФЛИКТА

01.02.01 — теоретическая механика

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

Москва — 2006

Работа выполнена в Институте проблем механики РАН

Научный руководитель:

академик РАН Ф. Л. Черноусько

Официальные оппоненты: член-корреспондент РАН Ярошевский В. А., доктор физико-математических наук, профессор Братусь А. С.

Ведущая организация:

Институт проблем управления РАН

Защита состоится 5 октября 2006 года в 15:00 на заседании диссертационного совета Д 002.240.01 при Институте проблем механики РАН по адресу: 119526, Москва, проспект Вернадского, 101-1, ИПМех РАН.

С диссертацией можно ознакомиться в библиотеке Института проблем механики РАН.

Автореферат разослан "_"_ 2006 года.

Ученый секретарь

диссертационного совета Д 002.240.01

кандидат физико-математических наук, '^^^^"Сысоева Е. Я.

4

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

Актуальность темы. Для моделирования процесса управления двумя или несколькими движущимися объектами в условиях конфликта, когда перед маневрирующими объектами стоят противоположные цели, а их возможности различны, широко используется аппарат теории дифференциальных игр, получивший значительное развитие в последние десятилетия. Становление теории дифференциальных игр связано с именами Р.Айзекса, Р.Беллмана, Л.С.Понтрягина, Н.Н.Красовского. Существенные результаты по теории дифференциальных игр и оптимального управления получены в работах: В. Г. Болтянского, Р. В. Гамкрелидзе, А.Б.Куржанского, А.А.Меликяна, Е.Ф.Мищенко, Ю.С.Осипова, А. А. Петросяна, Б. Н. Пшеничного, А. И. Субботина, А.Г.Ченцова, Ф.Л.Черноусько, А.А.Чикрия и других авторов. Среди зарубежных специалистов отметим: Дж. Брекуэлла, В. Флеминга, А. Фридмана и др.

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

РОС. НАЦИОНАЛЬНАЯ БИБЛИОТЕКА С.-Петербург

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

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

Исследование задач подобного типа не было достаточно интенсивным вследствие их большей сложности, по сравнению с задачами, использующими функционалы традиционного типа. В последнее десятилетие завершен серьезный этап в обосновании метода динамического программирования для задач оптимального управления и дифференциальных игр. Появились эффективные методы анализа и построения особых (сингулярных) траекторий, решения задач с неизвестными границами, с неаддитивными функционалами. В связи с этим отметим работы А.И.Субботина, А.А.Меликяна, С.Реггеуга.

В диссертации для построения субоптимального синтеза в исходной игровой задаче предлагается использовать численные методы. Эти методы следуют идее, предложенной в работах Ф. Л. Черноусько, А.А.Меликяна и основываются на некотором прогнозе относительно движения преследуемого игрока. Этот прогноз заключаются в предположении, что преследуемый игрок, начиная с текущего момента времени, применяет некоторое заданное программное управление. Такое упрощение позволяет свести исходную игровую задачу к задаче оптимального управления для одного игрока, решение которой в одних случаях удается получить аналитически, а в других - численно. Далее, на основе построенного синтеза для упрощенных задач, рассматриваются различные стратегии преследования первым игроком второго. Полу-

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

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

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

Научная новизна. Основные результаты диссертации являются новыми, получены автором самостоятельно и опубликованы. На защиту выносятся следующие результаты:

1. Реализация синтеза и доказательство его оптимальности для случая, когда преследуемый игрок неподвижен.

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

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

4. Разработка численного алгоритма построения барьерных поверхностей для определения минимального радиуса захвата преследуемого игрока. Исследование этих поверхностей с использованием трехмерной компьютерной графики. Построение особых траекторий, на которых управление первого игрока равняется нулю. Исследование структуры особых траекторий.

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

движения второго игрока и решенных задач оптимального управления.

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

Достоверность полученных результатов вытекает из корректности постановок исследуемых задач и строгого применения математических методов. Результаты компьютерного моделирования подтверждают теоретические выводы.

Апробация работы. Результаты диссертации докладывались:

— на IX Всероссийском съезде по теоретической и прикладной механике (Н.Новгород, 2006 г.)

— на семинаре Института проблем механики РАН 'Теория управления и динамических систем" (руководитель семинара - академик РАН Ф. JI. Черноусько)

— на научных конференциях Московского Физико - технического института (Москва, Долгопрудный - 2003, 2004, 2005 гг.)

Публикации. По теме диссертации опубликовано 7 работ, в том числе в журналах Российской академии наук [1, 2, 3] и трудах научных конференций [4, 5, 6, 7].

Структура диссертации. Диссертация состоит из введения, 3 глав, приложения и списка литературы. Общий объем диссертации 103 страницы, набранных в текстовом редакторе LATEX. Библиографический список содержит 69 наименования.

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ Во введении формулируется цель работы, обосновывается актуальность рассматриваемой задачи, в сжатом виде излагается содержание всех глав, дал обзор литературы по теме диссертации.

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

Игра происходит на плоскости. В ней участвуют два игрока: преследователь Р (первый игрок) и убегающий Е (второй игрок). Скорости игроков Р и Е постоянны, а радиусы кривизны траекторий движения ограничены снизу заданными величинами. В качестве фазовых координат системы удобно взять следующие: х\ — расстояние между игроками и углы хг, хз, которые составляют векторы скоростей первого и второго игроков соответственно с отрезком РЕ (рис. 1).

Рис. 1

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

х — Асозжз — СО8Х2, ¿2 = а — и, хз — ¡IV — а (1)

с ограничениями

М < 1, м < 1. (2)

Здесь и, V — управляющие параметры игроков Р и Е соответственно, <т = (втхг + Л8шха)/х1, а постоянные А, ц равны соот-

ветственно линейной и максимальной угловой скоростям игрока Е. Предполагается, что оба игрока в каждый момент времени t могут точно измерить фазовый вектор системы x(t).

В фазовом пространстве х = (xi, 12, хз) £ Я3 определена скалярная функция S(x), называемая функцией качества. Платой в игре является значение минимума по времени

J[x°,u,v] = min5(a;(i;a;0,'U,t;)) ->• minmax, х — (xi,Х2,жз), (3)

где x(t;x°,u,v) — решение уравнений динамики (1) на полубесконечном интервале t > 0, отвечающее начальному значению х° и некоторым допустимым управлениям и, v игроков Р, Е. Эту величину первый игрок стремится минимизировать выбором управления и, а второй - максимизировать за счет v. Управления и, v могут быть программными или в форме синтеза; основное требование к ним подразумевает существование решения системы (1).

Предполагается, что функция качества S(x 1, хг, хз) имеет следующий вид

S{xi, Х2, х3) = j4i(xi - R)2 + А2sin2(x2/2) + A3sin2(x3/2), (4)

где Ai, А2, Лз, R — заданные положительные постоянные. Эта функция может трактоваться как функция, характеризующая вероятность поражения второго игрока первым из позиции х = (xi, Х2, х3). Чем меньше значение функции 5(х) в данный момент времени, тем предпочтительней положение первого игрока для поражения второго.

Такую модель использовали Ю.Н.Желнин1 и В.А.Ярошевский2 при исследовании оптимального маневрирования самолетов с установившимися в горизонтальной плоскости скоростями в условиях конфликтной ситуации.

1Желиин Ю.Н. Линеаризованная задача преследования и уклонения на плоскости// Ученые записки ЦАГИ. 1977. Т. 8. № 3.

2Ярошевский В.А., Круглое Б.П., Кузьмин В.П. Оптимальные маневры в плоской задаче// Тр. ЦАГИ. 1975. № 1203.

Следует также отметить, что впервые задача (1-3) была сформулирована и качественно исследована в работе Р.Айзекса3. Здесь она использовалась для моделирования игры двух автомобилей, причем функция качества (4) зависела только от расстояния между игроками (А\ ф О, R = Ач — A3 = 0 в (4)).

В данной работе показано, что в силу инвариантности уравнений динамики (1) относительно следующей замены фазовых координат

/г /

Х1 = Xl, х2 = —Х2, х3 = —Хз

для построения синтеза достаточно рассмотреть некоторую область фазового пространства. Далее эта область разбивается на две подобласти, в зависимости от значения расстояния xi между игроками. В первой подобласти (подобласть Gi) расстояние между игроками мало, и задача первого игрока здесь заключается в уменьшении начальных значений углов хг и Во второй подобласти (подобласть G2) начальное расстояние между игроками велико и основную роль в функции качества играет фазовая координата х\. Поэтому в Gi стратегия первого игрока должна быть направлена на уменьшение расстояния между игроками. При этом значениями углов и хз можно пренебречь. Это позволяет первому игроку эффективно использовать в Gi довольно простой метод — преследование вдоль линии визирования. Применяя эту стратегию, первый игрок приводит систему в подобласть Gi, где ее дальнейшее использование становится неэффективным. В G\ первый игрок должен оптимизировать уже не только расстояние между игроками, но и направления векторов скоростей. Поэтому здесь имеет место сложное маневрирование двух игроков.

Для построения синтеза в области Gi предлагается использовать метод прогнозирования движения преследуемого игрока, предложенный Ф.Л. Черноусько и A.A. Меликяном4. Приводятся

3 Айзеке Р. Дифференциальные игры М.-. Мир, 1967. 479 с.

4 Черноусько Ф. Л., Меликян A.A. Игровые задачи управления и поиска.

М.: Наука, 1978. 270 с.

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

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

В первой задаче предполагается, что, следующие три параметра в соотношениях (1), (4) обращаются в нуль:

Физически этот предельный случай означает, что преследуемый игрок неподвижен, а функция качества (4) не зависит от угла хз.

Показано, что при упрощениях (5) существует бесконечное множество стратегий и*(£) преследующего игрока, приводящих систему в наилучшую для этого игрока позицию (Я, 0, 0) (см. рис. 2), соответствующую точке О фазового пространства.

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

На основе принципа максимума Понтрягина предложен некоторый синтез управления. Показано, что реализованный синтез удовлетворяет всем условиям регулярности5 и, следовательно, яв-

6 Болтянский В. Г. Математические методы оптимального управления. М.: Наука, 1969. 407 с.

Л = 0, М = 0, Аз = 0.

(5)

Рис. 2

ляется оптимальным. В фазовом пространстве координат (2:1,2:2) оптимальные траектории имеют вид, представленный на рис. 3.

Во второй задаче также полагается, что преследуемый игрок неподвижен, но в отличие от первой задачи, предполагается справедливым неравенство A3 Ф 0 в (4). Это означает, что задано направление движения, по которому первый игрок должен приблизиться ко второму. Показано, что в этом случае также целесообразно рассматривать задачу достижения наилучшей для первого игрока позиции за минимальное время. При этом исходная игровая задача сводится к трехмерной задаче оптимального быстродействия.

С использованием результатов работ Ю.И.Бердышева6, В. С. Пацко, С.Г.Пятко, А.А.Федотова7 предлагается синтез и доказывается его оптимальность.

В третьей задаче исследуется случай, когда скорость преследуемого игрока отлична от нуля (Л > 0 в (1)), а его управление постоянно на всем интервале движения. Показано, что при пре-

6 Бердышев Ю. И. Синтез оптимального управления для одной системы 3-го порядка // Вопросы анализа нелинейных систем автоматического управления: Тр. ИММ УНЦ АН СССР Свердловск, 1973. Вып. 12. С. 91-101.

7Пацко В. С., Пятпко С.Г., Федотов A.A. Трехмерное множество достижимости нелинейной управляемой системы // Изв. РАН. Теория и системы управления. 2003. №3. С. 8-16.

Рис. 3

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

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

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

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

При построении барьерных поверхностей предполагается, что функция качества S{x) в (3) квадратична по своим переменным и имеет вид

S(xi, Х2, х3) = Ai(ari - R)2 + А2х\ + А3х\, (6)

где Ai, А2, A3, R — заданные положительные постоянные. Таким образом, поверхностями уровня функции S(x) являются эллипсоиды с центром в точке 0(R, 0,0). Функция качества (6) по прежнему характеризует вероятность поражения преследуемого игрока из текущей позиции. Нетрудно показать, что (6) получается из (4) разложением в ряд Тейлора по фазовым координатам х^, х$ в окрестности прямой х2 — жз = 0. Упрощенный вид функции качества позволяет качественно исследовать структуру барьерных поверхностей.

Для определения минимального радиуса захвата исходная игровая задача степени рассматривается как ряд последовательно решаемых задач качества, в которых терминальным множеством является семейство поверхностей, образованных различными значениями функции S(x)

S(x) = p2.

Здесь р — параметр задачи качества (р > 0). При фиксированном параметре р—ро соответствующий эллипсоид считается границей терминального множества С. В задаче качества игрок Р стремится привести фазовый вектор на множество С, а игрок Е противодействует этому.

Используемый подход заключается в следующем. Варьируется величина ро и для каждого из значений решается задача качества, т.е. находятся барьерные поверхности, разделяющие фазовое про-J странство на области, из которых можно проникнуть внутрь тер-

минального множества и из которых этого сделать нельзя. Минимальное значение параметра р = pj, при котором барьерные 1 поверхности начинают полностью смыкаться, определяет мини-

мальное значение функции качества, которое может быть достигнуто в этой задаче Sm[a — pj . Это решение условно называется "предельным". Предельный характер решения состоит в том, что преследующий, несмотря на все усилия, не может проникнуть внутрь терминального множества сколь долго бы процесс преследования ни продолжался. Следовательно, цена игры вне области, ограниченной предельными барьерными поверхностями, остается постоянной. Это указывает на то, что оптимальные управления игроков в этой области могут быть неединственными. Наличие такого типа оптимальных решений в игровой задаче является достаточно характерным8. Неединственность решения вне предельной области позволяет, в частности, сформулировать дополнительный

8Melikyan A., Akhmetzhanov A. A linear 2D differential game with a minimumtype cost function// 11 Internat. Symp. on Dynamic Games and Applications. Proceedings V. 2. Tucson Arisona. 2004. P. 637-649.

критерий, что позволяет выделить однозначную ветвь решения.

Для исследования барьерных поверхностей применяются численные методы, основанные на построении регулярных (классических) характеристик уравнения Айзекса - Беллмана которое для рассматриваемой задачи имеет вид

min max {v\i\ + + ^з^з) = (7)

и V

= Vi (А cos х3 - соэжг) + (i>2 - )сг - \и2\ + мкз| = 0.

Здесь геометрический смысл вектора и = (^1,^2,^3) ~~ внешняя нормаль к терминальному множеству в точке (х1,х2,хз). Этот вектор является градиентом некоторой вспомогательной скалярной функции, для которой барьерная поверхность является поверхностью уровня. Экстремальные управления ü,v, доставляющие минимум и максимум (7), определяются выражениями

й — sign t/2, v = sign 1/3.

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

В качестве примера рассматривается полная картина барьерных поверхностей при Ai = i,i = 1 — 3 в (б), А = 0.8, ц — 0.7 в (1). Такое соотношение скоростей игроков соответствует тому, что преследователь имеет преимущество и в линейной и в угловой скоростях. При ро = 0.4 барьерные поверхности полностью смыкаются и имеют вид, представленный на рис. 4. Здесь допустимая область на эллипсоиде выделена светлым, а ее граница отмечена знаками "+". Эта область определяет множество точек в которых преследователь, несмотря на противодействие преследуемого, выбором своего управления может заставить систему проникнуть внутрь эллипсоида и тем самым уменьшить значение функции качества. Траектории, стартующие из границы допустимой области

при Х2 > 0 можно разделить на два типа: Р(++) и Р(Н—). Точки окончания этих траекторий отмечены на рисунке соответственно знаками "о" и "*". Траектории типа Р{++) характеризуются тем, что для них значения управлений игроков равны и = V = 1. В абсолютном пространстве это соответствует ситуации, когда оба игрока движутся вдоль окружностей наименьшего радиуса в одном и том же направлении (по часовой стрелке). При движении по траекториям типа Р(-|—) управления имеют противоположные знаки: и = 1, V = — 1. В этом случае игроки перемещаются по окружностям в разных направлениях, первый игрок — по часовой стрелке, а второй - против нее. При х2 < 0 барьерные траектории симметрично отображаются относительно прямой Х2 = жз = 0, а значения управлений на них меняют знак на противоположный.

Рис. 4

Траектории типа Р(++) и —) смыкаются в боковой части эллипсоида, образую незаполненную область в окрестности точки F(R + ро\/Я7,0,0). Показано, что в окрестности точки F смыкание барьерных поверхностей формируется за счет особых траек-

торий, стартующих из точек и въ в которых нарушается гладкость границы допустимой области. Через 7 (см. рис. 4) обозначена кривая пересечения барьерных поверхностей.

При ро = 0.7 картина барьерных поверхностей имеет вид, представленный на рис. 5.

Рис. 5

В этом случае структура барьеров в окрестности точки Р качественно не изменяется, но нарушается непрерывность кривой 7, что приводит к их размыканию в боковой части эллипсоида. Через образованное пространство между барьерными поверхностями преследователь может добиться проникновения фазовой точки внутрь эллипсоида, обеспечив себе меньшее значение функции качества.

Численно варьируя значение параметра ро от 0.4 до 0.7, можно определить предельное значение ро = при котором барьеры начинают размыкаться. В данном примере это значение равно Р*0 = 0.5.

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

алгоритмы преследования второго игрока первым в области G\. Предлагаемые численные алгоритмы используют позиционные стратегии, в которых управления и и и в момент времени t определяются равенствами

u(t) = Л(г(4), ¥>i(t), <Р2(«)), v{t) = /а(г(<), fi(t), <p2{t)), (8)

где /i и /2 - некоторые функции, характеризующие стратегию каждого игрока. Множество значений этих функций дискретно E(fi) = Е(/г) = {—1,0,1}. Так как в области G\ расстояние между игроками мало (¡ci ~ R), то при построениях полагается, что минимальное значение функции качества достигается на некотором ограниченном отрезке [О, Г]. Далее этот отрезок покрывается достаточно мелкой равномерной сеткой и считается, что игроки могут менять свое управление лишь в узлах сетки, а внутри каждого интервала оно постоянно. При этом в узлах сетки управления uni) динамически пересчитываются в соответствии с равенствами (8).

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

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

Публикации по теме диссертации

[11 Желнин Ю. Я., Меликян А. А., Утемов А. Е., Черноусь-ко Ф. Л. Наискорейшее приведение нелинейного маневрирующего объекта в оптимальную позицию. ПММ, 2005, т.69, вып.2, с.179-190.

[2] Желнин Ю. #., Утемов А. Е. Построение барьерных поверхностей в одной игровой задаче преследования-уклонения. Изв. РАН. Теория и системы управления. 2005. №5. С. 87-95.

[3] Утемов А. Е. Численные алгоритмы оптимизации управления в одной задаче преследования-уклонения. Изв. РАН. Теория и системы управления. 2006. №3. С. 63-81.

[4] Утемов А. Е. Частный случай дифференциальной игры преследования // Тезисы докладов: XLVI научная конференция МФТИ. Москва - Долгопрудный: МФТИ, 2003, часть III, с. 42.

[5] Утемов А. Е. Численное построение минимального радиуса захвата в дифференциальной игре преследования // Тезисы докладов: XLVII научная конференция МФТИ. Москва -Долгопрудный - Жуковский: МФТИ, 2004, часть II, с. 95.

[6] Утемов А. Е. Разработка численных алгоритмов расчета управления движением в одной игровой задаче преследования - уклонения // Тезисы докладов: XLVIII научная конференция МФТИ. Москва - Долгопрудный: МФТИ, 2005, часть III, с. 239.

[7| Желнин Ю. Н, Утемов А. Е. Численный алгоритм реализации субоптимального синтеза в игровой задаче преследования - уклонения на плоскости //IX Всероссийский съезд по теоретической и прикладной механике. Н.Новгород, 2006. Тезисы докладов.

Утемов Александр Евгеньевич

Моделирование управления маневрирующими объектами в условиях конфликта

Автореферат диссертации на соискание ученой степени кандидата физико-математических наук

Подписано к печати 07.07.2006. Заказ №11-2006г. Тираж 80 экз.

Отпечатано на ризографе, ИПМех РАН 119526 Москва, проспект Вернадского, д. 101, к. 1.

PI 5 8 9 0

-ÍSTS3 3

f

Введение.

Глава 1. Общий подход к моделированию игровой задачи преследования - уклонения

1.1 Постановка игровой задачи. Функция качества.

1.2 Разделение фазового пространства на подобласти.

Применение позиционных стратегий в каждой подобласти

1.3 Использование гипотез о поведении преследуемого игрока. Сведение игровой задачи к задачам оптимального управления

Глава 2. Решение задач оптимального управления

2.1 Реализация оптимального синтеза для случая

A = /i = A2 =

2.1.1 Формулировка задачи оптимального управления

2.1.2 Синтез управления

2.1.3 Обоснование оптимальности синтеза

2.2 Случай Л = /г = О, А2 Ф

2.2.1 Структура оптимальных траекторий.

2.2.2 Расчет оптимальной траектории

2.3 Случай применения преследуемым игроком постоянного управления при А^Ои/л^О ■ 2.3.1 Движение с постоянной кривизной траектории

2.3.2 Прямолинейное движение

Глава 3. Численное моделирование.

3.1 Построение барьерных поверхностей

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

3.1.2 Вспомогательная задача качества

3.1.3 Численный пример

3.1.4 Особые траектории

3.1.5 Полная картина барьерных поверхностей

3.2 Описание численных алгоритмов преследования второго игрока в области G

3.2.1 Метод локальной оптимизации

3.2.2 Стратегия преследования вдоль линии визирования

3.2.3 Метод преследования, основанный на оптимальном N синтезе для трехмерной упрощенной задачи.

3.2.4 Метод преследования, основанный на гипотезе о движении преследуемого с постоянной кривизной траектории

3.2.5 Метод преследования, основанный на гипотезе о прямолинейном движении преследуемого

3.3 Примеры реализации рассмотренных алгоритмов преследования при малых отклонениях фактического движения преследуемого игрока от прогнозируемого

3.4 Численный пример задачи реализации субоптимального синтеза в подобласти фазового пространства.

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

Для моделирования процесса управления двумя или несколькими движущимися объектами в условиях конфликта, когда перед маневрирующими объектами стоят противоположные цели, а их возможности различны, широко используется аппарат теории дифференциальных игр, получивший значительное развитие в последние десятилетия [1,15,30,31,44, 46, 55]. В этих задачах традиционно рассматриваются интегральные или терминальные функционалы, которые обеспечивают применимость метода динамического программирования во всей рассматриваемой области [1, 46]. Однако для практики представляют большой интерес также задачи оптимального управления и дифференциальных игр, в которых минимизируемым (максимизируемым) функционалом является максимальное (минимальное) значение некоторой скалярной функции фазового вектора вдоль траектории динамической системы. Интервал времени может быть конечным или бесконечным. Оптимальные траектории таких задач лишь частично удовлетворяют принципу оптимальности Беллмана. Если у рассматриваемой траектории и ее последнего фрагмента минимум функции качества достигается в будущем, то принцип оптимальности выполнен, а в противном случае он, как правило, не имеет места. Поэтому метод динамического программирования приводит здесь к задаче со свободной границей.

При моделировании воздушного боя двух самолетов с помощью диф-л < ференциальной игры с функционалом типа минимума одной из возможных трактовок упомянутой скалярной функцией является вероятность поражения противника при применении некоторого средства поражения (оружия) в данной точке фазового пространства. Тогда атакующий самолет стремится занять позицию с максимально возможной вероятностью поражения и затем применить оружие.

Исследование задач подобного типа не было достаточно интенсивным вследствие их большей сложности, по сравнению с задачами, использующими функционалы традиционного типа. В последнее десятилетие завершен серьезный этап в обосновании метода динамического программирования для задач оптимального управления и дифференциальных игр [31, 67]. Появились эффективные методы анализа и построения особых (сингулярных) траекторий [18, 57], решения задач с неизвестными границами [48, 51].

Некоторые необходимые условия оптимальности для игровых задач с подобным функционалом рассмотрены в [48, 57], задачи оптимального управления со свободной границей (имеющей иную природу) решены в [51]. В [57, 59] с помощью метода сингулярных характеристик построена неизвестная граница в игровой задаче сближение на конической поверхности с простым движением игроков.

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

В силу указанной выше специфики, для построения субоптимального синтеза в исходной игровой задаче предлагается использовать численные методы. Эти методы следуют идее, предложенной в [44], и основываются на некотором прогнозе относительно движения преследуемого игрока. Этот прогноз заключаются в предположении, что преследуемый игрок, начиная с текущего момента времени, применяет некоторое заданное программное управление. Такое упрощение позволяет свести исходную игровую задачу к задаче оптимального управления для одного игрока, решение которой в одних случаях удается получить аналитически [4, 5, 10, И, 14, 22], а в других - численно [3, 8, 21, 42, 44, 64]. Далее, на основе построенного синтеза для упрощенных задач, рассматриваются различные стратегии преследования первым игроком второго. Полученные таким образом стратегии используются для построения субоптималь-л ного синтеза в исходной игровой задаче.

Модельные уравнения движения

В диссертации рассматривается игровая задача на плоскости. В ней участвуют два игрока: преследователь Р (первый игрок) и убегающий Е (второй игрок). Скорости игроков Р и Е постоянны и равны V\ и V2, а радиусы кривизны траекторий движения ограничены снизу заданными величинами R\ и R2 соответственно. Предполагается, что оба игрока в каждый момент времени управляют выбором значения кривизны своей траектории, располагая информацией о текущем положении системы в фазовом пространстве координат (г, <р\, ^2) и о величинах Vi, V2, R\, Я2. Здесь г — расстояние между игроками, а (9^2) ~ угол между векторами скорости первого (второго) игрока и отрезком РЕ. Угол <pi отсчитывается против часовой стрелки, угол ср2 — по часовой стрелке, (рис. 0.1).

Такая динамика игроков в рассматриваемой задаче соответствует известной игре двух автомобилей, которая была впервые сформулирована и качественно исследована в книге Р. Айзекса [1].

Используя выкладки, аналогичные проделанным ранее [1], можно показать, что динамика относительного положения игроков описывается нелинейной системой трех дифференциальных уравнений

Рис. 0.1 г = v2 cos <Р2 — Vi cos ifi,

0.0.1) щ =

Vi sin <pi + V2 sin ip2 Vi . У2

--—(p2 = —V

Ri

R2

Vi sin (pi + V2 sin <p2 r r и ограничениями и\ < 1, М < 1

0.0.2)

Здесь и, v — управляющие параметры игроков Р и Е.

Роли игроков фиксированы, а минимизируемым (первым игроком) и максимизируемым (вторым игроком) функционалом является минимальное значение заданной скалярной неотрицательной функции 5(r, ip\, <£>2) (функции качества) фазового вектора вдоль траектории динамической системы на достаточно большом промежутке времени. Функция качества S(r, (pi, (Р2) характеризует вероятность поражения второго игрока первым из текущей позиции. Для рассматриваемой задачи она имеет вид

S{r, <ph ср2) = Аг{г - Я)2 + А2 sin%i/2) + А3 sin2(<p2/2) (0.0.3)

Нулевое значение функции качества соответствует ситуации, когда преследователь находится позади преследуемого на заданном расстоянии от него, а векторы скоростей сонаправлены и лежат на одной прямой (см. рис. 0.2).

Отождествляя углы <ph щ кратные 27Г, будем считать, что в этой позиции фазовый вектор системы находится в точке 0(i?,O,O).

Такая задача возникает при исследовании оптимального маневрирования самолетов с установившимися в горизонтальной плоскости скоростями в условиях конфликтной ситуации [10, 13, 45].

Основное отличие рассматриваемой задачи от работ этого направления [1, 10, 13, 28, 29, 38, 39, 45, 49, 50, 54, 56, 60, 66, 69] заключается в структуре функции качества (0.0.3), в состав которой, кроме расстояния, Р

Рис. 0.2 входит угловое положение векторов скорости относительно линии визирования.

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

Следует также отметить, что используемая в работе модель применялась различными авторами для постановок как игровых задач [13, 23, 27, 28, 29, 32, 49, 55, 62, 63, 65, 68], так и для задач оптимального управления [2, 4, 5, 7,17, 25, 26, 66]. В частности, в [4] синтезировано оптимальное управление, обеспечивающее наискорейшее попадание автомобиля из начального состояния в фиксированную точку плоскости движения. Эта же задача, но при более сложной модели движения, описываемой нелинейной системой четвертого порядка, решена в [5].

Подобная игровая задача, известная как "игра двух автомобилей", но с другой скалярной функцией качества рассмотрена в [1, 47, 69], где получена зависимость радиуса захвата, обеспечивающего перехват менее скоростного, но более маневренного преследуемого, от линейных скоростей и максимальных скоростей разворота автомобилей. В [61] рассмотрен частный случай игровой задачи двух автомобилей, в которой и линейные, и угловые скорости обоих игроков полагаются равными.

Кроме того, в [16] исследовалась игровая задача двух автомобилей, в которой скорость преследуемого игрока полагалась малой по сравнению со скоростью преследователя (V2 <С V\ в (0.0.1)). В этой работе, с помощью метода малого параметра [40, 41], получен синтез, отражающий качественный характер оптимального управления игроков при малых скоростях преследуемого игрока.

Краткое содержание диссертации.

Диссертация состоит из введения, трех глав, приложения и списка литературы.

1. Айзеке Р. Дифференцальные игры. М.: Мир, 1967. 479 с.

2. Алешков Ю. 3. Оптимальный вывод точки на траекторию, соответствующую требуемому методу наведения // Вестник ЛГУ, матем., мех., астроном., 1963, № 19, С. 85-91.

3. Братусъ А. С. Метод малого параметра для построения приближенных стратегий одного класса дифференциальных игр // ПММ. 1975. Т. 39. Вып. 6. С. 1006-1016.

4. Бердышев Ю. И. Синтез оптимального управления для одной системы 3-го порядка // Вопросы анализа нелинейных систем автоматического управления: Тр. ИММ УНЦ АН СССР Свердловск, 1973. Вып. 12. С. 91-101.

5. Бердышев Ю. И. Синтез оптимального по быстродействию управления для одной нелинейной системы четвертого порядка // ПММ. 1975. Т. 39. Вып. 6. С. 985-994.

6. Болтянский В. Г. Математические методы оптимального управления. М.: Наука, 1969. 407 с.

7. Болычевцев Э. М. Одна задача оптимального управления // Вестн. МГУ. Сер. 1. Математика, механика. 1968. Ш. С. 91-98.

8. Брайсон А., Хо Ю-Ши Прикладная теория оптимального управления управления. М.: Мир, 1972.

9. Васильев Ф. П. Численные методы решения экстремальных задач. М.: Наука, 1980.

10. Желнин Ю.Н. Линеаризованная задача преследования и уклонения на плоскости// Ученые записки ЦАГИ. 1977. Т. 8. № 3.

11. Желнин Ю. Н., Утемов А. Е. Построение барьерных поверхностей в одной игровой задаче преследования-уклонения. Изв. РАН. Теория и системы управления. 2005. №5. С. 87-95.

12. Желнин Ю. Н, Утемов А. Е. Численный алгоритм реализации субоптимального синтеза в игровой задаче преследования уклонения на плоскости //IX Всероссийский съезд по теоретической и прикладной механике. Н.Новгород, 2006. Тезисы докладов.

13. Желнин Ю. #., Шилов Ю. Я. Нелинейная игровая задача преследования на плоскости // Уч. зап. ЦАГИ. 1974. Т. 5. № 5.

14. Желнин Ю. Я., Меликян А. А., Утемов А. Е., Черноусъко Ф. JI. Наискорейшее приведение нелинейного маневрирующего объекта в оптимальную позицию. ПММ, 2005, т.69, вып.2, с. 179-190.

15. Красовский Н.Н., Субботин А.И. Позиционные дифференциальные игры. М., Наука, 1974.

16. Корнеев В. А., Меликян А. А. Оптимальный синтез в игровой задаче преследования с малым параметром. Известия академии наук СССР. Техническая кибернетика. 1982, N2 3.

17. Кукушкин А. П. Исследование структуры оптимальных по быстродействию траекторий в плоском поле тяготении // Вопросы оптимизации нелинейных систем автоматического управления. Тр. ИММ УНЦ АН СССР. Вып. 12. Сверловск, 1975.

18. Меликян А. А. Сингулярные характеристики уравнений в частных производных первого порядка// ДАН. 1996. Т. 351. № 1. С. 24-28.

19. Меликян А. А., Овакимян Я. В. Дифференциальная игра простого сближения на многообразиях// ПММ. 1993. Т. 57. Вып.1. С. 41-51.

20. Моисеев Я. Я Численные методы оптимальных систем. М.: Наука, 1977.

21. Моисеев Я. Я. Элементы теории оптимальных систем. М.: Наука, 1975.

22. Пацко В. С., Пятко С.Г., Федотов А.А. Трехмерное множество достижимости нелинейной управляемой системы // Изв. РАН. Теория и системы управления. 2003. №3. С. 8-16.

23. Пацко В. С., Пятко С. Г,Кумков С. И. и др. Оценивание движения воздушного судна на основе информационных множеств при неполных замерах координат // Науч. докл. академии ГА. С.-Петербург. Екатеринбург: ИММ УрО РАН, 1999.

24. Понтрягин Л. С., Болтянский В. Г., Гамкрелидзе Р. В., Мищенко Е. Ф. Математическая теория оптимальных процессов. М.: Физматгиз, 1961. 391 с.

25. Проблемы механики управляемого движения // Сб. статей под ред. Верещагина И. Ф. Перм. ун-т. 1976. №8.

26. Репьях Н. А. Локально оптимальный синтез управления летательным аппаратом // Сб. статей под под ред. Верещагина И. Ф. Перм. ун-т. 1972. т.

27. Розенберг Г. С. Построение траекторий оптимального преследования // Автоматика и телемеханика. Т. 26. 1965. №4. С. 629-633.

28. Рубинович Е. Я. Дифференциальная игра программного преследования с ограничением на разворот преследуемого // Автоматика и телемеханика. 1996. №10. С. 76-94.

29. Рубинович Е. Я. Дифференциальная игра программного преследования с ограничением на разворот преследователя // Автоматика и телемеханика. 1978. №9. С. 38-44.

30. Субботин А. И. Обобщенные решения уравнений в частных производных первого порядка: перспективы динамической оптимизации. Москва-Ижевск, Институт компьютерных исследований, 2003.

31. Субботин А. И. Обобщенные решения уравнения Гамильтона-Якоби. М., Наука, 1995.

32. Симакова Э. Н. Об одной задаче преследования на плоскости // А и Т. 1968. №7.

33. Утемов А. Е. Численные алгоритмы оптимизации управления в одной задаче преследования-уклонения. Изв. РАН. Теория и системы управления. 2006. №3. С. 63-81.

34. Утемов А. Е. Частный случай дифференциальной игры преследования // Тезисы докладов: XLVI научная конференция МФТИ. Москва Долгопрудный: МФТИ, 2003, часть III, с. 42.

35. Утемов А. Е. Численное построение минимального радиуса захвата в дифференциальной игре преследования // Тезисы докладов: XLVII научная конференция МФТИ. Москва Долгопрудный - Жуковский: МФТИ, 2004, часть II, с. 95.

36. Утемов А. Е. Разработка численных алгоритмов расчета управления движением в одной игровой задаче преследования уклонения // Тезисы докладов: XLVIII научная конференция МФТИ. Москва -Долгопрудный: МФТИ, 2005, часть III, с. 239.

37. Федоренко Р. П. Приближенное решение задач оптимального управления. М.: Наука, 1978.

38. Хамса М. X., Колас И., Рунгалъдер В. Оптимальные по быстродействию траектории полета в задаче преследования. В кн.: Управление космическими аппаратами и кораблями. М.: Наука, 1971, с. 410-418.

39. Чериоусъко Ф. Л. Некоторые задачи оптимального управления с малым параметром. ПММ, 1968, т. 32, вып. 1.

40. Чериоусъко Ф. Л., Акуленко Л. Д., Соколов Б. Н. Управление колебаниями. М.: Наука, 1980.

41. Чериоусъко Ф. Л., Баничук Н. В. Вариационные задачи механики и управления. Численные методы. М.: Наука, 1973.

42. Черноусъко Ф. JI., Колмановский В. Б. Вычислительные приближенные методы оптимального управления. В кн.: Итоги науки и техн. Мат. анализ, т. 14. М., ВИНИТИ, 1977.

43. Черноусъко Ф. JI., Меликян А.А. Игровые задачи управления и поиска. М.: Наука, 1978. 270 с.

44. Ярошевский В.А., Круглое Б.П., Кузьмин В.П. Оптимальные маневры в плоской задаче// Тр. ЦАГИ. 1975. № 1203.

45. Bellman R. Dynamic programming // Princeton, N.J., Univ. Press; London, Oxford Univ. Press, 1957.

46. Breakwell J. V., Merz A. W. Minimum required capture radius in a copla-nar model of the aerial combat problem// J. American Institute of Aeronautics and Astronautics. 1977. V. 15. № 8.

47. Botkin N. D. Approximation schemes for finding the value functions for differential games with nonterminal payoff functional// Internat. J. Analysis and its Applications. 1994. V. 14. P. 203-220.

48. Cockayne E. Plane Pursuit with Curvature Constraints. SIAM Journal of Applied Mathematics, Vol. 15, Nov. 1967, pp. 1511-1516.

49. Cockayne E. J., Hall G. W. C. Plane motion of a Particle Subject to Curvature Constraints // SIAM J. Control, 1975, Vol. 13, No. 1, pp. 197-220.

50. Dorr oh J. R. and Ferreyra G. A free boundary problem in Rd with both smooth and nonsmooth fit. SIAM J. of Control and Optimization. 1998, V. 36, No 2, pp. 579-589.

51. Dubins L. E. On curves of minimal length with a constraint on average curvature and with prescribed initial and terminal positions and tangents, Armer. J. Math., 79 (1957). pp. 497-516.

52. Ferreyra G., Hijab O. A simple free boundary problem in Rd// SIAM J. Control and Optimization. 1994. V. 32. № 2. P. 501-515.

53. Imado F. Some features of the game between the supersonic ASM and the counterattack AMM.// International Game Theory Review. 2005. V. 7. № 3. P. 245-260.

54. Meier L. A new technique for solving pursuit-evasion differential games // IEEE Trans. Automat. Control. 1969. V. 14. №5.

55. Maslov E. P, Olshanskiy V. K, Rubinovich E. Ya. On a Piecewise Open-Loop Control Differential Game // Proc. Third IFAC Simposium on Sensitivity, Adaptivity and Optimality. Ischia, Italy. 1973. P. 364-372.

56. Melikyan A. A. Generalized characteristics of first order PDEs: Applications in Opimal Control and Differential Games. Birkhauser, Boston, 1998.

57. Melikyan A., Akhmetzhanov A. A linear 2D differential game with a minimum-type cost function// 11 Internat. Symp. on Dynamic Games and Applications. Proceedings V. 2. Tucson Arisona. 2004. P. 637-649.

58. Melikyan A. A., Hovakimyan N. V. and Harutunian L. L. Games of simle pursuit and approach on two dimensional cone// JOTA, 1998, V. 98, No 3, pp. 515-543.

59. Melzak Z. A. Plane motion with curvature limitations, J. Soc. Indust. Appl., Math., 9 (1961), № 3. pp. 422-432.

60. Merz A. W. The Game of Two Identical Car// J. optimization theory and applications. 1972. V. 9. №. 5.

61. Olsder G. J., Breakwell J. V. Role determination in serial dogfight. International Journal of Game Theory, 1974, Ns 3.

62. Pachter M., Getz W. M. The geometry of the barrier in the "game of two cars". Optimal Control, Applications and Methods, 1980, vol. 1.

63. Patsko V.S., Turova V.L. Level sets of the value function in differential games with the homocidial chauffeur dynamics// International Game Theory Review. 2001. V. 3. № 1. P. 67-112.

64. Patsko V.S., Turova V.L. Homicidal chauffeur game. Computation of level sets of the value fanction // 8th Internat. symp. on dynamic games and applications. Maastricht, 1998.

65. Pecsvaradi T. Optimal Horizontal Guidance Law for Aircraft in the Terminal Area /j IEEE Trans, on Automatic Control. 1972. V. AC-17.№ 6.

66. Subbotin A. I. Generalized Solutions of First Order PDEs: the Dynamicalr Optimization Perspective. Birkhauser, Boston, 1995.

67. Salmon D. M. Policies and controller design for pursuing vehichle // IEEE « Trans. Automat. Control. 1969. V. 14. №5.

68. Zhang Si-Ying, Wu Han-Sheng, Wang Jing-Cai. An approach to solve the role ambiguity problem in aerial combat, Journal of Spacecraft. Vol. 14, No. 2, 1977.i'