기술 요약: 준-정책 근사를 통한 혼합 위계 게임의 효율적 해결

문제 정의

다중 로봇 조정에는 종종 의사결정이 순수한 동시적 (내시) 이나 순수한 순차적 (스택엘버그) 이 아닌, 둘의 혼합인 복잡한 정보 구조가 수반됩니다. 기존 게임 이론 솔버는 특히 다음을 포함하는 혼합 위계 게임을 처리하는 데 어려움을 겪습니다:

1. 비선형 제약 조건(예: 비선형 운동 역학에서 비롯된 것).
2. 비이차 목적 함수(단순한 이차 비용 이상의 복잡한 작업을 인코딩).
3. 숲 구조 정보 패턴, 여기서 로봇들은 서로 다른 가지 간 내시 균형을 통해 상호작용하는 리더 - 팔로워 체인 (나무) 을 형성합니다.

주요 이론적 및 계산적 장벽은 이러한 게임에 대한 1 차 최적성 조건 (카루시 - 쿤 - 터커 또는 KKT 조건) 을 유도할 때 위계 깊이가 증가함에 따라 팔로워들의 최적 반응 정책의 고차 미분값을 계산해야 한다는 점입니다. 이로 인해 깊은 위계나 복잡한 역학을 가진 경우 직접적인 해법이 비실용적이 됩니다.

방법론

저자들은 고차 미분값 계산을 피하기 위해 최적성 조건을 근사화함으로써 $N$-로봇 숲 구조 혼합 위계 게임을 해결하는 프레임워크를 제안합니다.

1. 문제 공식화

게임은 노드가 로봇을 나타내고 간선이 리더 - 팔로워 관계를 나타내는 방향 비순환 그래프 $G$로 모델링됩니다. 저자들은 $G$가 숲(연결되지 않은 나무들의 합집합) 이라고 가정하여 각 로봇이 최대 하나의 직접적인 리더를 가지도록 합니다.

• 전략: 각 로봇 $i$는 등식 제약 조건 $g_i(z_i)=0$(예: 역학) 하에서 목적 함수 $J_i(z)$를 최소화합니다.
• 균형 정의: 혼합 위계 균형은 각 로봇이 다음을 만족해야 함을 요구합니다:
  • 스택엘버그 조건: 리더들의 전략이 주어졌을 때 자신의 전략과 자신의 하위 트리의 전략을 최적화합니다.
  • 내시 조건: 자신이 영향을 미칠 수 없는 다른 가지의 로봇들 (내시 상대) 의 전략이 주어졌을 때 자신의 전략을 최적화합니다.

2. 준-정책 근사

정확한 KKT 조건에서 고차 미분값의 비실용성을 우회하기 위해 저자들은 준-정책 근사를 도입합니다:

• 메커니즘: 리더에 대한 KKT 조건을 유도할 때, 이 방법은 팔로워들의 최적 반응 정책을 내포합니다. 그러나 이러한 정책이 리더의 전략에 대한 완전한 재귀적 의존성을 계산하는 대신 (이는 고차 미분값을 생성함), 이 방법은 팔로워 정책의 고차 미분값을 무시합니다.
• 효과: 이는 재귀적 복잡성을 줄여 KKT 시스템을 오직 1 차 정책 기울기만을 사용하여 구성할 수 있게 합니다. 이는 최근의 피드백 내시 및 스택엘버그 게임에 대한 연구를 혼합 위계 설정으로 확장합니다.

3. 부정확한 뉴턴 솔버

저자들은 결과적인 근사 KKT 시스템을 해결하기 위해 부정확한 뉴턴 방법을 개발합니다:

