397.61 에너지(배터리 SoC) 제약을 포함한 계획 최적화

1. 개요

자율 로봇 시스템의 임무 수행 능력은 탑재된 에너지 저장 장치, 특히 배터리의 충전 상태(State of Charge, SoC)에 의해 근본적으로 제한된다. 배터리 SoC는 로봇이 임무를 수행하는 동안 연속적으로 감소하며, 임무 완료 전 에너지가 고갈되면 임무 실패뿐 아니라 로봇 자체의 손실을 초래할 수 있다. 따라서 에너지 제약을 명시적으로 고려한 임무 계획 최적화는 실용적 자율 시스템 설계에서 필수적인 요소이다.

본 절에서는 배터리 SoC의 수학적 모델링, 에너지 제약이 포함된 최적화 문제의 정식화, 그리고 대표적인 해법 알고리즘을 체계적으로 다룬다.

2. 배터리 에너지 모델링

2.1 충전 상태(SoC)의 정의

배터리의 충전 상태 $\text{SoC}(t)$ 는 시간 $t$ 에서의 잔여 용량을 정격 용량(nominal capacity)에 대한 백분율로 표현한 값이다.

$\text{SoC}(t) = \frac{Q_{\text{remaining}}(t)}{Q_{\text{nominal}}} \times 100\%$

여기서 $Q_{\text{remaining}}(t)$ 는 시간 $t$ 에서의 잔여 전하량 [Ah], $Q_{\text{nominal}}$ 은 정격 전하량이다. SoC의 동적 변화는 **쿨롱 계수법(Coulomb counting)**에 의해 다음과 같이 모델링된다.

$\text{SoC}(t) = \text{SoC}(t_0) - \frac{1}{Q_{\text{nominal}}} \int_{t_0}^{t} I(\tau) \, d\tau$

여기서 $I(\tau)$ 는 시간 $\tau$ 에서의 방전 전류이다. 양의 전류는 방전을, 음의 전류는 충전을 나타낸다.

2.2 에너지 소비 모델

로봇의 에너지 소비는 크게 **이동 에너지(locomotion energy)**와 **페이로드 에너지(payload energy)**로 분류된다.

이동 에너지 모델: 지상 이동 로봇의 경우, 이동 에너지 소비는 속도 $v$ , 질량 $m$ , 경사 $\theta$ , 마찰 계수 $\mu$ 등에 의존한다.

$P_{\text{loco}}(v, \theta) = \left( mg \sin\theta + \mu mg \cos\theta + \frac{1}{2} C_d \rho A v^2 \right) v + P_{\text{idle}}$

여기서 $g$ 는 중력 가속도, $C_d$ 는 항력 계수, $\rho$ 는 공기 밀도, $A$ 는 전면 투영 면적, $P_{\text{idle}}$ 은 유휴 전력이다.

멀티로터 드론의 경우, 호버링 및 비행 에너지 모델은 다음과 같이 표현된다(Stolaroff et al., 2018).

$P_{\text{flight}}(v) = P_{\text{hover}} \left( \frac{1}{2} \sqrt{1 + \frac{v^4}{v_h^4}} + \frac{v^2}{2v_h^2} \right)^{1/2} + \frac{1}{2} C_d \rho A v^3$

여기서 $P_{\text{hover}} = \sqrt{\frac{(mg)^3}{2\rho A_{\text{rotor}}}}$ 는 호버링 전력, $v_h$ 는 유도 속도이다.

페이로드 에너지 모델: 센서 구동, 연산 처리, 통신 등 임무 수행에 필요한 에너지를 포함한다.

$P_{\text{payload}} = P_{\text{sensor}} + P_{\text{compute}} + P_{\text{comm}}$

2.3 총 에너지 소비와 SoC 제약

임무 $\tau_i$ 를 수행하는 데 소요되는 총 에너지 $E_i$ 는 다음과 같이 산출된다.

$E_i = \int_{t_{\text{start}}}^{t_{\text{finish}}} \left[ P_{\text{loco}}(t) + P_{\text{payload}}(t) \right] dt$

임무 시퀀스 $\sigma = (\tau_{\sigma_1}, \tau_{\sigma_2}, \ldots, \tau_{\sigma_n})$ 의 실행 가능 조건은 모든 시점에서 SoC가 안전 한계(safety margin) $\text{SoC}_{\min}$ 이상을 유지해야 한다는 것이다.

$\text{SoC}(t) \geq \text{SoC}_{\min}, \quad \forall t \in [t_0, t_{\text{end}}]$

안전 한계 $\text{SoC}_{\min}$ 은 귀환에 필요한 에너지 여유분, 비상 상황 대응을 위한 예비 에너지, 그리고 배터리 심방전(deep discharge) 방지를 위한 한계를 포함한다.

