기술 요약: 대규모 다중 에이전트 경로 탐색을 위한 지역적 학습을 통한 의사소통

문제 정의

다중 에이전트 경로 탐색 (MAPF) 은 자동화 창고나 자율 주행 차량 대열과 같은 공유 환경에서 여러 동종 에이전트를 조정하기 위한 근본적인 추상화입니다. 목표는 $n$개의 에이전트가 그래프 상에서 시작 정점에서 목표 정점으로 이동할 때 충돌 (정점 또는 간선 충돌) 없이 개별 계획을 계산하는 것입니다. 최적 MAPF 솔버가 존재하지만, 이 문제는 NP-난해 (NP-hard) 이며 에이전트 수가 증가함에 따라 확장성이 급격히 저하됩니다.

국소적 관측에 기반하여 에이전트가 결정을 내리는 탈중앙화 접근법은 확장성 달성을 위한 길을 제시하지만, 종종 조정의 질을 확보하는 데 어려움을 겪습니다. MAPF-GPT 와 같은 최근의 학습 기반 방법은 대규모 데이터셋을 사용한 모방 학습 (IL) 을 통해 강력한 결과를 달성했습니다. 그러나 이러한 모델들은 일반적으로 명시적인 에이전트 간 의사소통이 부족하며, 협력적 행동을 추론하기 위해 오직 국소적 관측에만 의존합니다. 기존 의사소통 기반 탈중앙화 방법들은 종종 상호작용을 국소적 관측의 단일 라운드 교환으로 제한하는데, 이는 밀집 환경에서 복잡한 충돌을 해결하기에 불충분할 수 있습니다.

방법론: LC-MAPF

저자들은 LC-MAPF(다중 에이전트 경로 탐색을 위한 지역적 의사소통) 를 제안합니다. 이는 에이전트 조정을 강화하기 위해 학습 가능한 다중 라운드 의사소통 모듈을 도입한 탈중앙화 학습 기반 프레임워크입니다.

아키텍처

이 모델은 약 300 만 개의 파라미터를 가진 트랜스포머 기반 아키텍처를 기반으로 구축되었습니다. 각 시간 단계 $t$에서 각 에이전트 $u$의 워크플로우는 다음과 같습니다:

1. 관측 인코딩: 에이전트는 비용-to-고 행렬, 자기 특성 (위치, 목표, 탐욕적 행동, 이력), 그리고 $k$개의 가장 가까운 이웃의 특성을 포함하는 토큰화된 시퀀스로 구성된 구조화된 국소 관측 $o^t_u$를 수신합니다. 이는 시퀀스 $X_{0,u}$로 임베딩됩니다.
2. 잠재 상태 압축: 관측 크기와 무관한 의사소통 확장성을 보장하기 위해, 트랜스포머 인코더가 입력을 처리하고 "잠재 병목 (latent bottleneck)"(Perceiver 아키텍처에서 영감) 이 인코딩된 토큰을 압축된 잠재 상태 $z_u \in \mathbb{R}^{T_{latent} \times d_{latent}}$로 압축합니다.
3. 반복적 의사소통: 에이전트들은 $R_{comm}$라운드의 국소적 의사소통을 수행합니다 (기본값 $R_{comm}=4$).
   • 각 라운드 $r$에서, 에이전트는 이웃들 (및 자기 자신) 로부터 메시지를 수신합니다.
   • 디코더는 에이전트의 잠재 상태 $z_u$와 수신된 이웃 메시지 $C^r_u$를 융합합니다.
   • 메시지 헤드는 다음 라운드에 전송될 업데이트된 메시지 벡터 $m^r_u$를 생성합니다.
   • 결정적으로, 메시지는 감독되지 않습니다. 네트워크는 역전파를 통해 최종 행동 손실을 최소화하는 데 필요한 정보를 무엇인지 학습하며, 이로써 의사소통 전략이 자연스럽게 발현됩니다.
4. 행동 예측: 최종 의사소통 라운드 후, 예측 헤드는 행동 로짓을 출력하며, 이는 행동 선택을 위한 확률 분포로 변환됩니다.

학습

LC-MAPF 는 전문가 시연 (expert demonstrations) 을 사용하여 **모방 학습 (Imitation Learning)*을 통해 학습됩니다. 학습 데이터셋은 다양한 맵 유형 (미로, 무작위, 주택) 에서 중앙 집중식 솔버 (LaCAM) 로부터 파생된 약 7 억 5 천만 개의 관측 - 행동 쌍으로 구성됩니다. 목표는 예측된 행동과 전문가 행동 간의 교차 엔트로피 손실을 최소화하는 것입니다. 의사소통 메시지에 대한 명시적 감독은 제공되지 않으며, 모델은 집단적 행동의 질을 향상시키기 위해 의사소통하는 법을 학습합니다.

