397.18 자원 제약 조건의 모델링

1. 자원 제약의 개요

자율 로봇 시스템의 임무 계획에서 자원 제약 조건(resource constraint)은 로봇이 보유하거나 소비하는 유한한 자원의 가용량, 소비율, 보충 조건 등에 관한 요구사항을 수학적으로 기술하는 조건이다. 자원 제약은 에너지(배터리), 연료, 탑재 용량(payload), 통신 대역폭, 계산 자원, 소모품 등 다양한 물리적 및 논리적 자원에 대하여 발생하며, 이들의 적절한 모델링은 실행 가능한 임무 계획의 수립에 필수적이다 (Ghallab, Nau, & Traverso, 2004).

자원 제약은 다음의 기본 유형으로 분류된다:

소모성 자원(Consumable Resource): 사용에 따라 감소하며, 보충이 가능하거나 불가능한 자원 (에너지, 연료, 소모품)
재사용 자원(Reusable Resource): 작업 수행 중에만 점유되고, 작업 완료 후 반환되는 자원 (통신 채널, 적재 공간, 도킹 스테이션)
비축적 자원(Non-accumulative Resource): 시간 경과에 따라 축적되지 않으며, 각 시점에서의 가용량이 독립적으로 결정되는 자원 (통신 대역폭, 계산 처리율)

2. 에너지 자원의 수학적 모델링

2.1 배터리 충전 상태 모델

배터리 기반 로봇의 에너지 자원은 충전 상태(State of Charge, SoC) $E(t) \in [0, E_{\max}]$ 로 모델링된다. SoC의 시간적 변화는 에너지 소비율 $P_{\text{consume}}(t)$ 에 의하여 다음과 같이 기술된다:

$\dot{E}(t) = -P_{\text{consume}}(t)$

이산 시간 모델에서는:

$E(k+1) = E(k) - P_{\text{consume}}(k) \cdot \Delta t$

에너지 소비율은 로봇의 행동 모드에 따라 상이하며, 일반적으로 다음의 요소들의 합으로 구성된다:

$P_{\text{consume}}(t) = P_{\text{locomotion}}(t) + P_{\text{payload}}(t) + P_{\text{sensor}}(t) + P_{\text{compute}}(t) + P_{\text{comm}}(t)$

각 항은 이동(locomotion), 탑재물 운반(payload), 센서 운용, 연산(computation), 통신(communication)에 의한 소비 전력이다.

2.2 에너지 가용성 제약

임무 수행 중 에너지가 고갈되지 않아야 하는 경성 제약은 다음과 같이 표현된다:

$E(t) \geq E_{\min}, \quad \forall t \in [t_0, t_f]$

여기서 $E_{\min}$ 은 최소 허용 충전 상태로서, 안전 귀환에 필요한 예비 에너지(reserve energy)를 포함한다. 드론의 경우, 귀환 비행에 필요한 에너지를 항상 확보해야 하므로:

$E(t) \geq E_{\text{return}}(\mathbf{p}(t), \mathbf{p}_{\text{base}}) + E_{\text{margin}}$

여기서 $E_{\text{return}}(\mathbf{p}(t), \mathbf{p}_{\text{base}})$ 는 현재 위치 $\mathbf{p}(t)$ 에서 기지 $\mathbf{p}_{\text{base}}$ 까지의 복귀에 필요한 에너지, $E_{\text{margin}}$ 은 안전 여유이다.

2.3 이동 거리 기반 에너지 모델

비행 로봇의 에너지 소비는 비행 거리와 탑재 중량에 의하여 결정되며, 다음의 근사 모델이 사용된다:

$E_{\text{flight}} = \int_{0}^{T} P(v(t), m(t), \mathbf{w}(t)) \, dt$

여기서 $P$ 는 순간 소비 전력, $v(t)$ 는 대기 속도, $m(t)$ 는 총 질량, $\mathbf{w}(t)$ 는 바람 벡터이다. 호버링(hovering) 상태에서의 전력 소비 $P_{\text{hover}}$ 는 추력-중력 균형 조건으로부터 산출된다:

$P_{\text{hover}} = \frac{(mg)^{3/2}}{\sqrt{2\rho A}}$

여기서 $g$ 는 중력 가속도, $\rho$ 는 공기 밀도, $A$ 는 로터 디스크 면적이다 (Stolaroff et al., 2018).

3. 탑재 용량 제약

3.1 중량 제약

로봇의 탑재물(payload) 중량에 대한 제약은 다음과 같이 표현된다:

$\sum_{j \in \mathcal{J}(t)} w_j \leq W_{\max}, \quad \forall t$

여기서 $\mathcal{J}(t)$ 는 시각 $t$ 에서 로봇이 적재하고 있는 물품의 집합, $w_j$ 는 물품 $j$ 의 중량, $W_{\max}$ 는 최대 적재 용량이다. 물류 로봇의 배송 임무에서, 로봇이 복수의 배송 지점을 순회하면서 물품을 적재 및 하역하는 경우, 각 시점에서의 적재 상태를 추적해야 한다:

