Задача преследования-уклонения

Самая старая игра мира

Охотник преследует зайца. Лиса гонится за кроликом. Военный перехватчик — за целью. Задача преследования-уклонения (Pursuit-Evasion, PE) — одна из древнейших прикладных математических задач. Айзекс придал ей строгую математическую форму и открыл первые удивительные результаты: оптимальная стратегия не всегда «лети прямо к противнику». Иногда нужно «упреждать». В сложных случаях стратегия определяется топологией пространства и «барьерной поверхностью», разделяющей зоны захвата и уклонения.

Постановка: простейший вариант

Два игрока в ℝ². Преследователь P с позицией xP ∈ ℝ², скорость |u| ≤ α. Убегающий E с позицией xE ∈ ℝ², скорость |v| ≤ β.

Динамика: ẋP = u, ẋE = v, |u| ≤ α, |v| ≤ β.

Расстояние: r(t) = |xP(t) − xE(t)|.

Захват: r(t) ≤ l (захватывающий радиус). P хочет достигнуть захвата, E — избежать.

Три основных случая

Случай 1: α > β (P быстрее)

Захват гарантирован при любой стратегии E. Оптимальная стратегия P: Pure Pursuit (просто лети к E) — обеспечивает захват за конечное время.

Но не оптимальна по времени захвата! Оптимальная стратегия: Constant Bearing Navigation (курс постоянного пеленга) — угол «пеленга» (угол на цель) остаётся постоянным. Это стратегия, используемая ракетами PN (Proportional Navigation).

Почему Pure Pursuit субоптимальна? При «крутых» манёврах цели P «тянется» за E, проходя больший путь. Constant Bearing держит «курс перехвата» и сокращает расстояние быстрее.

Случай 2: α = β (одинаковые скорости)

Захват возможен, если E «к западу» от P или другие специфические начальные условия. «Классическая игра в кошки-мышки» — неоднозначный случай.

Случай 3: α < β (E быстрее)

Уклонение гарантировано. Оптимальная стратегия E: бежать напрямую от P (максимизировать расстояние).

Игра Айзекса «Homicidal Chauffeur»

Более интересный случай: P — автомобиль с минимальным радиусом поворота r (кинематически ограниченный), E — пешеход. Иногда ограниченная маневренность P позволяет E уйти даже при меньшей скорости!

Динамика P: ẋP = α cos θ, ẏP = α sin θ, θ̇ = u/r (u ∈ [−1,1]). Динамика E: ẋE = v₁, ẏE = v₂, v₁² + v₂² ≤ β².

Барьерная поверхность: Айзекс нашёл геометрию области начальных условий, из которых захват гарантирован (Capture Zone) и из которых уклонение гарантировано (Escape Zone). Граница — «барьер» — является особым решением HJI.

Стратегия «упреждения» (Proportional Navigation)

В реальных ракетных системах используется пропорциональная навигация (PN):

aN = N · |r| · LOS_rate

где aN — поперечное ускорение ракеты, N — навигационная константа (обычно 3-5), LOS_rate — угловая скорость линии визирования (Line of Sight).

Оптимальность: при линейной динамике и малом угле PN с N → ∞ оптимальна. При N = 4-5 практически близка к оптимуму.

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

Численный пример: оптимальное время захвата

Параметры: P и E в ℝ², α = 2, β = 1, l = 0 (точечный захват). Начальные позиции: xP = (0,0), xE = (10, 0).

Оптимальная стратегия P (straight line chase): лети напрямую к xE(t). Так как α = 2β, P нагоняет E: dr/dt = −(α − β·cos φ), где φ — угол между u и v.

При оптимальной стратегии E (максимизировать r): v направлен прочь от P, φ = π. Тогда dr/dt = −(α − β) = −1. Время захвата: T = r₀ = 10.

Если E маневрирует поперечно: P всё равно нагонит (α > β), только нелинейной траекторией. Время будет > 10.

Применения в автономных системах

Беспилотники: задача безопасного избегания столкновений — реверс задачи преследования. Автомобиль A хочет «убежать» от B, чтобы не столкнуться. Оптимальный «убегающий» алгоритм минимизирует риск.

Multi-UAV захват: группа преследователей против одного убегающего. Результат: достаточно 2 скоординированных преследователя для гарантированного захвата даже более быстрого E в ограниченном пространстве.

Роботы: patrol-evader задача для автономных охранных роботов. Библиотека SafeRL использует HJI для вычисления «безопасных» управлений в реальном времени.

Игры с препятствиями

В реальных задачах преследования пространство содержит препятствия — стены, здания, запретные зоны. Это резко усложняет задачу: оптимальные траектории огибают препятствия, и аналитические решения редки. Численное решение HJI на сетке учитывает геометрию через граничные условия. Современные методы (Reach-avoid HJ analysis, Tomlin et al.) вычисляют «безопасные множества» — состояния, из которых преследователь гарантированно достигает цели, избегая столкновений с препятствиями.

Кооперативное преследование

Когда несколько преследователей действуют совместно, задача становится принципиально другой: даже более медленные преследователи могут гарантированно поймать быстрого убегающего, если их количество достаточно. Классический результат: в плоскости 3 кругов (область внутри окружности) достаточно одного преследователя любой ненулевой скорости для гарантированного захвата (теорема о львах и людях). На полуплоскости при равных скоростях достаточно одного, на плоскости — требуются специальные стратегии. В играх pursuit на графах задача определения числа необходимых преследователей называется cop number и связана с топологией графа.

Игры с неполной информацией

В реальных задачах преследователь не всегда видит убегающего точно. Возникают игры с частичной информацией: преследователь имеет шумные измерения, должен оценивать состояние и одновременно действовать. Это объединение задач теории оценивания (фильтр Калмана) и теории дифференциальных игр. Sub-class: Search games — преследователь не видит цель вообще и должен искать её случайным или детерминированным паттерном.

Реализация в реальном времени

Для практических систем (автономных автомобилей, дронов) задача преследования-уклонения должна решаться в реальном времени:

Offline: предвычислить функцию ценности V на сетке состояний
Online: lookup ближайшего значения V и градиента, выбор оптимального управления
MPC (Model Predictive Control): на каждом шаге решать задачу оптимизации на коротком горизонте

Применения

Военная авиация: системы автоматического перехвата (AIM-120 AMRAAM, Patriot)
Космос: маневрирование спутников для уклонения от обломков
Безопасность: автоматические системы охраны периметра
Спорт: анализ оптимальных стратегий в командных играх (хоккей, футбол)
Биология: моделирование охоты хищников, эволюция систем «хищник-жертва»