C$^2$-Explorer: Contiguity-Driven Task Allocation with Connectivity-Aware Task Representation for Decentralized Multi-UAV Exploration

이 논문은 제한된 통신 환경에서 다중 UAV 탐사의 효율성을 극대화하기 위해, 연결성 인식 작업 표현과 연속성 기반 작업 할당 기법을 도입한 분산형 프레임워크인 C$^2$-Explorer 를 제안하며, 이를 통해 탐사 시간과 이동 거리를 기존 최첨단 방법 대비 각각 43.1% 와 33.3% 단축하는 성과를 입증했습니다.

핵심

🌲 1. 문제 상황: "혼란스러운 탐험대"

상상해 보세요. 여러분이 낯선 거대한 숲이나 복잡한 미로에 여러 대의 드론을 보냈습니다. 하지만 드론들은 서로 통신할 수 있는 거리가 매우 짧습니다.

기존의 방법들은 다음과 같은 문제를 겪었습니다:

• 지도 공유의 한계: 드론들이 서로의 위치와 지도를 실시간으로 공유하려면 통신이 완벽해야 하는데, 나무나 기둥에 가려 통신이 끊기면 혼란이 생깁니다.
• 비효율적인 이동: "가장 가까운 곳부터 가자"는 식으로 생각하다 보니, 드론 A 는 숲의 왼쪽 끝으로 갔다가, 다음엔 오른쪽 끝으로 뛰어가기를 반복합니다. 마치 집 안의 방을 청소할 때, 거실 → 화장실 → 안방 → 다시 거실을 오가며 청소하는 것처럼 비효율적입니다.
• 불가능한 임무: 드론이 갈 수 없는 벽 뒤에 숨겨진 공간을 '해야 할 일'로 잘못 인식하기도 합니다.

💡 2. C2-Explorer 의 해결책: "똑똑한 탐험대장"

이 시스템은 두 가지 핵심 아이디어로 위 문제를 해결합니다.

🗺️ 아이디어 1: "연결성 지도" (Connectivity-aware Task Representation)

기존 드론들은 공간을 단순히 '정사각형 격자'로 나누어 생각했습니다. 하지만 숲이나 건물은 격자처럼 깔끔하지 않죠.

• 비유: 기존 방식은 지도를 바둑판으로 나누어, 바둑판 한 칸 안에 '갈 수 없는 구석진 공간'과 '갈 수 있는 공간'이 섞여 있어도 그냥 '한 칸'으로 취급했습니다.
• C2-Explorer 의 방식: 드론들은 실제 길과 연결된 상태를 먼저 파악합니다. 마치 등산로 지도를 그리듯, "이곳은 길이 막혀서 갈 수 없으니 제외하고, 저곳은 길이 이어져 있으니 하나의 탐험 구역으로 묶자"라고 구분합니다.
• 효과: 드론이 갈 수 없는 곳에 시간을 낭비하지 않고, 실제로 연결된 공간만 '임무'로 인식하게 됩니다.

🤝 아이디어 2: "이웃 친구와 함께" (Contiguity-driven Task Allocation)

임무를 나누어 줄 때, 드론들에게 "너는 저기서, 너는 저기서"라고 막 섞어서 주지 않습니다.

• 비유: 기존 방식은 주사위를 굴려서 임무를 배분하는 것처럼, 드론 A 에게는 '북쪽'과 '남쪽'을, 드론 B 에게는 '동쪽'과 '서쪽'을 섞어서 줍니다. 그래서 드론들은 가운데를 가로질러 계속 왕복해야 합니다.
• C2-Explorer 의 방식: **"이웃한 임무는 같은 드론이 맡아라"**는 규칙을 적용합니다. 드론 A 는 북쪽의 모든 방을 한 번에 다 청소하고, 드론 B 는 남쪽의 모든 방을 한 번에 다 청소합니다.
• 효과: 드론들이 한곳에 머물며 탐사를 마치기 때문에, 불필요한 이동 (왕복) 이 사라지고 훨씬 빠르게 끝납니다.

🚁 3. 실제 작동 방식 (시스템 구조)

1. 지도 만들기: 드론들은 LiDAR(레이저) 를 이용해 주변을 스캔하고, '어디로 갈 수 있는지'를 연결된 그래프 (지도) 로 만듭니다.
2. 임무 나누기: 통신이 가능한 드론들이 모이면, 그중 한 대가 '임시 지휘관'이 되어 위 두 가지 규칙 (연결성 + 이웃 임무) 을 적용해 드론들에게 임무를 배분합니다.
3. 이동 및 탐사: 각 드론은 배정받은 '연속된 구역'을 따라 부드럽게 날아가며 탐사를 완료합니다.

📊 4. 결과: 얼마나 빨라졌나요?

이론과 실제 실험 (실제 드론을 숲과 건물에 날려보냄) 에서 놀라운 결과를 보였습니다.

