397.63 통신 커버리지 제약 하의 연결성 보장형 임무 계획

1. 개요

자율 로봇 시스템이 원격 운용되거나 다중 로봇 간 협력을 수행하는 환경에서는, 기지국(base station) 또는 다른 로봇과의 **통신 연결성(communication connectivity)**이 임무 수행의 전제 조건이 된다. 통신 범위의 물리적 한계, 지형에 의한 전파 차폐, 간섭 등의 요인으로 인해 로봇이 임무 영역의 모든 지점에서 통신 연결을 유지할 수 있는 것은 아니다. 따라서 통신 커버리지 제약을 임무 계획에 명시적으로 반영하여, 임무 수행 전 과정에서 통신 연결성을 보장하는 **연결성 보장형 임무 계획(connectivity-constrained mission planning)**이 요구된다.

본 절에서는 통신 커버리지의 수학적 모델링, 연결성 제약이 포함된 임무 계획 문제의 정식화, 그리고 대표적 해법을 체계적으로 다룬다.

2. 통신 커버리지 모델링

2.1 통신 범위 모델

로봇 간 또는 로봇-기지국 간의 통신 채널은 무선 전파의 물리적 특성에 의해 결정된다. 통신 범위 모델의 대표적 유형은 다음과 같다.

디스크 모델(Disk Model): 가장 단순한 모델로, 송수신기 간 거리가 통신 반경 $R_{\text{comm}}$ 이내이면 통신이 가능하고, 초과하면 불가능한 이진(binary) 모델이다.

$\text{connected}(i, j) \iff \|p_i - p_j\| \leq R_{\text{comm}}$

여기서 $p_i, p_j$ 는 로봇 $i$ 와 $j$ 의 위치 벡터이다.

경로 손실 모델(Path Loss Model): 실제 무선 전파 환경을 보다 정밀하게 반영하는 모델이다. 수신 전력 $P_r$ 은 송신 전력 $P_t$ 와 거리 $d$ 의 함수로 다음과 같이 표현된다.

$P_r(d) = P_t - PL(d) = P_t - \left( PL_0 + 10 \alpha \log_{10}\frac{d}{d_0} + X_\sigma \right)$

여기서 $PL_0$ 는 기준 거리 $d_0$ 에서의 경로 손실, $\alpha$ 는 경로 손실 지수, $X_\sigma \sim \mathcal{N}(0, \sigma^2)$ 는 섀도잉(shadowing) 효과를 나타내는 확률 변수이다.

통신 링크의 품질은 수신 신호 대 잡음비(Signal-to-Noise Ratio, SNR)로 평가된다.

$\text{SNR}(d) = \frac{P_r(d)}{N_0 B}$

$N_0$ 는 잡음 전력 스펙트럼 밀도, $B$ 는 채널 대역폭이다. 안정적 통신을 위해서는 $\text{SNR}(d) \geq \text{SNR}_{\min}$ 을 만족해야 한다.

레이트레이싱 모델(Ray Tracing Model): 실내 환경이나 복잡한 도심 환경에서 전파의 반사, 회절, 산란을 정밀하게 시뮬레이션하는 모델이다. 연산 비용이 높지만 통신 가용 영역을 정확히 예측할 수 있다.

2.2 통신 그래프

다중 로봇 시스템의 통신 구조는 통신 그래프(communication graph) $G_{\text{comm}} = (V, E_{\text{comm}})$ 로 모델링된다. 정점 $V$ 는 로봇 및 기지국을 나타내고, 간선 집합 $E_{\text{comm}}$ 은 직접 통신 가능한 쌍을 나타낸다.

$E_{\text{comm}} = \{(i, j) \mid \text{connected}(i, j) = \text{true}\}$

통신 그래프의 **연결성(connectivity)**은 임의의 두 노드 사이에 통신 경로(멀티홉 포함)가 존재하는지 여부로 판정된다. 그래프 이론적으로 이는 그래프 $G_{\text{comm}}$ 가 **연결(connected)**되어 있는지 여부에 해당한다.

2.3 대수적 연결성(Algebraic Connectivity)

커버리지 연결성의 정량적 척도로서 **대수적 연결성(Fiedler value)**이 널리 사용된다. 통신 그래프의 라플라시안 행렬(Laplacian matrix) $L$ 의 두 번째로 작은 고유값 $\lambda_2(L)$ 이 대수적 연결성이다.

$L = D - A$

여기서 $D$ 는 차수 행렬(degree matrix), $A$ 는 인접 행렬(adjacency matrix)이다.

$\lambda_2(L) > 0 \iff G_{\text{comm}} \text{는 연결 그래프}$

$\lambda_2$ 의 값이 클수록 통신 네트워크의 연결 강건성(robustness)이 높으며, 단일 링크 장애에 대한 내성이 증가한다.

3. 연결성 제약 포함 임무 계획 문제

3.1 정적 연결성 제약

가장 엄격한 형태의 연결성 제약은 임무 수행의 모든 시점에서 모든 로봇이 기지국과 (직접 또는 멀티홉으로) 연결되어야 한다는 것이다.