$W(k+1) = W(k) + \sum_{j \in \mathcal{J}_{\text{load}}(k)} w_j - \sum_{j \in \mathcal{J}_{\text{unload}}(k)} w_j$

여기서 $\mathcal{J}_{\text{load}}(k)$ 와 $\mathcal{J}_{\text{unload}}(k)$ 는 단계 $k$ 에서 적재 및 하역되는 물품의 집합이다.

3.2 부피 제약

탑재물의 부피에 대한 제약은 다음과 같이 표현된다:

$\sum_{j \in \mathcal{J}(t)} v_j \leq V_{\max}, \quad \forall t$

여기서 $v_j$ 는 물품 $j$ 의 부피, $V_{\max}$ 는 최대 적재 부피이다. 중량과 부피 제약이 동시에 적용되는 경우, 양자를 모두 만족하는 적재 조합을 결정하는 문제는 다차원 배낭 문제(multidimensional knapsack problem)로 환원된다.

4. 재사용 자원의 모델링

4.1 단일 자원 수용 용량 제약

재사용 자원의 수용 용량(capacity) 제약은 동시에 해당 자원을 사용하는 작업의 수가 가용 수량을 초과하지 않아야 함을 명세한다:

$\sum_{i : \tau_i \text{ active at } t} r_i^{(k)} \leq R_k, \quad \forall t, \; \forall k$

여기서 $r_i^{(k)}$ 는 작업 $\tau_i$ 가 자원 $k$ 를 사용하는 양, $R_k$ 는 자원 $k$ 의 총 가용량이다. 이는 자원 제약 프로젝트 스케줄링 문제(Resource-Constrained Project Scheduling Problem, RCPSP)의 핵심 제약에 해당한다 (Brucker et al., 1999).

4.2 도킹 스테이션 제약

충전 또는 물품 교환을 위하여 도킹 스테이션(docking station)을 방문해야 하는 경우, 스테이션의 동시 수용 능력에 대한 제약이 발생한다:

$\sum_{i=1}^{N_{\text{robot}}} \mathbb{1}[\text{robot } i \text{ docked at station } s \text{ at time } t] \leq C_s, \quad \forall s, \; \forall t$

여기서 $C_s$ 는 스테이션 $s$ 의 동시 도킹 수용 능력, $\mathbb{1}[\cdot]$ 은 지시 함수(indicator function)이다.

5. 통신 자원 제약

5.1 대역폭 제약

다중 로봇 시스템에서의 통신 대역폭 제약은 동시에 전송되는 데이터의 총량이 가용 대역폭을 초과하지 않아야 함을 명세한다:

$\sum_{i=1}^{N_{\text{robot}}} b_i(t) \leq B_{\max}, \quad \forall t$

여기서 $b_i(t)$ 는 로봇 $i$ 의 시각 $t$ 에서의 데이터 전송률, $B_{\max}$ 는 총 가용 대역폭이다. 고해상도 영상 전송, 포인트 클라우드 전송 등의 데이터 집약적 임무에서, 대역폭 제약은 동시 전송 로봇 수를 제한하거나 전송 데이터의 압축 수준을 조정하는 계획 결정에 영향을 미친다.

5.2 통신 채널 할당

유한 수의 통신 채널을 다수의 로봇이 공유하는 환경에서, 채널 할당에 대한 배타적 접근 제약은 다음과 같이 표현된다:

$\sum_{i=1}^{N_{\text{robot}}} x_{ic}(t) \leq 1, \quad \forall c \in \mathcal{CH}, \; \forall t$

여기서 $x_{ic}(t) \in \{0, 1\}$ 는 로봇 $i$ 가 시각 $t$ 에서 채널 $c$ 를 사용하는지를 나타내는 이진 변수, $\mathcal{CH}$ 는 통신 채널의 집합이다.

6. 자원 제약 프로젝트 스케줄링

6.1 RCPSP의 정식화

자원 제약 프로젝트 스케줄링 문제(RCPSP)는 자원 제약하에서 임무 완료 시간을 최소화하는 정수 계획 문제로 정식화된다 (Brucker et al., 1999):

$\begin{aligned} \min \quad & C_{\max} \\ \text{subject to} \quad & s_j \geq s_i + p_i, \quad \forall (i, j) \in \mathcal{E} \quad (\text{선후 관계}) \\ & \sum_{i \in \mathcal{A}(t)} r_{ik} \leq R_k, \quad \forall k, \; \forall t \quad (\text{자원 제약}) \\ & C_{\max} \geq s_i + p_i, \quad \forall i \quad (\text{총 소요 시간}) \end{aligned}$