• 알고리즘: 솔버는 역위상 순서로 반복하여 각 로봇에 대한 근사 KKT 조건을 구성합니다. 그런 다음 고차 항을 0 으로 만든 근사 야코비안을 사용하여 선형 시스템을 풀어 탐색 방향을 결정합니다.
• 수렴: 저자들은 고차 정책 민감도가 1 차 기울기에 비해 작을 경우 (강한 정규화가 적용된 제어 문제에서 종종 충족되는 조건), 비이차 목적 함수와 비선형 제약 조건을 가진 게임에 대한 국소 지수 수렴에 대한 이론적 증명을 제공합니다.

주요 기여

1. 원칙적 근사: 팔로워들의 최적 반응을 국소적 1 차 정책 근사 (준-정책) 로 내포함으로써 비선형 등식 제약 혼합 위계 게임에 대한 근사 최적성 조건을 구성하는 새로운 방법.
2. 확장 가능한 알고리즘: 비선형 비용과 제약 조건을 가진 임의의 숲 구조 혼합 위계 게임을 위한 효율적이고 유연한 솔버. 저자들은 국소 지수 수렴을 이론적으로 증명하고 경험적으로 입증했습니다.
3. 오픈 소스 구현: MixedHierarchyGames.jl이라는 고도로 최적화된 Julia 라이브러리를 공개했습니다. 이 라이브러리는 수백 개의 변수를 가진 하드웨어 실험 및 시뮬레이션을 포함한 복잡한 시나리오를 지원합니다.

실험 결과

이 접근 방식은 하드웨어와 시뮬레이션 모두에서 평가되었습니다:

• 하드웨어 (표적 경비): 추격자, 경비원, 표적이 포함된 3 로봇 실험입니다. 경비원은 표적을 이끌며, 둘 모두 추격자와 내시 관계를 가집니다. 솔버는 표준 CPU 에서 실시간(평균 호출당 13.6ms) 으로 실행되어, 표적 경비 목표를 달성하기 위해 로봇들을 감쇠 지평선 방식으로 성공적으로 조정했습니다.
• 시뮬레이션 (컨보이 병합): 네 가지 다른 위계 구조 (순수 내시, 두 가지 혼합 위계, 순수 스택엘버그 체인) 하에서 4 차량 병합 시나리오가 테스트되었습니다.
  • 솔버는 위계 구조를 변경하면 명확하고 해석 가능한 행동 (예: 위치 유지를 위해 가속하는 리더 차량 vs 양보하는 차량) 으로 이어짐을 보여주었습니다.
  • 모든 결과 균형은 안전한 상호작용을 보장했습니다.
  • 경험적 결과는 목적 함수의 단조 감소와 균형 근처의 국소 지수 수렴을 확인하여 정리 1 을 검증했습니다.

중요성과 주장

이 논문은 비선형 역학과 비이차 목적 함수를 가진 혼합 위계 게임을 효율적으로 해결할 수 있게 함으로써, 이전에는 선형/이차 설정이나 단순한 구조로 제한되었던 다중 로봇 계획의 중요한 격차를 해소했다고 주장합니다.

• 실시간 실현 가능성: 준-정책 근사는 고차 미분값의 계산 병목 현상을 성공적으로 제거하여 복잡한 정보 구조에 대한 실시간 수렴을 가능하게 합니다.
• 일반화 가능성: 이 프레임워크는 내시와 스택엘버그 게임을 특수한 경우로 통합하며 임의의 숲 위상을 처리합니다.
• 실용적 영향: 이 방법은 동적 환경에서 솔버가 생성한 계획을 로봇들이 성공적으로 실행한 하드웨어 실험을 통해 실제 배포에 적합함이 입증되었습니다.

저자들은 현재 숲 구조 가정 (가정 2) 이 단일 리더 나무로 범위를 제한하지만, 제안된 준-정책 접근법이 로봇 공학에서 복잡한 비대칭 정보 게임을 해결하는 견고한 기반을 제공한다고 결론지었습니다. 향후 연구는 이 가정을 완화하여 다중 리더 구조를 허용하고 부등식 제약을 포함시키는 것을 목표로 합니다.