Ушаков Андрей Вячеславович, Иванов Алексей Геннадьевич

Построение трехмерных максимальных стабильных мостов

Дифференциальная игра в исходном пространстве и эквивалентная игра

В исходной игре фазовый вектор x может иметь любую размерность m ≥ 3, но выпуклое целевое множество M зависит только от трех выделенных компонент фазового вектора. Предполагаем, что ограничения P, Q на управления первого и второго игроков — отрезки.

Стандартной заменой переменных (при помощи трех строк фундаментальной матрицы Коши) переходим к эквивалентной дифференциальной игре без фазовой переменной в правой части. Здесь фазовый вектор y имеет размерность 3.

Аппроксимирующая игра

Для построения максимального стабильного моста в рамках аппроксимирующей игры разбиваем ось времени с шагом Δ влево от момента окончания θ точками t_i, при этом t₀=θ. На каждом шаге замораживаем динамику эквивалентной системы. Результатом построений будут t-сечения W_i=W(t_i) ⊂ R³ аппроксимирующего максимального стабильного моста W.
Построение сечений производится в попятной процедуре: на первом шаге на основе целевого выпуклого многогранника строится выпуклый многогранник W₁; на втором шаге на основе W₁ идет построение выпуклого многогранника W₂ и т.д.
Построение очередного сечения W_i+1 моста сводится к операциям над выпуклыми многогранниками, а именно, к нахождению алгебраической суммы F_i многогранника W_i и отрезка −Δ·P_i (учет действия первого игрока) и нахождению геометрической разности многогранника F_i и отрезка Δ·Q_i (учет действия второго игрока). Последнее эквивалентно взятию выпуклой оболочки разности ρ(•, F_i) − ρ(•, Δ·Q_i) опорных функций множеств F_i и Δ·Q_i.
Для непрерывной, положительно однородной, кусочно-линейной функции γ : l → γ(l) с выпуклыми конусами линейности используем следующее представление: вводим на единичной сфере S сетку (граф) G(γ), определяемую пересечением сферы с конусами линейности функции γ. В каждом узле G(γ) записываем значение функции γ.
При построении опорной функции ρ(•, W_i+1) многогранника W_i+1 требуем, чтобы все конусы линейности функции ρ(•, W_i) были трехгранными и, соответственно, секторы сетки G(ρ(•, W_i)) — треугольными. Для этого нужно разбить секторы начальной сетки на треугольные и в дальнейшем при образовании новых сеток вводить в случае необходимости дополнительное разбиение (триангуляцию сетки).

Учет действия первого игрока

Сетка G(ρ(•, F_i)) есть результат наложения сеток G(ρ(•, W_i)) и G(ρ(•, P_i)). Поскольку P_i — отрезок в R³, то G(ρ(•, P_i)) представляет собой окружность на сфере S — пересечение сферы с проходящей через нуль плоскостью, ортогональной P_i. При наложении сеток появляются новые узлы. Поэтому при построении сетки G(ρ(•, F_i)) устанавливаем дополнительные связи для того, чтобы конусы линейности функции ρ(•, F_i) были трехгранными.

Учет действия второго игрока

Пересчитываем значения опорной функции ρ(•, F_i) в узлах сетки G(ρ(•, F_i)) с учетом действия второго игрока. Получаем функцию η_i(l).
Для перехода к опорной функции многогранника W_i+1 следует отбросить в графе G(ρ(•, F_i)) узлы, связанные с "нарушением" локальной выпуклости функции η_i(l). При этом осуществляется переход к новой кусочно-линейной функции, анализируется нарушение ее локальной выпуклости и т.д.
С этой целью разработана итерационная процедура. Организуем список "подозрительных" связей между узлами. Первоначально в этот список заносятся связи сетки G(ρ(•, F_i)), "разрубаемые" графом G(ρ(•, Q_i)) и соседние к ним. Затем идет корректировка этих связей, суть которой в исправлении нарушений локальной выпуклости. Список подозрительных связей при этом может пополняться другими связями. Наоборот, связи, удовлетворяющие условиям локальной выпуклости, удаляются из списка. Процесс заканчивается при исчерпании массива подозрительных связей.

Базовые статьи

Зарх М.А., Пацко В.С.
Численное решение дифференциальной игры наведения третьего порядка.
Изв. АН СССР. Техническая кибернетика. 1987. №6. C.162–169.

Зарх М.А., Пацко В.С.
Построение максимальных стабильных мостов в линейной дифференциальной игре.
сб. "Синтез оптимального управления в игровых системах", Свердловск, 1986. С.46–61.

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

Алгоритм построения максимального стабильного моста

/* Подготовительные действия */
Получение структуры выпуклого многогранника M=W₀ по заданным вершинам
Построение графа (сетки G(ρ(W₀))) выпуклого многогранника по его структуре
Триангуляция построенного графа (сетки G(ρ(W₀)))

/* Построение t-сечений W_i=W(t_i) максимального стабильного моста W */
Цикл пока ((θ-t_i) < τ_f)
{
	Построение сетки G(ρ(F_i))
	Построение набора П (набора связей, на которых функция φ_i может быть не выпукла)
	Цикл пока набор П не пуст
	{
		Если функции φ_i выпукла на первой связи из набора П, то
		{	Удаляем первую связь из набора П	}
		иначе
		{	Корректировка функции φ_i и набора П	}
	}
}

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

Работа с программой

Представленная здесь программа позволяет просматривать уже просчитанные максимальные стабильные мосты. Для этого запустите программу (файл LinearDiff3DGame.OpenGLVisualizer.exe), выберите в меню "Actions" пункт "Load" и в появившемся диалоговом окне выберите файл с посчитанным мостом (файл типа .dat).

После того, как посчитанный мост загрузится, его можно просматривать, выбирая при помощи ползунка (внизу слева) просматриваемое t-сечение. Само t-сечение можно вращать при помощи клавиш "A" (влево), "D" (вправо), "W" (вверх), "S" (вниз). Клавишами "C" и "Z" сечение приближается и отдаляется.

Архив с программой называется MaxStableBridgeBuilder.zip. Для работы программа требует операционную систему не ниже WindowsXP, предустановленный .NET Framework версии не ниже 3.5. При работе программы могут возникать артефакты визуализации, связанные с поддержкой OpenGL драйверами видеокарт.

Примеры

1. Материальная точка

Система имеет вид:

Параметры расчета моста: c_* = 2.5, время окончания счета τ_f = 6. Посчитанный мост находится в файле MaterialPointBridge.dat. Каждое t-сечение представляет собой срезку на уровне c_* надграфика функции цены дифференциальной игры с динамикой

фиксированным моментом окончания и терминальной функцией платы γ.

2. Осциллятор

Система имеет вид:

Параметры расчета моста: c_* = 2.5, время окончания счета τ_f = 6. Посчитанный мост находится в файле OscillatorBridge.dat.

3. Задача о посадке самолета с трехмерным терминальным множеством

Система имеет вид:

Параметры расчета моста: время окончания счета τ_f = 6. Посчитанный мост находится в файле AirplaneTaskBridge.dat.