기술 요약: GraphChase: 도시 네트워크 보안 게임을 위한 플랫폼 및 벤치마크

문제 정의

도시 네트워크 보안 게임(Urban Network Security Games, UNSGs)은 법 집행 기관(추격자)이 도시 도로 네트워크를 통해 탈출하는 범죄자(도망자)를 차단하기 위해 한정된 자원을 전략적으로 배분해야 하는 시나리오를 모델링합니다. 2인 제로섬 게임 분야에서는 상당한 진전이 있었으나, UNSG를 해결하는 것은 협력, 경쟁 및 불완전한 정보가 포함된 다수 플레이어 게임이라는 특성 때문에 독특한 과제를 안겨줍니다.

현재 이 분야는 세 가지 주요 한계에 직면해 있습니다:

1. 표준화 결여: 통일된 실험 플랫폼의 부재로 인해 구현 방식이 서로 호환되지 않고, 데이터 구조가 일관되지 않으며, 알고리즘 간의 교차 평가가 어렵습니다.
2. 현실성과 확장성의 트레이드오프: 최적화 기반 방법론은 가중 이동 시간을 모델링하기 위해 혼합 정수 선형 계획법(MILP)에 의존하는 경우가 많으나 대규모 네트워크로 확장하는 데 실패합니다. 반면, 최신(SOTA) 학습 기반 방법론은 일반적으로 학습을 용이하게 하기 위해 환경을 가중치가 없는 그래프로 단순화하며, 이 과정에서 실제 도로 구간의 이질성(예: 다양한 길이 및 제한 속도)을 무시합니다.
3. Sim-to-Real 격차: 기존 접근 방식은 가중치가 있는 네트워크에 배포될 때 견고성과 확장성 측면에서 어려움을 겪으며, 이는 단순화된 학습 환경과 현실적인 조건 사이의 일반화 격차를 드러냅니다.

방법론: GraphChase 플랫폼

이러한 과제를 해결하기 위해 저자들은 UNSG 연구를 표준화하고 현실적인 환경에서의 시뮬레이션을 지원하도록 설계된 오픈 소스 플랫폼인 GraphChase를 소개합니다. 이 플랫폼은 환경, 에이전트, 솔버를 분리하는 모듈형 아키텍처를 채택합니다.

핵심 구성 요소

1. 게임 모듈 (환경):

   • 그래프 표현: 도로 네트워크를 유향 및 무향 에지를 모두 지원하는 그래프 $G=(V, E, \omega)$로 모델링합니다. $\omega(u, v)$가 연속적인 이동 시간을 나타내는 가중치 에지를 처리합니다.
   • 상태 표현: 에이전트는 정점(vertex) 또는 에지(edge) 상에 위치하며, $(u, v, \delta)$ 튜플로 표현됩니다 (여기서 $\delta$는 정점 $u$로부터의 거리). 이를 통해 이산 시간 단계 프레임워크 내에서 연속적인 움직임을 구현할 수 있습니다.
   • 역학(Dynamics): 에이전트가 타임 스텝 시작 시점에 결정하고 정점에 도달했을 때 즉각적으로 결정하는 하이브리드 의사결정 메커니즘을 사용합니다. 게임은 포획(거리 $\le \epsilon$), 탈출(출구 노드 도달), 또는 타임아웃($T$) 시 종료됩니다.
   • 정보 구조: 추격자와 도망자 모두에 대해 완전 관측성부터 부분 관측성에 이르는 네 가지 정보 시나리오를 지원하며, 추격자 간의 독립적 또는 협력적 의사결정을 허용합니다.

2. 에이전트 모듈:

   • 정책 표현(신경망 또는 휴리스틱) 및 궤적 수집을 위한 통일된 인터페이스를 제공합니다.
   • 환경 상호작용, 전처리 및 배치 구축을 캡슐화하는 Runner를 도입하여 효율적인 데이터 수집을 위한 벡터화된 롤아웃(rollout)을 지원합니다.
   • 정책 공간 응답 오라클(PSRO)과 같은 프레임워크를 위한 정책 클로닝 및 지속성을 포함한 반복적 게임 이론 학습을 지원합니다.

3. 솔버 모듈:

   • 최적 대응(best-response) 학습을 위한 플러그 앤 플레이 최적화 도구(예: PPO, MAPPO)를 구현합니다.
   • 최적 대응 오라클(RL 또는 휴리스틱)과 메타 솔버(예: 투영 복제 역학, Projected Replicator Dynamics)로 분해되는 게임 이론적 학습 프레임워크, 특히 PSRO를 지원합니다.
   • 핵심 게임 로직을 수정하지 않고도 커스텀 솔버를 구현할 수 있도록 합니다.

벤치마크 프로토콜

GraphChase는 다음과 같은 표준화된 벤치마크 프로토콜을 구축합니다:

• 알고리즘: CFR-MIX, NSG-NFSP, NSGZero, Pretrained PSRO, Grasper를 포함한 최신 알고리즘 통합.
• 실행 모드: 경로 기반 실행(도망자가 게임 시작 전 목표 출구와 경로를 선택)과 단계별 실행(에이전트가 각 결정 지점에서 행동을 샘플링)을 모두 지원합니다.
• 평가 지표:
  • 최악의 효용(Worst-Case Utility): 모든 도망자 경로를 열거하여 추격자의 최소 효용을 찾습니다.
  • 의사 최악의 효용(Pseudo Worst-Case Utility): 대규모 그래프를 처리하기 위해 각 출구에 대해 경로를 샘플링하여 최악의 경우를 근사합니다.
  • 시각화: 궤적 및 의사결정 과정을 분석하기 위한 도구.

