💻 computer science

Distributed Lloyd-Based algorithm for uncertainty-aware multi-robot under-canopy flocking

이 논문은 사전 환경 정보나 명시적 통신 없이 온보드 센싱과 계산만으로 복잡한 숲속 환경에서도 충돌을 피하고 군집 유지가 가능한 분산형 불확실성 인식 다중 로봇 flocking 알고리즘을 제안하고, 시뮬레이션 및 실제 실험을 통해 그 유효성을 입증합니다.

원저자: Manuel Boldrer, Vit Kratky, Viktor Walter, Martin Saska

게시일 2026-03-02

📖 3 분 읽기☕ 가벼운 읽기

CC BY 4.0

원저자: Manuel Boldrer, Vit Kratky, Viktor Walter, Martin Saska

원본 논문은 CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) 라이선스로 제공됩니다. ✨ 이것은 아래 논문에 대한 AI 생성 설명입니다. 저자가 작성하거나 승인한 것이 아닙니다. 기술적 정확성을 위해서는 원본 논문을 참조하세요. 전체 면책 조항 읽기

이 논문은 **"숲속에서 서로 말도 안 하고, 지도도 없이, 하지만 서로 떨어지지 않고 안전하게 날아다니는 드론 떼"**에 대한 이야기입니다.

기존의 드론 연구들은 대부분 서로 통신을 하거나(비행 중 데이터를 주고받음), 미리 정해진 지도가 있거나, 정교한 센서가 있는 실험실 환경에서만 작동했습니다. 하지만 이 연구는 진짜 숲속처럼 복잡하고, 통신이 안 되며, 지도도 없는 환경에서도 드론들이 무리 지어 날 수 있는 방법을 개발했습니다.

이 복잡한 기술 내용을 일상적인 비유로 쉽게 설명해 드릴게요.

1. 핵심 아이디어: "눈을 감고도 서로를 아는 무리"

이 논문에서 개발한 알고리즘의 핵심은 로이드 (Lloyd) 알고리즘을 기반으로 합니다. 이를 쉽게 비유하자면 다음과 같습니다.

상황: 여러분이 어두운 숲속에 4 명의 친구와 함께 있습니다. 서로 말도 못 하고, 손전등도 없으며, 지도도 없습니다. 하지만 서로의 위치를 감지할 수 있는 작은 센서만 있습니다.
목표: 숲을 가로질러 반대편으로 이동해야 하는데, 친구들과 너무 멀어지지 않으면서 (무리 유지), 나무에 부딪히지 않고 (장애물 회피) 이동해야 합니다.
해결책: 이 논문은 각 드론이 **"내 주변을 내 눈으로만 보고, 내 친구들이 어디 있는지 감지해서, 그들과의 거리를 유지하며 가장 안전한 길로 가라"**는 명령을 내립니다.

2. 주요 기술 3 가지 (비유로 설명)

① "보이지 않는 울타리" (Convex Weighted Voronoi Diagram)

드론들이 서로 충돌하지 않도록 각 드론에게 보이지 않는 '개인 영역'을 만들어줍니다.

비유: 마치 치킨 (닭) 이 알을 품는 것처럼, 각 드론은 자신과 가장 가까운 친구나 나무 사이에서 정확히 중간 지점을 기준으로 영역을 나눕니다.
이 영역은 고정된 것이 아니라, 친구가 가까이 오면 영역이 줄어들고, 친구가 멀어지면 넓어집니다. 이렇게 하면 서로의 영역이 겹치지 않아 충돌을 피할 수 있습니다.

② "유연한 심리" (Adaptive Control & Uncertainty)

실제 세상에서는 드론이 바람에 흔들리거나, 센서가 친구의 위치를 정확히 못 잡는 경우가 있습니다 (오차).

문제: 센서가 "친구가 5 미터 떨어져 있어"라고 말했는데, 실제로는 6 미터 떨어져 있다면? 그냥 5 미터만 믿고 가면 충돌할 수 있습니다.
해결책: 이 알고리즘은 **"아마도 친구가 이 정도는 더 멀리 있을지도 몰라"**라고 생각하며 여유를 둡니다.
비유: 마치 사람이 어두운 길에서 친구를 기다릴 때, "아마 저기서 조금 더 멀리 있을 거야"라고 생각하고 더 넓은 공간을 확보하며 기다리는 것과 같습니다. 오차가 크다고 판단되면 드론은 더 조심스럽게 (느리게) 움직입니다.

③ "리더 없는 무리" (Distributed & No Communication)

이 시스템의 가장 놀라운 점은 리더가 없다는 것과 통신이 없다는 것입니다.

