rss rss hh new rss rss hh new

-Поиск по дневнику

-Подписка по e-mail

-Постоянные читатели

BlooDandMilK Elenka2000 Python3 Stock_Market_Trading _ghbhjif balloonic dmitriy1800 ВаШуня Виталий_Хлусов Главный_синоптик

-Статистика

Создан: 17.03.2011
Записей:
Комментариев:
Написано: 51

Отчеты:
Посетители
Поисковые фразы

Игровое управление моделям в условиях неполной информации

Воскресенье, 09 Июля 2017 г. 23:59 + в цитатник

(В соавторстве с Юлией Филимоновой jul305a@gmail.com)

Введение

Представьте себе, что летите такой весь победитель на базу, бомб уже нет, и ничего не предвещает беды…

А тут, скажем, горочка из тумана/облаков выступает неожиданно, или, что несколько хуже, — вот это… И вам рады, но исключительно в качестве цели:

#поравалить — а вот как это делать с математическим уклоном сейчас и будем разбираться.
Да и вообще есть множество случаев, когда необходимо уклониться от неожиданно возникшей помехи/преграды, нашЛось, как говорят в Яндексе, например.

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

Часть первая — модель в «простых движениях»

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

$$$display$$\dot x = u, \ x(t_0) = x_0,$$display$$$

где $$inline$x(t)\in R^n \ u\in P\subset R^n$inline$$ , -управление ограничено $$inline$P:|u|math> (что логично, т.к. скорость не бесконечна), а $inline$R^n$inline$ — $inline$n$inline$ -мерное Евклидово пространство (для нашего примера, как видно, вполне достаточно двумерного). Множество $inline$M$inline$ — наша база, т.е. сюда мы хотим вернуться в целости и сохранности, — располагается в точке $inline$x_1$inline$ .$

Что это нам даёт? Если проинтегрировать уравнение, то мы получим траекторию движения — прямую линию $$inline$x(t)=u t +C$inline$$ , то есть, куда направлено управление, туда и летим. Значит, при отсутствии помех вектор управления $$inline$u$inline$$ сонаправлен с вектором движения $$inline$x_1 - x_0$inline$$ .

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

