Игровое уравнение Гамильтона-Якоби-Айзекса

От ГЯ-Беллмана к ГЯ-Айзекса

В теории оптимального управления ценовая функция V(x,t) удовлетворяет уравнению Гамильтона-Якоби-Беллмана (HJB). Когда появляется второй игрок с противоположными интересами, уравнение модифицируется: вместо min по u появляется min по u и max по v одновременно. Это уравнение Гамильтона-Якоби-Айзекса (HJI) — центральное уравнение теории дифференциальных игр. Его решение — функция ценности игры V(x,t) — задаёт оптимальные стратегии обоих игроков.

Функция ценности игры

Определение: V(x, t) = min_{u(·)} max_{v(·)} J(x, t; u(·), v(·)) — значение игры, начатой из состояния x в момент t.

Терминальное условие: V(x, T) = g(x) — стоимость конечного состояния.

V(x, t) должна удовлетворять уравнению в частных производных.

Вывод уравнения HJI

Используем принцип оптимальности: при оптимальной игре

V(x, t) = min_u max_v [F(x,u,v,t)dt + V(x + f(x,u,v)dt, t + dt)]

Разложим V в ряд Тейлора: V(x + fdt, t + dt) ≈ V + V_t dt + ∇V·f dt.

min_u max_v [F dt + V_t dt + ∇V·f dt] = 0

Разделив на dt:

Уравнение HJI: ∂V/∂t + H*(x, t, ∇V) = 0

где игровой гамильтониан: H*(x, t, p) = min_{u∈U} max_{v∈V} {F(x, u, v, t) + pᵀ f(x, u, v, t)}

здесь p = ∇_x V — «сопряжённые переменные» (аналог импульса).

Условие Айзекса

Условие Айзекса: min_{u∈U} max_{v∈V} H(x,u,v,p) = max_{v∈V} min_{u∈U} H(x,u,v,p)

Где H(x,u,v,p) = F + pᵀf — лагранжиан задачи.

Смысл: «игровой гамильтониан» одинаков при перестановке min и max. Это аналог условия «равновесия» в статических играх.

Когда выполнено: при компактных U, V и непрерывном H — всегда (теорема минимакса Неймана). При несвязных управлениях могут быть проблемы.

Если нарушено: значение игры может зависеть от порядка ходов (кто первый «объявляет» стратегию). Нужно различать «нижнее значение» V⁻ = max_v min_u J и «верхнее» V⁺ = min_u max_v J.

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

При известном V(x,t) оптимальные стратегии:

u*(x,t) = argmin_{u∈U} H(x, u, v*(x,t), ∇V) (для P) v*(x,t) = argmax_{v∈V} H(x, u*(x,t), v, ∇V) (для E)

При выполнении условия Айзекса эти стратегии существуют и определяются одновременно через седловую точку H*.

Регулярность и вязкостные решения

HJI — нелинейное УЧП первого порядка. Классическое (гладкое) решение существует не всегда: могут возникать «особые» поверхности — барьеры, переключения, несвязности. Эти особенности имеют ясный физический смысл (граница «зоны захвата»), но нарушают гладкость V.

Вязкостные решения (Кранделл-Лионс, 1983): расширенное понятие решения для нелинейных УЧП первого порядка. Единственность вязкостного решения HJI установлена при разумных условиях (Evans-Souganidis, 1984).

Численные методы: конечные разности с монотонными схемами (Osher-Shu upwind), level-set методы (Osher-Sethian). Эти методы точно аппроксимируют вязкостное решение.

Полный разбор: простая игра преследования в ℝ

Динамика: ẋ = u − v, x ∈ ℝ, u ∈ [−1,1] (P), v ∈ [−a,a] (E, a < 1).

Функционал: J = x(T)² (минимизируем удалённость при T).

HJI: ∂V/∂t + min_{|u|≤1} max_{|v|≤a} [(u−v) ∂V/∂x] = 0.

Игровой гамильтониан: H* = min_{u} max_{v} [(u−v) p] = min_u [up − a|p|] = −|p| − a|p| = −(1+a)|p|.

(u* = −sign(p), v* = a·sign(p))

HJI: ∂V/∂t − (1+a)|∂V/∂x| = 0, V(x,T) = x².

Решение ищем как V(x,t) = φ(x − u*(T−t))... сложно аналитически. Для t близкого к T: V ≈ x² − (1+a)·2|x|·(T−t) + O((T−t)²). Оптимальная стратегия P: u* = −sign(x), то есть двигаться к нулю (к равновесию).

Применения

HJI используется в теории управления робастными регуляторами (H∞-управление), в авиации (управление перехватчиком), в автономных системах (безопасная навигация). Численное решение HJI на сетке — стандартный метод в «Hamiltion-Jacobi toolbox» (MATLAB) и BEACLS (C++).

Численное решение HJI

В отличие от линейных УЧП, HJI требует специализированных схем. Классическая монотонная схема upwind:

Дискретизировать состояние x на сетке xᵢ
Вычислить градиент ∇V через односторонние разности с учётом знака
Вычислить H* через минимакс на каждой ячейке
Шаг вперёд по времени: V^{n+1} = V^n − Δt · H*

Схема устойчива при условии CFL: Δt ≤ Δx / max|f|. Сходимость к вязкостному решению гарантирована теоремой Барля-Сугандиса.

Размерность как ограничение

Главная проблема HJI — проклятие размерности: для размерности n требуется N^n узлов сетки, где N — число узлов на ось. При n = 6 (стандартная задача 3D кинематики двух тел) и N = 100 это 10¹² ячеек — на грани возможного. Современные методы для высокой размерности:

Decomposition: разбиение задачи на подзадачи меньшей размерности (Mitchell, Tomlin)
Sparse grids (Smolyak): уменьшение числа узлов до O(N log^n)
Neural network approximation: Deep BSDE (E-Han-Jentzen, 2017), PINNs — нейросеть аппроксимирует V(x,t), решая HJI как loss function
Reinforcement learning: вместо явного решения HJI — обучение оптимальной политики через симуляцию

Применения в реальном времени

Для задач реального времени (авиация, автономные машины) используется off-line вычисление V на сетке плюс on-line lookup. Toolbox helperOC позволяет за минуты вычислить «безопасное множество» для квадрокоптеров, после чего управление в полёте выбирается по табличным значениям ∇V.