• 시간 단축: 기존 최고의 기술 (SOTA) 보다 약 43% 더 빠르게 탐사를 완료했습니다. (예: 100 분 걸리던 일을 57 분 만에 끝냄)
• 이동 거리 단축: 드론이 날아간 총 거리가 약 33% 줄어듭니다. (배터리 소모가 훨씬 적어짐)
• 실제 검증: 실제 나무가 우거진 숲과 기둥이 있는 건물에서도 드론들이 통신이 끊기는 상황에서도 잘 협력하며 탐사했습니다.

🎯 요약

C2-Explorer는 드론들에게 "가장 가까운 곳부터 가라"는 단순한 지시 대신, **"어디가 서로 연결되어 있는지 먼저 파악하고, 이웃한 곳들을 한 번에 깔끔하게 처리하라"**는 지능적인 전략을 가르친 시스템입니다.

마치 효율적인 청소부 팀이 방을 청소할 때, 방을 무작위로 오가는 게 아니라 "거실 → 주방 → 식탁" 순서로 한 번에 정리하듯, 드론들도 불필요한 왕복 없이 미지의 공간을 빠르게 정복하는 것입니다.

기술 요약

1. 연구 배경 및 문제 정의 (Problem)

무인 항공기 (UAV) 를 이용한 자율 탐사는 구조화되지 않은 환경에서 3D 재구성, 수색 및 구조, 시설 점검 등에 필수적입니다. 그러나 단일 UAV 는 체공 시간의 한계로 인해 넓은 영역을 탐사하기 어렵기 때문에, 다중 UAV 협업이 필수적입니다. 하지만 제한된 통신 환경 하에서 효율적인 다중 UAV 탐사를 구현하는 데는 다음과 같은 두 가지 주요 병목 현상이 존재합니다.

• 부적절한 작업 표현 (Task Representation): 기존 방법들은 그리드 기반의 균일한 분할을 사용하거나 프론티어 (frontier) 를 작업 단위로 사용합니다.
  • 그리드 기반 방법은 복잡한 환경 (기둥, 벽 등) 에서 공간적 연결성을 고려하지 않아, 물리적으로 분리된 영역을 하나의 작업으로 잘못 통합하여 불필요한 이동 (detour) 을 유발합니다.
  • 프론티어 기반 방법은 실시간 전역 맵 공유를 필요로 하여 통신 대역폭을 많이 소모하거나, 통신이 불안정할 경우 성능이 급격히 저하됩니다.
• 시공간적 연속성 (Spatiotemporal Contiguity) 의 부재: 기존 작업 할당 알고리즘은 주로 순간적인 국소 최적화 (Greedy) 에 의존하거나, 단순히 이동 거리만 고려합니다. 이로 인해 한 UAV 가 시간의 흐름에 따라 공간적으로 인접하지 않은 작업들을 번갈아 수행하게 되어, 영역 간 불필요한 왕복 이동이 발생하고 탐사 효율이 떨어집니다.

2. 제안 방법론 (Methodology: C2-Explorer)

이 논문은 제한된 통신 환경에서 **연결성 인식 작업 표현 (Connectivity-Aware Task Representation)**과 **연속성 주도 작업 할당 (Contiguity-Driven Task Allocation)**을 결합한 탈중앙화 프레임워크 C2-Explorer를 제안합니다.

A. 연결성 인식 작업 표현 (Connectivity-aware Task Representation)

• 연결성 그래프 구축: 탐사 공간을 coarse grid 로 분할한 후, 각 그리드 내에서 연결된 성분 라벨링 (CCL) 을 수행하여 자유 공간과 미탐사 영역을 분리합니다. 이를 기반으로 **연결성 그래프 (Connectivity Graph)**를 점진적으로 구축합니다.
  • 그래프의 정점은 지역 (Region) 의 앵커가 되며, 간선은 자유 공간, 미탐사 영역, 그리고 문 (Portal) 을 통해 연결됩니다.
• 독립 작업 단위 생성: 공간적으로 분리된 미탐사 영역은 별도의 독립적인 작업 단위 (Task Unit) 로 정의됩니다.
  • 장애물로 둘러싸여 접근 불가능한 영역은 'INVALID'로 표시되어 할당에서 제외됩니다.
  • 각 작업 단위는 미탐사 볼륨의 수 (작업량), 볼록 껍질 (Convex Hull) 정보 등을 포함하는 경량 데이터 구조로 표현되어 통신 부하를 줄입니다.

B. 연속성 주도 작업 할당 (Contiguity-driven Task Allocation)