$$$display$$\ddot x = u \Rightarrow \left\{ \begin{array}{rcl} \dot x_1 &=& x_2\\ \dot x_2 &=& u. \end{array} \right.$$display$$$

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

Описанная модель отражает наши динамические возможности. Добавим в нее противника $$inline$v$inline$$ , который всячески старается нам помешать:

$$$display$$ x = u - v,\, x(t_0) = x_0,\, \exists T: x(T)\in M,\, \forall tmath>$

Здесь аналогично ограниченное управление $$inline$Q:|v|math>.$

При этом мы заранее не знаем, где притаился противник, а он, при этом, знает всё и ждёт себе, пока мы подлетим поближе, для того чтобы при помощи своего управления $$inline$v$inline$$ достать нас множеством $$inline$N$inline$$ .

Поскольку наша цель — всё--таки попасть на $$inline$M$inline$$ , гарантированно уклонившись от $$inline$N$inline$$ , и мы должны знать от чего, собственно, мы уклоняемся, то рано или поздно помеху мы обнаружим. В случае безынерционного движения мы можем не знать о ней ничего до предпоследнего момента времени, так как в этом случае мы всегда можем направить вектор скорости (и, соответственно, траекторию) в сторону от помехи.

При этом, как можно заметить, помеха типа <<гора>> не самая страшная ситуация, так как она неподвижна, хотя и является большим препятствием, — хуже если противник подвижен, поэтому надо обсудить ещё пару моментов:

чтобы иметь возможность уклоняться, мы должны обладать большими динамическими возможностями, чем противник, иначе рано или поздно нас поймают, то есть $$inline$Q$inline$$ в некотором смысле должно быть меньше $$inline$P$inline$$ ;
пусть множество помехи, которым управляет противник — выпуклое, иначе, если применять стратегию уклонения <<угол падения равен углу отражения>> — можно и не уклониться.

Воспользовавшись приведенными выше эвристическими рассуждениями, посмотрим, как можно решить приведенную выше задачу при следующих условиях в пространстве $$inline$R^2$inline$$ :

$$$display$$ \begin{array}{rcl} \dot{x}_1 &=& u_1 - v_1,\\ \dot{x}_2 &=& u_2 - v_2. \end{array}$$display$$$

Здесь $$inline$x_1,\ x_2$inline$$ — координаты объекта $$inline$x$inline$$ на плоскости, $$inline$x(t) = [x_1(t),\ x_2(t)]^{T} \in \mathbb{R}^2.$inline$$

Пусть объект начинает движение из точки $$inline$x(t_0) = [3,\ 4]^{T} \in \mathbb{R}^2.$inline$$
Ограничения на управления $$inline$u(t),\ v(t)$inline$$ имеют вид

$$inline$u(t) \in P \subset \mathbb{R}^2,\ P = S_{1} ([0,\ 0]^{T})$inline$$ — круг радиуса 1;
$$inline$v(t) \in Q \subset \mathbb{R}^2,\ Q = S_{0.9} ([0,\ 0]^{T})$inline$$ — круг радиуса 0.9.

Первый игрок стремится перевести траекторию системы за конечное время на терминальное множество $$inline$M = S_{1}([12,\ 6]^{T})$inline$$ — круг радиуса 1 с центром в точке $$inline$[12,\ 6]^{T}$inline$$ , избежав при этом попадания на множество помехи $$inline$N = S_{2}([8,\ 5]^{T})$inline$$ — круг радиуса 2 с центром в точке $$inline$[8,\ 5]^{T}$inline$$ .

Время успешного завершения игры первым игроком $$inline$T = 36.0$inline$$ .

Траектория движения системы и компоненты управления первого игрока показаны на следующих рисунках.

Траектория движения системы.
Зависимость первой компоненты управления от времени.
Зависимость второй компоненты управления от времени.

Данный подход, очевидно имеет несколько недостатков, а именно:

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

Часть вторая — модель всё ещё в «простых движениях», но сокращается количество переключений

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

Давайте думать на один шаг вперёд: если наша система сначала наводилась на цель, а на следующем шаге начала уклонятся, то можно найти точку, в которую система придёт через два шага, и наводиться сразу на неё как на промежуточную цель. Можем? По нашему предположению — ДА.

На том же примере посмотрим, что получается. Время успешного завершения игры первым игроком сократилось почти в три раза с $$inline$T = 36.0$inline$$ до $$inline$T = 11,5$inline$$ . Количество переключений тоже резко уменьшилось. Берём на заметку — думать хотя бы на шаг вперёд эффективно ~~и вообще полезно для здоровья~~.

Траектория движения системы и компоненты управления первого игрока показаны на на следующих рисунках.

Часть третья — модель всё ещё в «простых движениях», но теперь решаем вопрос с приближением <<по нормали>>

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

Построение дополнительного множества избегания для траектории.

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

Часть четвертая — математический базис

Для того, чтобы построить управления инерционными объектами необходимо всё таки погрузиться в теорию, так как простые эвристические рассуждения в этом случае работать перестают и, соответственно, необходимо подобрать теоретическую основу решения. Если у вас ~~жёсткий приступ лени~~ не хватает времени, то раздел можно, пропустить и воспользоваться сразу результатами, интересующиеся же — смотрим дальше.

В качестве основы будем использовать теорию дифференциальных игр, которые в нашей стране развивались Львом Семёновичем Понтрягиным [1] (если не знаете кто такой — обязательно почитайте, Личность с большой буквы, как говорится, таких уже не делают) и Красовским Николаем Николаевичем [2].

Для решения нам потребуются два множества:

куда можно попасть первым игроком — множество достижимости первого игрока;
откуда можно завершить преследование вторым игроком первого.
А также способ их построения, реализуемый на практике.

С первым множеством, при отсутствии помехи всё более или менее понятно, если можем построить его таким образом, чтобы включить конечное множество $$inline$M$inline$$ — значит игру завершим успешно, не сможем — значит игра точно не сможет быть завершена. Строится оно в теории следующим образом — для каждой точки начиная с начальной $$inline$x_0$inline$$ путём перебора всех доступных управлений строим множество в которое можем попасть через $$inline$\Delta t$inline$$ , после чего операцию повторяем. Выглядит довольно сложно, но для выпуклых множеств и линейных систем можно всё радикально упростить, используя аппарат выпуклого анализа, — опорные функции и введя соответствующие сетки [4]. Построение такого множества решает задачу наведения первого игрока, назовём её — задача А.
Наведение на множество $M$ в условиях отсутствия помехи.

Что касается второго множества — множества откуда второй игрок может поймать нас и от которого нам и нужно уклоняться, то здесь несколько сложнее — следите за пальцами:

с одной стороны, если мы "приближаемся" к противнику, то ввиду превосходства наших возможностей, чем мы дальше от него тем вероятность нас поймать, — этому потом придётся дать строгое объяснение;
с другой стороны — если мы "удаляемся" от противника, то ввиду того же самого нашего превосходства противник не сможет нас поймать в любом случае.

То есть что получается множество от которого мы уклоняемся должно быть с одной стороны большим (при приближении), а с дугой стороны (при удалении) может быть едва превышающим то, от которого необходимо уклониться?
Уклонение от множества $$inline$N$inline$$ .

~~Совпадение?~~ Противоречие? Не думаю. Подобно Доку в "Назад в будущее" с его "пространственно-временным континуумом" вспомним, что у нас есть ещё одна переменная — время и будем трактовать термины "приближаемся" и "удаляемся" приведенные в кавычках как поведение системы вдоль траектории, что не всегда совпадает с прямолинейным движением и уж точно не характеризуется расстоянием в евклидовом пространстве. Зато временем движения до конкретной точки понятия "далеко-близко" и "приближаемся-удаляемся" характеризуются очень неплохо.
В этом случае давайте будем строить управление уклонения не от множества от которого нам надо уклоняться $$inline$N$inline$$ , а от множества в которое оно преобразуется (а оно уменьшится ввиду превосходства первого игрока) к моменту его приближение на соответствующее временной интервал в множеству $$inline$N$inline$$ — т.е. построим этакую воронку направленную к первому игроку своей узкой стороной и будем отталкиваться уже от неё. Построение такого множества в каждый момент игры и уклонение от него будет решает задачу уклонения первого игрока, назовём её — задача Б.

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

Формализуем теперь движение нашего объекта $$inline$x$inline$$ , в $$inline$x$inline$$ --мерном евклидовом пространстве $$inline$\mathbb{R}^n$inline$$ следующей системой дифференциальных уравнений:

$$$display$$\dot{x} = A x + B u - C v,$$display$$$

где $$inline$x \in \mathbb{R}^n,\ u \in P \subset \mathbb{R}^p,\ v \in Q \subset \mathbb{R}^q$inline$$ ; $$inline$P,\ Q$inline$$ — выпуклые компакты из евклидовых пространств $$inline$\mathbb{R}^p,\ \mathbb{R}^q$inline$$ ; $$inline$A,\ B,\ C$inline$$ — постоянные матрицы, $$inline$A \in \mathbb{R}^{n \times n},\ B \in \mathbb{R}^{n \times p},\ C \in \mathbb{R}^{n \times q}$inline$$ , что обеспечивает существование, единственность и продолжимость при всех $$inline$t \ge t_0$inline$$ решения задачи Коши.

Вектор $$inline$u$inline$$ находится в распоряжении первого игрока, вектор $$inline$v$inline$$ находится в распоряжении второго игрока.

Движение начинается при $$inline$t = t_0$inline$$ из начального состояния $$inline$(x_0,\ t_0)$inline$$ и протекает под воздействием измеримых по Лебегу функций $$inline$u(t) \in P,\ v(t) \in Q$inline$$ .

В $$inline$\mathbb{R}^n$inline$$ выделены некоторые непустые выпуклые замкнутые множества $$inline$M$inline$$ и $$inline$N$inline$$ . Множество $$inline$M$inline$$ является терминальным множеством первого игрока. Цель первого игрока — добиться выполнения включения $$inline$x(t_1) \in M$inline$$ при некотором $$inline$t_1 \ge t_0$inline$$ . Множество $$inline$N$inline$$ является терминальным множеством второго игрока и множеством помехи первого игрока. Цель второго игрока — добиться выполнения включения $$inline$x(t_1') \in N$inline$$ при некотором $$inline$t_1' \ge t_0$inline$$ . В момент первого попадания точки $$inline$x(t)$inline$$ на $$inline$N$inline$$ игра считается успешно завершенной вторым игроком. Дополнительная задача первого игрока — избежать попадания точки $$inline$x(t)$inline$$ на $$inline$N$inline$$ .

Игра считается успешно завершенной первым игроком в момент первого попадания точки $$inline$x(t)$inline$$ на $$inline$M$inline$$ при условии, что для всех предыдущих моментов времени точка $$inline$x(t)$inline$$ ни разу не попадала на $$inline$N$inline$$ . Таким образом, цели игроков не совпадают, и точка $$inline$x(t)$inline$$ находится под воздействием противоборствующих управлений $$inline$u(t),\ v(t)$inline$$ .

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

динамические возможности конфликтно управляемого объекта $$inline$x$inline$$ , то есть матрицы $$inline$A,\ B,\ C$inline$$ , множества $$inline$P,\ Q$inline$$ ;
начальное состояние игры $$inline$(x_0, t_0)$inline$$ ;

Предполагается также, что первый игрок способен обнаружить множество $$inline$N$inline$$ не позднее чем за время $$inline$\Theta>0$inline$$ , значению которого определим ниже.

Определим стратегию первого игрока $$inline$u(t) = U(x_0, t_0, v_t(\cdot))$inline$$ как отображение, определенное на множестве произвольных измеримых функций $$inline$v(t) \in Q,\ t \ge t_0$inline$$ , и обладающее следующим свойством: для произвольной измеримой $$inline$v(t) \in Q,\ t \ge t_0$inline$$ , функция $$inline$u(t) = U(x_0, t_0, v_t(\cdot))$inline$$ измерима по $$inline$t$inline$$ и $$inline$u(t) \in P$inline$$ .

Задача A: Найти начальные состояния $$inline$(x_0, t_0)$inline$$ , для которых первый игрок обладает такой стратегией, что она обеспечивает окончание игры для произвольной измеримой $$inline$v \in Q$inline$$ не позже некоторого конечного момента. Такие состояния $$inline$(x_0, t_0)$inline$$ будем называть решениями задачи A.

Б:Второй игрок обладает полной информацией о ходе игры.
Определим стратегию второго игрока $$inline$v(t) = V(x_0, t_0, u_t(\cdot))$inline$$ как отображение, определенное на множестве произвольных измеримых функций $$inline$u(t) \in P,\ t \ge t_0$inline$$ , и обладающее следующим свойством: для произвольной измеримой $$inline$u(t) \in P,\ t \ge t_0$inline$$ , функция $$inline$v(t) = V(x_0, t_0, u_t(\cdot))$inline$$ измерима по $$inline$t$inline$$ и $$inline$v(t) \in Q$inline$$ .

Задача Б: Найти начальные состояния $$inline$(x_0, t_0)$inline$$ , для которых второй игрок обладает такой стратегией, что она обеспечивает окончание игры для произвольной измеримой $$inline$u \in P$inline$$ не позже некоторого конечного момента. Такие состояния $$inline$(x_0, t_0)$inline$$ будем называть решениями задачи Б.

Будем считать, что $$inline$M = M^1 + M^2$inline$$ , где $$inline$M^1$inline$$ — линейное подпространство пространства $$inline$\mathbb{R}^n$inline$$ , $$inline$M^2$inline$$ — выпуклый компакт, $$inline$M^2 \subset L^1,\ L^1 \oplus M^1 = \mathbb{R}^n$inline$$ . Аналогично $$inline$N = N^1 + N^2$inline$$ , где $$inline$N^1$inline$$ — линейное подпространство пространства $$inline$\mathbb{R}^n$inline$$ , $$inline$N^2$inline$$ — выпуклый компакт, $$inline$N^2 \subset L^1,\ L^1 \oplus N^1 = \mathbb{R}^n$inline$$ . При этом $$inline$\pi$inline$$ — оператор ортогонального проектирования из $$inline$\mathbb{R}^n$inline$$ в $$inline$L^1$inline$$ , $$inline$\pi \in \mathbb{R}^{\nu \times n}$inline$$ . Данные построения нужны для того, чтобы учесть, что игра у нас в общем случае (а при наличии инерционных объектов это так и есть) ведётся в пространстве меньшей размерности чем размерность системы дифференциальных уравнений.

Подраздел 4.1. Достаточное условие разрешимости задачи уклонения первого игрока от множества $$inline$N$inline$$

Рассмотрим задачу Б — задачу преследования вторым игроком первого и построим для неё множество точек, из которого данная задача будет иметь решение. Так вот, для подобного типа задач Понтрягин придумал способ построения нужного множества — альтернированная сумма — $$inline$W(t)$inline$$ [3], [5]. Так вот альтернированная сумма мало того является выпуклым компактом, так ещё и $$inline$v$inline$$ -стабильно (т.е. позволяет строить нужные нам стратегии второго игрока), а также обеспечивает выполнение условия существования седловой точки маленькой игры [6, стр. 56] (что означает, что игра в принципе разрешима) — т.е. всё и сразу.

Из [6, стр. 69 — теорема 17.1] следует, что в этих условиях можно воспользоваться теоремой об альтернативе:

Для всякой начальной позиции $$inline$(t_0, x_0)$inline$$ и выбранного $$inline$\bar T \ge t_0$inline$$ верно одно из двух утверждений:
1) Либо найдется стратегия $$inline$\bar{v}$inline$$ , которая для всех движений $$inline$x(t)=x(t,t_0,x_0,\bar{v})$inline$$ обеспечит встречу $$inline$\{\tau,x(\tau)\}\in N$inline$$ за конечное время $$inline$\tau<\bar{T}$inline$$ . То есть, в классе позиционных стратегий второго игрока разрешима задача преследования (задача Б).
2) Либо, в противном случае, найдется стратегия $$inline$\bar{u}$inline$$ , которая для всех движений $$inline$x(t)=x(t,t_0,x_0,\bar{u})$inline$$ , обеспечит уклонение от множества $$inline$\epsilon$inline$$ -окрестности множества $N$ вплоть до момента времени $$inline$\bar{T}$inline$$ . То есть, в классе позиционных стратегий первого игрока разрешима задача уклонения (задача А).

