본 논문은 다중 로봇 면적 탐색 경로 계획(MCPP) 문제를 4-neighbor 2D 그리드에서 다루고 있다. 기존 방법들은 쿼드런트를 조밀화한 그리드에서 탐색 트리를 먼저 계산하고 Spanning Tree Coverage (STC) 패러다임을 이용하여 경로를 생성하는 방식으로, 부분적으로 막힌 2x2 블록이 있는 그리드에는 적용할 수 없다는 한계를 지닌다. 본 논문에서는 문제를 직접 그리드 G에서 재정의하여 그리드 기반 MCPP 해결에 혁신을 가져오고 새로운 NP-hardness 결과를 제시한다. 부분적으로 막힌 블록이 포함된 경우에도 제한된 비최적성으로 완전한 탐색을 보장하는 새로운 패러다임인 Extended-STC (ESTC)를 제안한다. 또한, ESTC와 세 가지 새로운 이웃 연산자를 지역 탐색 전략에 통합하여 그리드 G에서 직접 탐색 경로를 최적화하는 새로운 알고리즘 프레임워크인 LS-MCPP를 제시한다. 기존의 그리드 기반 MCPP 연구와 달리, 다중 에이전트 경로 찾기(MAPF) 기법을 MCPP에 처음으로 적용하는 다재다능한 후처리 절차를 통합하여 두 중요한 분야를 융합한다. 이 절차는 MAPF 변형을 해결하여 로봇 간 충돌을 효과적으로 해결하고 회전 비용을 수용하여 실제 응용에 더 적합한 MCPP 솔루션을 만든다. 광범위한 실험을 통해 최대 100대의 로봇을 256x256 크기의 그리드에서 수 분 내에 해결하는 등 솔루션의 품질과 효율성이 크게 향상됨을 보여준다. 실제 로봇을 이용한 검증을 통해 실제 환경에서도 솔루션의 실현 가능성을 확인하였다.