3. 에너지 제약 포함 문제의 정식화

3.1 에너지 제약 임무 계획 최적화 문제

에너지 제약이 포함된 임무 계획 최적화 문제는 다음과 같이 정식화된다.

$\begin{aligned} \max_{\sigma, \mathbf{v}} \quad & J(\sigma) = \sum_{i=1}^{|\sigma|} v_i \cdot x_i \\ \text{s.t.} \quad & \text{SoC}(t_k) \geq \text{SoC}_{\min}, \quad \forall k \\ & \text{SoC}(t_k) = \text{SoC}(t_{k-1}) - \frac{E_{\sigma_k} + E_{\text{travel}}(l_{\sigma_{k-1}}, l_{\sigma_k})}{E_{\text{batt}}} \\ & x_i \in \{0, 1\}, \quad \forall i \\ & \text{선후 관계 제약} \\ & \text{시간 창(Time Window) 제약} \end{aligned}$

여기서 $v_i$ 는 임무 $\tau_i$ 의 가치, $x_i$ 는 임무 선택 결정 변수(1이면 선택, 0이면 미선택), $E_{\text{travel}}(l_a, l_b)$ 는 위치 $l_a$ 에서 $l_b$ 까지의 이동 에너지, $E_{\text{batt}}$ 는 배터리 총 에너지 용량이다.

이 문제는 에너지 제약이 추가된 **배향 문제(Orienteering Problem, OP)**의 일반화로 볼 수 있으며, NP-난해(NP-hard)이다(Golden et al., 1987).

3.2 귀환 에너지 보장 제약

로봇이 임무 수행 후 기지(base station)로 안전하게 귀환해야 하는 경우, 시퀀스의 임의 시점에서 귀환에 필요한 에너지를 보장해야 한다.

$\text{SoC}(t_k) \geq \text{SoC}_{\min} + \frac{E_{\text{return}}(l_{\sigma_k}, l_{\text{base}})}{E_{\text{batt}}}, \quad \forall k$

$E_{\text{return}}(l, l_{\text{base}})$ 는 현재 위치 $l$ 에서 기지까지의 귀환 에너지이다. 이 제약은 시퀀스의 각 단계에서 동적으로 평가되어야 하며, 잔여 에너지가 귀환 한계에 도달하면 즉시 귀환 절차를 시작한다.

3.3 충전 기회를 포함한 확장 모델

충전 스테이션(charging station)이 운용 환경에 배치된 경우, 임무 시퀀스 중간에 충전 방문을 삽입하여 운용 범위를 확장할 수 있다. 충전 스테이션 집합 $S = \{s_1, s_2, \ldots, s_p\}$ 가 주어진 경우, 확장된 최적화 모델은 다음과 같다.

$\begin{aligned} \max_{\sigma, \mathbf{x}, \mathbf{y}} \quad & \sum_{i=1}^{n} v_i x_i - \lambda \sum_{j=1}^{p} t_{\text{charge},j} y_j \\ \text{s.t.} \quad & \text{SoC 제약 유지} \\ & t_{\text{charge},j} = \frac{\text{SoC}_{\text{target}} - \text{SoC}_{\text{arrive},j}}{r_{\text{charge}}} \cdot y_j \\ & y_j \in \{0, 1\} \end{aligned}$

여기서 $y_j$ 는 충전 스테이션 $s_j$ 방문 여부, $t_{\text{charge},j}$ 는 충전 소요 시간, $r_{\text{charge}}$ 는 충전 속도, $\lambda$ 는 충전 시간에 대한 패널티 계수이다.

4. 해법 알고리즘

4.1 동적 계획법(Dynamic Programming) 기반 접근

에너지 제약이 포함된 임무 시퀀싱 문제를 동적 계획법으로 해결하기 위해, 상태를 $(S, i, e)$ 로 정의한다. 여기서 $S$ 는 이미 수행한 임무의 집합, $i$ 는 마지막으로 수행한 임무, $e$ 는 현재 SoC의 이산화된 값이다.

$V(S, i, e) = \max_{j \notin S} \left\{ V(S \cup \{j\}, j, e - \Delta e_{ij}) + v_j \right\}$

단, 실행 가능 조건 $e - \Delta e_{ij} \geq e_{\min} + e_{\text{return},j}$ 를 만족해야 한다. $\Delta e_{ij}$ 는 임무 $i$ 의 위치에서 임무 $j$ 로 이동하여 $j$ 를 수행하는 데 소요되는 에너지이다.

이 접근법의 시간 복잡도는 $O(2^n \cdot n \cdot E_{\text{levels}})$ 로, 임무 수가 적을 때 최적해를 보장하지만 대규모 문제에는 적용이 어렵다.

4.2 혼합 정수 선형 계획법(MILP) 정식화