При этом, ввиду $$inline$v$inline$$ -стабильности множества $$inline$W(T)$inline$$ на сновании [6, стр. 62 — теорема 15.1] получим, что условие:

$$$display$$ \forall t \in [t_0, \bar T]: x(t_0) \notin W(t)$$display$$$

является достаточным условием решения задачи уклонения первого игрока из начальной позиции $$inline$(t_0, x_0)$inline$$ от $$inline$\epsilon$inline$$ -окрестности множества $$inline$N$inline$$ в течение времени $$inline$\bar T$inline$$ .

Если ресурсы первого игрока, определяемые множеством $$inline$P$inline$$ , превосходят ресурсы второго игрока, определяемые множествами $$inline$Q$inline$$ и $$inline$N$inline$$ , то найдется такое время $$inline$\Theta$inline$$ , что $$inline$W(\Theta) = \emptyset$inline$$ .
Существование момента $$inline$t$inline$$ , для которого выполнено включение $$inline$x(t) \in W(t)$inline$$ , обеспечивает разрешимость задачи Б за время из диапазона $$inline$[t, t+\Theta]$inline$$ .

То есть можно построить стратегию $$inline$u(x_0, t_0, x(t))$inline$$ , удовлетворяющую условию:

$$$display$$ \forall \tau \in [t, t + \Theta]: x(\tau, u(x_0, t_0, x(\tau))) \notin W(\tau).$$display$$$

