Deploying Ten Thousand Robots: Scalable Imitation Learning for Lifelong Multi-Agent Path Finding

저자: He Jiang, Yutong Wang, Rishi Veerapaneni, Tanishq Duhan, Guillaume Sartoretti, Jiaoyang Li · ICRA 2025

라이선스

• 오픈 액세스
• 논문: CC BY 4.0

아래 내용은 모두 논문의 라이선스(CC BY 4.0)에 따라 논문 전문을 바탕으로 하며, 그림에는 저자를 표기했습니다.

요약

SILLM은 강력한 탐색 기반 솔버를 모방하고, 공간 통신, 교통 안내, PIBT 충돌 복구를 더하여 10,000개 에이전트에 대해 단계당 1 s 이내로 계획하며 가장 높은 처리량을 낸다.

중요한 이유

자동화 창고는 이미 수천 대의 로봇을 운영하고 있으며(논문은 2022년 Amazon 물류 센터의 로봇이 4,000대를 넘었다고 인용한다), 따라서 그 규모에서 단계당 1초 미만의 계획으로 높은 처리량을 유지하는 플래너는 로봇 군 제어와 직접 관련된다. 결과는 학습된 정책이 탐색 방식의 충돌 처리 및 교통 인식 안내와 결합되면, 느린 최적 솔버뿐 아니라 가장 강력한 확장형 탐색 기반 솔버도 능가할 수 있음을 보여 준다.

문제

평생 다중 에이전트 경로 탐색(LMAPF)은 각 에이전트가 목표에 도달하자마자 새 목표를 부여하므로, 처리량(시간 단계당 도달한 목표 수)을 최대화하면서 충돌 없는 경로를 계속 재계획해야 한다. 학습 기반 솔버는 지역 관측으로부터 빠르게 반응하지만, 대부분 수십에서 수백 개의 에이전트로만 시험되었고 PIBT 같은 확장형 준최적 탐색 솔버를 이기지 못한다. 이 논문은 10,000개 에이전트 규모에서 학습 기반 솔버와 탐색 기반 솔버를 모두 이기는 것을 목표로 한다.

제안 방법

SILLM은 11×11 시야에서 모든 에이전트가 공유하는 합성곱 정책으로, 각 이웃의 특징 벡터를 정확한 상대 격자 위치에 삽입하는 Spatially Sensitive Communication 모듈을 갖는다. 관측은 세 가지 휴리스틱 안내 지도(Backward Dijkstra, 교차 고속도로 형태의 Static Guidance, TrafficFlow 기반 Dynamic Guidance) 중 하나를 인코딩하며, 단순화된 CS-PIBT 단계는 학습된 행동에 충돌이 없으면 그대로 유지하고 충돌이 있으면 PIBT로 복구한다. 정책은 2023 League of Robot Runners 우승작 WPPL의 핵심인 Windowed MAPF-LNS를 반복적으로 모방하여, 600개 에이전트가 있는 축소 지도에서 학습된다.

핵심 통찰

• 이웃의 특징을 정확한 상대 위치에 배치하는 방식(공간 민감 통신)이 절제 실험에서 어텐션 기반 통신과 통신 없음보다 우수했으며, 이는 정밀한 공간 추론이 LMAPF에 중요함을 시사한다.
• 애니타임(anytime) 대규모 솔버(Windowed MAPF-LNS)를 모방하면 PRIMAL2, SCRIMP, MAGAT 같은 이전 모방 학습기를 제한했던 소규모 학습 인스턴스(에이전트 8–10개)를 피할 수 있다.
• 최적의 안내 방식은 지도에 따라 다르다. Static Guidance는 교차형 분류 지도와 창고 지도에, Backward Dijkstra는 무작위 지도에 적합했고, Dynamic Guidance는 Paris와 Berlin 도시 지도에서 가장 좋았다.
• PIBT 기반 충돌 복구는 학습된 행동에 충돌이 없으면 이를 그대로 유지하며, 흔히 쓰이는 '정지(freeze)' 전략의 불필요한 대기와 교착 상태를 피한다.
• 단순한 MAPPO 강화 학습은 모방 학습보다 성능이 낮았으며, 모방 학습 후에 MAPPO를 적용해도 측정 가능한 향상은 없었다.

주요 결과

