Дифференциальные игры с конечным горизонтом

Дифференциальные игры с конечным горизонтом

Терминальный момент: что происходит «в конце»

В задачах с конечным горизонтом [0, T] состояние системы x(T) имеет особый статус: функция g(x(T)) задаёт «терминальный выигрыш». Это определяет «границы» — наборы начальных состояний x₀, из которых P или E могут гарантировать нужный исход. Математически: функция ценности определяется из HJI с терминальным условием V(x,T) = g(x) и «считается назад» до t = 0.

Структура решения через обратную индукцию

Принцип оптимальности даёт: V(x,t) = min_u max_v {F(x,u,v,t)dt + V(x+f·dt, t+dt)}.

Это «уравнение Беллмана» в обратном времени: зная V при t+dt, вычисляем V при t. Начинаем от T (где V(x,T) = g(x)) и «идём назад».

Для LQ-игр: V(x,t) = xᵀP(t)x (квадратичная по x), P(t) — матрица Риккати-Айзекса, удовлетворяющая ОДУ.

LQ-игра с конечным горизонтом

ẋ = Ax + Bu + Cv, J = xᵀ(T)Gx(T) + ∫₀ᵀ [xᵀQx + uᵀRu − vᵀSv] dt.

Уравнение Риккати-Айзекса:

−Ṗ = AᵀP + PA + Q − PBR⁻¹BᵀP + PCS⁻¹CᵀP, P(T) = G.

(Интегрируем назад по времени от T к 0.)

Оптимальные стратегии (линейные обратные связи):

u*(t) = −R⁻¹Bᵀ P(t) x(t) v*(t) = S⁻¹Cᵀ P(t) x(t)

Условие разрешимости: уравнение Риккати должно иметь решение на всём [0,T]. При больших T (или больших C) решение может «взорваться» — значение игры не ограничено.

Зоны выживания и захвата

Для задач с терминальной «мишенью»: T = «целевое множество» (например, шар вокруг E).

V(x, T) = 1 если x ∈ T, иначе −1.

Функция ценности принимает значения в {−1, +1}: P захватил (±1 для P) или E убежал.

Reach-Avoid множество: начальные условия x₀, из которых P может гарантировать захват. Граница = барьерная поверхность.

Вычисление: level-set метод (Hamilton-Jacobi toolbox). V(x,t) = 0 — граница. V(x,t) < 0 — зона P, V(x,t) > 0 — зона E.

Полный разбор: двумерная игра захвата

Система: ẋP = uP, ẋE = uE, |uP| ≤ αP, |uE| ≤ αE. Захват: |xP − xE| ≤ l.

Заменим переменную: r = xP − xE (относительное положение). ṙ = uP − uE.

J = 0 если |r(T)| ≤ l (захват), 1 иначе (уклонение).

Простейший 1D-случай (r ∈ ℝ): HJI: ∂V/∂t + min_u max_v [(u−v) ∂V/∂r] = 0.

Функция ценности V(r,t): V = 0 если |r| ≤ l, и V(r,t) = V(|r| − (αP−αE)(T−t), T) для |r| > l.

При αP > αE: P захватывает E если |r(0)| ≤ l + (αP−αE)T. Зона захвата растёт с T.

При αP < αE: зона захвата — только |r(0)| ≤ l (уже захвачен), E убегает.

Численные методы для HJI

Метод конечных разностей: дискретизация по x на сетке, интегрирование HJI назад по t.

Требования: монотонная (upwind) схема для правильного вязкостного решения. Число точек: O((1/h)^n) — экспоненциально от размерности!

Проклятие размерности: для n=4 и шаге h=0.1: 10⁴ = 10,000 точек — выполнимо. Для n=6: 10⁶ — сложно. Для n=10: невозможно.

Выходы:

• Deep learning для HJI (DeepReach, 2021): нейросеть аппроксимирует V(x,t) → работает в высоких размерностях
• Линеаризация: V ≈ xᵀP(t)x (LQ-приближение)
• PINN (Physics-Informed Neural Networks): обучение нейросети удовлетворять HJI как физическому ограничению

Задачи с фиксированным временем

В играх с конечным горизонтом важны несколько вариантов терминальных условий:

• Фиксированное T, свободное x(T): V(x, T) = g(x) — задача с терминальной стоимостью
• Фиксированный xT: достичь заданного состояния — V(xT, T) = 0, V(x, T) = +∞ для x ≠ xT (вырождение)
• Свободное T (момент остановки): T определяется первым моментом, когда x(T) попадает в целевое множество — игры с моментом остановки

Принцип динамического программирования

Принцип оптимальности Беллмана для игр: V(x, t) = inf_u sup_v {∫_t^{t+δ} F dτ + V(x(t+δ), t+δ)}. Это локальное условие порождает уравнение HJI и связывает значения в разные моменты времени. Решение — вязкостное решение HJI с терминальным условием V(x, T) = g(x), интегрируемое назад от T до 0.

Reachability и зоны достижимости

Для практических задач безопасности часто важен не оптимум, а множество достижимости — какие состояния x игрок может гарантировать в момент T при наихудшей стратегии противника. Это решается через signed distance: определяем V(x, T) как расстояние со знаком до целевого множества и решаем HJI назад. Уровневое множество {V ≤ 0} — зона гарантированного достижения.

Применения

Дифференциальные игры с конечным горизонтом — основа задач безопасной навигации квадрокоптеров (Tomlin, Mitchell), маневрирования военных самолётов (Air Combat Maneuvering), обхода препятствий автономным транспортом, управления реактором на конечном временном окне. Библиотеки helperOC, hj_reachability реализуют эти алгоритмы для размерностей до 5-6.