주요 기여

1. 통일된 플랫폼: 환경과 알고리즘을 분리하여 동일한 작업에 대한 전략의 공정한 교차 평가를 가능하게 하고 호환성 문제를 해결하는 GraphChase를 개발했습니다.
2. 벤치마크 확립: 다양한 게임 설정에 걸쳐 신뢰할 수 있는 베이스라인을 제공하고 성능 지표를 설정하기 위해 여러 딥러닝 기반 알고리즘을 통합했습니다.
3. Sim-to-Real 격차 규명: 현재의 접근 방식이 특히 가중치가 있는 도로 네트워크에 배치될 때 성능 저하를 겪는 등 확장성과 견고성 측면에서 상당한 한계가 있음을 입증하는 광범별 실험을 수행했습니다.

실험 결과

저자들은 플랫폼을 검증하고 알고리즘을 평가하기 위해 48코어 CPU와 8개의 NVIDIA A30 GPU를 갖춘 서버에서 실험을 진행했습니다.

• 재현성 및 정확성: GraphChase는 5x5 및 7x7 그리드 그래프에서 기존 문헌(Pretrained PSRO, Grasper, NSGZero, NSG-NFSP, CFR-MIX)의 결과를 성공적으로 재현했습니다. 또한 Grasper과 같은 기존 코드베이스의 비효율성을 해결하여 논리적 일관성을 유지하면서도 더 나은 학습 성능을 달야냈습니다.
• 계산 효율성: 벡터화된 환경 설계 덕분에 GraphChase는 기존 구현에 비해 전체 샘플링 처리량을 1.38배 향상시켰으며, 도망자(1.96배) 및 추격자(1.72배)의 최적 대응 계산 속도를 가속화했습니다.
• 실제 토폴로지 벤치마크: 6개의 실제 지도(싱가포르, 맨해튼, 뭄바이 등)에 대한 테스트 결과 성능 편차가 나타났습니다. 알고리즘은 일부 토폴로지에서는 높은 효용을 달성했으나, 노드/에지 수가 많고 시간 지평이 긴 맨해튼이나 타임스퀘어와 같은 복잡한 환경에서는 어려움을 겪었습니다.
• 견고성 평가:
  • 호라이즌 변화(Horizon Shift): $T=4$에서 학습된 정책은 $T=8$에서 테스트될 때 상당한 효용 저하를 보였으며, 이는 시간 지평 변화에 대한 제한된 견고성을 나타냅니다.
  • 에지 가중치 변동: 가중치가 없는 그래프에서 학습된 정책는 가중치가 있는 그래프에서 테스트될 때 상당한 성능 저하를 겪었으며, 이는 에지 비용의 이질성에 대한 견고성 부족을 강조합니다.
• 확장성: 기존 알고리즘은 100x100 그리드에서 학습에 실패했으며, 30x30 그리드에서도 의사결정에 필요한 경로 열거의 기하급수적 폭발로 인해 정체되었습니다. 이는 현재 솔버들의 확장성 장벽을 보여줍니다.
• 단계별 정책 실행: 뭄바이 지도(가중 및 무가중)에 대한 실험은 GraphChase가 단계별 PPO 정책을 학습하고 평가할 수 있음을 보여주었습니다. 휴리스틱 방어자는 휴리스틱 공격자를 상대로 잘 작동했지만 PPO 공격자를 상대로는 고전했으며, PPO 방어자는 가중치가 있는 그래프에서 낮은 포획률을 보여 현실적인 가중 토폴로지에서의 학습 난이도를 확인시켜 주었습니다.

의의 및 주장

본 논문은 GraphChase가 UNSG에 특화된 최초의 오픈 소스 플랫폼으로서, 이론적 게임 해결과 현실적인 도시 보안 애플리케이션 사이의 간극을 메우는 유연한 멀티플레이어 게임 환경을 제공한다고 주장합니다.

• 표준화: 통일된 인터페이스를 제공함으로써 UNSG 연구의 진입 장벽을 낮추고, 확장 가능하고 현실적인 보안 과제에 집중하는 커뮤니티를 육성합니다.
• 현실적 모델링: 가중 그래프와 하이브리드 의사결정을 지원함으로써 기존의 무가중 모델보다 실제 시나리오(예: 교통 패턴)의 역동성을 더 잘 포착합니다.
• 멀티플레이어 게임의 테스트베드: 이 플랫폼은 포괄적인 영역(예: 밀렵 방지 및 적대적 팀 게임)에 적용 가능한 복잡한 멀티플레이어 설정에서 내쉬 균형(NE) 및 팀-맥심인 균형(TME)을 계산하기 위한 테스트베드 역할을 합니다.
• 한계 식별: 본 연구는 현재의 SOTA 알고리즘이 가중 에지 비용이나 대규모 네트워크에 대해 견고하지 못함을 명시적으로 정량화하여, 전역 액션 공간 탐색에서 벗어난 새로운 접근 방식의 필요성을 촉구합니다.

저자들은 GraphChase를 탈출 계획을 돕기 위한 도구가 아니라, 공공 안전 전략을 개선하기 위한 방어적 계획 및 평가 도구로 정의합니다.