Задача быстродействия "из точки в точку"

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

Задача быстродействия\(~-\) задача перевода системы из начального фиксированного положения в конечное, также фиксированное, положение за минимальное время.

Пусть наша система описывается следующими условиями: \[ \begin{cases} \dot{x}(t) = f(x(t), u(t)), \\ x(t_0) = x^0, \\ x(t_1) = x^1, \\ u(\tau) \in \mathcal{P}(\tau) \in \text{conv}\mathbb{R}^m, \\ t_1 - t_0 \rightarrow \underset{u(\cdot)}{\text{inf}}, \end{cases} \]

где \(x_0, x_1, t_0 \) - фиксированы, \(A(t), B(t), f(t) \) - непрерывны, а \(\mathcal{P} \) непрерывно как многозначное отображение (это требование гарантирует нам, что для любого \(l: \rho(l\vert\mathcal{P}(\tau)\) по \(\tau\) непрерывна\(^1\)).

\(^1\)В частности, при \(m=1\) множество \(\mathcal{P}\) выглядит как \(\mathcal{P} = [a(\tau), b(\tau)]\); непрерывность многозначного отображения означает, что \(a(\tau), b(\tau)\) - непрерывны.

Заметим, что в общем случае функционал имеет вид: \[ \mathcal{J} = \int\limits_{t_0}^{t_1}f^0(x(t), u(t))dt \rightarrow \underset{u(\cdot)}{\text{inf}} \] Принимая \(f^0 \equiv 1 \), получаем задачу быстродействия с функционалом \(\mathcal{J} = t_1 - t_0\).

Сопряженная переменная имеет следующий вид: \(\psi = (\psi_1, ..., \psi_n)\).

Выпишем функцию Гамильтона-Понтрягина: \[ \mathcal{H}(\psi, x, u) = \langle \psi, f(x(t), u(t)) \rangle. \]

Тогда можно говорить о сопряженной системе: \[ \dot{\psi} = -\frac{\partial \mathcal{H}}{\partial x(t)}. \]

Заметим, что гамильтонианом системы называется \(M = \underset{u\in \mathcal{P}}{\text{sup}} \mathcal{H}(\psi, x, u)\). Однако в задаче быстродействия супремум достижим, поэтому \(M = \underset{u\in \mathcal{P}}{\text{max}} \langle \psi, f(x(t), u(t)) \rangle\).

Принцип максимума Понтрягина

Теорема(ПМП для автономной задачи быстродействия)

Пусть \((x^*(\cdot), u^*(\cdot))\) \(~-\) оптимальная пара, \(\mathcal{H}\) \(~-\) функция Гамильтона–Понтрягина. Тогда существует \(\psi^*:[t_0, t_1] \rightarrow \mathbb{R}^n \), \(\psi^* \neq 0 \) такое, что:

1) Сопряженная система (СС): \[\dot{\psi} = -\frac{\partial H(\psi(t), x(t), u(t))}{\partial x(t)} \bigg|_{x=x^*(t) \\ u=u^*(t) \\ \psi = \psi^*(t)};\] 2) Условие максимума (УМ): \[u^*(t) \stackrel{\textrm{п.в.}}{\in} \underset{u \in \cal{P}}{\text{Argmax}} \mathcal{H}(\psi^*(t), x^*(t), u(t));\] 3) \[M(\psi^*(t), x^*(t)) \equiv \text{const} \geqslant 0.\]

Доказательство принципа максимума Понтрягина можно найти в книге: Л.C. Понтрягин, В.Г. Болтянский, Р.В. Гамкрелидзе, Е.Ф. Мищенко. "Математическая теория оптимальных процессов". — М.: Наука, 1976 [1].

В общем случае еще учитывается условие трансверсальности на концах, однако поскольку рассматриваемая задача быстродействия является задачей "из точки в точку", их можно опустить. Уточним, что в задаче быстродействия нецелесообразно вводит дополнительную координату в вектор \(x\) и сопряженную переменную \(\psi\), поскольку все условия, связанные с этой дополнительной координатой, равны нулю или не имеют значения.

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

Примеры

Отметим, что отказ от требования \(u(\tau) \in \mathcal{P}(\tau) \in \text{conv}\mathbb{R}^m\) невозможен; в этом случае \( \overline{\mathcal{X}_\mathcal{P}[t_1]} = \mathcal{X}_\overline{\mathcal{P}}[t_1] \). Разумность такого отказа показывает следующий пример:

Пример 1

Пусть система описывается уравнениями \[ \begin{cases} \dot{x} = u, \\ x(0) = 0, \\ u(\tau) \in [-1, 1]. \end{cases} \]