비유: 물고기 떼나 새 떼를 생각해보세요. 무리 전체를 지휘하는 리더가 있는 게 아니라, 각 개체가 옆에 있는 친구만 보고 움직입니다.
드론들도 마찬가지입니다. "내 친구가 어디 있나?"만 보고 결정합니다. 통신이 끊겨도, 지도가 없어도 각자 판단해서 무리를 유지하며 이동합니다.

3. 실험 결과: "진짜 숲속에서 성공!"

연구진은 이 이론을 체코 공과대학교에서 실제로 검증했습니다.

장소: 나무가 빽빽한 진짜 숲 (GNSS 위성 신호도 안 받는 곳).
대상: 최대 4 대의 드론.
결과: 드론들은 서로 말도 안 하고, 지도도 없이, 나무 사이를 비집고 지나가면서도 서로 떨어지지 않고 안전하게 목적지까지 도착했습니다.

4. 왜 이 연구가 중요한가요?

기존 기술들은 "완벽한 환경"에서만 작동했습니다. 하지만 이 논문은 **"불완전한 세상"**을 다룹니다.

재난 구조: 통신이 두절된 재난 현장에서 드론 떼가 실종자를 찾을 때.
농업: 농약 살포 시 드론들이 서로 부딪히지 않고 효율적으로 일할 때.
군사/감시: 적의 방해로 통신이 끊겨도 무리가 흩어지지 않고 임무를 수행할 때.

요약

이 논문은 **"각자 자신의 눈과 센서만 믿고, 오차가 있을 때를 대비해 여유를 두며, 리더 없이도 서로를 배려하는 드론 떼"**를 만드는 방법을 제시했습니다. 마치 어둠 속에서도 서로 떨어지지 않고 길을 찾는 물고기 떼처럼, 드론들도 이제 복잡한 현실 세계에서 자유롭게 날아다닐 수 있게 된 것입니다.

제시된 논문 "Distributed Lloyd-based algorithm for uncertainty-aware multi-robot under-canopy flocking"에 대한 상세한 기술 요약은 다음과 같습니다.

1. 문제 정의 (Problem)

이 논문은 복잡한 환경 (특히 밀집된 숲과 같은 캐노피 하) 에서 다중 로봇 시스템 (드론 군집) 이 명시적인 통신 (Explicit Communication) 없이, 사전 환경 정보 없이, 그리고 온보드 센서 및 계산 능력만을 사용하여 안전한 무리 짓기 (Flocking) 를 수행하는 문제를 다룹니다.
주요 도전 과제는 다음과 같습니다:

통신 부재: 로봇 간 미래 궤적, 위치, 속도 등의 시간 의존적 정보를 교환하지 않음.
불확실성: 추적 오차 (Tracking errors) 및 센서 측정 오차 (Measurement uncertainties) 가 존재하는 상황.
안전 및 근접 유지: 장애물 및 다른 로봇과의 충돌을 피하면서도, 사전 정의된 이웃 로봇들과의 최대 거리 (근접 유지 제약) 를 준수해야 함.
비정형 환경: GNSS 신호가 차단된 숲과 같은 비정형 환경에서의 작동.

2. 제안된 방법론 (Methodology)

저자들은 로이드 (Lloyd) 알고리즘을 기반으로 한 분산 제어 알고리즘을 제안했습니다. 이 접근법은 각 로봇이 국부 정보만을 사용하여 자신의 위치를 결정하며, 다음과 같은 핵심 기법을 사용합니다.

Convex Weighted Voronoi Diagram (CWVD) 활용:
- 로봇의 작업 공간 (Cell) 을 정의하기 위해 CWVD 를 사용합니다. 이는 이웃 로봇과 장애물의 위치를 고려하여 각 로봇이 담당할 영역을 분할합니다.
- 안전성 보장: 로봇의 물리적 크기와 장애물을 고려하여 셀의 경계를 재조정 ( $\tilde{V}^p_i, \tilde{V}^o_i$ ) 하고, 센서 반경 내 ( $S_i$ ) 만을 고려하여 충돌을 방지합니다.
- 근접 유지 (Flocking): 특정 이웃 로봇들과의 거리가 일정 임계값 ( $\Gamma_{ij}$ ) 을 초과하지 않도록 셀을 추가로 제한 ( $M_i$ ) 하여 군집 행동을 유도합니다. 최종 셀 $F_i$ 는 안전성과 근접 유지 조건을 모두 만족하도록 설계됩니다.
적응형 가중 함수 및 제어:
- 로이드 알고리즘의 목적 함수를 최소화하기 위해 기울기 하강법 (Gradient Descent) 기반의 비례 제어 법칙을 적용합니다.
- 불확실성 대응 전략: 추적 오차와 측정 오차를 보상하기 위해 가중 함수의 확산 인자 ( $\beta_i$ $β_{i}$ ) 를 적응적으로 조절합니다.
  - 오차가 클수록 로봇은 목표 지점보다 셀 내부의 더 안전한 영역 (경계에서 떨어진 곳) 으로 이동하도록 $\beta_i$ 를 조절하여, 이론적으로 보장된 안전 마진 ( $d_u$ ) 을 유지합니다.
  - 이는 로봇이 오차로 인해 셀 밖으로 나가는 것을 방지하고, 최악의 경우에도 가장 보수적인 행동을 취하도록 합니다.
