2025-11-12T02:22:29.481811

PSN Game: Game-theoretic Prediction and Planning via a Player Selection Network

Qiu, Ouano, Palafox et al.
While game-theoretic planning frameworks are effective at modeling multi-agent interactions, they require solving large optimization problems where the number of variables increases with the number of agents, resulting in long computation times that limit their use in large-scale, real-time systems. To address this issue, we propose 1) PSN Game: a learning-based, game-theoretic prediction and planning framework that reduces runtime by learning a Player Selection Network (PSN); and 2) a Goal Inference Network (GIN) that makes it possible to use the PSN in incomplete information games where agents' intentions are unknown. A PSN outputs a player selection mask that distinguishes influential players from less relevant ones, enabling the ego player to solve a smaller, masked game involving only selected players. By reducing the number of players in the game, and therefore reducing the number of variables in the corresponding optimization problem, PSN directly lowers computation time. The PSN Game framework is more flexible than existing player selection methods as it 1) relies solely on observations of players' past trajectories, without requiring full state, action, or other game-specific information; and 2) requires no online parameter tuning. Experiments in both simulated scenarios and human trajectory datasets demonstrate that PSNs outperform baseline selection methods in 1) prediction accuracy; and 2) planning safety. PSNs also generalize effectively to real-world scenarios in which agents' objectives are unknown without fine-tuning. By selecting only the most relevant players for decision-making, PSN Game offers a general mechanism for reducing planning complexity that can be seamlessly integrated into existing multi-agent planning frameworks.
academic

PSN Game: Теоретико-игровое предсказание и планирование через сеть выбора игроков

Основная информация

  • ID статьи: 2505.00213
  • Название: PSN Game: Game-theoretic Prediction and Planning via a Player Selection Network
  • Авторы: Tianyu Qiu, Eric Ouano, Fernando Palafox, Christian Ellis, David Fridovich-Keil (Техасский университет в Остине)
  • Классификация: cs.RO (Робототехника), math.OC (Оптимизация и управление)
  • Дата публикации: 2025 (препринт arXiv)
  • Ссылка на статью: https://arxiv.org/abs/2505.00213

Аннотация

Хотя теоретико-игровые фреймворки планирования эффективны при моделировании взаимодействия многоагентных систем, они требуют решения крупномасштабных задач оптимизации, количество переменных в которых растёт с числом агентов, что приводит к чрезмерному времени вычисления и ограничивает применение в крупномасштабных системах реального времени. Для решения этой проблемы авторы предлагают: 1) PSN Game — фреймворк теоретико-игрового предсказания и планирования на основе обучения, который снижает время выполнения путём обучения сети выбора игроков (PSN); 2) сеть вывода целей (GIN), позволяющую PSN использоваться в играх с неполной информацией, когда намерения агентов неизвестны. PSN выводит маску выбора игроков, различая влиятельных игроков и менее релевантных, что позволяет собственному агенту решать меньшие маскированные игры, включающие только выбранных игроков. Путём сокращения количества игроков в игре и, следовательно, количества переменных в соответствующей задаче оптимизации, PSN напрямую снижает время вычисления.

Исследовательский контекст и мотивация

Определение проблемы

Основная проблема, с которой сталкиваются теоретико-игровые фреймворки планирования в многоагентных системах, заключается в том, что вычислительная сложность растёт кубически с числом агентов. Как показано на рисунке 2, при использовании существующих решателей время вычисления растёт как O(N³), где N — количество игроков. Это делает теоретико-игровые методы непрактичными для крупномасштабных систем реального времени.

Значимость исследования

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

Ограничения существующих методов

Существующие методы выбора игроков имеют следующие проблемы:

  1. Сильная зависимость от информации: Требуют управляемые входы, функции стоимости и другую информацию, специфичную для игры
  2. Сложная настройка параметров: Требуют настройку параметров, специфичных для окружения
  3. Окостенелые стратегии выбора: Методы ранжирования, основанные на простых эвристиках (расстояние, градиент), лишены адаптивности

Основные вклады

  1. Предложена неконтролируемая сеть выбора игроков (PSN): Обучается с использованием дифференцируемого решателя динамических игр, поддерживает обратное распространение через маски выбора
  2. Построена контролируемая сеть вывода целей (GIN): Выводит цели агентов из исторических траекторий, позволяя PSN применяться в сценариях с неизвестными намерениями
  3. Разработан фреймворк с уменьшающимся временным горизонтом: Использует PSN для эффективного выявления равновесных стратегий путём решения игр сокращённого размера
  4. Экспериментальная валидация: На многоагентных симуляциях и наборах данных реальных человеческих траекторий PSN Game эффективно сокращает размер игры на 50%-75%, достигая значительного ускорения

Подробное описание методов

Определение задачи

Рассмотрим конечный временной горизонт дискретной открытой игры Нэша N агентов, где каждый агент i имеет состояние xki∈Rnx_k^i \in \mathbb{R}^n и управляющий вход uki∈Rmu_k^i \in \mathbb{R}^m. Переход состояния агента подчиняется уравнению динамики: xk+1i=fi(xki,uki)x_{k+1}^i = f^i(x_k^i, u_k^i)