Тогда множеством достижимости \(\mathcal{X}_1\) буде бесконечный треугольник в I и IV квадрантах, лежащий внутри прямых \(x=t\) и \(x=-t\). При этом, геометрически ясно, что замена множества допустимых управлений с отрезка \([-1, 1]\) на двухточечное множество \(\{-1, 1\}\)не изменит множества достижимости: любую точку, лежащую внутри \(\mathcal{X}_1\), можно соединить с началом координат ломанной, содержащей звенья, параллельные прямым \(x=t\) и \(x=-1\).

Именно этот прием используется при управлении парусными судами при отсутствии попутного ветра(при этом говорят, что судно идет галсом).

Введем множество достижимости \[ \mathcal{X}[t_1] = \mathcal{X}(t_1, t_0, x^0) = \{ x = x(t_1, t_0, x^0 \vert u(\cdot)), u(\tau) \in \mathcal{P} \}. \]

Введем также трубку достижимости \(\mathcal{X}[\cdot]\). Следует понимать, что множество достижимости - это множество, а трубка достижимости - это функция, отображающая время на соответствующее множество достижимости. Ее графиком будем называть множество \( \mathcal{X}[\cdot] = \{(t,x): x\in\mathcal{X}[t]\} \).

Ключевую роль играет следующее утверждение

Утверждение 1

Если \(t_1^*-t_0\) - время оптимального взаимодействия, \( x^*, u^* \) - соответственно траектория и управления, отвечающие этому времени, то \( (t_1^*, x^*(t_1^*)) \in \partial\mathcal{X}[\cdot] \).

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

Пример 2

Пусть система описывается уравнениями \[ \begin{cases} \dot{\rho} = u_1, \vert u_1 \vert \le 1, \\ \dot{\varphi} = u_2, \vert u_2 \vert \le 1, \\ \rho(0) = \rho^0 > 0, \\ \varphi(0) = \varphi^0. \end{cases} \]

Если бы это были декартовы координаты на плоскости, то трубкой достижимости была бы "распухающий квадрат" \( \mathcal{X}[t_1] = \{ \vert x-x^0 \vert \le t_1, \vert y - y^0 \vert \le t_2 \} \). В нашем же случае это будет "распухающий кольцевой сектор", и множество достижимости не будет выпуклым. Это приведет к тому, что если финальная точка будет отвечать углу в \(\pi\), то \( (t_1^*, x^*(t_1^*)) \notin \partial\mathcal{X}[\cdot] \).

Введем функцию \(\varepsilon[t_1] = d(x^1, \mathcal{X}[t_1])\).

Утверждение 2

\( t_1^* - t_0 \) - время оптимального взаимодействия \( \iff t_1^*\) - наименьший корень уравнения \( \varepsilon[t_1] = 0, t_1 \ge t_0 \).

При этом стоит иметь в виду, что если некое множество \(Z\) - компакт, то \(x \in Z \iff d(x, Z) = 0\).

Свойства множества достижимости

Далее доказательства опускаются, но их знать обязательно нужно.

Утверждение 3

\( \mathcal{X}[t_1] \in \text{conv}\mathbb{R}^n \).

Лемма 1 (ОЧЕНЬ важная)

\( \sup_{u(\cdot)} \left[ \int\limits_{t_0}^{t_1} <s(\tau), u(\tau)> d\tau \right] = \int\limits_{t_0}^{t_1} \sup_{u \in \mathcal{P}} <s(\tau), u> d\tau \).

Условие максимума