$\lambda_2(L(\mathbf{p}(t))) > 0, \quad \forall t \in [t_0, t_{\text{end}}]$

여기서 $\mathbf{p}(t) = [p_1(t), p_2(t), \ldots, p_n(t)]$ 는 시간 $t$ 에서의 전체 로봇 위치 벡터이다.

이 제약은 로봇의 이동 경로와 위치가 통신 연결성에 직접적으로 영향을 미치므로, 임무 계획과 경로 계획이 결합된 복합 최적화 문제를 유발한다.

3.2 간헐적 연결성 제약

상시 연결이 과도한 제약이 되는 경우, 간헐적 연결성(intermittent connectivity) 제약으로 완화할 수 있다. 이 경우 로봇은 일시적으로 통신 범위를 벗어날 수 있지만, 주기적으로 통신 가능 지점으로 복귀하여 데이터를 전송해야 한다.

$\exists t_k \in [t_{k-1} + T_{\min},\, t_{k-1} + T_{\max}]: \text{connected}(r, \text{base}, t_k), \quad \forall k$

여기서 $T_{\max}$ 는 최대 허용 단절 시간이다.

3.3 통신 성능 보장 제약

연결 여부의 이진 제약을 넘어, 최소 데이터 전송률(throughput) 또는 최대 지연(latency)을 보장하는 서비스 품질(Quality of Service, QoS) 제약으로 확장할 수 있다.

$\text{throughput}(r, \text{base}, t) \geq R_{\min}, \quad \forall t$

Shannon 용량 공식에 의하면, 달성 가능한 최대 전송률은 다음과 같다.

$C = B \log_2(1 + \text{SNR})$

따라서 QoS 제약은 최소 SNR 제약으로 환원된다.

$\text{SNR}(d_{\text{eff}}(t)) \geq 2^{R_{\min}/B} - 1$

4. 연결성 보장형 임무 계획 알고리즘

4.1 통신 제약 포함 최적화 정식화

연결성 보장형 임무 계획 문제는 다음과 같이 정식화된다.

$\begin{aligned} \max_{\sigma, \mathbf{p}(\cdot)} \quad & J(\sigma) = \sum_{i=1}^{n} v_i x_i \\ \text{s.t.} \quad & \lambda_2(L(\mathbf{p}(t))) \geq \lambda_{\min}, \quad \forall t \\ & \|\dot{p}_j(t)\| \leq v_{\max}^{(j)}, \quad \forall j, \forall t \quad \text{(속도 제약)} \\ & \text{에너지 제약} \\ & \text{선후 관계 제약} \end{aligned}$

$\lambda_{\min} > 0$ 은 연결성 마진이다.

4.2 그래프 기반 이산 접근

운용 환경을 이산 그래프 $G_{\text{env}} = (V_{\text{env}}, E_{\text{env}})$ 로 모델링하고, 각 정점에서의 통신 연결성을 사전에 평가하여 통신 가용 정점 집합을 식별하는 방식이다.

통신 가용 경로(Communication-Feasible Path): 경로 $\pi = (v_0, v_1, \ldots, v_K)$ 의 모든 정점에서 기지국과의 통신이 가능한 경로이다.

$\text{connected}(v_k, \text{base}) = \text{true}, \quad \forall k \in \{0, 1, \ldots, K\}$

통신 가용 정점만을 포함하는 부분 그래프 $G_{\text{comm}} \subseteq G_{\text{env}}$ 를 구성하고, 이 부분 그래프 내에서 임무 시퀀싱과 경로 탐색을 수행한다. 이 접근법은 임무 공간을 축소하므로 계산 효율이 높지만, 해의 최적성이 감소할 수 있다.

4.3 릴레이 배치 전략

통신 범위 밖의 임무 지점에 도달하기 위해 릴레이(relay) 로봇을 배치하여 통신 경로를 확장하는 전략이다. $m$ 개의 릴레이 로봇 $\{r_1^{\text{relay}}, r_2^{\text{relay}}, \ldots, r_m^{\text{relay}}\}$ 의 위치를 최적화하여 임무 수행 로봇과 기지국 간의 멀티홉 통신 경로를 구성한다.

릴레이 배치 최적화 문제는 다음과 같이 정식화된다.

$\begin{aligned} \min_{p_1^{\text{relay}}, \ldots, p_m^{\text{relay}}} \quad & m \quad \text{(릴레이 수 최소화)} \\ \text{s.t.} \quad & G_{\text{comm}}(\mathbf{p}_{\text{all}}) \text{가 연결 그래프} \end{aligned}$

스타이너 트리 문제(Steiner Tree Problem)와의 관련성이 있으며, NP-난해이다. 탐욕적 릴레이 배치 알고리즘은 임무 로봇과 기지국 사이의 최장 링크를 반복적으로 분할하여 릴레이를 삽입하는 방식으로 동작한다.

4.4 연결성 유지 포텐셜 필드

연속 공간에서의 연결성 유지를 위해 포텐셜 필드(potential field) 기반 접근법이 활용된다. 각 로봇 쌍 $(i, j) \in E_{\text{comm}}$ 에 대해, 통신 범위의 경계에 가까워질수록 증가하는 반발 포텐셜을 정의한다.

