제7부 자율성·군집
7.9 군집 I: 알고리즘·분산 제어·통신 제약
7.9.1 이 장에서 배우는 것 / 선수 지식 / 특히 중요한 독자
여러 대의 무인기가 한 일을 나눠 한다. 드론 쇼는 수천 대로 그림을 그리고, 재난 현장에서는 여러 대가 구역을 나눠 실종자를 찾으며, 농경지에서는 방제기 여러 대가 고랑을 나눈다. 이 장은 그 협조가 어떤 알고리즘으로 이루어지고, 통신이 그 알고리즘을 어디서 붕괴시키는가를 작성한다. 핵심은 하나다. 군집의 성능은 기체 한 대의 성능보다 누가 누구와 얼마나 자주 말하는가에 더 크게 달려 있다.
배우는 것:
- 군집의 정의와 구조 — 중앙 집중·분산·혼합의 구분, 결정마다 다른 시간 척도.
- 합의 알고리즘 — 그래프 라플라시안, 수렴 속도를 정하는 대수적 연결도 $\lambda_2$, 지연을 견디는 한계를 정하는 최대 고윳값.
- 대형 유지와 충돌 회피 — Reynolds의 세 규칙, 인공 퍼텐셜, 속도 장애물(2.14.9.3)과, 갱신 주기·손실·위치 오차가 최소 간격을 붕괴시키는 크기.
- 작업 할당과 탐색 분담 — 헝가리안 최적 할당, 경매, 합의 기반 경매(CBBA)의 개념과 협조가 없을 때의 손실.
- 통신 제약 — 대역(채널 부하)·지연·패킷 손실·망 분할이 합의와 대형에 주는 영향을 3.10의 수치와 잇는다.
- 드론 쇼의 실제 — 중앙에서 계산한 궤적, RTK, 시각 동기로 이루어지는 "자동 비행"의 구조.
선수 지식: 다중 접속과 경쟁 방송의 처리량은 3.10(3.10.4·3.10.9), MANET 라우팅은 3.10.6.2, 공대공 채널은 3.4.3.3, 속도 장애물은 2.14.9.3, RTK는 4.2.6.2, 탐색 이론은 6.12.10이다. 수식은 행렬의 고윳값과 확률 수준이다. 그래프 이론과 분산 최적화의 일반론은 자매서 robotics(BK-07)의 몫이다. 이 장은 같은 종류의 기체가 모인 군집을 다루고, 능력이 다른 공중·지상·수중 로봇의 협업은 7.15가 다룬다.
특히 중요한 독자: 엔지니어는 7.9.4~7.9.7의 계산과 7.9.11의 워크스루를 본다. 사업·운영 담당자는 7.9.2(구조), 7.9.10(드론 쇼), 7.9.12(트레이드오프)를 먼저 본다. 정책·인증 담당자는 7.9.9(결정의 시간 척도)와 7.9.15를 본다. 다수 기체를 승인할 때 무엇을 물어야 하는지가 거기서 나온다.
기준 시점과 경계. 이 장은 2026년 10월을 기준으로, 지식은 2026년 중반까지 반영했다. 수치는 일반적 모형, 교육용 가정이며 특정 체계·제품의 성능이 아니다. 기록과 제원은
(공개 주장치)로 표시했다. 시뮬레이션은 파이썬 표준 라이브러리(math·random)와 고정 시드 20261028로 돌렸다(mil-uam/fig-src/7.9-model.py, 표의 수치는7.9-calc.py). 이 장은 협조 알고리즘의 일반 원리와 민간 예(드론 쇼·협동 매핑·수색·농업·통신 중계)로 사용한다. 군집 공격·포화 공격·방공망 돌파 같은 전술은 다루지 않는다. 군집 작전 개념과 지휘통제는 10.10, 무기 체계의 자율성과 의미 있는 인간 통제(MHC)는 19.3이 맡는다. 시험·평가·보증은 7.10, 한 사람이 여러 대를 감독하는 문제는 7.11이 이어 받는다.
7.9.2 개념·직관 — "여러 대"가 아니라 "협조의 구조"
여러 대를 띄운다고 군집이 되지는 않는다. 조종자 열 명이 기체 열 대를 따로 몰면 다수 기체 운용이다. 군집(swarm)은 여러 기체가 정보를 주고받으며 하나의 목표를 나눠 수행하는 체계를 말한다. 문헌의 정의는 기관마다 다르다. 이 장은 "기체끼리 또는 기체와 중앙이 상태를 주고받아 각자의 행동을 서로에게 맞추는가"를 기준으로 사용한다.
협조를 누가 계산하느냐로 세 구조를 나눈다.
| 구조 | 누가 결정하나 | 강점 | 약점 | 예 |
|---|---|---|---|---|
| 중앙 집중 | 지상국 또는 지휘 기체 하나가 모두의 경로·할당을 계산 | 최적에 가깝고 검증이 쉽다 | 중앙과 링크가 단일 고장점, 대수에 비례하는 링크 부하 | 드론 쇼, 방제기 경로 배정 |
| 분산 | 기체마다 이웃 정보만으로 같은 규칙을 따른다 | 일부가 빠져도 나머지가 계속한다, 규모 확장 | 최적이 아니고, 전체 행동을 증명하기 어렵다 | 근접 충돌 회피, 대형 유지 |
| 혼합 | 느린 결정은 중앙, 빠른 안전은 각자 | 두 장점을 나눠 갖는다 | 두 층의 경계 설계가 어렵다 | 협동 매핑·수색의 실제 구성 |
자동과 자율의 구분(0.2.6)을 군집에도 그대로 사용한다. 미리 계산한 궤적을 각자 정밀하게 따라가는 드론 쇼는 수천 대가 함께 날아도 자동 비행에 가깝다(0.4.9). 기체가 상황을 보고 할당이나 경로를 스스로 바꾸면 그 결정의 범위만큼 자율이다. 군집을 말할 때는 무엇을(간격·경로·할당) 기체가 스스로 정하는지를 함께 적는다.
세 축의 요구는 이렇게 다르다.
| 축 | 군집이 사용되는 곳 | 주된 요구 |
|---|---|---|
| 군용 드론 | 넓은 구역의 감시·통신 중계 같은 운용 개념(10.10) | 통신이 끊기는 환경에서의 분산 결정, 사람 통제의 유지(19.3) |
| 민간 UAS | 드론 쇼, 협동 매핑·측량, 수색구조, 방제, 통신 중계 | 정해진 공간 안의 분리, 승인 가능한 단순성, 비용 |
| AAM | 군집은 아니지만, 같은 회랑과 버티포트를 사용하는 다수 기체의 조정 | 전략적 분리(9.14·14.22)와 기체 수준 분리(2.14)의 결합 |
7.9.3 통신 위상과 그래프 — 누가 누구와 말하는가
군집을 그래프로 본다. 기체는 꼭짓점, 서로 정보를 주고받는 쌍은 변이다. 인접 행렬 $A$(이웃이면 1)와 차수 행렬 $D$(이웃 수의 대각 행렬)로 그래프 라플라시안을 정의한다.
$$L=D-A,\qquad 0=\lambda_1\le\lambda_2\le\cdots\le\lambda_N$$
결론부터: 두 번째로 작은 고윳값 $\lambda_2$를 대수적 연결도(algebraic connectivity, Fiedler, 1973)라 한다. $\lambda_2>0$이면 그래프가 이어져 있고, 클수록 정보가 빨리 퍼진다. 가장 큰 고윳값 $\lambda_N$은 반대로 지연에 얼마나 약한가를 정한다(7.9.4). 대표 위상의 고윳값은 식으로 구해진다. 링은 $\lambda_k=2(1-\cos(2\pi k/N))$, 경로는 $2(1-\cos(k\pi/m))$, 격자는 두 경로의 합, 완전 그래프는 $N$이다.
| 위상(16대) | $\lambda_2$ | $\lambda_N$ | 링크 수 | 64대일 때 $\lambda_2$ | 64대일 때 링크 수 |
|---|---|---|---|---|---|
| 스타(중앙 하나) | 1.00 | 16.0 | 15 | 1.00 | 63 |
| 링 | 0.152 | 4.00 | 16 | 0.0096 | 64 |
| 격자(4×4, 8×8) | 0.586 | 6.83 | 24 | 0.152 | 112 |
| 완전 그래프 | 16.0 | 16.0 | 120 | 64.0 | 2,016 |
읽을 것 둘. 첫째, 링의 $\lambda_2$는 대수의 제곱에 반비례해 줄어든다. 16대에서 64대로 가면 16배 작아진다. 이웃하고만 말하는 긴 사슬은 커질수록 급격히 느려진다. 둘째, 완전 그래프는 가장 빠르지만 링크가 $N(N-1)/2$개로 늘어난다. 무선에서 "모두가 모두를 듣는다"는 것은 모두가 한 채널을 나눠 사용한다는 뜻이어서 대수가 늘면 손실이 커진다(7.9.5). 위상의 선택은 속도와 채널 부하의 교환이다.
7.9.4 합의 알고리즘과 수렴 속도
합의(consensus)는 각 기체가 가진 값(바람 추정, 집결 시각, 진행 방향)을 이웃과의 교환만으로 같은 값에 모으는 절차다. 가장 단순한 규칙은 "이웃과의 차이만큼 조금씩 다가간다"이다.
$$\dot x_i=\kappa\sum_{j\in\mathcal N_i}(x_j-x_i)\ \Longleftrightarrow\ \dot{\mathbf x}=-\kappa L\mathbf x,\qquad x_i[k+1]=x_i[k]+\varepsilon\sum_{j\in\mathcal N_i}\bigl(x_j[k]-x_i[k]\bigr)$$
| 기호 | 뜻 |
|---|---|
| $x_i$ | 기체 $i$의 값 |
| $\mathcal N_i$ | 기체 $i$의 이웃(정보를 받는 상대) |
| $\kappa$ | 연속 시간 이득 [1/s] |
| $\varepsilon$ | 이산 반복의 걸음, 이 장은 $1/(1+\text{최대 차수})$ |
그래프가 이어져 있고 양방향이면 값의 합이 보존되므로 모두 처음 값의 평균으로 모인다. 불일치는 $e^{-\kappa\lambda_2 t}$보다 빨리 줄어든다. 즉 시상수가 $1/(\kappa\lambda_2)$다(Olfati-Saber·Murray, 2004). 이산 반복에서는 한 번에 $\rho=\max_{k\ge2}\lvert1-\varepsilon\lambda_k\rvert$배씩 준다. 16대에서 불일치가 1 %로 줄 때까지 반복 수를 계산과 모의로 구했다.
| 위상(16대) | 예측(가장 느린 성분만 있을 때) | 모의(초깃값 균등 분포, 200회 평균) |
|---|---|---|
| 스타(분산 규칙) | 71.4회 | 71.8회 |
| 링 | 88.4회 | 60.4회 |
| 격자 4×4 | 37.0회 | 27.6회 |
| 완전 그래프 | 1회 | 1.0회 |
예측이 모의보다 큰 것은 예측이 가장 느린 모드만 있는 최악의 초깃값을 가정했기 때문이다. 64대에서는 링이 720.9회, 격자가 81.9회로 늘고(50회 평균) 완전 그래프는 여전히 1회다. 방송이 10 Hz라면 반복 한 번이 0.1 s이므로 64대 링의 합의는 1분이 넘게 걸린다.
지연이 한계를 만든다. 모든 링크에 같은 지연 $\tau$가 있으면 연속 합의는 다음 조건에서만 수렴한다(Olfati-Saber·Murray, 2004).
$$\tau<\frac{\pi}{2\kappa\lambda_N}$$
16대, $\kappa=0.5$ 1/s로 계산하면 다음과 같다.
| 위상 | 시상수 $1/(\kappa\lambda_2)$ | 지연 한계 $\pi/(2\kappa\lambda_N)$ |
|---|---|---|
| 스타 | 2.00 s | 0.196 s |
| 링 | 13.1 s | 0.785 s |
| 격자 4×4 | 3.41 s | 0.460 s |
| 완전 그래프 | 0.12 s | 0.196 s |
빠른 위상이 지연에 약하다. 완전 그래프는 0.12 s 만에 모이지만 지연이 0.2 s를 넘으면 진동하며 발산한다. 이득 $\kappa$를 낮추면 지연 한계가 늘지만 같은 비율로 느려진다. 이득을 이웃 수로 나누는 정규화 규칙은 $\lambda_N$을 2 이하로 묶어 지연 내성을 얻는 대신 속도를 내준다. 합의의 속도와 지연 내성은 같은 고윳값으로 맞바뀐다.
7.9.5 통신 제약 — 대역·지연·손실·분할
통신은 네 가지 방식으로 협조를 깎는다.
| 제약 | 원인 | 협조에 주는 영향 | 이어지는 장 |
|---|---|---|---|
| 대역(채널 부하) | 대수 × 방송 주기 × 패킷 크기 | 경쟁 방송의 충돌, 갱신 주기를 낮추게 만든다 | 3.10.9 |
| 지연 | 접속 대기, 다중 홉, 재전송 | 합의의 지연 한계, 낡은 이웃 위치 | 3.10.7·3.10.6.3 |
| 패킷 손실 | 충돌과 근접 기체의 대역 내 간섭, 페이딩, 기체 몸체의 가림 | 수렴이 늦어지고 합의값이 평균에서 벗어난다 | 3.4.3.3 |
| 망 분할 | 거리, 지형, 중계 기체 상실 | $\lambda_2=0$ — 분할된 무리끼리는 합의가 불가능하다 | 3.10.6·3.16.6 |
채널 부하는 대수에 비례한다. 3.10.9와 같은 가정(상태 80 B를 초당 10번, 1 Mbit/s 한 채널, 모두가 서로 듣는 순수 ALOHA)에서 제공 부하는 $G=0.0064N$이고 충돌하지 않을 확률은 $e^{-2G}$다. 손실률은 4대 5.0 %, 16대 18.5 %, 32대 33.6 %, 64대 55.9 %, 128대 80.6 %다.
| 위상(16대) | 손실 0 | 손실 18.5 %(16대) | 손실 55.9 %(64대 상당) | 합의값의 치우침(55.9 %) |
|---|---|---|---|---|
| 링 | 60.4회(6.0 s) | 77.9회(7.8 s) | 150.0회(15.0 s) | 4.2 % |
| 격자 4×4 | 27.6회(2.8 s) | 35.0회(3.5 s) | 67.8회(6.8 s) | 3.2 % |
| 완전 그래프 | 1.0회(0.1 s) | 3.8회(0.4 s) | 9.3회(0.9 s) | 1.8 % |
(괄호 안은 10 Hz 방송의 시간, 치우침은 처음 불일치에 대한 RMS 비율이다.) 손실은 두 가지를 한다. 수렴을 늦추고, 주고받음이 비대칭이 되어 합의값을 처음 평균에서 이탈시킨다. 바람 추정의 평균처럼 값 자체가 중요한 합의에서는 이 치우침이 오차가 된다. 받았다는 확인을 주고받는 대칭 갱신이나 합을 따로 나르는 방식(push-sum)이 이를 줄인다 (방식별 성능은 문헌 확인 필요).
안전에는 평균이 아니라 공백의 꼬리가 중요하다. 방송 주기 $T$, 손실률 $p$에서 정보의 평균 공백은 $T/(1-p)$이고, 공백이 $kT$를 넘을 확률은 $p^k$다.
| 방송 | 손실 | 평균 공백 | 공백 > 1 s의 확률 | 공백 > 2 s의 확률 |
|---|---|---|---|---|
| 10 Hz | 0 | 0.10 s | 0 | 0 |
| 10 Hz | 55.9 % | 0.23 s | $3.0\times10^{-3}$ | $8.9\times10^{-6}$ |
| 2 Hz | 55.9 % | 1.13 s | 0.31 | 0.098 |
| 1 Hz | 0 | 1.00 s | 0 | 0 |
2 Hz에 손실 55.9 %는 평균 공백이 1 Hz와 비슷하지만, 열 번에 한 번은 2 s 넘게 이웃을 보지 못한다. 다음 절의 충돌 회피 결과가 이 차이를 그대로 보여 준다. 공대공 채널에서는 기체 몸체와 로터가 가장 큰 가림이고 상대 속도가 도플러를 정한다(3.4.3.3). 손실은 독립이 아니라 몰려서 오는 경우가 많아 이 표보다 꼬리가 길다.
7.9.6 대형 유지와 충돌 회피
Reynolds의 세 규칙(Reynolds, 1987)은 새 떼의 움직임을 이웃만 보는 세 규칙으로 흉내 냈다. ① 분리 — 너무 가까운 이웃에서 멀어진다. ② 정렬 — 이웃의 평균 속도에 맞춘다. ③ 응집 — 이웃의 중심으로 다가간다. 무인기 군집은 여기에 목표 추종(가야 할 곳)을 더한다. 실제 드론 무리에 이 계열을 적용해 30대 규모를 실외에서 날린 연구가 있다(Vásárhelyi 외, 2018).
다른 방법도 같은 틀 위에 있다.
- 인공 퍼텐셜 — 목표는 인력으로, 장애물과 이웃은 척력으로 작용하는 힘의 합(Khatib, 1986). 단순하지만 힘이 상쇄되는 국소 최소점에서 멈출 수 있다.
- 대형 오프셋 합의 — 각 기체가 정해진 상대 위치 $r_i$를 두고 $x_i-r_i$에 대해 합의하면 대형이 유지된다. 7.9.4의 수렴·지연 결론이 그대로 적용된다.
- 속도 장애물과 ORCA — 상대 속도가 충돌 원뿔 밖에 있도록 속도를 고른다(2.14.9.3). 서로 절반씩 피하는 상호 속도 장애물(ORCA, van den Berg 외)은 다수 기체로 확장된다.
이 규칙들은 모두 이웃의 위치와 속도가 맞다는 가정 위에 있다. 그 가정이 깨지는 크기를 원 교환 시험으로 보았다. 반지름 20 m 원 위의 16대가 동시에 맞은편 점으로 가므로 모두 가운데를 지난다. 기체는 최대 3 m/s, 가속 3 m/s², 분리 반지름 5 m다. 이웃 정보는 방송으로만 받고, 받은 위치를 받은 속도로 외삽한다. 항법 오차는 기체마다 일정한 바이어스로 넣었다(기준은 RTK 고정해 수준의 한 축 2 cm, 2.7.8.1). 두 기체의 상대 오차는 바이어스의 $\sqrt2$배다.
| 경우(200회) | 최소 간격 5 % 값 | 중앙값 | 1 m 미만 | 0.5 m 미만 | 완료 시각(중앙) |
|---|---|---|---|---|---|
| 기준: 10 Hz, 손실 0, 2 cm | 1.25 m | 1.54 m | 0.5 % | 0 % | 44.9 s |
| 10 Hz, 손실 55.9 % | 1.21 m | 1.54 m | 0 % | 0 % | 45.0 s |
| 2 Hz, 손실 0 | 1.19 m | 1.54 m | 1.5 % | 0 % | 45.0 s |
| 1 Hz, 손실 0 | 0.88 m | 1.38 m | 6.5 % | 0 % | 45.6 s |
| 2 Hz, 손실 55.9 % | 0.09 m | 0.79 m | 68.0 % | 28.0 % | 42.0 s |
| 1 Hz, 손실 55.9 % | 0.04 m | 0.28 m | 98.5 % | 76.0 % | 41.0 s |
| 10 Hz, 위치 바이어스 σ 0.5 m | 0.66 m | 1.38 m | 16.0 % | 2.5 % | 41.1 s |
| 10 Hz, 위치 바이어스 σ 1.5 m | 0.01 m | 0.08 m | 100 % | 99.0 % | 39.4 s |
| 정렬 규칙 없음(10 Hz, 2 cm) | 0.42 m | 1.04 m | 43.0 % | 6.0 % | 35.9 s |
읽을 것 넷. ① 10 Hz에서는 손실 55.9 %도 견딘다. 외삽이 0.23 s의 평균 공백을 메운다. ② 주기와 손실이 동시에 발생하면 절벽이 있다. 2 Hz나 손실 55.9 % 하나는 견디지만 둘이 동시에 발생하면 시행의 68 %가 1 m 안으로 들어온다. 앞 절의 "공백이 2 s를 넘을 확률 0.098"이 그 원인이다. ③ 위치 오차는 통신보다 무섭다. 상대 오차가 평형 간격(약 1.5 m)과 같은 크기가 되면 통신이 완벽해도 붕괴한다(바이어스 1.5 m). 단독 GNSS의 절대 오차는 수 m이지만 가까운 수신기끼리는 공통 오차가 지워져 상대 오차가 더 작다. 그래도 바이어스 0.5 m 가정에서 16 %가 1 m 안으로 들어왔다. 드론 쇼가 RTK를 사용하는 이유다. ④ 정렬은 간격을 사고 시간을 판다. 정렬을 빼면 9 s 빨리 끝나지만 43 %가 1 m 안으로 들어온다. 이웃과 속도를 맞추면 상대 속도가 줄기 때문이다.
이 모형은 2차원 점 질량이고, 바람·하강풍·기체 크기·제어 지연을 넣지 않았다. 숫자보다 경향(공백의 꼬리, 위치 오차와 간격의 비)을 읽는다.
7.9.7 작업 할당 — 경매와 합의 기반 할당
$N$대에 과제 $N$개(점검 지점, 탐색 칸, 방제 구획)를 하나씩 맡기는 문제는 할당 문제다. 이동 거리의 합을 비용으로 두면 중앙에서는 헝가리안 방법이 $O(N^3)$에 최적을 준다(Kuhn, 1955). 분산에서는 기체들이 과제에 값을 매겨 입찰하는 경매 방식을 사용한다.
- 경매 알고리즘(Bertsekas, 1988) — 가격을 올려 가며 최적에 가까운 할당에 수렴한다.
- 순차 탐욕 경매 — 남은 짝 가운데 가장 싼 것부터 낙찰한다. 단순하고 빠르다.
- 합의 기반 경매(CBBA, Choi·Brunet·How, 2009) — 기체마다 과제 묶음을 입찰하고, 누가 무엇을 낙찰했는지에 대해 이웃과 합의한다. 통신 위상이 이어져 있으면 충돌 없는 할당에 이른다.
과제를 1 km 정사각형 안에 무작위로 두고 500회 비교했다.
| 대수 = 과제 수 | 탐욕 경매 ÷ 최적(총거리) | 95 % 값 | 탐욕 경매 ÷ 최적(가장 먼 한 대) | 협조 없음 — 커버한 과제 |
|---|---|---|---|---|
| 4 | 1.063 | 1.282 | 1.23 | 63.1 % |
| 8 | 1.095 | 1.237 | 1.41 | 60.1 % |
| 16 | 1.139 | 1.274 | 1.71 | 58.6 % |
| 32 | 1.172 | 1.278 | 2.06 | 58.5 % |
협조가 없으면 과제의 약 40 %가 버려진다. 각자 가장 가까운 과제로 가면 여러 대가 같은 과제로 몰리기 때문이다. 탐욕 경매는 총거리로는 최적의 6~17 % 안에 들지만, 가장 늦게 끝나는 기체의 거리는 총거리 최적 할당보다 1.2~2.1배 길다. 마지막에 남은 먼 짝을 억지로 맺기 때문이다. 임무 시간이 가장 늦은 기체로 정해지는 수색에서는 총거리보다 최장 거리를 줄이는 기준이 맞다.
통신이 할당을 정한다. 순차 경매는 낙찰 한 건마다 모두가 결과를 알아야 하므로, 지름 $D$홉의 망에서 한 차례에 $D$번의 전달이 필요하다. 4×4 격자의 지름은 6홉이고 10 Hz 방송이면 한 차례가 약 0.6 s다. 몇 분짜리 임무의 재할당에는 충분하다. 망이 분할되면 두 무리가 같은 과제를 각자 낙찰할 수 있어, 다시 이어질 때 충돌을 푸는 규칙(시각 표시, 우선순위)이 필요하다.
7.9.8 커버리지·탐색 분담과 통신 중계
탐색 분담은 할당의 연속판이다. 구역을 칸으로 나눠 기체마다 맡기고, 각 칸을 왕복 경로로 커버한다. 고전 탐색 이론(6.12.10)에서 기체 $N$대가 면적 $A$를 적용 계수 1로 커버하는 시간은 $A/(NWv)$다($W$ 탐색 폭, $v$ 속도). 대수를 늘리면 시간이 $1/N$로 줄지만 이륙점에서 칸까지의 이동과 칸 경계의 중복은 줄지 않는다. 경로 계획 자체는 7.2이 다룬다.
구역을 나누는 방법은 셋이다. ① 사전 분할 — 계획 단계에서 같은 넓이의 칸으로 나눈다. 단순하고 검증이 쉽지만 한 대가 빠지면 그 칸이 빈다. ② 보로노이 분할(Lloyd 반복, Cortés 외, 2004) — 각 기체가 자기에게 가장 가까운 영역을 맡고, 영역의 무게중심으로 움직이기를 반복한다. 기체가 빠지면 이웃이 자연히 영역을 넓힌다. ③ 동적 경매 — 남은 칸을 주기적으로 다시 입찰한다(7.9.7).
통신 중계는 군집의 한 역할이다. 지상국 가시선 밖으로 나간 기체를 위해 한 대가 높이 떠서 중계한다(3.16.6). 중계는 도달을 늘리지만 처리량을 홉 수로 나누고 단일 고장점이 된다(3.10.6.3). 탐색 대수 가운데 몇 대를 중계에 돌릴지는 커버하는 속도와 연결의 교환이다. 이동하면서도 연결을 유지하려면 $\lambda_2>0$을 제약으로 두는 연결 유지 제어가 사용된다 (구체 방법은 문헌 확인 필요).
7.9.9 중앙 집중 대 분산 — 결정의 시간 척도
군집 설계의 첫 질문은 "중앙인가 분산인가"가 아니다. 결정마다 필요한 반응 시간과 통신이 주는 시간을 비교하는 것이다.
| 결정 | 필요한 반응 시간 | 통신이 주는 시간 | 어울리는 곳 |
|---|---|---|---|
| 근접 충돌 회피 | 0.1~1 s(간격 1.5 m, 상대 속도 수 m/s) | 방송 공백의 꼬리 수 s | 기체 각자(국지 규칙, 2.14) |
| 대형 유지 | 1~10 s | 이웃 합의 수 s | 이웃 사이 분산 |
| 과제 재할당 | 10 s~분 | 경매 한 차례 약 0.6 s | 분산 경매 또는 중앙 |
| 임무 계획·궤적 | 분~시간(비행 전) | 제약 없음 | 중앙(최적화·검증) |
| 비상(복귀·착륙) | 수 s | 링크 상실 가능 | 기체 각자의 사전 절차(2.6.6) |
빠른 안전은 각자, 느린 최적화는 중앙에 두는 것이 혼합 구조의 원칙이다. 드론 쇼는 이 원칙의 극단이다. 거의 모든 결정을 비행 전에 중앙에서 끝내고, 비행 중에는 각 기체가 자기 궤적을 따르며 이상이 있으면 정해진 비상 절차로 빠진다.
7.9.10 드론 쇼의 실제 — 중앙 계획과 정밀 위치
공연용 드론 쇼는 군집 기술이 대중 앞에 나온 대표 사례다(0.4.6, 응용 산업은 14.5). 공개된 구조는 다음과 같다.
- 중앙 설계. 애니메이션 도구로 장면(대형)을 만들고, 장면 사이의 전환에서 기체마다 목표점을 할당한다. 이 할당이 7.9.7의 할당 문제이고, 경로가 서로 가깝게 지나지 않도록 최소 간격과 속도·가속 한계를 비행 전에 검사한다.
- 궤적 업로드. 기체마다 시각이 붙은 자기 궤적과 조명 명령을 비행 전에 받는다. 비행 중 기체끼리 협조할 필요가 거의 없다.
- 정밀 위치와 시각 동기. 위치는 RTK로 cm급을 얻는다. 제조사 문서는 고정해에서 1~2 cm를 말하지만 보정이 cm급을 보장하지는 않는다고 함께 적는다
(공개 주장치, Verge Aero 문서). 시각은 GNSS 시각으로 맞춘다. - 지상 감시와 중단. 지상국은 모든 기체의 상태를 보고, 이상 기체를 착륙시키거나 공연 전체를 멈춘다. 기체마다 지오펜스와 비상 착륙 절차가 있다(2.6).
규모의 기록은 빠르게 바뀐다. 2018년 평창 동계올림픽 개회식의 1,218대 장면(사전 촬영 영상으로 알려져 있다, 0.4.6)이 상징적 기록이었다. 2025년 10월 중국 류양(瀏陽)의 공연은 컴퓨터 한 대가 동시에 띄운 15,947대로 기네스 기록에 올랐다고 보도되었다 (공개 주장치, 언론 보도 — 2차). 이 기록이 "컴퓨터 한 대"로 정의된다는 점이 구조를 말해 준다. 수만 대 규모의 쇼는 분산 협조가 아니라 중앙 계획과 정밀 위치의 산물이다.
대수가 커지면 드문 고장이 매번 일어난다. 기체 한 대가 한 공연에서 고장 날 확률이 $q$이면 $N$대 가운데 적어도 한 대가 고장 날 확률은 $1-(1-q)^N$이다. $q=10^{-3}$, $N=1{,}000$이면 0.63이다. 그래서 쇼의 안전은 "고장이 없음"이 아니라 고장 난 기체가 관객 쪽 경계를 넘지 않음으로 설계한다. 이 확률을 시험으로 입증하는 문제는 7.10가 다룬다.
7.9.11 수치 예시·워크스루 — 16대가 4 km²를 나눠 수색한다
과제. 지진 뒤 2 km × 2 km 구역에서 실종자를 찾는다. 2 kg 쿼드콥터(1.7.7)를 고도 60 m, 10 m/s로 날린다. 탐색 폭은 6.12.10의 83.6 m(0.5 m 대상, $N_{50}$ 8화소 가정)다. 이륙점은 구역 한가운데다. 모든 값은 교육용 가정이다.
| 단계 | 계산 | 결과 |
|---|---|---|
| ① 한 대로는 | $4\times10^6/(83.6\times10)$ | 4,785 s = 79.7분 — 체공 18.1분(2.9.8)의 네 배가 넘는다 |
| ② 16대 분할 | 500 m 정사각형 16칸, 칸마다 $0.25\times10^6/836$ | 칸 탐색 5.0분 |
| ③ 이동 | 가장 먼 칸 중심 1,061 m, 왕복 | 3.5분 — 합 8.5분으로 체공 안 |
| ④ 할당 | 사전 분할로 시작, 이상 시 경매(7.9.7) | 4×4 격자 망에서 경매 한 차례 약 0.6 s |
| ⑤ 상태 방송 | 16대 × 10 Hz × 80 B, 한 채널 경쟁 방송 | 손실 18.5 % — 10 Hz 외삽으로 근접 분리 유지(7.9.6) |
| ⑥ C2 | 3.10.10의 TDMA 구성 | 최악 지연 32.6 ms, 50대까지 여유 |
| ⑦ 임무 데이터 | 후보 영상 조각 128 kbit/s × 16(3.12.9의 가정) | 2.05 Mbit/s — 영상 채널의 일부 |
| ⑧ 한 대 상실 | 칸 절반(150 s 분량)을 이웃 넷이 나눔 | 이웃마다 37 s 추가 |
읽을 것 셋. 첫째, 이 임무의 협조는 대부분 비행 전의 분할로 끝난다. 비행 중 협조가 필요한 것은 이동 구간의 근접 분리와 상실 기체의 재할당뿐이다. 둘째, 16대는 경쟁 방송으로도 견디지만 64대로 늘리면 손실이 55.9 %가 되어 방송 주기를 낮출 여유가 사라진다. 그때는 슬롯 배정(3.10.5)이나 이웃 수 제한이 필요하다. 셋째, 후보 영상을 보는 사람은 한 명이나 두 명이다. 16대가 보내는 후보와 경보를 사람이 감당하는지가 이 임무의 실제 병목이다(7.11). 가림·기저율·구역 배분의 효과는 6.12.11과 같다.
7.9.12 설계 트레이드오프
① 중앙 계획형. 지상에서 모든 궤적과 할당을 최적화하고 기체는 따른다. 최적에 가깝고 비행 전에 검증할 수 있다. 대가는 중앙과 링크의 단일 고장점, 그리고 계획에 없던 일(바람, 고장, 새 정보)에 약하다는 점이다.
② 완전 분산형. 기체마다 이웃 정보로 같은 규칙을 따른다. 일부가 빠져도 계속하고 대수에 따라 늘어난다. 대가는 최적이 아니고, 창발 행동을 미리 증명하기 어렵다는 점이다(7.10).
③ 혼합형. 계획과 할당은 중앙이나 느린 합의로, 근접 분리와 비상은 기체 각자의 국지 규칙으로 둔다. 두 층의 경계(중앙 계획이 국지 회피와 충돌하는 경우)를 설계해야 한다.
견해: 민간 협동 임무의 기본은 ③이고, 그 안에서 안전 기능은 가장 단순한 국지 규칙으로 두는 편이 낫다고 본다. 근거는 셋이다. 첫째, 7.9.6에서 근접 분리를 깨뜨린 것은 몇 초의 정보 공백과 위치 오차였다. 이 시간 척도는 어떤 중앙 계산도 링크 너머에서 대신할 수 없다. 둘째, 할당처럼 느린 결정은 7.9.7의 수치대로 분산으로도 총거리 최적의 6~17 % 안에 들고, 중앙이 살아 있으면 최적을 사용하면 된다. 셋째, 안전 기능이 단순할수록 런타임 보증(7.8)으로 감싸고 시험으로 입증하기 쉽다(7.10). 반대로 드론 쇼처럼 공간과 시간이 완전히 통제된 공연은 ①이 가장 단순하고 승인받기 쉽다.
7.9.13 세 축 비교
| 항목 | 군용 드론 | 민간 UAS | AAM |
|---|---|---|---|
| 협조의 목적 | 넓은 구역의 감시·중계 같은 운용 개념(10.10) | 쇼·매핑·수색·방제·중계 | 회랑·버티포트에서 다수 기체의 분리와 순서 |
| 주 구조 | 통신 단절을 전제로 한 분산·혼합 | 중앙 계획 + 국지 분리 | 중앙(운항 관리·USS)의 전략 조정 + 기체의 DAA |
| 통신 가정 | 끊기고 방해받는 링크(5.8) | 면허 불요 대역의 경쟁 방송, 셀룰러 | 인증된 C2·지상 인프라(15.15) |
| 위치 정밀 | GNSS 거부에 대비한 대체 항법(4.13) | RTK(쇼·측량) | 인증 항법·감시 |
| 사람의 위치 | 의미 있는 인간 통제(19.3) | 한 사람이 여러 대(7.11·14.16) | 원격 감독자 한 명이 여러 대(7.11·15.23) |
| 보증의 쟁점 | 창발 행동과 통제 유지 | 경계 이탈 확률 | 분리 보증과 인증(17.13) |
7.9.14 관련 규격·프로토콜
군집 알고리즘 자체를 정하는 표준은 확인하지 못했다. 군집은 기존 통신·항법·교통 정보 규격 위에서 동작한다.
| 문서 | 발행 | 무엇을 정하나 | 상세 |
|---|---|---|---|
| MAVLink 2 | 공개 프로젝트 | 기체·지상국 메시지. 시스템 ID가 1바이트라 한 망의 식별 수에 한계가 있다 | 9.5 |
| ROS 2·DDS | OSRF·OMG | 기체 간 발행·구독 미들웨어 | 9.6 |
| OLSRv2(RFC 7181), IEEE 802.11s | IETF·IEEE | MANET 라우팅·와이파이 메시 | 3.10 |
| STANAG 4586 | NATO | 하나의 통제소가 여러 체계를 다루는 상호운용 구조 | 9.7 |
| ASTM F3548-21 | ASTM | UTM 서비스 제공자 간 전략적 조정(운용 의도 교환) | 9.14 |
| ASTM F3411(Remote ID) | ASTM | 기체마다의 원격 식별 메시지 (판 확인 필요) | 9.12 |
| IEEE 1516(HLA) | IEEE | 대규모 분산 시뮬레이션 — 군집 시험(7.10) | 9.21 |
7.9.15 관련 규제·인증 요구와의 연결
| 대상 | 요구 | 이 장과의 연결 | 상세 |
|---|---|---|---|
| 한 사람이 여러 대 운용(미국) | 14 CFR 107.35는 한 사람이 동시에 둘 이상의 무인기 운용에서 조종하거나 원격조종 책임자·육안 감시자 역할을 하는 것을 금지하고, 107.205에 따라 면제(waiver) 대상이다. FAA는 드론 쇼 같은 "군집" 운용이 107.35 면제로 허가되어 왔다고 밝혔다 | 드론 쇼·협동 운용(7.9.10) | 17.5·7.10 |
| BVLOS 신규칙안(미국) | 2025년 8월 Part 108 규칙안은 기체 대 비행 조정자(flight coordinator) 비율을 1:1로 두고, FAA가 인정한 방법으로만, 제조사 운용 지침의 비율 안에서 늘리게 했다. 최종 규칙은 이 장의 기준 시점에 확인하지 못했다 (확인 필요) | 1:N 협동 운용 | 17.6·7.11 |
| EU·한국 | 특정 범주의 운용 위험 평가와 승인으로 다루는 것으로 이해되나, 한 원격조종사의 다수 기체 운용을 직접 정한 조항은 확인하지 못했다 (확인 필요) | 다수 기체의 위험 평가 | 17.17·18.6 |
| 주파수 | 면허 불요 대역의 공유와 출력 제한, 면허 대역의 할당 | 채널 부하(7.9.5) | 17.19·18.16 |
| 운용 위험 평가 | 다수 기체의 지상·공중 위험, 봉쇄(경계 이탈 방지) | 대수와 고장 확률(7.9.10) | 17.17·7.10 |
| 군 체계 | 자율 기능의 통제와 무기 검토 | 이 장의 범위 밖 | 10.10·19.3·19.5 |
7.9.16 함정과 한계
| 오해 | 실제 | 더 볼 곳 |
|---|---|---|
| "드론 쇼는 자율 군집이다" | 중앙에서 계산한 궤적을 RTK로 따라가는 자동 비행이다 | 7.9.10·0.2.6 |
| "모두가 모두와 통신하면 가장 좋다" | 가장 빠르지만 채널 부하와 지연 민감도가 가장 크다 | 7.9.3·7.9.4 |
| "패킷 손실률이 같으면 위험도 같다" | 공백의 꼬리(주기 × 연속 손실)가 근접 분리를 정한다 | 7.9.5·7.9.6 |
| "통신만 좋으면 간격이 유지된다" | 상대 위치 오차가 간격과 같은 크기면 통신이 완벽해도 붕괴한다 | 7.9.6 |
| "분산이면 고장에 강하다" | 망이 분할되면 합의가 불가능하고, 중계 기체가 단일 고장점이 된다 | 7.9.5·7.9.8 |
| "대수를 늘리면 시간이 $1/N$로 준다" | 이동·중복·통신·사람의 검토는 줄지 않는다 | 7.9.11 |
이 장의 한계도 밝혀 둔다.
- 모형은 2차원 점 질량과 이상화한 채널이다. 하강풍, 기체 크기, 제어 지연, 몰려오는 손실, 고도 분리를 넣지 않았다.
- 손실은 링크마다 독립으로 두었다. 실제 무선의 손실은 시간과 공간에서 상관되어 꼬리가 더 길다.
- 할당 비교는 거리 비용 하나다. 체공·탑재·시간 창 제약은 넣지 않았다.
- 창발 행동의 검증, 고장 주입, 대수에 따른 확장성은 7.10가 이 모형을 불러 이어서 다룬다.
7.9.17 체크포인트·연구 질문
체크포인트
- 링 16대와 64대의 $\lambda_2$를 식으로 구하고, 합의 시간이 몇 배 느려지는지 말하라.
- $\kappa=0.5$ 1/s의 완전 그래프 16대에서 링크 지연이 0.3 s이면 합의는 어떻게 되는가?
- 32대가 80 B 상태를 초당 10번 1 Mbit/s 한 채널에 경쟁 방송하면 손실률은 얼마인가?
- 2 Hz 방송, 손실 55.9 %에서 이웃을 2 s 넘게 보지 못할 확률을 구하라.
- 협조 없이 각자 가장 가까운 과제를 고르면 왜 과제의 약 40 %가 버려지는가?
- 드론 쇼 1,000대에서 기체당 고장 확률이 $10^{-4}$이면 공연마다 적어도 한 대가 고장 날 확률은?
연구 질문 — 이 장에서 파생되는 열린 주제(25.7에 모은다)
- 손실·지연 아래의 합의 보증 — 상관된 패킷 손실과 변하는 지연에서 합의의 수렴 시간과 치우침을 확률로 보장하는 설계는 무엇인가(7.10)?
- 근접 분리의 정보 요구 — 간격·속도·위치 오차가 주어졌을 때 방송 주기와 허용 손실의 경계를 해석적으로 구할 수 있는가?
- 중앙 계획과 국지 회피의 경계 — 드론 쇼의 계획 궤적에 국지 회피를 더할 때, 회피가 계획을 깨뜨리지 않음을 어떻게 보이는가(7.8)?
- 수색 군집의 사람 병목 — 대수를 늘릴 때 후보 검토와 경보가 사람의 능력을 넘는 지점을 함께 최적화할 수 있는가(7.11)?
1차 출처(이 장)
- Reynolds, C. W., "Flocks, Herds, and Schools: A Distributed Behavioral Model," Computer Graphics(SIGGRAPH '87) 21(4), 1987.
- Fiedler, M., "Algebraic connectivity of graphs," Czechoslovak Mathematical Journal 23, 1973.
- Olfati-Saber, R.; Murray, R. M., "Consensus Problems in Networks of Agents With Switching Topology and Time-Delays," IEEE Transactions on Automatic Control 49(9), 2004.
- Khatib, O., "Real-Time Obstacle Avoidance for Manipulators and Mobile Robots," International Journal of Robotics Research 5(1), 1986.
- van den Berg, J. et al., "Reciprocal n-Body Collision Avoidance," Robotics Research(ISRR 2009), Springer, 2011.
- Vásárhelyi, G. et al., "Optimized flocking of autonomous drones in confined environments," Science Robotics 3(20), 2018.
- Kuhn, H. W., "The Hungarian method for the assignment problem," Naval Research Logistics Quarterly 2, 1955.
- Bertsekas, D. P., "The auction algorithm: A distributed relaxation method for the assignment problem," Annals of Operations Research 14, 1988.
- Choi, H.-L.; Brunet, L.; How, J. P., "Consensus-Based Decentralized Auctions for Robust Task Allocation," IEEE Transactions on Robotics 25(4), 2009.
- Cortés, J. et al., "Coverage control for mobile sensing networks," IEEE Transactions on Robotics and Automation 20(2), 2004.
- 14 CFR 107.35·107.205, 그리고 FAA·TSA, "Normalizing Unmanned Aircraft Systems Beyond Visual Line of Sight Operations"(규칙안), 90 FR 38212, 2025-08-07.
출처를 찾고 판을 추적하는 방법은 0.9에서 다룬다.
다음 장: 7.10에서는 이 장의 알고리즘을 어떻게 시험하고 보증하는가를 다룬다. 군집의 행동은 기체 하나하나의 규칙에서 창발하므로 몇 번의 비행시험으로는 드문 실패를 볼 수 없다. 그 장은 이 장의 모형을 불러 대수를 늘리는 실험과 고장 주입을 하고, 드문 사건의 확률을 시뮬레이션으로 입증하려면 몇 번을 돌려야 하는지를 계산한다.