대규모 다중 에이전트 경로탐색을 위한 로컬 커뮤니케이션 학습

MAPF에서 다수의 에이전트가 충돌 없이 목표를 달성하려면 에이전트 간의 협력이 필수적이다. 기존 분산 학습 기반 접근은 보통 단일 메시지 교환에 의존하여 협력의 한계를 보였고, 스케일이 커질수록 성능 저하가 심해질 수 있다. LC-MAPF는 다중 라운드의 로컬 커뮤니케이션을 도입해 근접 이웃 간 정보 공유를 반복적으로 조정하고, 메시지에 대한 명시적 지도 없이도 협력 구조를 학습한다. 이를 통해 학습 기반 MAPF 솔버의 성능을 개선하고 선형 스케일링을 유지한다.

1. 문제 정의: MAPF는 에이전트들이 시간축에서 충돌 없이 목표를 달성하도록 각자 행동을 선택해야 하는 문제다. 독립적 관측에 기초한 분산 정책이 일반화하면서도 협력이 어려운 한계가 있다.
2. 해결 원리: o_tu를 X0,u로 임베딩하고, Encoder로 맥락을 얻은 뒤, LatentEncoder를 통해 작은 잠재 상태 zu를 얻는다. 각 라운드에서 이 잠재 상태와 neighbor 메시지 C_r_u를 결합해 h_r_u를 업데이트하고, 다시 메시지를 생성한다(m_r_u). R_comm 라운드 이후 a_Rcomm_u를 통해 행동 로짓을 산출하고 p_u를 얻는다. 메시지는 감독 신호 없이도 역전파를 통해 어떤 정보를 주고받아야 하는지가 학습된다.
3. 라운드 수의 영향: 학습 중 사용된 라운드 수와 동일한 라운드 수에서 최상의 성능이 나타나며, 4 라운드에서 일반화 및 협력이 가장 잘 작동한다. 더 많은 라운드는 충돌 감소 경향은 보이나 성공률 향상은 크지 않다.
4. 성능 및 스케일: LC-MAPF는 1,000~5,000 에이전트 규모에서도 선형 스케일링을 유지했고, 메시지 실패나 이웃 수 제한 같은 현실적 제약에도 비교적 강인한 편이다.

리드-온-리드: o_tu = [cost-to-go, it_u, n_tu,1, ..., n_tu,k]로 구성된 구조화된 관찰을 Transformer 인코더에 입력한다. X0,u = Etok(o_tu) + Epos + Enbr로 임베딩된 뒤 Henc_u = Encoder(X0,u)로 컨텍스트를 얻는다. 정보 버틀넥으로 L_enc_q를 가진 LatentEncoder가 zu를 생성한다. 이 Latent 상태는 각 에이전트의 내부 표현으로 사용되어 메시지 교환에 참여한다.

• 커뮤니케이션 라운드: C_r_u = { m_{r-1}_v + E_dec_nbr(v) } (v ∈ N(u) ∪ {u}), h_r_u = Decoder(L_dec_q, [zu, C_r_u]), m_r_u = MsgHead(h_r_u).
• 행동 예측: a_u = ActionHead(h_Rcomm_u), p_u = softmax(a_u).
• 학습 목표: L = CE(a_u^∗, a_u)로 정의되며, 로직은 모든 에이전트에 대해 배치 평균으로 계산된다. 메시지는 직접 감독되지 않으며, 역전파는 수신 에이전트의 행동 로짓에 대한 영향을 통해 메시지의 내용이 학습되도록 흐른다.
• 구현 및 하이퍼파라미터: Rcomm = 4, 모델은 RMSNorm, SwiGLU, QK-normalization, Differential Attention 등을 포함한 트랜스포머 블록으로 구성된다. 데이터는 23.5M 샘플을 포함하는 4맵셋에서 수집되며, 800,000 회 반복 학습, 배치 32, gradient accumulation 16, 3M 파라미터, AdamW 최적화, cosine lr decay를 사용한다.

주요 벤치마크: LC-MAPF는 Random, Mazes, Warehouse, Cities Tiles 맵에서 baselines보다 동등하거나 우수한 성능을 보였고, 85M 파라미터 MAPF-GPT 및 MAPF-GPT-DDG를 상회했다. Mazes 맵에서 MAPF-GPT-85M의 평균 상대 SoC가 1.42인 반면 LC-MAPF는 1.4로 더 나은 편이었다. Warehouse 맵에서 HMAGAT가 거의 같은 수의 인스턴스를 해결했으나 다른 맵에서 LC-MAPF의 성능은 더 좋았다. 라운드 ablation: 다중 커뮤니케이션의 중요성을 확인했고, 학습 시에 사용된 4 라운드가 가장 좋은 성능을 보였으며, 그 이상은 성공률 증가에 큰 이점을 주지 않았다. 메시지 실패 실험에서 20%/50% 실패를 가정하면, 48명 이상의 에이전트 구간에서 성공률이 크게 감소했고, 50% 실패에서 64/80명 구간에서 현저한 성능 저하가 나타났다. 네트워크 이웃의 수 제한: 관심 이웃 수를 1/2/4/8/13으로 제한했을 때, 대규모 에이전트 수에서 성공률이 급격히 감소했다. 예를 들어 48명에서 Limit=4/8/13인 경우 각각 0.86, 0.96, 0.98의 성공률을 보였고, Limit=1인 경우 0.10으로 가장 낮았다. 이로써 커뮤니케이션 규모가 성능에 중요한 영향을 미친다. 대규모 평가: 256×256 맵에서 최대 5,000 에이전트를 사용했고, makespan는 인스턴스가 2048로 표시되면 미해결로 간주된다. LC-MAPF는 1,000 에이전트 구간에서 약 0.12초/스텝, 5,000 에이전트 구간에서 약 0.65초/스텝의 선형 스케일링을 보였다.

• 전체 아키텍처: o_tu를 Transformer 인코더에 입력하는 X0,u, latent 벡터 zu, 다중 라운드 커뮤니케이션, 메시지 디코더, 최종 ActionHead를 통한 로그it 산출.
• 수학적 기반: X0,u = Etok(o_tu) + Epos + Enbr; zu = LatentEncoder(L_enc_q, H_enc_u); C_r_u = { m_{r−1}v + E_dec_nbr(v) }{v∈N(u)∪{u}}; h_r_u = Decoder(L_dec_q, [zu, C_r_u]); m_r_u = MsgHead(h_r_u); a_u = ActionHead(h_Rcomm_u); p_u = softmax(a_u).
• 학습 목표: L = CE (a_u, a_u^∗)을 모든 에이전트에 대해 배치 평균으로 최소화. 메시지 자체에 대한 직접 감독은 없으며, 메시지가 학습을 통해 어떤 정보를 전달해야 하는지 경로를 통해 결정된다.
• 구현 세부: RMSNorm, SwiGLU, combined pre-/post-normalization과 QK-normalization, Differential Attention 기법을 도입했다. Rcomm은 기본적으로 4로 설정되며 PyTorch 2.3.1 및 CUDA 12.2 기반으로 학습했다. 데이터는 총 23.5M 샘플, 750M observation-action 쌍을 포함한다. 학습은 800,000 반복, 배치 32, gradient accumulate 16, effective 배치는 512에 상응한다. 하드웨어는 NVIDIA H100 80GB를 사용했다.