Выпуск N 7 (46)

ЧИСЛЕННОЕ РЕШЕНИЕ ЗАДАЧИ О МЯГКОЙ ПОСАДКЕ
В ТЕОРЕТИКО-ИГРОВОЙ ПОСТАНОВКЕ

Козлов А.И, кандидат технических наук

Рассмотрим игровую задачу преследования одного управляемого объекта, движущегося в горизонтальной плоскости, другим управляемым объектом, движущимся в пространстве. Цель преследователя - достичь равенства координат и скоростей с убегающим, то есть совершить мягкую посадку. При этом убегающий может противодействовать догоняющему, выбирая тот или иной алгоритм убегания. Кроме того, в задаче присутствуют фазовые ограничения - преследователь не может пересечь плоскость, в которой движется убегающий. В работе предлагается метод численного решения этой задачи, позволяющий найти управление преследователя, обеспечивающее мягкую посадку при любом, заранее неизвестном управлении убегающего.

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

Пусть движение преследователя задается уравнением
,   ,   ,    ,                          (1)

где x1, x2 ≈ координаты на плоскости, x3 ≈ высота, ? ≈ коэффициент сопротивления среды, ? > 0 ≈ параметр управления, u(t) ≈ управление. Движение убегающего задается уравнением
     ,    ,     ,               (2)

где y1, y2 ≈ координаты на плоскости, ?? ≈ коэффициент сопротивления среды, ? > 0 ≈ параметр управления, v(t) ≈ управление. Таким образом, убегающий все время движется в плоскости x3 = 0. Преследователь должен совершить точную мягкую посадку, то есть за конечное время добиться выполнения равенств
 .                                                              (3)

Сведем сформулированную выше игровую задачу к задаче оптимального быстродействия [6]. Введем новую переменную
 .                                                                 (4)

Вычитая уравнение (2) из уравнения (1) с учетом (4), получим
 .                                              (5)

Будем считать, что начальные координаты и скорости убегающего и преследователя заданы, тогда заданы начальные значения для переменной  . Рассмотрим следующую задачу оптимального быстродействия.
Объект описывается системой дифференциальных уравнений
 ,       ,                                           (6)

при наличии фазовых ограничений  . Начальное и конечное положение объекта задано
 ,                                                      (7)

 .                                                        (8)

Необходимо найти управление w(t), переводящее объект из заданного начального положения (7) в конечное положение (8) за минимально возможное время T.

Выполнение условий (8) будет означать для преследователя точную мягкую посадку. Зная значение управления w(t) и значение скорости убегающего   в каждый момент времени, нетрудно получить значение управления u(t) преследователя, обеспечивающее мягкую посадку при любом допустимом управлении убегающего:
 .                                                (9)

Из уравнения (5) следует, что для успешного решения задачи преследования ресурс преследователя по управлению должен быть достаточно велик, а именно
  .                       (10)

С другой стороны, из выражения (9) при условии ограниченности управления u следует, что управление w также должно быть ограничено
 .                                                (11)

Таким образом, при решении задачи оптимального быстродействия (6)-(8), будем выбирать управления из шара радиусом
 ,                                                      (12)

лежащего внутри множества  (11).

Для решения задачи оптимального быстродействия (6)-(8) воспользуемся принципом максимума Понтрягина. Сведем систему (6) из трех уравнений второго порядка к системе из шести уравнений первого порядка относительно переменных  . Функция Гамильтона-Понтрягина для системы (6) с учетом фазовых ограничений будет иметь вид

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

где   ≈ величина, зависящая от оставшихся  .
Согласно принципу максимума Понтрягина оптимальное управление доставляет максимум функции   и при ограничениях   имеет вид
 ,  ,  .      (15)

Объединяя сопряженную систему  , систему (6), в которую подставим выражения для компонент управления (15), краевые условия (7) и (8), получаем краевую задачу принципа максимума, которую будем решать методом пристрелки.

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

то есть такой набор начальных значений   и время Т, при которых сумма в правой части выражения (16) обращается в 0.  Рассчитанное для таких ???(0) в соответствии с выражениями (15) управление w(t) будет использоваться затем в выражении (9) для вычисления управления преследователя u(t) давать решение задачи о мягкой посадке.

