Multiplayer Reach-Avoid Differential Games with Defender-Side Information Delay

기술 요약: 방어자 측 정보 지연이 존재하는 다수 대 다수 도달-회피 차분 게임

문제 정식화
본 논문은 2차원 평면에서 유한한 속도로 이동하는 다수의 방어자와 다수의 공격자가 관여하는 도달-회피(reach-avoid) 차분 게임의 한 부류를 조사한다. 핵심적으로 다루는 과제는 방어자 측의 정보 지연의 존재이다. 이 설정에서 공격자는 실시간 상태 정보를 보유하는 반면, 각 방어자 $D_i$는 다른 에이전트(다른 방어자 및 공격자 모두)의 상태를 일정한 시간 지연 $\tau_i$를 두고 관찰한다. 결과적으로, 방어자는 공격자의 현재 위치가 아닌 과거 위치($t-\tau_i$)를 바탕으로 제어 결정을 내린다.

이 게임은 $N$명의 방어자와 $M$명의 공격자로 구성된다. 공격자는 볼록하고 닫힌 목표 영역 $T$에 도달하는 것을 목표로 하며, 방어자는 공격자가 $T$에 도달하기 전(반경 $r_i$ 내에서)에 공격자를 포획하는 것을 목표로 한다. 공격자가 포획되면 방어자는 포획 지점과 $T$ 사이의 거리를 최대화하려 하고, 공격자는 이 거리를 최소화하려 한다. 게임은 모든 공격자가 포획되거나 목표 영역에 진입할 때 종료된다. 저자들은 문제가 잘 정의되도록 특정 초기 조건을 가정한다: 지연 구간 동안 방어자는 정지 상태이며, 공격자는 목표 영역 외곽에서 시작하고, 방어자의 속도가 공격자보다 빠르며($\bar{v}_D > \bar{v}_A$), 초기 거리는 지연 기간이 끝나기 전 즉각적인 포획을 방지할 만큼 충분히 멀다.

방법론
저자들은 문제를 해결하기 위해 볼록 해석학 및 게임 이론적 평형 개념과 결합된 기하학적 접근 방식을 채택한다.

1. 일대일(One-Attacker-One-Defender) 분석:

   • 공격 영역 특성화: 저자들은 먼저 "지연된 공격 영역"($R_{total}^A$)에 대한 명시적인 해석적 특성화를 도출한다. 이 영역은 방어자의 반응 지연을 고려했을 때 공격자가 방어자보다 늦지 않게 도달할 수 있다고 보장할 수 있는 점들의 집합을 나타낸다.
   • 볼록성 증명: 거리 제약 조건과 지연 파라미터에 의해 정의된 경계의 특정 곡률 분석을 사용하여, 이 공격 영역이 완만한 가정 하에 **볼록 집합(convex set)**임을 증명한다.
   • 최적 전략: 볼록한 공격 영역을 바탕으로, 저자들은 포획 지점(공격 영역 중 목표 영역에 가장 가까운 점)을 찾기 위한 볼록 최적화 문제를 공식화한다. 양측 플레이어의 최적 전략은 해당 포획 지점을 향해 최대 속도로 직선 운동을 하는 것으로 도정된다.
   • 평형 검증: 본 논문은 이러한 전략들이 **부분 게임 완전 내쉬 평형(subgame-perfect Nash equilibrium, SPNE)**을 구성함을 입증한다. 이는 게임을 두 단계(방어자가 게임에 진입하기 전과 후)로 나누고 역방향 귀납법(backward induction)을 사용하여 매 단계에서의 최적성을 보여줌으로써 증명된다.

