A Player Selection Network for Scalable Game-Theoretic Prediction and Planning

1. 문제 정의 (Problem)

게임 이론적 계획 (Game-theoretic planning) 프레임워크는 다중 에이전트 상호작용을 모델링하는 데 효과적이지만, 확장성 (Scalability) 에 심각한 한계가 있습니다.

• 계산 복잡도: 에이전트 수가 증가함에 따라 최적화 문제의 변수 수가 급증하며, 계산 시간은 에이전트 수에 대해 세제곱 (cubic, $O(N^3)$) 으로 증가합니다. 이는 대규모 실시간 시스템 (예: 복잡한 교통 상황, 군집 로봇) 에서의 적용을 불가능하게 만듭니다.
• 기존 방법의 한계: 기존 플레이어 선택 방법들은 거리 기반 임계값 (Threshold-based) 이나 순위 기반 (Ranking-based) 휴리스틱에 의존합니다. 이러한 방법들은 종종 제어 입력이나 게임 특정 파라미터 (비용 함수 등) 를 필요로 하거나, 고정된 수의 에이전트를 선택해야 하여 환경에 따라 매개변수 튜닝이 필요하고, 중요한 에이전트를 누락하거나 불필요한 에이전트를 포함할 수 있습니다.

2. 제안 방법론 (Methodology)

저자들은 PSN Game이라는 새로운 학습 기반 게임 이론적 프레임워크를 제안합니다. 이는 두 가지 핵심 네트워크를 통해 게임 크기를 축소하고 효율성을 높입니다.

A. 플레이어 선택 네트워크 (Player Selection Network, PSN)

• 역할: 자아 에이전트 (Ego agent) 와 주변 에이전트들의 과거 궤적 (Trajectories) 만을 입력받아, 상호작용에 가장 중요한 '영향력 있는 플레이어'를 식별하는 플레이어 선택 마스크 (Mask) 를 출력합니다.
• 작동 원리:
  • PSN-Full: 모든 에이전트의 과거 상태 (위치, 속도 등) 를 입력받습니다.
  • PSN-Partial: 부분적인 관측 정보 (예: 위치만) 만을 입력받습니다.
  • 소프트 마스크 (Soft Mask): 이산적인 선택 (0 또는 1) 은 역전파를 어렵게 하므로, 네트워크는 $[0, 1]$ 범위의 연속적인 값을 출력합니다. 이는 공유 비용 (Shared cost) 을 재가중치 (Reweight) 하는 방식으로 구현되며, 런타임 시 임계값을 적용하여 이진 마스크로 변환됩니다.
  • 학습: 미분 가능한 게임 솔버 (Differentiable game solver) 를 통해 역전파가 가능하도록 훈련됩니다. 손실 함수는 이진화 (Binary), 희소성 (Sparsity, 선택된 에이전트 수 최소화), 유사성 (Similarity, 관측된 궤적 복원), 비용 (Cost, 게임 비용 최소화) 을 고려합니다.

B. 목표 추론 네트워크 (Goal Inference Network, GIN)

• 역할: 다른 에이전트의 의도 (목표) 를 알 수 없는 불완전 정보 게임 (Incomplete-information games) 환경에서 작동할 수 있도록 합니다.
• 작동 원리: 과거 궤적 관측치를 바탕으로 다른 에이전트의 목표 (Goal) 를 추론하여, PSN 이 선택한 소수의 에이전트와 함께 축소된 게임 (Masked Game) 을 구성합니다.

C. 축소된 게임 해결 (Masked Game Solver)

• PSN 이 선정한 소수의 에이전트 (가장 관련성 높은 에이전트) 만을 포함하는 마스크된 나시 게임 (Masked Nash Game) 을 구성합니다.
• 자아 에이전트는 이 축소된 게임의 나시 균형 (Nash Equilibrium) 전략을 계산하여 계획을 수립합니다. 이를 통해 최적화 문제의 크기를 획기적으로 줄이고 계산 시간을 단축합니다.

3. 주요 기여 (Key Contributions)

1. 목표 지향적 플레이어 선택 네트워크 (PSN): 미분 가능한 동적 게임 솔버와 결합되어 선택 마스크를 통해 역전파가 가능한 학습 기반 네트워크를 도입했습니다.
2. 지도 학습 기반 목표 추론 네트워크 (GIN): 에이전트의 의도가 알려지지 않은 상황에서도 PSN 을 적용 가능하게 하여 불완전 정보 게임을 해결합니다.
3. 재귀적 시간 범위 (Receding Horizon) 계획 프레임워크: PSN 을 활용하여 축소된 게임을 효율적으로 해결함으로써, 실시간 다중 에이전트 예측 및 계획이 가능한 프레임워크를 구축했습니다.
4. 실증적 검증: 시뮬레이션 환경과 실제 보행자 궤적 데이터셋 (CITR) 을 통해 PSN 의 성능을 검증했습니다.

4. 실험 결과 (Results)

실험은 4 명, 10 명, 20 명의 에이전트 시나리오와 실제 보행자 데이터 (CITR) 에서 수행되었습니다.

• 게임 크기 축소: PSN 은 전체 에이전트 수의 50%~75% 를 줄여 게임 크기를 축소하면서도 성능을 유지했습니다.
• 예측 정확도 (Prediction): 평균 변위 오차 (ADE) 와 최종 변위 오차 (FDE) 에서 기존 거리 기반, 순위 기반 (kNN, Gradient, Hessian 등) 방법들과 경쟁력 있거나 더 우수한 성능을 보였습니다. 특히 20 에이전트 환경에서도 훈련된 10 에이전트 모델이 간단한 전처리 (Pre-filter) 와 함께 잘 일반화되었습니다.
• 계획 안전성 (Planning Safety): 충돌 비용 (Collision Cost) 과 최소 거리 (Minimum Distance) 측면에서 PSN 은 전체 에이전트를 고려한 풀 게임 (Full-game) 과 유사하거나 더 나은 안전성을 보여주었습니다.
• 불완전 정보 적응: GIN 과 결합 시, 에이전트의 목표가 알려지지 않은 상황에서도 경쟁력 있는 예측 및 계획 성능을 유지했습니다.
• 데이터 요구 사항: 런타임 시 제어 입력, 비용 함수, 게임 파라미터가 필요하지 않으며, 과거 궤적 (위치 또는 상태) 만으로 작동하여 유연성이 높습니다.

5. 의의 및 결론 (Significance)

• 실시간 확장성: 게임 이론적 계획의 계산 병목 현상을 해결하여, 대규모 다중 에이전트 시스템에서도 실시간 계획이 가능하도록 했습니다.
• 실용성: 복잡한 환경 파라미터 튜닝 없이, 관측 데이터만으로 작동하여 다양한 시나리오 (자율주행, 로봇 군집 등) 에 적용 가능합니다.
• 안전성과 효율성의 균형: 불필요한 에이전트를 배제함으로써 계산 효율성을 높이면서도, 안전에 중요한 에이전트만 선별하여 충돌을 방지하는 최적의 균형을 달성했습니다.

이 연구는 다중 에이전트 계획 분야에서 학습 기반의 지능적 선택 메커니즘이 기존 휴리스틱 방법들을 대체할 수 있음을 보여주었으며, 복잡한 실시간 상호작용 시스템에 게임 이론을 적용하는 새로운 패러다임을 제시했습니다.