Следовательно, для того, чтобы обеспечить уклонение от множества $$inline$N$inline$$ , необходимо проверять приведенное выше условие как для текущего момента времени $$inline$t$inline$$ , так и для всех последующих моментов времени на глубину $$inline$t + \Theta$inline$$ .

Множество $$inline$\Phi(\Theta, t)$inline$$ , построенное в виде:

$$$display$$ \Phi(\Theta,t) = \bigcup_{\tau\in[t,t+\Theta]}W(\tau),$$display$$$

характеризует минимальное расстояние между преследователем и убегающим в момент времени $$inline$t$inline$$ , на котором преследование может быть завершено успешно. Откуда в общем-то и следует, что обнаруживать помеху мы должны за такое время (не за расстояние), за которое сможем от неё уклониться, что логично.

И, если настоящие математики на некоторое время закроют глаза, так как следующее рассуждение является ооочень частным случаем, то на пальцах это выглядит следующим образом: пусть множество помехи у нас шарик радиуса 5, множество управления шарик радиуса 2, а помехи -- соответственно 1, тогда время за которое мы должны обнаруживать помеху никак не должно быть меньше 4. Математики могут открывать глаза.

Аналогичным образом можно решить задачу наведения на множество $$inline$M$inline$$ в условиях отсутствия помехи. При этом достаточным условием наведения траектории системы на множество $$inline$M$inline$$ является условие:

