기술 요약: 다중 에이전트 추격-회피 게임에서의 프리미티브 가이드 트리 탐색 (Primitive-Guided Tree Search)

1. 문제 정의

본 논문은 그래프 상의 다중 에이전트 추격-회피 게임(Pursuit-Evasion Games, PEGs)에서 내쉬 균형(Nash equilibrium) 정책을 계산하는 과제를 다룹다. 이 게임에서 추격자(Pursuers, Red) 팀은 회피자(Evaders, Blue) 팀이 지정된 탈출 노드에 도달하기 전에 이들을 포획하려고 시도한다. 핵심적인 어려움은 에이전트 수가 증가함에 따라 결합 상태(joint state) 및 행동(action) 공간이 기하급수적으로 성장한다는 점이다.

기존 방식들은 다음과 같은 트레이드오프에 직면해 있다:

• 오프라인 방식 (예: PSRO, MAPPO): 정책을 오프라인에서 학습하지만, 학습 과정에서 보지 못한 적대적 행동에 대한 적응력이 부족하고 높은 학습 복잡도를 수반하는 경우가 많다.
• 온라인 계획 방식 (예: MCTS): 현재 상태에 적응할 수 있지만, 동시 다수 에이전트 게임 특유의 거대한 브랜칭 팩터(branching factor)로 인해 깊은 탐색이 계산적으로 불가능해진다.
• 하이브리드 방식 (예: AlphaZero 변형): 정확한 가치/정책 근사치를 학습하는 데 방대한 데이터를 필요로 하거나, 2인 게임 설정으로 제한되는 경우가 많다.

본 연구의 목표는 오프라인 균형 계산의 전략적 깊이와 온라인 탐색의 적응성을 결합한 확장 가능하고 견고한 프레임워크를 개발하는 것이다.

2. 방법론: 프리미티브 가이드 트리 탐색 (PGTS)

저자들은 복잡한 다중 에이전트 게임을 다루기 쉬운 하위 게임들로 분해하고, 이러한 솔루션들을 온라인 동시 이동 몬테카를로 트리 탐색(Simultaneous-Move MCTS, SM-MCTS)에 통합하는 하이브리드 프레임워크인 **프리미티브 가이드 트리 탐색(Primitive-Guided Tree Search, PGTS)**을 제안한다.

2.1 오프라인 단계: 프리미티브 서브 팀 게임

PGTS는 전체 게임을 직접 해결하는 대신, 에이전트의 부분 집합이 포함된 작고 대표적인 "프리미티브(primitive)" 하위 게임들의 정확한 내쉬 균형을 사전 계산한다:

• 1v1: 추격자 1명 대 회피자 1명.
• 2v1: 추격자 2명 대 회피자 1명.
  이들은 제한된 상태 공간($V \times V$ 및 $V^2 \times V$)에서 샤플리 값 반복법(Shapley value iteration)을 사용하여 해결된다. 출력값에는 런타임 사용을 위해 캐싱된 최적 혼합 정책($\pi^*$)과 가치 함수($V^*$)가 포함된다.

2.2 온라인 단계: 트리 탐색

각 타임스텝마다 PGTS는 현재의 결합 상태로부터 트리 탐색을 수행한다. 이 알고리즘은 두 가지 결정적인 방식으로 표준 SM-MCTS를 수정한다:

1. 프리미티브 가이드 확장 (Primitive-Guided Expansion):
   브랜칭 팩터를 완화하기 위해, 알고리즘은 모든 가능한 결합 행동을 확장하지 않는다. 대신, 오프라인 프리미티브 정책을 사용하여 탐색을 유도한다:

   • 각 회피자에 대해, 알고리즘은 가장 가까운 $k_r$ 명의 추격자를 식별한다.
   • 사전 계산된 내쉬 정책($\pi^*_{1v1}, \pi^*_{2v1}$)을 기반으로 국소적 상호작용(1v1 및 2v1 그룹)에 대한 결합 행동을 샘플링한다.
   • 이러한 샘플들은 사전 확률(priors)에 대한 과도한 몰입을 방지하기 위해 휴리스틱 최단 경로 행동 및 무작위 탐색과 함께 보강된 제한된 후보 행동 집합을 형성한다.

2. 서브 팀 대리물을 통한 리프 가치 추정 (Leaf Value Estimation via Sub-team Surrogates):
   비싼 몬테카를로 롤아웃을 지평선까지 실행하는 대신, 알고리즘은 오프라인 프리미티브 가치 함수를 사용하여 리프 노드의 가치를 추정한다.

   • 알고리즘은 현재 상태를 일련의 프리미티브 서브 팀으로 분해하여 전체 게임 가치를 근사한다.
   • **순차적 매칭 전략(sequential matching strategy)**을 채택한다: 먼저, 2v1 가치 행렬에 대한 헝가리안 알고리즘(Hungarian algorithm)을 사용하여 (높은 차원의 협동인 공동 포위 등을 포착하기 위해) 2v1 상호작용을 형성하도록 에이전트들을 탐욕적으로 매칭한다.
   • 남은 에이전트들은 1v1 상호작용으로 매칭된다.
   • 리프 가치는 이러한 프리미티브 가치들의 합산된 총합이며, 이를 통해 정확한 결과 추정을 유지하면서도 더 얕은 깊이에서 탐색을 종료할 수 있게 한다.