여기서 $s_i$ 는 작업 $i$ 의 시작 시각, $p_i$ 는 처리 시간, $\mathcal{A}(t)$ 는 시각 $t$ 에서 활성화된 작업의 집합, $r_{ik}$ 는 작업 $i$ 의 자원 $k$ 요구량이다.

RCPSP는 NP-hard 문제로 알려져 있으며 (Blazewicz et al., 1983), 정확 해법으로는 분기 한정법(branch and bound), 유전 알고리즘(genetic algorithm), 시뮬레이션 어닐링(simulated annealing) 등의 메타 휴리스틱(metaheuristic)이 활용된다.

6.2 누적 자원 제약

소모성 자원의 경우, 자원의 누적 소비가 총 가용량을 초과하지 않아야 하는 누적 제약(cumulative constraint)이 부과된다:

$\sum_{i=1}^{k} c_i \leq E_0, \quad \forall k = 1, \ldots, n$

여기서 $c_i$ 는 $i$ 번째 작업의 자원 소비량, $E_0$ 는 초기 자원 보유량이다. 충전 또는 보급 기회가 있는 경우, 자원의 증감을 포함한 누적 모델로 확장된다:

$E(k) = E_0 - \sum_{i=1}^{k} c_i + \sum_{j=1}^{k} r_j$

여기서 $r_j$ 는 $j$ 번째 보충 이벤트의 자원 회복량이다.

7. 다중 자원 제약의 통합 모델링

7.1 선형 계획 기반 통합

다중 자원 제약을 선형 계획법(LP)으로 통합하면 다음의 형태를 취한다:

$\begin{aligned} \min_{\mathbf{x}} \quad & \mathbf{c}^\top \mathbf{x} \\ \text{subject to} \quad & A_{\text{time}} \mathbf{x} \leq \mathbf{b}_{\text{time}} \quad (\text{시간 제약}) \\ & A_{\text{resource}} \mathbf{x} \leq \mathbf{b}_{\text{resource}} \quad (\text{자원 제약}) \\ & A_{\text{precedence}} \mathbf{x} \leq \mathbf{b}_{\text{precedence}} \quad (\text{선후 관계}) \\ & \mathbf{x} \geq \mathbf{0} \end{aligned}$

이산적 할당 결정이 포함되는 경우, 혼합 정수 선형 계획법(MILP)으로 확장된다.

7.2 자원 프로파일 분석

자원 프로파일(resource profile)은 시간에 따른 자원의 가용량과 소비량의 변화 양상을 시각화하는 도구이다. 각 시각 $t$ 에서의 자원 사용량 $U_k(t)$ 는 다음과 같이 계산된다:

$U_k(t) = \sum_{i : s_i \leq t < s_i + p_i} r_{ik}$

자원 프로파일 분석을 통하여 자원 병목(bottleneck) 구간을 식별하고, 작업 배치를 조정하여 자원 사용의 평활화(leveling)를 수행할 수 있다 (Neumann, Schwindt, & Zimmermann, 2003).

8. 자율 로봇 임무에서의 자원 제약 사례

8.1 다중 드론 감시 임무

다수의 드론이 넓은 영역을 감시하는 임무에서, 각 드론의 배터리 용량, 비행 속도, 충전 시간 등이 자원 제약으로 작용한다. 임무 계획은 모든 드론의 배터리 잔량이 안전 한계 이하로 떨어지지 않도록 비행 경로와 충전 스케줄을 동시에 최적화해야 한다.

8.2 물류 로봇 배송 임무

물류 로봇의 멀티 픽업 배송 임무에서, 적재 용량(중량 및 부피), 배터리 잔량, 배송 시한이 복합적 자원 제약을 형성한다. 각 배송 경로에서의 누적 적재량이 용량을 초과하지 않으면서, 에너지 소비가 가용 배터리 용량 내에 유지되어야 하며, 동시에 각 배송 지점의 시한을 준수해야 한다.

9. 참고문헌

Blazewicz, J., Lenstra, J. K., & Rinnooy Kan, A. H. G. (1983). “Scheduling Subject to Resource Constraints: Classification and Complexity.” Discrete Applied Mathematics, 5(1), 11–24.
Brucker, P., Drexl, A., Möhring, R., Neumann, K., & Pesch, E. (1999). “Resource-Constrained Project Scheduling: Notation, Classification, Models, and Methods.” European Journal of Operational Research, 112(1), 3–41.
Ghallab, M., Nau, D., & Traverso, P. (2004). Automated Planning: Theory and Practice. Morgan Kaufmann.
Neumann, K., Schwindt, C., & Zimmermann, J. (2003). Project Scheduling with Time Windows and Scarce Resources. Springer.
Stolaroff, J. K., Samaras, C., O’Neill, E. R., Luber, A., Ziv, A. S., & Dillingham, C. (2018). “Energy Use and Life Cycle Greenhouse Gas Emissions of Drones for Commercial Package Delivery.” Nature Communications, 9, 409.