에너지 제약 임무 계획 문제는 혼합 정수 선형 계획법(Mixed Integer Linear Programming, MILP)으로 정식화할 수 있다. 결정 변수 $x_{ij} \in \{0, 1\}$ 는 임무 $i$ 다음에 임무 $j$ 를 수행하는지 여부를 나타낸다.

$\begin{aligned} \max \quad & \sum_{i \in T} v_i \sum_{j \in T \cup \{d\}} x_{ij} \\ \text{s.t.} \quad & \sum_{j \in T \cup \{d\}} x_{ij} \leq 1, \quad \forall i \in T \\ & \sum_{i \in T \cup \{o\}} x_{ij} = \sum_{k \in T \cup \{d\}} x_{jk}, \quad \forall j \in T \\ & e_j \leq e_i - \Delta e_{ij} \cdot x_{ij} + M(1 - x_{ij}), \quad \forall i, j \\ & e_i \geq e_{\min} + e_{\text{return},i}, \quad \forall i \\ & x_{ij} \in \{0, 1\} \end{aligned}$

여기서 $o$ 는 출발 기지, $d$ 는 도착 기지, $M$ 은 충분히 큰 상수(Big-M)이다. 이 정식화는 상용 MILP 솔버(Gurobi, CPLEX 등)를 활용하여 풀 수 있으며, 중소 규모 문제에 대해 최적해 또는 최적에 근접한 해를 효과적으로 산출한다.

4.3 메타휴리스틱 기반 접근

대규모 임무 집합에 대해서는 정확해 알고리즘의 계산 비용이 과도하므로, 메타휴리스틱(metaheuristic) 알고리즘이 실용적 대안으로 활용된다.

유전 알고리즘(Genetic Algorithm, GA): 임무 시퀀스를 염색체(chromosome)로 인코딩하고, 교차(crossover), 돌연변이(mutation), 선택(selection) 연산을 통해 진화시킨다. 에너지 제약은 적합도 함수(fitness function)에 패널티항으로 반영하거나, 수리 연산자(repair operator)를 통해 위반 해를 수정한다.

$f(\sigma) = \sum_{i \in \sigma} v_i - \mu \cdot \max\left(0, \text{SoC}_{\min} - \min_{k} \text{SoC}(t_k)\right)$

개미 군집 최적화(Ant Colony Optimization, ACO): 인공 개미가 임무 그래프를 탐색하며, 페로몬(pheromone)과 휴리스틱 정보를 기반으로 임무를 순차적으로 선택한다. 에너지 제약은 선택 가능한 임무 후보를 필터링하는 데 활용된다.

$p_{ij}^k = \frac{[\tau_{ij}]^\alpha \cdot [\eta_{ij}]^\beta \cdot \mathbf{1}[\text{SoC 제약 만족}]}{\sum_{l \in \mathcal{N}_i^k} [\tau_{il}]^\alpha \cdot [\eta_{il}]^\beta \cdot \mathbf{1}[\text{SoC 제약 만족}]}$

여기서 $\tau_{ij}$ 는 페로몬 강도, $\eta_{ij}$ 는 휴리스틱 정보(예: 가치/에너지 비율), $\alpha, \beta$ 는 가중 지수, $\mathcal{N}_i^k$ 는 개미 $k$ 의 현재 위치 $i$ 에서의 선택 가능 임무 집합이다.

시뮬레이티드 어닐링(Simulated Annealing, SA): 현재 시퀀스에 대해 이웃 해(neighbor solution)를 생성하고, 목적 함수의 개선 여부와 온도 파라미터에 따라 수용 여부를 결정한다. 에너지 제약 위반 해의 수용 확률을 낮추어 탐색을 제약 가능 영역으로 유도한다.

5. 불확실성 하의 에너지 인식 계획

5.1 에너지 소비의 확률적 모델링

실제 환경에서의 에너지 소비량은 바람, 지형, 온도, 탑재 중량 변동 등 다양한 불확실성 요인에 의해 확정적으로 예측하기 어렵다. 확률적 에너지 소비 모델은 각 임무의 에너지 소비량 $E_i$ 를 확률 변수로 처리한다.

$E_i \sim \mathcal{N}(\mu_{E_i}, \sigma_{E_i}^2)$

이 경우, SoC 제약의 만족 확률을 보장하는 확률적 제약(chance constraint) 형태로 문제를 정식화한다.

$\Pr\left[\text{SoC}(t_k) \geq \text{SoC}_{\min}\right] \geq 1 - \epsilon, \quad \forall k$

여기서 $\epsilon$ 은 허용 가능한 제약 위반 확률이다.

정규 분포 가정 하에서, 이 확률적 제약은 다음의 결정론적 등가 제약으로 변환할 수 있다.

