본 논문은 다수의 에이전트가 네트워크 상에서 충돌을 피하며 각자의 목표 지점으로 이동하는 최적 경로 문제(Multiagent Path Finding, MAPF)를 다룬다. 기존 MAPF 문제에 에이전트 간의 제한된 통신 범위를 고려한 통신 제약 조건을 추가하여, 최단 시간(makespan) 내에 목표 지점에 도달하면서 동시에 통신 연결성을 유지하는 경로를 찾는 문제(Multiagent Path Finding with Communication Constraint, MAPFCC)를 연구한다. 본 논문에서는 특정 네트워크 구조(트리 토폴로지, 제한된 최대 차수, 제한된 트리 너비)에 대해 효율적인 세 가지 정확한 알고리즘을 제시하고, 에이전트 수가 입력으로 주어지는 경우 효율적인 알고리즘을 구성하는 것이 어려움을 보여준다.
