대규모 다중 에이전트 경로 탐색을 위한 로컬 통신 학습

Learning to Communicate Locally for Large-Scale Multi-Agent Pathfinding

다중 에이전트 경로 탐색(MAPF)은 여러 동질적인 에이전트가 공유 환경 내에서 동시에 이동하는 다중 로봇 경로 계획 문제에 대한 널리 사용되는 추상화 방법입니다. MAPF를 최적으로 해결하는 것은 NP-hard 문제이지만, 물류 및 수색 및 구조 활동과 같은 실제 응용 분야에서는 확장 가능하고 효율적인 솔루션이 매우 중요합니다. 이러한 문제를 해결하기 위해, 연구 커뮤니티에서는 머신러닝을 활용하는 다양한 분산형 최적화되지 않은 MAPF 솔루션을 제안했습니다. 이러한 방법들은 MAPF를 단일 에이전트의 관점에서 부분 관측 마르코프 결정 프로세스(Dec-POMDP)로 모델링하고, 각 시간 단계에서 에이전트가 로컬 관찰을 기반으로 행동을 결정하며, 일반적으로 강화 학습 또는 모방 학습을 통해 문제를 해결합니다. 우리는 동일한 접근 방식을 따르지만, 에이전트 간의 협력을 향상시키기 위해 효율적인 특징 공유를 가능하게 하는 학습 가능한 통신 모듈을 추가로 도입했습니다. 본 논문에서는 로컬 통신을 활용한 다중 에이전트 경로 탐색(LC-MAPF)이라는 일반화된 사전 훈련된 모델을 제시합니다. 이 모델은 인접한 에이전트 간의 다중 라운드 통신을 통해 정보를 교환하고 에이전트의 협력을 향상시킵니다. 실험 결과는 제안된 방법이 기존의 학습 기반 MAPF 솔루션, 즉 모방 학습 및 강화 학습 기반 접근 방식을 포함한 솔루션보다 다양한 지표에서 다양한 테스트 시나리오에서 더 우수한 성능을 보인다는 것을 보여줍니다. 주목할 만한 점은, 제안된 통신 메커니즘이 LC-MAPF의 확장성을 저해하지 않는다는 것입니다. 이는 통신 기반 MAPF 솔루션의 일반적인 문제점입니다.

Multi-agent pathfinding (MAPF) is a widely used abstraction for multi-robot trajectory planning problems, where multiple homogeneous agents move simultaneously within a shared environment. Although solving MAPF optimally is NP-hard, scalable and efficient solvers are critical for real-world applications such as logistics and search-and-rescue. To this end, the research community has proposed various decentralized suboptimal MAPF solvers that leverage machine learning. Such methods frame MAPF (from a single agent perspective) as a Dec-POMDP where at each time step an agent has to decide an action based on the local observation and typically solve the problem via reinforcement learning or imitation learning. We follow the same approach but additionally introduce a learnable communication module tailored to enhance cooperation between agents via efficient feature sharing. We present the Local Communication for Multi-agent Pathfinding (LC-MAPF), a generalizable pre-trained model that applies multi-round communication between neighboring agents to exchange information and improve their coordination. Our experiments show that the introduced method outperforms the existing learning-based MAPF solvers, including IL and RL-based approaches, across diverse metrics in a diverse range of (unseen) test scenarios. Remarkably, the introduced communication mechanism does not compromise LC-MAPF's scalability, a common bottleneck for communication-based MAPF solvers.