기술 요약: 비볼록 부분 결합 일반 내쉬 균형 문제(PDGNEP)를 위한 FALCON

문제 정식화

본 논문은 항공우주 및 로보틱스 분야의 다중 에이전트 최적 제어 문제를 해결하는 과제를 다루며, 이를 특히 **비볼록 미분 게임(non-convex differential games)**으로 모델링합니다. 저자들은 **부분 결합 일반 내쉬 균형 문제(Partially-Decoupled Generalized Nash Equilibrium Problems, PDGNEPs)**라고 불리는 특정 하위 클래스에 초점을 맞춥니다.

이 정식화에서 $N$개의 에이전트는 다음을 준수하며 개별 비용 함수 $J_i$를 최소화하고자 합니다:

1. 분리 가능한 역학(Separable Dynamics): 각 에이전트 $i$는 다른 에이전트의 제어나 상태와 독립적인 고유의 역학 $\dot{x}_i(t) = f(x_i(t), u_i(t))$에 따라 진화합니다.
2. 결합된 제약 조건(Coupled Constraints): 에이전트들은 모든 에이전트의 궤적에 의존할 수 있는 공유 등식 및 부등식 제약 조건 $C(X, \Upsilon) \leq 0$을 통해 결합됩니다.
3. 목표: 다른 에이전트들의 전략이 주어졌을 때, 어느 에이전트도 단독으로 자신의 비용을 개선할 수 없는 상태인 **오픈 루프 내쉬 균형(Open-Loop Nash Equilibrium)**을 찾는 것입니다.

기존 방법들은 다음과 같은 한계에 직면해 있습니다: 반복적 LQ 게임(iLQGames)은 제약 조건을 기본적으로 처리하지 못하며, 증강 라그랑지 게임(ALGAMES)은 성능이 개선되었으나 심한 비볼록성을 처리하는 데 어려움을 겪습니다. 또한 미분 게임 순차 이차 계획법(DG-SQP)은 수렴 보장을 제공하지만, 고도의 비볼록 시나리오에서 높은 계산 비용과 수치적 불안정성을 겪는 경우가 많습니다.

방법론: FALCON 알고리간

저자들은 **순차적 볼록 계획법(Sequential Convex Programming, SCP)**과 증강 라그랑지(Augmented Lagrangian) 프레임워크를 결합한 알고리즘인 FALCON(Fast Augmented Lagrangian Convexification for Open-loop Nash equilibria)을 제안합니다. 핵심 방법론은 다음과 같이 진행됩니다.

1. 연속 시간 제약 조건 강제화

이산화된 SCP 솔버에서 흔히 발생하는 샘플 간 제약 위반 문제를 해결하기 위해, 저자들은 외부 페널티(exterior-penalty) 접근 방식을 사용하여 제약 조건을 재구성합니다.

• 제약 위반의 연속 시간 척도인 $\Lambda_i(t)$를 정의하며, 이때 $C^2$ 매끄러움을 위해 3차 페널티 함수 $q(z) = [z]_+^3$를 사용합니다.
• 증강 상태 변수 $y_i(t)$는 이 위반 사항을 시간에 따라 누적합니다.
• 제약 조건은 단순히 이산화 노드에서만 강제되는 것이 아니라, 노드 사이의 $y_i$ 누적량을 제한함으로써 전체 연속 시간 구간 동안 강제되며, 이를 통해 이론적 경계 $\delta(\varepsilon)$ 내에서 점 단위(pointwise) 제약 만족을 보장합니다.

2. 증강 라그랑지 및 에피그래프 재구성

비볼록 목적 함수와 제약 조건을 처리하기 위해:

• 에피그래프 형태(Epigraph Form): 비볼록 비용 함수 $J_i$를 에피그래프 변수 $\tau_i$를 통해 제약 조건으로 이동시킵니다($J_i \leq \tau_i$를 만족하면서 $\tau_i$를 최소화). 이를 통해 목적 함수를 선형화하면서 비볼록성을 제약 조건에 남겨둘 수 있습니다.
• 증강 라그랑지: 역학 및 결합 제약 조건에 대한 라그랑지 승수($\lambda, \mu$)와 페널티 가중치($\omega$)를 포함하는 증강 라그랑지 함수 $L_i$를 구성합니다.

3. 순차적 볼록화 (SCvx*)

비볼록 게임은 일련의 볼록 하위 문제를 푸는 방식으로 반복적으로 근사됩니다:

• 선형화: 참조 궤적 $\bar{z}$ 주변에서 역학 및 제약 조건을 선형화합니다.
• 완화(Relaxation): 선형화로 인한 인위적인 불가능성(infeasibility)을 완화하기 위해 가상 제어($\xi$) 및 가상 버퍼($\zeta$) 변수를 도입합니다.
• 신뢰 영역(Trust Region): $\|z - \bar{z}\|_\infty \leq r$이라는 신뢰 영역 제약 조건은 근사가 유효하게 유지되도록 보장합니다.
• 포텐셜 게임 재구성: 결과물인 볼록 하위 문제는 **변분 일반 내쉬 균형(v-GNE)**으로 구조화됩니다. 개별 페널티 목적 함수의 합인 강력한 볼록 포텐셜 함수 $\Phi_k$를 구축함으로써, 하위 문제를 효율적인 **이차 원뿔 계획법(SOCP)**으로 해결합니다.