주요 기여

1. 새로운 의사소통 프레임워크: 명시적인 의사소통 레이블이나 감독 없이 전문가 행동 시연만을 사용하여 에이전트들이 의사소통할 수 있게 하는 LC-MAPF 프레임워크의 도입.
2. 최첨단 성능: 학습 가능한 탈중앙화 MAPF 솔버들 사이에서 새로운 최첨단 성능을 기록한 300 만 파라미터 트랜스포머 모델. 이는 다양한 지표와 맵 토폴로지에 걸쳐 기존 모방 학습 (IL) 및 강화 학습 (RL) 접근법 (MAPF-GPT, SCRIMP, DCC, MAGAT 변형 포함) 을 능가합니다.
3. 의사소통을 통한 확장성: 제안된 다중 라운드 의사소통 메커니즘이 에이전트 수가 증가함에 따라 선형 확장성을 유지함을 입증함으로써, 의사소통 기반 솔버에서 흔히 발생하는 병목 현상을 해결했습니다.
4. 애블레이션 및 견고성 분석: 다음과 같은 광범위한 연구를 통해 입증됨:
   • 다중 라운드 의사소통 (특히 4 라운드) 이 높은 성공률에 필수적입니다.
   • 시스템은 작은 에이전트 집단에서 메시지 실패 (최대 50% 노이즈) 에 대해 견고합니다.
   • 의사소통 이웃 크기를 제한하는 것은 밀집 시나리오에서 성능을 현저히 저하시킵니다.

실험 결과

실험은 무작위, 미로, 창고, 도시 맵 유형을 포괄하는 POGEMA 벤치마크에서 수행되었습니다.

• 성공률: LC-MAPF 는 8500 만 파라미터 MAPF-GPT 를 포함한 모든 베이스라인과 동등하거나 더 높은 성공률을 달성했습니다. 이는 모든 맵 유형과 에이전트 수 (표준 테스트에서는 최대 256 개, 대규모 평가에서는 최대 5,000 개) 에서 입증되었습니다.
• 해의 질: 중앙 집중식 최적 플래너 (LaCAM*) 대비 합계 비용 (Sum-of-Costs, SoC) 측면에서 LC-MAPF 는 일관되게 최상이거나 최상에 근접한 비율을 달성했습니다.
• 확장성: 256x256 맵에서 최대 5,000 개의 에이전트를 대상으로 한 대규모 테스트에서 LC-MAPF 는 선형 확장성을 유지했습니다. 계산 시간은 예측 가능하게 증가했습니다 (예: 1,000 개 에이전트당 약 0.12 초/단계에서 5,000 개 에이전트당 약 0.65 초/단계).
• 실제 배포: 저자들은 모듈형 미로 환경에서 물리적 다중 로봇 플랫폼 (수정된 JetBots) 에 LC-MAPF 를 성공적으로 배포했습니다. 회전/대기 동기화를 사용하여 이산적 계획과 연속적 제어를 연결함으로써, 에이전트들은 충돌 없이 목표를 달성하기 위해 성공적으로 조정되었습니다. 이는 방법론의 실제 적용 가능성을 검증했습니다.

중요성과 주장

이 논문은 LC-MAPF 가 효과적인 반복적 국소 의사소통이 전문가 궤적에서 암묵적으로 학습될 수 있음을 입증함으로써 탈중앙화 다중 에이전트 조정 분야에서 중요한 진전을 이루었다고 주장합니다. 의사소통을 무시하거나 단일 라운드 감독 교환에 의존하는 이전 방법들과 달리, LC-MAPF 는 에이전트들이 동적으로 협상하고 충돌을 해결할 수 있게 하는 다중 라운드 비감독 의사소통 메커니즘을 활용합니다.

저자들은 이 접근법이 해의 질과 확장성 사이의 균형을 성공적으로 유지하며, 의사소통 기반 방법들이 계산 병목 현상으로 고통받는 일반적인 트레이드오프를 극복했다고 강조합니다. 그 결과들은 LC-MAPF 가 다양한 보이지 않는 환경과 대규모 에이전트 집단을 처리할 수 있는 일반화 가능한 사전 학습 모델로서 기능하며, 물류 및 수색 구조와 같은 실제 로봇 응용 분야에 대한 견고한 솔루션을 제공함을 시사합니다.