Для минимизации функции   применим модифицированный метод Нелдера-Мида , который состоит в следующем.

Будем рассматривать задачу поиска минимума некоторой функции F(x), заданной на параллелепипеде   при наличии ограничений типа неравенств  . Необходимо найти точку x*, принадлежащую параллелепипеду, удовлетворяющую ограничениям и доставляющую минимум функции F(x).

ШАГ 1. Переход в пространство нормированных независимых переменных x. Зададим начальную точку  , и перейдем от параллелепипеда Пх к кубу  , выполнив нормировку независимых переменных. В дальнейшем для удобства будем опускать штрих.

ШАГ 2. Выбор начального симплекса. Построим внутри куба Кx регулярный симплекс (правильный многогранник с n+1 вершиной), одна из вершин которого совпадает с точкой  . Координаты векторов, соответствующих вершинам симплекса, будем хранить в таблице X размером n+1 на n. I-ая строка таблицы будет соответствовать i-ой вершине симплекса, а j-ый столбец - j-ой компоненте i-ой вершины. Таким образом, первая строка этой таблицы будет содержать компоненты вектора  . Элементы этой таблицы определяются выражениями:

 ,     .             (17)
Здесь к - величина, определяющая размер начального симплекса, а s определяет направленность  симплекса внутри куба Кx. При построении таблицы X проверяется, чтобы каждая вершина начального симплекса удовлетворяла ограничениям. Если какая-либо вершина не удовлетворяет ограничениям, размер начального симплекса уменьшается вдвое и строится новый начальный симплекс. После того, как таблица X создана, построим вектор Fv, компонентами которого являются значения функции F(x) для соответствующих строк таблицы X, т.е. значения функции, соответствующие вершинам симплекса.

ШАГ 3. Построение следующего симплекса. Выбираем в таблице X строку, которой соответствует максимальная компонента вектора Fv. Пусть эта строка имеет номер M. Следующим шагом является отбрасывание этой вершины как наихудшей и построение нового симплекса, который содержит все оставшиеся вершины и еще одну новую вершину, которая получается отображением отбрасываемой вершины относительно центра тяжести противоположной грани симплекса. При этом построение нового симплекса может осуществляться либо в один, либо в несколько шагов в зависимости от значения функции в новой вершине и от того, удовлетворяет ли новая вершина ограничениям. При этом симплекс на определенной итерации теряет регулярность и уменьшается. Координаты новых вершин могут задаваться выражениями
 ,  ,  .                     (18)

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

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

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

2. При решении сформулированной выше задачи оптимального быстродействия минимизируемая функция  , как показали расчеты, не всегда является выпуклой, что делает невозможным применение некоторых градиентных методов. Поэтому в ШАГ 3 метода были внесены изменения, позволяющие учесть случаи попадания симплекса на вогнутую поверхность. Как показали расчеты, внесенные изменения значительно повысили эффективность метода при численном решении задач оптимального быстродействия.
На рис. 1 показаны управления преследователя, найденные путем численного решения описанной выше задачи при следующих начальных данных:

 
 .                            (20)
 

Убегающий формировал свое управление в соответствии с законом
  .                                          (21)

На рис. 2 показаны траектории движения преследователя и убегающего. Преследователь движется в пространстве, убегающий ≈ в плоскости xOy. Мягкая посадка была осуществлена через 10.7245 сек.
 
Рис. 1. Компоненты управления преследователя
 
Рис 2. Траектории движения преследователя и убегающего

1. Albus J., Meystel A., The Eagle Snatch, Intelligent Systems: A Semiotic Perspective, Proceedings of the 1996 International Multidisciplinary Conference, NIST, Gaithersburg, 1996, USA.

2. Chikrii A.A., Conflict Controlled Processes. - Kluwer Academic Publishers, Boston-London-Dordrecht, 1997. - 427 p.

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

4. Банди Б. Методы оптимизации. - Москва: Радио и связь, 1998. -128 с.

5. Козлов А.И., Исследование и алгоритмическая реализация нелинейной схемы компромиссов: Автореферат дис. канд. тех. наук. - Киев: ИК НАНУ, 1995. - 17 с.

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