$$$display$$ \exists T: z(t_0) \in \bar{W}(T).$$display$$$

Подраздел 4.2. Построение управления первого игрока для решения задачи А

Пусть первый игрок может заметить множество помехи $$inline$N$inline$$ не раньше, чем за время $$inline$\Theta$inline$$ . Это означает, если ввести равномерное разбиения $$inline$\omega_K$inline$$ временного отрезка $$inline$[t_0,\ T]$inline$$ , что первый игрок может заметить помеху не раньше, чем за $$inline$s$inline$$ шагов по времени:

$$$display$$ s = \frac{\Theta}{\Delta_{\omega_K}}.$$display$$$

Тогда возможность перехвата вторым игроком первого (успешного завершения задачи Б) в момент $$inline$\tau + \Delta_{\omega_K}$inline$$ определяется условием:

$$$display$$x(\tau) \in \Delta_{\omega_K} \pi e^{\tau A}CQ + W(\tau),\, \tau\in[t,t+\Theta].$$display$$$

Здесь первый мы в момент времени $$inline$\tau$inline$$ проверяем, возможна ли поимка первого игрока на следующем шаге $$inline$\tau + \Delta_{\omega_K}$inline$$ .
Будем строить управление первого игрока, считая, что выполнены следующие предположения.

На второго игрока наложены следующие ограничения:

второй игрок никогда не сможет достичь терминального множества $$inline$M$inline$$ :

$$$display$$\forall T: \Phi( T, \tau) \cap M \neq \emptyset;$$display$$$

в противном случае стратегия "закрыть собой" обеспечит победу второму игроку;
начальная позиция игры не принадлежит множеству $inline$\Phi( T, \tau)$inline$, откуда возможно успешное завершение задачи Б — преследования вторым игроком первого:

$$$display$$x(t_0)\notin \Phi( T, \tau),$$display$$$

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

Рассмотрим задачу уклонения первого игрока от множества $$inline$N$inline$$ отдельно от задачи наведения на целевое множество $$inline$M$inline$$ .

При этом, если для нашей игры выполнено приведенное выше предположение, то при любом начальном значении $$inline$x_0: x_0 \notin \Phi(\Theta,\tau)$inline$$ , можно показать, что существует такая стратегия уклонения, что расстояние между траекторией $$inline$x(t)$inline$$ и множеством избегания $$inline$\Phi(\Theta,\tau)$inline$$ может будет больше $$inline$\epsilon$inline$$ и зависеть только от хода игры, а не от её начального значения.

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

При этом, в качестве стратегии уклонения можно выбрать управление экстремального сдвига, обеспечивающее, согласно теореме об альтернативе [6, стр. 69], уклонение от множества $$inline$N$inline$$ в виде:

$$$display$$ U(\theta - t_i, x(\theta - t_i)) \in \underset{u \in P} {\mathrm{argmax}} \left\{ \pi u,\tilde{\psi_i}(x(\theta - t_i)) \right\},$$display$$$

где

$$$display$$\tilde{\psi_i}(x(\theta-t_i))\in \underset{\psi \in S_1(0)} {\mathrm{argmin}} \left\{ c(\Phi(\Theta,\tau),\psi)-(\pi x(\theta-t_i),\psi) \right\}.$$display$$$

Так как выполняются условия леммы 15.2 [6, стр. 65], то, повторяя её доказательство, получаем нужную оценку для минимального евклидового расстояния между траекторией $$inline$x(t)$inline$$ и множеством $$inline$\Phi(\Theta,\tau)$inline$$ , которая стремится к $$inline$0$inline$$ при измельчении шага разбиения по времени.

Рассмотрим теперь задачу наведения траектории системы на терминальное множество $$inline$M$inline$$ . При отсутствии каких-либо помех в виде множества $$inline$N$inline$$ и выполнении условия теоремы об альтернативе задача наведения разрешима, если начальная точка $$inline$x(t_0)$inline$$ принадлежит множеству управляемости, а само управление наведения будет иметь вид:

$$$display$$ U(\theta-t_i,x(\theta-t_i))\in \underset{u \in P}{\mathrm{argmin}}(\pi u,\tilde{\psi_i}(x(\theta-t_i))).$$display$$$

Будем строить управление наведения--уклонения в следующем виде:
- определяем $$inline$T$inline$$ в ходе построения альтернированного интеграла, решающего для нашей системы задачу наведения;
- рассматриваем движение системы в момент $$inline$t_i$inline$$ , $$inline$i=\overline{0,T}$inline$$ .
Проверяем для следующего шага пустоту пересечения:

$$$display$$ \pi (x(t_i) + P) \cap \Phi(\Theta,\tau)$$display$$$
- если множество достижимости системы из точки $$inline$x(t_i)$inline$$ не пересекается с множеством $$inline$\Phi(\Theta,t_i)$inline$$ , то первый игрок выбирает управление наведения;
- в противном случае первый игрок выбирает управление уклонения.
Отметим, что в общем случае условие окончания игры наведения может быть нарушено, т.е. $$inline$w(t_{i+1})\notin W(T)$inline$$ , где $$inline$T$inline$$ , $$inline$W(T)$inline$$ — это найденные ранее значения времени окончания игры и соответствующий ему альтернированный интеграл. В данном случае необходим пересчёт альтернированного интеграла Л.С. Понтрягина $$inline$W(T^j)$inline$$ и поиск соответствующего ему нового времени окончания игры $$inline$T^j$inline$$ , $$inline$j$inline$$ -натуральное число.

Применяя описанную стратегию, первый игрок в каждый момент времени будет либо наводиться на терминальное множество $$inline$M$inline$$ , сокращая расстояние до него, либо уклоняться от множества помехи $$inline$N$inline$$ , не попадая внутрь него.