분산 및 비동기 제어:
- 모든 로봇은 별도의 리더 없이, 온보드 센서 (IMU, 2D LiDAR, 고도 센서, UVDAR) 만을 사용하여 비동기적으로 의사결정을 내립니다.
- 공통 기준 좌표계가 필요 없으며, 상대적 위치 정보만으로도 작동합니다.

3. 주요 기여 (Key Contributions)

새로운 분산 군집 제어 알고리즘: 밀집된 장애물 환경 (숲) 에서 통신 없이도 안전하고 효과적인 무리 짓기를 가능하게 하는 알고리즘 제안.
이론적 안전성 및 근접 유지 조건: 불확실성과 추적 오차가 존재하는 환경에서 충돌 방지와 이웃 간 거리 유지를 보장하는 충분 조건을 수학적으로 증명 (Theorem 1, 2).
불확실성 보상 메커니즘: 측정 오차와 추적 오차를 정량적으로 분석하여, 알고리즘 파라미터 ( $\beta_i$ ) 를 실시간으로 조정하는 적응형 전략 제시.
실제 환경 검증: 시뮬레이션뿐만 아니라, GNSS 가 없는 실제 숲 환경에서 최대 4 대의 UAV 를 이용한 실증 실험을 수행하여 알고리즘의 유효성을 입증.

4. 실험 결과 (Results)

시뮬레이션:
- 다양한 수의 로봇 (9 대, 16 대) 과 장애물 환경에서 테스트되었습니다.
- 불확실성 보상을 위한 파라미터 ( $d_u$ ) 를 올바르게 설정할 경우, 충돌 없이 100% 성공률로 목표 지점에 도달함을 확인했습니다.
- 기존 통신 기반이 아닌 알고리즘 (PACNav 등) 과 비교 시, 로봇 수가 증가하거나 환경이 복잡해져도 성능이 저하되지 않고 안전성과 근접 유지가 보장됨을 보였습니다.
실제 실험 (Real-world Experiments):
- 환경: 체코 공과대학교 (CTU) 의 밀집된 숲.
- 플랫폼: 최대 4 대의 UAV.
- 센서: RPLiDAR A3 (장애물 감지), UVDAR (상대 위치 추정), IMU, 고도 센서.
- 결과: 4 대의 드론이 서로 충돌하지 않으면서, 사전 정의된 이웃 관계에 따라 40m 거리를 이동했습니다. 모든 안전 제약과 군집 유지 제약이 미션 전체 동안 만족되었습니다.
- 성능: 평균 속도 약 0.3~~0.37 m/s, 최대 속도 약 1.0~~1.4 m/s 수준으로 안정적으로 작동했습니다.

5. 의의 및 중요성 (Significance)

통신 의존성 제거: 통신 인프라가 부재하거나 제한적인 환경 (재난 지역, 밀집된 숲, 군사 작전 등) 에서도 다중 로봇 시스템이 자율적으로 협력할 수 있는 가능성을 열었습니다.
강건성 (Robustness): 센서 오차와 추적 오차를 명시적으로 고려하여, 실제 환경에서 발생할 수 있는 불확실성 하에서도 안전을 보장합니다. 이는 기존 많은 알고리즘이 이상적인 환경 가정 하에 설계된 것과 대조적입니다.
실용성: 오픈 소스로 공개되었으며, 실제 비정형 환경 (Unstructured Environment) 에서 성공적으로 검증되어 상용화나 실제 임무 적용에 대한 높은 잠재력을 보여줍니다.
이론과 실전의 결합: 수학적 증명 (충분 조건) 을 바탕으로 파라미터를 설정하는 체계적인 방법을 제시하여, 경험적 튜닝에 의존하는 기존 방식의 한계를 극복했습니다.

이 논문은 통신이 불가능하고 환경이 복잡하며 오차가 존재하는 극한 환경에서도 다중 로봇 시스템이 안전하고 효율적으로 군집 행동을 할 수 있음을 입증한 중요한 연구로 평가됩니다.