메타 에이전트 충돌 기반 최적 다중 에이전트 경로 찾기

다중 에이전트 경로 찾기 문제(MAPF)의 작업은 각기 다른 시작 지점과 목표 위치를 가진 여러 에이전트를 위한 경로를 찾아 에이전트가 충돌하지 않도록 하는 것입니다. 이 문제는 A* 알고리즘에 기반한 알고리즘으로 최적 해결이 가능합니다. 최근에는 Conflict-Based Search (CBS)라는 대체 알고리즘을 제안하였으며(Sharon et al. 2012), 일부 경우 A*-기반 알고리즘보다 우수함을 보여주었습니다. CBS는 두 수준의 알고리즘입니다. 상위 수준에서는 에이전트 간의 충돌에 기초한 트리에서 검색이 수행됩니다. 하위 수준에서는 한 번에 단일 에이전트에 대해서만 검색이 수행됩니다. 어떤 경우에 CBS가 매우 효율적이지만, 다른 경우에는 A*-기반 알고리즘보다 더 열악합니다. 본 논문은 CBS를 메타 에이전트 CBS(MA-CBS)로 일반화함으로써 후자의 경우에 초점을 맞춥니다. 주요 아이디어는 내부 충돌 수가 주어진 경계를 초과하는 경우 에이전트 그룹을 메타 에이전트로 결합하는 것입니다. MA-CBS는 모든 완전 MAPF 해결기 위에서 실행될 수 있는 프레임워크로 작용합니다. 우리는 새로운 접근 방식을 분석하고 기본 CBS 및 많은 경우 A*-기반 최적 해결기를 초월하는 실험 결과를 제공합니다.