• 연속성 정규화 CVRP: 작업 할당 문제를 차량 경로 문제 (CVRP) 로 모델링하되, **그래프 인접성 연속성 페널티 (Graph-adjacency Contiguity Penalty)**를 도입합니다.
  • 기존 CVRP 는 이동 거리만 최소화하지만, 본 방법은 그래프 상에서 인접하지 않은 작업 쌍을 같은 UAV 에 할당할 경우 페널티를 부과합니다.
  • 페널티 함수 $\psi(\rho_{ij})$는 두 작업 간의 거리와 허용 가능한 연결 반경 ($R_c$) 의 비율을 기반으로 하며, 인접하지 않은 할당을 억제하여 UAV 가 시간적으로 연속적이고 공간적으로 인접한 작업들을 수행하도록 유도합니다.
• 탈중앙화 통신 프로토콜: 통신 범위 내의 UAV 들 중 ID 가 가장 낮은 UAV 를 임시 호스트 (Host) 로 선정하여 CVRP 를 풀고, 작업 시퀀스를 다른 UAV 들에게 전파합니다. 손실 패킷이나 순서 왜곡을 견디기 위해 'Proposal-Commit-Finalize' 단계의 커밋 스타일 핸드셰이크 프로토콜을 사용합니다.

C. 단일 UAV 경로 계획 (CP-guided Planning)

• 할당된 작업 목록을 기반으로 전역 경로 계획 (Global CP Planning) 을 수행합니다.
• 비대칭 외판원 문제 (ATSP) 를 풀 때 이동 거리뿐만 아니라 속도 일관성 (Velocity Consistency) 을 고려하여 매끄러운 경로를 생성합니다.
• 로컬 레벨에서는 프론티어 클러스터링과 TSP 변형을 통해 구체적인 탐사 경로를 생성하고, B-spline 을 사용하여 동역학적으로 가능한 부드러운 궤적을 생성합니다.

3. 주요 기여 (Key Contributions)

1. 연결성 인식 작업 표현: 분할된 공간의 위상적 연결성을 모델링하여, 공간적으로 분리된 미탐사 영역을 독립 작업 단위로 분리하고 접근 불가능한 영역을 필터링합니다. 이는 불필요한 이동을 줄이고 작업 할당의 합리성을 높입니다.
2. 연속성 주도 작업 할당: 인접성 제약이 포함된 이동 비용 최적화 문제를 제안하여, 그래프 기반 페널티를 통해 비연속적인 할당을 억제하고 시공간적으로 연속적인 작업 집합을 형성합니다.
3. 광범위한 검증: 시뮬레이션 및 실제 비행 실험을 통해 제안된 방법의 유효성과 효율성을 입증했습니다.

4. 실험 결과 (Results)

• 시뮬레이션 성능: Cubicle Office, Open-plan Office, Octa Maze 등 3 가지 복잡한 환경에서 4 대의 UAV 를 사용하여 실험했습니다.
  • 탐사 시간: 기존 최첨단 (SOTA) 방법 (RACER, FAME) 대비 평균 43.1% 단축.
  • 경로 길이: 평균 33.3% 감소.
  • 특히 구조가 복잡하고 통신이 제한된 환경에서 기존 방법들의 성능 저하 (불필요한 이동, 중복 탐사) 를 효과적으로 해결했습니다.
• 확장성: UAV 대수 증가 (2 대 $\to$ 4 대) 시에도 경로 길이의 불필요한 증가를 억제하며 효율적인 확장이 가능함을 보였습니다.
• 통신 범위 영향: 통신 거리 ($r_{comm}$) 가 5m 에서 15m 로 증가함에 따라 성능이 지속적으로 향상되지만, 5m 의 엄격한 제한 조건에서도 안정적으로 작동함을 확인했습니다.
• 실제 비행 실험: 3 대의 실제 UAV 를 사용하여 숲 (Unstructured woodland) 과 기둥이 있는 건물 (Structured building) 환경에서 성공적인 탐사를 수행했습니다.

5. 의의 및 결론 (Significance)

이 논문은 제한된 통신 환경 하에서 다중 UAV 협업 탐사의 핵심 문제인 작업 표현의 비효율성과 작업 할당의 비연속성을 동시에 해결했습니다.

• 기술적 의의: 단순한 거리 기반 최적화를 넘어, 환경의 위상적 구조 (Topology) 를 작업 표현과 할당 알고리즘에 직접 통합함으로써, 복잡한 실제 환경에서의 탐사 효율성을 획기적으로 높였습니다.
• 실용적 가치: 통신이 불안정하거나 대역폭이 제한된 실제 현장 (재난 지역, 대형 시설 등) 에서 UAV 군집이 자율적으로 효율적으로 작동할 수 있는 강력한 프레임워크를 제공합니다.
• 오픈소스: 코드와 데이터는 공개되어 향후 연구 및 개발의 기반을 마련했습니다.

결론적으로, C2-Explorer 는 탈중앙화 다중 UAV 시스템이 복잡한 환경에서 불필요한 이동을 최소화하고, 연속적이고 효율적인 탐사를 수행할 수 있도록 하는 새로운 패러다임을 제시합니다.