$\mu_{\text{SoC}}(t_k) - \Phi^{-1}(1-\epsilon) \cdot \sigma_{\text{SoC}}(t_k) \geq \text{SoC}_{\min}$

$\Phi^{-1}$ 은 표준 정규 분포의 역누적 분포 함수이다.

5.2 강건 최적화 접근

확률 분포의 정확한 추정이 어려운 경우, 강건 최적화(robust optimization) 접근법을 채택할 수 있다. 에너지 소비의 불확실성 집합 $\mathcal{U}$ 를 정의하고, 최악의 경우(worst case)에도 제약을 만족하는 해를 구한다.

$\min_{\sigma} \max_{\mathbf{E} \in \mathcal{U}} \text{cost}(\sigma, \mathbf{E}) \quad \text{s.t.} \quad \text{SoC}(t_k, \mathbf{E}) \geq \text{SoC}_{\min}, \quad \forall k, \forall \mathbf{E} \in \mathcal{U}$

타원체(ellipsoidal) 불확실성 집합 $\mathcal{U} = \{\mathbf{E} \mid \|\mathbf{E} - \boldsymbol{\mu}\|_{\Sigma^{-1}} \leq \Omega\}$ 을 사용하면, 강건 대응 문제는 제2차 원뿔 계획법(Second-Order Cone Programming, SOCP)으로 환원될 수 있다(Ben-Tal & Nemirovski, 1999).

6. 재충전 스케줄링과 경로 최적화의 통합

6.1 에너지 인식 순회 문제

충전 기회를 포함한 임무 계획은 **연료 제약 차량 경로 배정 문제(Fuel-Constrained Vehicle Routing Problem, FCVRP)**와 밀접한 관련이 있다. 이 문제는 로봇이 충전 스테이션을 방문하여 에너지를 보충하면서 임무 지점들을 순회하는 최적 경로를 구하는 것이다.

$\begin{aligned} \min \quad & \sum_{(i,j) \in E} d_{ij} x_{ij} \\ \text{s.t.} \quad & e_j \leq e_i - \delta_{ij} x_{ij} + F \cdot z_j, \quad \forall (i,j) \\ & z_j \leq 1, \quad z_j \in \{0, 1\} \quad (j \in S) \\ & e_i \geq e_{\min}, \quad \forall i \end{aligned}$

여기서 $z_j$ 는 충전 스테이션 $j$ 에서의 충전 여부, $F$ 는 충전으로 회복 가능한 최대 에너지량이다.

6.2 적응형 에너지 관리 전략

실시간 SoC 모니터링에 기반한 적응형 에너지 관리 전략은 다음 계층적 구조를 따른다.

전략 계층(Strategic Layer): 임무 계획 단계에서 전체 에너지 예산을 배정하고, 충전 스테이션 방문 계획을 수립한다.
전술 계층(Tactical Layer): 임무 실행 중 실시간 SoC를 모니터링하고, 예상 에너지 소비와의 편차가 임계값을 초과하면 임무 시퀀스를 재조정한다.
작전 계층(Operational Layer): 속도 프로파일 최적화, 고도 조절 등 에너지 효율적 이동 궤적을 실시간으로 생성한다.

이 계층적 접근법은 계획의 최적성과 실행의 적응성을 동시에 확보한다.

7. 성능 평가 지표

에너지 제약 포함 임무 계획의 성능은 다음 지표로 평가된다.

지표	정의	비고
임무 달성률	$\frac{\text{완료된 임무 수}}{\text{계획된 임무 수}} \times 100\%$	에너지 부족으로 인한 미완료 포함
에너지 효율	$\frac{\sum v_i x_i}{\Delta \text{SoC}}$	단위 에너지당 달성 가치
SoC 마진	$\min_k \text{SoC}(t_k) - \text{SoC}_{\min}$	안전 여유의 최솟값
충전 횟수	$\sum y_j$	충전 스테이션 방문 횟수
총 운용 시간	$t_{\text{end}} - t_0$	충전 시간 포함

8. 참고 문헌

Ben-Tal, A., & Nemirovski, A. (1999). “Robust Solutions of Uncertain Linear Programs.” Operations Research Letters, 25(1), 1–13.
Golden, B. L., Levy, L., & Vohra, R. (1987). “The Orienteering Problem.” Naval Research Logistics, 34(3), 307–318.
Stolaroff, J. K., Samaras, C., O’Neill, E. R., Luber, A., Mitchell, A. S., & Ceperley, D. (2018). “Energy Use and Life Cycle Greenhouse Gas Emissions of Drones for Commercial Package Delivery.” Nature Communications, 9, Article 409.
Sundar, K., & Rathinam, S. (2014). “Algorithms for Routing an Unmanned Aerial Vehicle in the Presence of Refueling Depots.” IEEE Transactions on Automation Science and Engineering, 11(1), 287–294.