2.3 행동 선택

프레임워크는 트리를 순회하기 위해 두 가지 선택 연산자를 지원한다:

• 레그렛 매칭 (Regret Matching, RM): 각 노드에서 추정된 행렬 게임에 레그렛 매칭을 적용하여 혼합 정책을 계산한다.
• 디커플드 UCT (Decoupled UCT, DUCT): 각 팀의 한계 행동 가치(marginal action values)에 독립적으로 상한 신뢰 구간(Upper Confidence Bounds)을 적용한다.

3. 주요 기여

• 하이브리드 프레임워크: 작은 규모의 반복되는 국소적 상호작용(프리미티브)의 정확한 오프라인 내쉬 솔루션을 온라인 트리 탐색에 독특하게 통합한 PGTS를 도입하였다.
• 구조화된 확장 (Structured Expansion): 단순한 무작위 또는 순수 휴리스틱 샘플링이 아닌, 오프라인 균형 계산에서 도출된 전략적 사전 확률에 기반하여 행동을 샘플링함으로써 브랜칭 팩터를 줄이는 메커니즘을 제공한다.
• 확장 가능한 리프 평가: 딥 롤아웃 없이도 리프 노드를 평가하기 위해 오프라인 프리미티브 가치 함수와 순차적 매칭 알고리즘(2v1을 1v1보다 우선시함)을 활용하는 대리 가치 추정 방법을 사용한다.
• 협동 유지 (Coordination Preservation): 서브 팀을 독립적으로 취급하는 단순 분해 방식과 달리, PGTS는 프리미티브에 의해 가이드되는 전체 행동 공간에서의 결합 행동 롤아웃을 수행함으로써 팀 수준의 협동을 유지한다.

4. 실험 결과

저자들은 네 가지 그래프 토폴로지(두 개의 7x7 그리드(Easy/Hard), 200개 노드의 스코틀랜드 야드 그래프, 151개 노드의 실제 애틀랜타 그래프)에서 PGTS를 평가하였다. 추격자 팀은 다양한 회피자 행동을 대상으로 테스트되었다.

베이스라인:

• MT-PSRO: 멀티 태스크 정책 공간 응답 오라클 (학습 기반).
• NSGZero: 네트워크 보안을 위한 신경망 가이드 MCTS.
• Decomposition (분해): 트리 탐색 없이 서브 팀 분해만을 사용하는 베이스라인.
• Intercepting (차단): 휴리스틱 최단 경로 베이스라인.

결과:

• 강건성 (Robustness): PGTS(RM 및 DUCT 변형 모두)는 모든 토폴로지에서 일관되게 가장 높은 **최악의 경우 효용(Worst-Case Utility, WCU)**을 달성하였으며, 이는 최단 경로 회피자에게 과적합되는 경향을 보인 학습 기반 베이스라인(MT-PSRO, NSGZero)을 크게 상회하였다.
• 협동 (Coordination): PGTS는 순수 "Decomposition" 베이스라인보다 우수한 성능을 보였으며, 이는 트리 탐색 구성 요소가 정적 분해가 놓치는 팀 수준의 협동을 효과적으로 포착함을 입증한다.
• 절제 연구 (Ablation): 프리미티브 가이드 확장을 제거하거나 2v1 프리미티브를 제거하면 특히 크고 복잡한 그래프(Scotland Yard, Atlanta)에서 성능이 크게 하락하였으며, 이는 효과적인 탐색과 가치 추정을 위해 두 구성 요소가 모두 필수적임을 확인시켜 준다.

5. 의의 및 주장

본 논문은 PGTS가 다중 에이전트 PEG의 "차원의 저주"에 대한 확장 가능한 솔루션을 제공한다고 주장한다. 작은 규모의 반복되는 국소적 상호작용(프리미티브)을 활용하여 전역 탐색을 가이드함으로써, 이 방법은 다음을 달ian한다:

1. 계산적 용이성: 브랜칭 팩터와 탐색 깊이를 효과적으로 관리한다.
2. 적응성: 정적 분해와 달리, 전체 결합 행동 공간에서 협동 정책을 추론할 수 있는 능력을 유지한다.
3. 강건성: 학습된 분포에 의존하는 대신 게임 이론적 원칙에 기반하므로, 학습 단계에서 보지 못한 다양한 적대적 전략에 대해서도 잘 작동한다.

저자들은 이 접근 방식이 오프라인 균형 계산의 이론적 최적성과 온라인 계획의 실용적 적응성 사이의 간극을 메우며, 적대적 환경에서의 다중 에이전트 의사결정을 위한 견고한 프레임워크를 제공한다고 결론짓는다. 향후 연구로는 이를 부분 관측성(partial observability) 및 더 넓은 범위의 다중 에이전트 게임 클래스로 확장하는 것이 제안되었다.