Поскольку множество $$inline$N$inline$$ — строго выпуклый компакт, то для его огибания по описанной стратегии потребуется конечное время, а теорема об альтернативе гарантирует уклонение от множества $$inline$N$inline$$ в течение конечного времени. Поскольку задача наведения в условиях отсутствия помехи имеет решение за конечное время, то общее время завершения игры тоже конечно. При этом

$$$display$$ \bar{T}_{min} = T$$display$$$

— время завершения игры не меньше времени наведения, а $$inline$\bar{T}_{max}$inline$$ в общем случае оценить невозможно, хотя оно и существует.

Часть пятая — собираем всё вместе

Проверим теперь на практике, что даёт построенный способ управления сначала без учёта снижения колчества перекючений, а потом с учётом данной оптимизации. Для чего рассмотрим одну из типовых задач имеющих имя собственное — "Два крокодила", моделирующую движения двух инерционных объектов с разными динамическими параметрами. Соотвественно пусть теперь первый игрок стремится решить задачу А.

Соотвествующая система дифференциальных уравнений будет иметь вид:

$$$display$$\begin{array}{rcl} \dot{x}_1 &=& x_3,\\ \dot{x}_2 &=& x_4,\\ \dot{x}_3 &=& u_1 - v_1,\\ \dot{x}_4 &=& u_2 - v_2. \end{array}$$display$$$

Здесь $$inline$x_1,\ x_2$inline$$ — координаты объекта $$inline$x$inline$$ на плоскости, а $$inline$x_3,\ x_4$inline$$ — компоненты его скорости, $$inline$x(t) = [x_1(t),\ x_2(t),\ x_3(t),\ x_4(t)]^{T} \in \mathbb{R}^4;$inline$$
объект начинает движение из точки $$inline$x(t_0) = [3,\ 4,\ 0,\ 0]^{T} \in \mathbb{R}^4.$inline$$

Ограничения на управления $$inline$u(t),\ v(t)$inline$$ имеют вид

$$$display$$u(t) = [u_1(t),\ u_2(t)]^{T} \in P \subset \mathbb{R}^2,\ P = S_{1} ([0,\ 0]^{T}),$$display$$$

$$$display$$v(t) = [v_1(t),\ v_2(t)]^{T} \in Q \subset \mathbb{R}^2,\ Q = S_{0.9} ([0,\ 0]^{T}).$$display$$$

Первый игрок стремится перевести траекторию системы за конечное время на терминальное множество

$$$display$$M = S_{1}([12,\ 6]^{T}),$$display$$$

избежав при этом попадания на множество помехи

$$$display$$N = S_{2}([8,\ 5]^{T}).$$display$$$

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

$$$display$$T = 22,30.$$display$$$

Траектория движения системы и компоненты управления первого игрока показаны на следующих рисунках.

Траектория движения системы.

Зависимость первой компоненты управления от времени.

Зависимость второй компоненты управления от времени.

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

$$$display$$T = 8,80$$display$$$

а соответствующие траектории показаны на следующих рисунках.

Траектория движения системы.

Зависимость первой компоненты управления от времени.

Зависимость второй компоненты управления от времени.

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

Выводы

Что в итоге получаем (если дочитали, конечно, до этого места), — "наивный" и "продвинутый" способы управления динамической моделью, позволяющие конструктивно строить управление зависящие исключительно от позиции (см. книги Н.Н. Красовcкого, А.И. Субботина и Л.С. Понтрягина), причем не обладая полными знаниями о помехе.

Исходники посмотреть можно здесь: репозитарий на GitHub

Предупреждаю сразу, что некоторым элементам кода уже порядка 19 лет, и они делались в то время, когда в C++ не было синтаксического сахара, да так и остались, т.к. работают. За конструктивую критику будем признательны.

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

Отдельное спасибо Екатерине Кудешовой за критику.

Бибилиография

[1] Понтрягин Л.С. Жизнеописание Л. С. Понтрягина, математика, составленное им самим», М, 1983

[2] Красовский Н.Н. Теория управления движением: Линейные системы, М, Наука, 1968

[3] Григоренко Н.Л. Математические методы управления несколькими динамическими процессами, М, Издательство Московского Университета, 1990

[4] Ю.Н. Киселёв, С.Н. Аввакумов, М.В. Орлов ОПТИМАЛЬНОЕ УПРАВЛЕНИЕ. ЛИНЕЙНАЯ ТЕОРИЯ И ПРИЛОЖЕНИЯ, М, 2007

