우리는 개별 로봇의 능력이 제한된 로봇 군집(swarm)이 미지의 환경을 다중로봇 시스템으로 삼각분할(triangulation)하여 이를 기반으로 탐색, 커버리지, 감시를 조직하기 위한 근본적인 틀을 제시한다. 국소적으로는 하나의 개별 삼각형은 단일 로봇이 관리하기 쉽고 작은 영역을 커버한다. 반면 전역적으로는 삼각분할의 위상(topology)이 전체 환경의 기하를 근사적으로 포착한다. 이를 결합하면, 다중로봇 시스템은 탐색, 지도작성, 항법(navigation), 순찰(patrol)을 수행할 수 있다. 알고리즘은 로봇들이 자신의 알고리즘을 수행하는 동안 읽고 쓸 수 있는 삼각형에 정보를 저장할 수 있다. 이는 견고하면서도 다재다능한 물리적 데이터 구조(physical data structure, PDS)를 형성한다. 우리는 다중로봇 네트워크를 사용하여 미지의 2차원 유클리드 공간(two-dimensional Euclidean space)을 삼각분할하는 분산(distributed) 접근을 연구한다. 그 결과로 생성되는 PDS는 작업공간(workspace)의 간결한 표현이며, 각 삼각형에 대한 분산 지식을 포함하고, 삼각분할의 쌍대 그래프(dual graph)를 부호화하며, 보조 데이터(auxiliary data)에 대한 읽기 및 쓰기를 지원한다. 이러한 보조 정보를 저장하고 처리하는 능력은 단순한 로봇들이 복잡한 문제를 해결할 수 있게 해준다. 우리는 쌍대 그래프 항법(dual-graph navigation), 순찰, 위상학적 보로노이 테셀레이션(topological Voronoi tessellation)의 구성, 비볼록 영역(non-convex regions)에서의 지오데식 중심(geodesic centers) 위치 파악을 위한 분산 알고리즘을 개발한다. 또한, 구성된 삼각분할의 품질 및 삼각분할에서의 쌍대 그래프 연결성(connectivity)에 대한 이론적 성능 보장을 제공한다. 더 나아가, 물리적 항법에서의 경로 길이가 최단경로 유클리드 거리(shortest-path Euclidean distance)보다 상수 배 이내임을 보인다. 우리는 이러한 이론적 결과를 시뮬레이션과 열두 대 이상 로봇을 활용한 실험으로 검증한다.
*본 초록은 AI를 통해 원문을 번역한 내용입니다. 정확한 내용은 하기 원문에서 확인해주세요.