$\phi_{ij}(\|p_i - p_j\|) = \begin{cases} 0 & \text{if } \|p_i - p_j\| \leq R_{\text{safe}} \\ \frac{1}{R_{\text{comm}} - \|p_i - p_j\|} & \text{if } R_{\text{safe}} < \|p_i - p_j\| < R_{\text{comm}} \\ +\infty & \text{if } \|p_i - p_j\| \geq R_{\text{comm}} \end{cases}$

이 포텐셜에 의한 제어 입력은 임무 수행을 위한 목표 지향 제어 입력과 결합되어, 연결성을 유지하면서 임무를 수행하는 경로를 생성한다(Zavlanos & Pappas, 2007).

$u_i = u_i^{\text{task}} + u_i^{\text{conn}} = u_i^{\text{task}} - \sum_{j \in \mathcal{N}_i} \nabla_{p_i} \phi_{ij}$

4.5 센트럴라이즈드 대 디센트럴라이즈드 접근

중앙 집중형(Centralized): 중앙 제어기가 모든 로봇의 위치와 통신 상태를 파악하고, 전체 통신 그래프의 연결성을 보장하는 글로벌 계획을 수립한다. 최적성이 높지만, 중앙 제어기의 단일 장애점(single point of failure) 문제와 통신 오버헤드가 증가한다.

분산형(Decentralized): 각 로봇이 로컬 이웃 정보만을 활용하여 연결성을 자율적으로 유지한다. 확장성이 높고 장애에 강건하지만, 글로벌 최적성을 보장하기 어렵다.

분산형 접근에서의 로컬 연결성 유지 조건은 다음과 같다.

$|\mathcal{N}_i(t)| \geq 1, \quad \forall i, \forall t$

즉, 각 로봇은 최소 하나의 통신 이웃을 항상 유지해야 한다. 더 강건한 조건은 $k$ -연결성( $k$ -connectivity)으로, 최소 $k$ 개의 노드 독립 경로가 존재하도록 보장하는 것이다.

5. 통신 불확실성의 모델링

5.1 확률적 통신 모델

무선 통신의 확률적 특성을 반영하여, 통신 성공 확률을 거리의 함수로 모델링한다.

$\Pr[\text{connected}(i, j)] = \exp\left(-\gamma \cdot \|p_i - p_j\|^2\right)$

$\gamma$ 는 환경 의존적 감쇄 계수이다. 이 확률 모델 하에서의 연결성 보장 제약은 다음과 같다.

$\Pr\left[\lambda_2(L(\mathbf{p}(t))) > 0\right] \geq 1 - \delta, \quad \forall t$

$\delta$ 는 허용 가능한 연결 단절 확률이다.

5.2 환경 변동에 따른 연결성 예측

기상 조건(강우, 안개), 전자기 간섭, 도심 환경의 동적 장애물 등에 의한 통신 품질 변동은 시공간적 확률 필드로 모델링할 수 있다. 이 예측 모델은 임무 계획 단계에서 통신 가용 영역을 비보수적(non-conservative)으로 추정하여 임무 수행 범위를 확장하는 데 활용된다.

6. 산업 응용 사례

6.1 지하 광산 탐사 로봇

지하 광산 환경은 전파 전파 조건이 극히 열악하여, 통신 범위가 심각하게 제한된다. 갱도(tunnel) 구조에 의한 도파관(waveguide) 효과와 교차점에서의 전파 확산을 고려한 통신 모델을 기반으로, 릴레이 로봇의 최적 배치와 탐사 로봇의 연결성 보장형 경로를 계획한다.

6.2 해양 자율 로봇

수중 환경에서는 전자기파 대신 음파(acoustic) 통신이 주로 사용되며, 전송 속도가 극히 낮고 지연이 크다. 따라서 간헐적 연결성 모델이 적합하며, 수면 부상을 통한 위성 통신 기회를 임무 시퀀스에 통합하는 계획이 필요하다.

6.3 재난 현장 다중 드론 운용

재난 현장에서의 통신 인프라 붕괴 상황에서, 드론 네트워크가 자체 메시(mesh) 통신을 구성하여 피해 현황 데이터를 기지국으로 전달한다. 드론 간 통신 연결성을 유지하면서 탐색 영역을 최대화하는 임무 계획이 핵심이다.

7. 참고 문헌

Goldsmith, A. (2005). Wireless Communications. Cambridge University Press.
Hollinger, G. A., & Singh, S. (2012). “Multirobot Coordination with Periodic Connectivity.” Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), 4457–4462.
Zavlanos, M. M., & Pappas, G. J. (2007). “Potential Fields for Maintaining Connectivity of Mobile Networks.” IEEE Transactions on Robotics, 23(4), 812–816.
Zavlanos, M. M., Egerstedt, M. B., & Pappas, G. J. (2011). “Graph-Theoretic Connectivity Control of Mobile Robot Networks.” Proceedings of the IEEE, 99(9), 1525–1540.