Перейдем непосредственно к решению задачи быстродействия. Выпишем в терминах опорных функций условие \( x^1 \in \mathcal{X}[t_1]: \) \[ <l, x^1> \le \rho(l \vert \mathcal{X}[t_1]) \] для любого \(l\), или, в терминах расстояний до множества, \( d(x^1, \mathcal{X}[t_1] = \varepsilon[t_1] = 0 \). Фиксируем произвольное число \(\hat{\varepsilon}\). Тогда верна следующая цепочка равносильных переходов: \[ d(x^1, \mathcal{X}[t_1]) \le \hat{\varepsilon} \iff x^1 \in \mathcal{X}[t_1] + \hat{\varepsilon}B_1(0) \iff <l, x^1> \le \rho(l \vert \mathcal{X}[t_1]) + \hat{\varepsilon}\vert\vert l \vert\vert. \]

В силу положительной однородности левой и правой части по \(l\), последнее соотношение можно нормировать и записать в виде \[ \sup_{\vert\vert l \vert\vert = 1}(<l, x^1> - \rho(l \vert \mathcal{X}[t_1])) \le \hat{\varepsilon}, \]

откуда следует, что \(\varepsilon[t_1] = \sup_{\vert\vert l \vert\vert}(<l, x^1> - \rho(l \vert \mathcal{X}[t_1])) \). Таким образом, отсюда время быстродействия \(t_1^*\) находится как наименьший корень уравнения \( \varepsilon[t_1^*] = 0 \).

Возьмем вектор \( l^0 \in \text{Argmax}_{\vert\vert l \vert\vert = 1}(<l, x^1> - \rho(l \vert \mathcal{X}[t_1])) \). Тогда \( <l^0, x^1> = \rho(l^0 \vert \mathcal{X}[t_1^*]) \), что означает, что \(x^1\) лежит на пересечении опорной гиперплоскости и самого множества. Отсюда \( u^*(\tau) = u^{l_0}(\tau) \). Таким образом, мы можем записать необходимое условие максимума:

Если \(u^*\) есть управление, доставляющее оптимальное управление, то \[ <B^T(\tau)\psi(\tau)u^*(\tau)> = \max_{u \in \mathcal{P}(\tau)}<B^T(\tau)\psi(\tau), u>. \]

Естественно встает вопрос: является ли это условие достаточным? Оказывается нет ~--- следующий пример показывается, что условию максимума может удовлетворять вообще любое допустимое управление!

Пример 3

Рассмотрим следующую задачу быстродействию: \[ \begin{cases} \dot{x}_1 = u - 1, \\ \dot{x}_2 = u + 1, \\ x^0 = [0, 0]^T, \\ x^1 = [-1, 1]^T, \\ \vert u(t) \vert \le 1. \end{cases} \]

В этой задаче, \( \mathcal{P}(t) \equiv \mathcal{P} = [-1, 1] \). Найдем опорную функцию для этой задачи: \[ \rho(l \vert \mathcal{X}[t_1]) = \int\limits_0^{t_1}<l, [-1, 1]^T> + \int\limits_0^{t_1}\rho([1, 1]^Tl \vert \mathcal{P}(\tau))d\tau = t_1(l_2 - l_1) + t_1\vert l_1 + l_2\vert. \]

Легко видеть, что это сумма опорных функций одноточечного множества и отрезка. С геометрической точки зрения, множество достижимости есть отрезок, соединяющий на плоскости точки \( [-1, -1]^T \) и \([1, 1]^T\), который "ползает" по плоскости. Очевидно, что для быстрейшего достижения очки \([-1, 1]^T\) надо "ползти" вверх по прямой \(y=-x\). Тогда в момент \(t^*=1\) мы достигнем финальной точки.

Однако для нахождения оптимального управления нам (формально) надо было бы найти вектор-максимизатор \(l_0\). На эту роль подходят векторы \( \frac{1}{\sqrt{2}}[-1, 1]^T \) и \( \frac{1}{\sqrt{2}}[1, -1]^T \).

Выпишем условие максимума: \[ <B^Tl^0, u^*> = \max_{u \in \mathcal{P}}<B^Tl^0, u>, \]

которое в нашем случае вид \(0 = 0\).

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

Условие нормальности (общности положения)

Рассмотрим частный случай нашей задачи: Пусть \(A, B\) - const, а \(\mathcal{P}\) - выпуклый многогранник с непустой внутренностью, построенный на точках \(u_1, u_2, \dots, u_M\), причем \(u_j \in \partial\mathcal{P}, j = \overline{1, M}\). Пусть \( w = w^{k,l} = u^k-u^l \), где \(k, l\) соединены ребром. Потребуем, чтобы выполнялось условие нормальности (или условие общности положения): \[ \text{Векторы } Bw, ABw, \dots, A^{n-1}Bw \text{ линейно независимы}. \] Отметим, что если \(\mathcal{P}\) имеет вид "параллелепипеда", \( \mathcal{P} = \{ u \in \mathbb{R}^m \vert a_i \le u_i \le b_i, i = \overline{1, m} \} \), а матрица \(B\) состоит из столбцов \(b^1, b^2, \dots, b^m\), то условие нормальности требует линейной независимости векторов \( b^i, Ab^i, \dots, A^{n-1}b^i \) для всех \(i\), что представляет собой в точности условие полной управляемости.

Роль этого условия раскрывает следующая теорема.

Теорема 1

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

Замечание 1

На самом деле, условие нормальности гарантирует строгую выпуклость множества достижимости.

Пример 4

Рассмотрим задачу \[ \begin{cases} \dot{x}_1 = u_1, \vert u_1 \vert \le 1, \\ \dot{x}_2 = u_2, \vert u_2 \vert \le 1. \\ \end{cases} \]

Эта система вполне управляема, но не сильно вполне управляема. Множество достижимости в данном случае ~--- квадрат (т.е. не строго выпуклое). Случай, в котором условие максимума выделяет единственное управление, бывает тогда, когда финальная точка оказывается на углу квадрата.

Условие управляемости при выпуклости множества \(\mathcal{P}\)

Теорема 2

Пусть \(\mathcal{P}\) строго выпукло и имеет непустую внутренностью, и выполнено условие полной управляемости, \[ \text{rg}[B\vert AB\vert \dots\vert A^{n-1}B] = n. \] Тогда условие максимума определяет оптимальное управление единственным образом.