4. 알고리즘 루프

알고리즘은 다음 과정을 반복합니다:

1. 순차적 선형화: 볼록 하위 문제를 생성합니다.
2. 단계 수락: 공동 포텐셜 비율 $\rho_k$(실제 비용 감소량 대 예측된 감소량 비교)를 사용하여 단계의 "품질"을 평가합니다. $\rho_k$가 임계값을 초과하면 단계가 수락됩니다.
3. 승수 업데이트: 제약 위반 및 사용자 정의 허용 오차 $\delta_k$에 따라 라그랑지 승수와 페널티 가중치를 업데이트합니다.
4. 신뢰 영역 조정: 수락 비율에 따라 신뢰 영역 반경 $r$을 동적으로 조정(축소 또는 확장)합니다.

주요 기여

1. 알고리즘 개발: 순차적 볼록화와 증강 라그랑지 기법을 결합하여 비볼록 PDGNEP 문제를 해결하는 새로운 알고리즘인 FALCON을 도입했습니다.
2. 이론적 보장: 완만한 가정(유계된 가속도, 리프시츠 연속성, $C^2$ 매끄러움) 하에서 오픈 루프 내쉬 균형으로의 **전역 수렴(global convergence)**을 증명했습니다. 솔루션은 동적으로 실행 가능하며, 연속 시간 관점에서 근사적으로 결합 가능함을 보장받습니다.
3. 연속 시간 안전성: 이산화 노드 사이의 안전 위반을 방지하기 위해 제약 조건을 연속적으로 강제하는 엄격한 정식화를 제시했습니다.
4. 효율성: 제안된 방식이 효율적인 SOCP 솔버를 사용하는 포텐셜 게임으로 하위 문제를 축소함으로써, 기존 DG-SQP 방식의 계산 병목 현상을 피할 수 있음을 입증했습니다.

수치 결과

저자들은 세 가지 뚜렷한 비볼록 미분 게임 시나리오에 대해 FALCON을 검증했습니다.

1. F1 오스틴 레이싱 (2 플레이어):

   • 시나리오: F1 오스틴 트랙의 급커브 구간에서 두 대의 차량이 경주하는 상황입니다.
   • 성능: 다양한 초기 조건에서 FALCON은 100% 수렴율을 달연한 반면, DG-SQP는 72%의 수렴율만을 보였습니다.
   • 속도: FALCON은 매우 빨랐으며, 평균 계산 시간은 0.873초로, DG-SQP의 50.021초에 비해 현저히 짧았습니다. ALGAMES는 동일한 기준에서 이 어려운 케이스를 해결하지 못했습니다.

2. 좁아지는 복도 (3 플레이어):

   • 시나리오: 세 대의 유니사이클 에이전트가 충돌 회피 및 통신 범위 제약을 유지하면서 두 개의 병목 지점이 있는 복도를 통과하는 상황입니다.
   • 관찰: 알고리즘은 비볼록 환경을 성공적으로 처리하였으며, 연속 시간 제약을 엄격히 준수하면서도 나타나는 협력적 행동(예: 에이전트들이 병목 지점을 통과하는 순서를 정함)을 보여주었습니다.

3. 우주선 레이디-밴딧-가드 (3 플레이어):

   • 시나리오: 클로셰-윌리츠-힐(Clohessy-Wiltshire-Hill) 역학을 포함하는 $R^6$ 공간에서의 이질적 게임으로, "레이디"(고가치 자산), "밴딧"(공격자), "가드"(방어자)가 등장합니다.
   • 관찰: FALCON은 복잡한 추격-회피-방어 게임을 해결하였으며, 가드가 밴딧을 차단하여 레이디가 탈출할 수 있도록 하는 시나리오를 성공적으로 시뮬레이션하며 교전 기하학의 비볼록성을 처리했습니다.

의의 및 주장

본 논문은 FALCON이 계산 효율성과 이론적 수렴 보장 사이의 간극을 메움으로써 비볼록 미분 게임을 해결하는 데 있어 중요한 진전을 이루었다고 주장합니다.

• 차별점: iLQGames와 달리 FALCON은 상태 및 제어 제약 조건을 기본적으로 처리합니다. DG-SQP와 달리, 수렴 보장을 희생하지 않으면서도 고도의 비볼록 설정에서 우수한 수치적 성능과 견고성을 제공합니다.
• 안전성: 연속 시간 제약 정식화는 샘플 간 위반이 허용되지 않는 안전 중심의 항공우주 애플리케이션에서 핵심적인 기능으로 강조됩니다.
• 확장성: 내부 루프를 SOCP로 해결 가능한 포텐셜 게임으로 축소함으로써, 이 방법은 복잡한 다중 에이전트 시스템에 대한 확장 가능한 접근 방식을 제공합니다.

저자들은 FALCON이 비볼록 미분 게임을 해결하기 위한 견고하고 빠르며 이론적 근거가 확실한 프레임워크를 제공하여, 추격-회피, 분쟁 중인 우주 작전, 협력 유도와 같은 복잡한 항공우주 운영에 적합하다고 결론짓습니다.