2. 다수 참여 시나리오로의 확장:

   • 일대다(One-Attacker-Multiple-Defenders): 공격 영역은 공격자와 각 방어자 사이의 개별 공격 영역들의 교집합으로 정의된다. 포획 지점은 모든 방어자의 제약 조건을 만족하는 볼록 최적화 문제를 풀어서 결정된다. 저자들은 선행 연구와 일치하게, 최적의 플레이 하에서는 최대 두 명의 방어자만으로도 포획 지점을 결정하기에 충분하다는 점을 언급한다.
   • 다대다(Multi-Attacker-Multi-Defender): 문제는 일반적인 $N$-대-$M$ 설정으로 확장된다. 저자들은 "지연을 고려한 쌍별 승리 관계"(특정 방어자가 특정 공격자를 포획할 수 있음을 보장하는지 여부)를 **최대 매칭 공식화(maximum matching formulation)**에 통합한다. 이를 통해 포획 횟수를 최대화하기 위한 방어자와 공격자의 최적 할당이 가능하다.

주요 기여
본 논문의 구체적인 기여는 다음과 같다:

1. 수학적 정식화: 방어자가 공격자 위치에 대해 지연된 정보를 가지고 작동하는 도달-회피 게임에 대한 엄밀한 정식화를 제안한다.
2. 해석적 특성화: 일대일 사례에 대해 지연된 공격 영역의 명시적인 해석적 표현을 도출하고, 시간 지연 역학에도 불구하고 그 볼록성을 증명하여 비자명한 결과를 제시한다.
3. 최적 전략 및 평형: 양측 플레이어를 위한 최적 전략을 도출하고, 지연으로 인해 발생하는 순차적 특성을 다루는 부분 게임 완전 내쉬 평형임을 증명한다.
4. 확장성: 일대다 및 일반적인 다수 에이전트 시나리오로 프레임워크를 확장하여, 포획 지점 계산 및 최대 매칭을 통한 방어자-공격자 할당 전략을 제공한다.

결과
이론적 발견을 검증하기 위해 세 가지 시나리오에 걸쳐 MATLAB을 이용한 수치 시뮬레이션을 수행하였다:

• 일대일: 시뮬레이션 결과, 제안된 최적 전략이 순수 공격(pure-attack) 및 순수 방어(pure-defense) 벤치마크 정책보다 우수한 성능을 보임을 확인하였다. 특히, 어느 한 쪽의 일방적인 이탈은 이탈한 플레이어에게 더 나쁜 결과를 초래하여, 전략의 평형 특성을 입증하였다.
• 일대다: 한 명의 공격자와 두 명의 방어자가 있는 시뮬레이션은 방어자 간의 협력 전략이 단독 방어자보다 더 나은 성능(공격자의 목표 도달 거리 최소화)을 달 수 있음을 보여주었다.
• 다수 에이전트: 세 명의 공격자와 세 명의 방어자 시나리오는 최대 매칭 방식의 효과를 보여주었다. 시뮬레이션은 방어자들이 자신이 포획을 보장할 수 있는 공격자에게 성공적으로 할당되는 반면, 할당되지 않은 공격자는 목표 영역에 성공적으로 도달함을 보여주었다.

의의 및 주장
본 논문은 특히 방어자 측의 정보 지연 조건 하에서 도달-회피 게임에 대한 최적 전략을 제공한 첫 번째 연구라고 주장한다. 기존 연구들이 공격자의 지연이나 표준적인 도달-회피 게임을 다루어 왔으나, 본 연구는 방어자의 정보가 본질적으로 지연될 때 어떻게 최적으로 성능 저하를 완화할 수 있는지에 대한 문헌적 공백을 메운다.

저자들은 자신들의 접근 방식이 고차원의 해밀턴-야코비-아이삭스(Hamilton-Jacobi-Isaacs, HJI) 방정식을 직접 푸는 어려움을 넘어선다는 점을 강조한다. 대신, 지연된 공격 영역의 기하학적 구조와 그 볼록성을 활용함으로써, 다루기 쉬운 검증 기반의 해석적 프레임워크를 제공한다. 이를 통해, 분석적으로 다루기 어려운 시나리오에서도 효율적인 승리 조건 및 평형 전략 계산이 가능해진다. 본 연구는 통신 및 처리 지연이 불가피한 적대적 시스템(예: 군사 또는 항공우주 응용 분야)의 보다 현실적인 모델링을 향한 단계로 자리매김한다.