[5] Григоренко Н.Л., Камзолкин Д.В., Пивоварчук Д.Г. Линейные дифференциальные игры, М, 2007

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

[7] Ли Э.Б., Маркус Л. Основы теории оптимального управления, М, Наука, 1972

[8] Понтрягин Л.С., Болтянский В.Г., Гамкрелидзе Р.В., Мищенко Е.Ф. Математическая теория оптимальных процессов, М, Наука, 1969

Original source: habrahabr.ru (comments, light).

https://habrahabr.ru/post/332142/

<a href="https://www.liveinternet.ru/users/rss_rss_hh_new/post417829374/">РРіСЂРѕРІРѕРµ СѓРїСЂР°РІР»РµРЅРёРµ РјРѕРґРµР»СЏРј РІ СѓСЃР»РѕРІРёСЏС… РЅРµРїРѕР»РЅРѕР№ РёРЅС„РѕСЂРјР°С†РёРё</a><br/>(Р’ СЃРѕР°РІС‚РѕСЂСЃС‚РІРµ СЃ Р®Р»РёРµР№ Р¤РёР»РёРјРѕРЅРѕРІРѕР№ jul305a@gmail.com)
Р’РІРµРґРµРЅРёРµ
РџСЂРµРґСЃС‚Р°РІСЊС‚Рµ СЃРµР±Рµ, С‡С‚Рѕ Р»РµС‚РёС‚Рµ С‚Р°РєРѕР№ РІРµСЃСЊ РїРѕР±РµРґРёС‚РµР»СЊ РЅР° Р±Р°Р·Сѓ, Р±РѕРјР± СѓР¶Рµ РЅРµС‚, Рё РЅРёС‡РµРіРѕ РЅРµ РїСЂРµРґРІРµС‰Р°РµС‚ Р±РµРґС‹вЂ¦

Рђ С‚СѓС‚, СЃРєР°Р¶РµРј, РіРѕСЂРѕС‡РєР° РёР· С‚СѓРјР°РЅР°/РѕР±Р»Р°РєРѕРІ РІС‹СЃС‚СѓРїР°РµС‚ РЅРµРѕР¶РёРґР°РЅРЅРѕ, РёР»Рё, С‡С‚Рѕ РЅРµСЃРєРѕР»СЊРєРѕ С…СѓР¶Рµ, вЂ” РІРѕС‚ СЌС‚РѕвЂ¦ Р РІР°Рј СЂР°РґС‹, РЅРѕ РёСЃРєР»СЋС‡РёС‚РµР»СЊРЅРѕ РІ РєР°С‡РµСЃС‚РІРµ С†РµР»Рё:

#РїРѕСЂР°РІР°Р»РёС‚СЊ вЂ” Р° РІРѕС‚ РєР°Рє СЌС‚Рѕ РґРµР»Р°С‚СЊ СЃ РјР°С‚РµРјР°С‚РёС‡РµСЃРєРёРј СѓРєР»РѕРЅРѕРј СЃРµР№С‡Р°СЃ Рё Р±СѓРґРµРј СЂР°Р·Р±РёСЂР°С‚СЊСЃСЏ.
Р”Р° Рё РІРѕРѕР±С‰Рµ РµСЃС‚СЊ РјРЅРѕР¶РµСЃС‚РІРѕ СЃР»СѓС‡Р°РµРІ, РєРѕРіРґР° РЅРµРѕР±С…РѕРґРёРјРѕ СѓРєР»РѕРЅРёС‚СЊСЃСЏ РѕС‚ РЅРµРѕР¶РёРґР°РЅРЅРѕ РІРѕР·РЅРёРєС€РµР№ РїРѕРјРµС…Рё/РїСЂРµРіСЂР°РґС‹, РЅР°С€Р›РѕСЃСЊ, РєР°Рє РіРѕРІРѕСЂСЏС‚ РІ РЇРЅРґРµРєСЃРµ, РЅР°РїСЂРёРјРµСЂ.
РћРіРѕРІРѕСЂРєР° РґР»СЏ РјР°С‚РµРјР°С‚РёРєРѕРІ. РР·Р»РѕР¶РµРЅРёРµ РЅР°РїСЂР°РІР»РµРЅРѕ СЃРєРѕСЂРµ... <a href="https://www.liveinternet.ru/users/rss_rss_hh_new/post417829374/">Р§РёС‚Р°С‚СЊ РґР°Р»РµРµ...</a>

Комментировать

« Пред. запись — К дневнику — След. запись »

Страницы: [1] [Новые]

LiveInternetLiveInternet