본 논문은 다중 로봇 면적 탐색 경로 계획(MCPP) 문제를 4-neighbor 2D 그리드에서 해결하는 새로운 방법을 제시합니다. 기존 방법들은 쿼드런트 조정 그리드에서 탐색 트리를 먼저 계산하고 스패닝 트리 탐색(STC) 패러다임을 사용하여 경로를 생성하는 방식으로, 부분적으로 막힌 2x2 블록이 있는 그리드에는 적용할 수 없다는 한계를 가지고 있습니다. 본 논문에서는 문제를 직접 그리드 상에서 재정의하여, 부분적으로 막힌 블록이 있는 그리드에서도 완전한 탐색을 보장하는 확장된 STC(ESTC) 패러다임을 제안합니다. 또한, ESTC와 세 가지 새로운 이웃 연산자를 지역 탐색 전략에 통합한 새로운 알고리즘 프레임워크 LS-MCPP를 제시합니다. 마지막으로, 다중 에이전트 경로 탐색(MAPF) 기법을 MCPP에 처음으로 적용하는 다용도 후처리 절차를 통합하여 로봇 간 충돌을 해결하고 회전 비용을 고려하여 실제 적용 가능성을 높였습니다. 실험 결과, 최대 100대의 로봇과 256x256 크기의 그리드에서도 수 분 내에 솔루션을 생성하며, 실제 로봇을 이용한 검증을 통해 실제 환경에서의 실행 가능성을 확인했습니다.
