MAPF 문제를 풀 수 있는 하위 문제로 분해하는 새로운 방법

이 기사에서는 다중 에이전트 경로 찾기(Multi-Agent Pathfinding, MAPF) 인스턴스를 더 작은 해석 가능한 부분 문제로 분해하기 위한 구조화된 방법론을 소개한다. 이 과정은 에이전트 종속성을 식별하고 관련 그래프를 통해 클러스터를 형성함으로써 시작된다. 이러한 클러스터는 피할 수 없는 에이전트 분석을 사용하여 부분 문제의 크기를 최소화하면서 해석 가능성을 유지하기 위해 반복적으로 이분한다. 추가적인 세분화는 방향 그래프와 강하게 연결된 구성 요소에서 파생된 해결 순서 제약 조건을 기반으로 수준을 도입한다. 마지막으로, 접근 방식은 시리얼 또는 병렬 MAPF 방법을 사용하여 부분 문제를 독립적으로 해결하고 안전하게 병합하는 방법을 설명한다. 최적의 분해를 달성하는 것이 보장되지 않지만, 이 프레임워크는 점진적으로 복잡성을 줄이고 충돌이 없는 실현 가능성을 유지한다.