• 10,000개 에이전트가 있는 여섯 개의 대형 지도에서 평균 처리량이 최고의 학습 기반 기준선 대비 137.7%, 최고의 탐색 기반 기준선 대비 16.0% 증가했다.
• 대형 지도에서의 대회 방식 점수: SILLM 0.99, SILLM(Dynamic Guidance만 사용) 0.94, WPPL 0.88, TrafficFlow 0.81, PIBT 0.61, Follower 0.52. RHCR과 SCRIMP는 단계당 수 분이 걸려 이 규모에서는 평가할 수 없었다.
• 대형 지도에서의 평균 단일 단계 계획 시간: SILLM 0.349 s, WPPL 4.143 s, Follower 4.125 s.
• 대형 지도에서 모든 안내 유형에 걸쳐 Learnable PIBT가 일반 PIBT를 이겼다(평균 점수 Backward Dijkstra에서 0.80 대 0.61, Static Guidance에서 0.85 대 0.75, Dynamic Guidance에서 0.94 대 0.81).
• 모형 창고에서 실제 로봇 10대가 충돌 없이 목표에 도달했다. 가상 로봇 100대에서는 Learnable PIBT가 PIBT보다 50% 높은 처리량을 냈다.
• 각 모방 반복은 50개 에피소드에서 1,500만 개의 행동-관측 쌍을 수집하며 12회 반복된다. 학습은 RTX 4090D GPU 4개를 갖춘 서버에서 지도당 12시간 미만이 걸린다.

한계

• 저자들은 하드웨어와 소프트웨어의 한계로 인해 물리적 검증이 소형 창고에서의 실제 로봇 10대와 가상 로봇 100대로 제한되었다고 밝히며, 실제 로봇 실험은 정성적으로 보고된다.
• 플래너는 모든 에이전트의 위치를 완벽하게 안다고 가정한다. 실제 로봇은 위치 추정을 위해 OptiTrack 모션 캡처 시스템이, 실행 오차를 흡수하기 위해 Action Dependency Graph가 필요했다.
• 안내 휴리스틱은 수작업으로 설계되었고, 최적의 휴리스틱은 인스턴스에 따라 달라 경험적으로 선택해야 하며, 그 하이퍼파라미터가 성능에 영향을 준다.
• 10,000개 에이전트로 학습하는 것은 메모리 요구량 때문에 피했다. 정책은 축소 지도에서 600개 에이전트로 학습되고 대형 지도에서 평가된다.
• 강화 학습은 시험된 형태로는 도움이 되지 않았다. 저자들은 더 나은 팀 보상 배분을 향후 과제로 남겨 둔다.

분야에 미친 영향

이 논문은 IEEE ICRA 2025 Best Paper Award on Multi-Robot Systems와 IEEE ICRA 2025 Best Student Paper Award를 수상했으며, 인용 횟수는 35회이다. 논문은 게재 승인 시 코드를 공개하겠다고 밝혔으며, 공식 프로젝트 페이지는 코드 저장소로 연결된다.

초록

평생 다중 에이전트 경로 탐색(Lifelong Multi-Agent Path Finding, LMAPF)은 에이전트에게 새로운 목표가 계속 할당되는 MAPF의 변형으로, 이러한 동적 변화를 수용하기 위해 잦은 재계획이 필요하다. 최근 이 분야는 개별 지역 관측을 바탕으로 단일 단계 행동을 반응적으로 생성하는 학습 기반 방법을 받아들였다. 그러나 이러한 방법이 최고의 탐색 기반 알고리즘의 성능에 필적하기는, 특히 대규모 환경에서 여전히 어렵다. 본 연구는 새로운 통신 모듈과 체계적인 단일 단계 충돌 해소 및 전역 안내 기법을 도입한 모방 학습 기반 LMAPF 솔버를 제안한다. 우리가 제안하는 솔버인 Scalable Imitation Learning for LMAPF(SILLM)는 최신 GPU의 도움으로 학습 기반 방법의 빠른 추론 속도와 탐색 기반 방법의 높은 해 품질을 모두 물려받는다. 최대 10,000개의 에이전트와 다양한 장애물 구조를 가진 여섯 개의 대규모 지도에서 SILLM은 최고의 학습 기반 및 탐색 기반 기준선을 능가하며, 각각 평균 137.7%와 16.0%의 처리량 향상을 달성한다. 또한 SILLM은 Amazon Robotics가 후원하는 국제 LMAPF 대회인 2023 League of Robot Runners의 우승 솔루션도 능가한다. 마지막으로 우리는 모형 창고 환경에서 실제 로봇 10대와 가상 로봇 100대로 SILLM을 검증했다.

링크

• arXiv 2410.21415: https://arxiv.org/abs/2410.21415
• DOI 10.1109/ICRA55743.2025.11127445: https://doi.org/10.1109/ICRA55743.2025.11127445
• PDF: https://arxiv.org/pdf/2410.21415v1
• 코드: https://github.com/DiligentPanda/Scalable-Imitation-Learning-for-LMAPF
• 프로젝트 페이지: https://diligentpanda.github.io/SILLM/