Цель каждого агента — минимизировать накопленную стоимость: Ji(x,u;θi)=∑k=0Tcki(xk,uk;θi)J^i(x,u;\theta^i) = \sum_{k=0}^T c_k^i(x_k, u_k; \theta^i)

Архитектура модели

1. Сеть выбора игроков (PSN)

PSN — это нейронная сеть, задача которой состоит в выводе маски MiM^i для балансирования производительности и разреженности. Предоставляются два варианта:

  • PSN-Full: На входе полная история состояний всех агентов x0:Kx_{0:K}
  • PSN-Partial: На входе частичные наблюдения {h(xk)}k=0K\{h(x_k)\}_{k=0}^K (например, только информация о положении)

Структура сети:

  • Кодировщик GRU (скрытая размерность 64) обрабатывает K-шаговую последовательность каждого агента
  • Слои MLP: 256→128→32 (активация ReLU, dropout=0.3)
  • Выходной слой Sigmoid производит непрерывную маску mji∈[0,1]m_j^i \in [0,1]

2. Маскированная игра Нэша

Определим маску выбора игроков Mi=(mji)∈{0,1}N−1M^i = (m_j^i) \in \{0,1\}^{N-1}, где:

1, & \text{агент j включён в игру} \\ 0, & \text{агент j исключён} \end{cases}$$ Маскированная игра $\Gamma^i(\tilde{x}_0, \tilde{f}; \theta, M^i)$ сохраняет только параметры и состояния агентов, наиболее релевантные для агента i. #### 3. Сеть вывода целей (GIN) GIN — это управляемая данными сеть, которая выводит цели агентов $p_g^i$ из частичных наблюдений траектории: - Входные данные: историческая траектория $\{h(x_k)\}_{k=0}^K$ - Выходные данные: 2D позиция цели $p_g^i$ - Функция потерь: среднеквадратичная ошибка $L_{Goal} = \frac{1}{|D| \cdot N}\sum_{d \in D}\sum_{i \in [N]} \|p_{g,ref}^i - G_\phi(x_{0:K})\|$ ### Проектирование функции потерь Обучение PSN использует составную функцию потерь: **Задача предсказания**: $$L_{Pred} = L_{Binary} + \sigma_1 L_{Sparsity} + \sigma_2 L_{Similarity}$$ **Задача планирования**: $$L_{Plan} = L_{Binary} + \sigma_3 L_{Sparsity} + \sigma_4 L_{Cost}$$ где: - $L_{Binary} = \frac{1}{N}\sum_{j=1}^N m_j^i(1-m_j^i)$: способствует бинаризации маски - $L_{Sparsity} = \frac{\|M^i\|_1}{N}$: поощряет выбор меньшего количества агентов - $L_{Similarity}$: поощряет выбор подмножества агентов, восстанавливающих наблюдаемые траектории - $L_{Cost}$: поощряет выбор подходящих агентов для минимизации стоимости игры ### Реализация с уменьшающимся временным горизонтом Алгоритм на каждом временном шаге $k$: 1. Выводит цели агентов через GIN 2. Получает адаптивную маску $M_k^i$ с использованием PSN 3. Решает маскированную игру для получения стратегии OLNE 4. Выполняет первый шаг управляющего входа и обновляет состояние ## Экспериментальная установка ### Наборы данных **Сценарии симуляции**: - Сценарий с 4 агентами: окружение 5м×5м - Сценарий с 10 агентами: окружение 7м×7м - Сценарий с 20 агентами: окружение 7м×7м (тестирование масштабируемости) **Реальные данные**: - Набор данных пешеходов CITR: окружение 7.5м×25.5м, 10 пешеходов **Параметры игры**: - Пространство состояний: 4 измерения (положение + скорость) - Динамика: модель двойного интегратора - Функция стоимости: включает отслеживание целей, штраф за скорость, стоимость управления и избежание столкновений ### Метрики оценки **Задача предсказания**: - ADE (Average Displacement Error): средняя ошибка смещения - FDE (Final Displacement Error): ошибка финального смещения - Consistency: согласованность выбора **Задача планирования**: - Navigation Cost: стоимость навигации - Collision Cost: стоимость столкновения - Control Cost: стоимость управления - Minimum Distance: минимальное расстояние - Trajectory Smoothness: гладкость траектории - Trajectory Length: длина траектории ### Методы сравнения 1. **Варианты PSN**: PSN-Threshold, PSN-Rank 2. **Методы на основе расстояния**: Distance, kNNs 3. **Методы на основе градиента**: Gradient, Hessian, Cost Evolution 4. **Методы на основе ограничений**: BF (Barrier Function), CBF (Control Barrier Function) ## Результаты экспериментов ### Основные результаты #### Производительность предсказания (Таблица 2) В сценарии с 4 агентами: - PSN-Full ADE: 0.1834м (оптимально) - PSN-Partial ADE: 0.1876м - Лучший базовый метод (Cost Evolution) ADE: 0.1861м В сценарии с 10 агентами: - PSN-Partial ADE: 0.2213м (оптимально) - PSN-Full ADE: 0.2314м - Лучший базовый метод (kNNs) ADE: 0.2343м #### Производительность планирования (Таблица 3) PSN показывает выдающиеся результаты по показателям безопасности: - **Стоимость столкновения**: оптимальна в сценариях с 4 и 10 агентами - **Минимальное расстояние**: входит в тройку лучших в обоих сценариях - Деградация безопасности по сравнению с полной игрой минимальна ### Адаптивность к играм с неполной информацией В сценариях с неизвестными целями (Таблицы 4-5) PSN в сочетании с GIN: - Показатели предсказания остаются в топ-2 - Показатели планирования входят в топ-3 - Показатели безопасности остаются оптимальными ### Проверка масштабируемости PSN, обученная на 10 агентах, в сценарии с 20 агентами: - PSN-Full ADE: 0.3108м (оптимально) - PSN-Partial ADE: 0.3152м (второе место) - Адаптируется к более крупномасштабным сценариям без переобучения ### Обобщение на реальные данные На наборе данных пешеходов CITR: - PSN-Partial ADE: 0.4931м (оптимально) - PSN-Full ADE: 0.4966м - Даже превосходит производительность решения полной игры ## Связанные работы ### Теоретико-игровое планирование Существующие методы сосредоточены в основном на малых окружениях (≤5 агентов), используя итеративные решатели стиля Ньютона. Сложность растёт кубически с числом игроков, что является фундаментальным препятствием для крупномасштабных систем реального времени. ### Методы выбора игроков **Методы на основе порогов**: Выбирают агентов на основе предопределённого порога расстояния, требуют обширной настройки параметров. **Методы ранжирования**: Выбирают top-k наиболее влиятельных агентов, но фиксированное количество выбора может быть слишком агрессивным или консервативным. **Преимущества данной работы**: 1. Требуют только наблюдения исторических траекторий, без привилегированной информации 2. Не требуют онлайн-настройки параметров 3. Адаптивно выбирают количество агентов ## Заключение и обсуждение ### Основные выводы 1. PSN Game успешно сокращает размер игры на 50%-75%, достигая значительного ускорения вычисления 2. Превосходит существующие базовые методы по точности предсказания и безопасности планирования 3. Демонстрирует хорошую способность к обобщению, адаптируясь к более крупномасштабным сценариям и реальным данным ### Ограничения 1. **Аппроксимация непрерывной маски**: Использует непрерывную маску для поддержки обратного распространения, требуя пороговой обработки во время выполнения 2. **Зависимость от обучающих данных**: Требует обучающих данных, сгенерированных полной игрой 3. **Предположения о модели динамики**: Эксперименты в основном основаны на модели двойного интегратора ### Будущие направления 1. Расширение на более сложные модели динамики 2. Исследование вывода других типов параметров игры 3. Изучение стратегий сквозного обучения ## Глубокая оценка ### Преимущества 1. **Значимость проблемы**: Решает основное узкое место вычисления в теоретико-игровом планировании 2. **Инновационность метода**: Впервые объединяет глубокое обучение и теорию игр для выбора игроков 3. **Полнота экспериментов**: Охватывает симуляции и реальные данные, валидирует несколько гипотез 4. **Практическая ценность**: Предоставляет универсальный механизм, который можно непосредственно интегрировать в существующие фреймворки ### Недостатки 1. **Отсутствие теоретического анализа**: Не предоставляет теоретических гарантий сходимости или ошибки аппроксимации 2. **Вычислительные издержки**: Хотя сокращает время решения игры, добавляет издержки вывода сети 3. **Ограничения сценариев**: Валидация в основном на задачах навигации, применимость к другим типам игр неизвестна ### Влияние 1. **Академический вклад**: Предоставляет новый подход к решению крупномасштабных многоагентных систем 2. **Практическое применение**: Имеет прямое применение в автономном вождении, роботизированных группах и других областях 3. **Воспроизводимость**: Предоставляет подробные детали реализации и параметры ### Применимые сценарии 1. **Плотные многоагентные окружения**: Такие как городской трафик, навигация толпы 2. **Системы с высокими требованиями к реальному времени**: Требующие частого переплана в динамических окружениях 3. **Сценарии с частичной наблюдаемостью**: Игры с неполной информацией, где намерения агентов неизвестны ## Библиография Статья цитирует 35 связанных работ, в основном охватывающих: - Методы теоретико-игрового планирования [8, 28, 9, 15] - Моделирование многоагентного взаимодействия [17, 20, 21, 24] - Эвристические методы выбора игроков [2, 27, 30] - Механизмы внимания и выбора соседей [3, 6, 32] --- Данная статья вносит важный вклад в решение проблемы вычислительной сложности в теоретико-игровом планировании, значительно повышая вычислительную эффективность многоагентных систем благодаря управляемому выбору игроков, открывая путь для крупномасштабных приложений реального времени.