396.29 자원 제약 조건의 정식화

1. 서론

로봇 임무 관리에서 자원 제약 조건(resource constraint)은 임무 수행에 필요한 물리적, 계산적, 통신적 자원의 유한성에 기인하는 제약이다. 배터리 에너지, 연료, 탑재 중량(payload capacity), 처리 연산 능력, 통신 대역폭, 저장 공간, 소모품(센서 프로브, 비콘 등) 등은 모두 유한한 자원에 해당하며, 이들의 소비와 가용량 사이의 관계를 정확하게 모델링하는 것은 실현 가능한 임무 계획의 수립에 필수적이다.

자원 제약의 정식화는 자원의 유형, 소비 패턴, 재생 가능 여부 등에 따라 상이한 수학적 모델을 필요로 한다. 본 절에서는 로봇 임무에 적용되는 자원 제약의 분류와 수학적 정식화 방법론, 그리고 자원 제약 하의 계획 알고리즘을 체계적으로 기술한다.

2. 자원의 분류

2.1 재생 가능 자원과 비재생 가능 자원

자원은 재생 가능 여부에 따라 두 가지 범주로 분류된다.

재생 가능 자원(renewable resource): 과업 수행 후 반환되어 다시 사용할 수 있는 자원이다. 처리 장치(CPU/GPU), 통신 채널, 작업 공간 등이 이에 해당한다. 재생 가능 자원의 핵심 제약은 임의의 시점 $t$ 에서 동시에 사용되는 자원의 총량이 용량을 초과하지 않아야 한다는 것이다:

$\sum_{i \in \mathcal{T}_{\text{active}}(t)} r_{ik} \leq R_k, \quad \forall t, \; \forall k \in \mathcal{K}_{\text{renew}}$

여기서 $\mathcal{T}_{\text{active}}(t)$ 는 시점 $t$ 에 실행 중인 과업 집합, $r_{ik}$ 는 과업 $\tau_i$ 가 자원 $k$ 에 대하여 요구하는 양, $R_k$ 는 자원 $k$ 의 총 용량이다.

비재생 가능 자원(non-renewable resource): 사용하면 소비되어 복원되지 않는 자원이다. 배터리 에너지, 연료, 소모성 센서 등이 이에 해당한다. 비재생 가능 자원의 제약은 전체 임무 기간에 걸친 누적 소비량이 초기 가용량을 초과하지 않아야 한다는 것이다:

$\sum_{i=1}^{n} c_{ik} \leq C_k^{\text{init}}, \quad \forall k \in \mathcal{K}_{\text{non-renew}}$

여기서 $c_{ik}$ 는 과업 $\tau_i$ 가 자원 $k$ 를 소비하는 양, $C_k^{\text{init}}$ 는 자원 $k$ 의 초기 총량이다.

2.2 이산 자원과 연속 자원

이산 자원(discrete resource): 정수 단위로 할당되는 자원이다. 로봇의 대수, 그리퍼(gripper)의 수, 센서 모듈의 수 등이 이에 해당한다:

$r_{ik} \in \mathbb{Z}^+, \quad \sum_{i \in \mathcal{T}_{\text{active}}(t)} r_{ik} \leq R_k$

연속 자원(continuous resource): 실수 값으로 할당되는 자원이다. 에너지 소비율, 통신 대역폭, 연산 능력 등이 이에 해당한다:

$r_{ik} \in \mathbb{R}^+, \quad \sum_{i \in \mathcal{T}_{\text{active}}(t)} r_{ik} \leq R_k$

2.3 저장 가능 자원(Reservoir Resource)

저장 가능 자원은 생산과 소비가 동시에 발생할 수 있는 자원이다. 배터리의 충전과 방전, 물탱크의 급수와 배수 등이 이에 해당한다. 저장 가능 자원의 수준(level)은 시간에 따라 변동하며, 다음과 같은 제약을 만족하여야 한다:

$L_k^{\min} \leq L_k(t) \leq L_k^{\max}, \quad \forall t$

여기서 $L_k(t)$ 는 시점 $t$ 에서의 자원 $k$ 의 수준이며, $L_k^{\min}$ 과 $L_k^{\max}$ 는 허용 범위의 하한과 상한이다. 자원 수준의 변화는 다음과 같이 모델링된다:

$L_k(t) = L_k(0) + \int_0^t \left[ \dot{p}_k(\tau) - \dot{c}_k(\tau) \right] d\tau$

여기서 $\dot{p}_k(\tau)$ 는 생산율(production rate), $\dot{c}_k(\tau)$ 는 소비율(consumption rate)이다.

3. 에너지 자원 제약의 정식화

3.1 배터리 에너지 모델

로봇의 배터리 에너지 제약은 임무 관리에서 가장 빈번하게 다루어지는 자원 제약이다. 배터리의 잔여 에너지 $E(t)$ 는 시간에 따라 다음과 같이 감소한다:

$E(t) = E_0 - \int_0^t P(\tau) d\tau$

여기서 $E_0$ 는 초기 에너지, $P(\tau)$ 는 시점 $\tau$ 에서의 전력 소비율이다. 임무의 에너지 제약은 잔여 에너지가 항상 양수를 유지하여야 하며, 안전 여유(safety margin) $E_{\text{reserve}}$ 를 고려하면:

$E(t) \geq E_{\text{reserve}}, \quad \forall t \in [0, T_{\text{mission}}]$

이동 과업에서의 에너지 소비는 이동 거리, 속도, 탑재 중량, 지형 조건 등에 의존한다. 단순화된 모델에서 경유점 $w_i$ 에서 $w_j$ 로의 이동 에너지는:

$E_{\text{move}}(w_i, w_j) = \alpha \cdot d(w_i, w_j) + \beta \cdot m_{\text{payload}} \cdot d(w_i, w_j)$

여기서 $d(w_i, w_j)$ 는 이동 거리, $\alpha$ 는 기본 에너지 계수, $\beta$ 는 탑재 중량 에너지 계수, $m_{\text{payload}}$ 는 탑재 중량이다.

3.2 연료 제약 모델

무인 항공기(UAV)나 수중 로봇의 연료 제약은 배터리와 유사하나, 연료 소비가 비선형적인 경우가 많다. 연료 소비율은 속도, 고도, 기상 조건 등의 함수이다:

$\dot{F}(t) = f(\mathbf{v}(t), h(t), \mathbf{w}_{\text{wind}}(t))$

여기서 $\dot{F}(t)$ 는 연료 소비율, $\mathbf{v}(t)$ 는 속도 벡터, $h(t)$ 는 고도, $\mathbf{w}_{\text{wind}}(t)$ 는 풍속 벡터이다.

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

실제 로봇 임무에서는 복수의 자원 제약이 동시에 존재하며, 이들 간의 상호 의존성(interdependency)을 반영하여야 한다. 예를 들어, 통신 대역폭의 증가는 에너지 소비를 증가시키며, 센서의 활성화는 연산 부하와 에너지 소비를 동시에 증가시킨다.

다중 자원 제약은 자원 벡터 $\mathbf{r}(\tau_i) = [r_{i1}, r_{i2}, \ldots, r_{iK}]$ 로 표현되며, 제약 조건은:

$\sum_{i \in \mathcal{T}_{\text{active}}(t)} \mathbf{r}(\tau_i) \leq \mathbf{R}^{\max}, \quad \forall t$

여기서 $\leq$ 는 성분별(component-wise) 비교이고, $\mathbf{R}^{\max} = [R_1^{\max}, R_2^{\max}, \ldots, R_K^{\max}]$ 는 자원 용량 벡터이다.

5. 자원 제약 하의 계획 문제

5.1 자원 제약 프로젝트 스케줄링 문제(RCPSP)

자원 제약 하의 임무 스케줄링은 RCPSP(Resource-Constrained Project Scheduling Problem)로 정식화된다:

$\min \; C_{\max}$

$\text{s.t.} \quad e_i \leq s_j, \quad \forall (\tau_i, \tau_j) \in \mathcal{P}$

$\sum_{i : s_i \leq t < e_i} r_{ik} \leq R_k, \quad \forall k, \; \forall t$

$s_i \geq 0, \quad \forall \tau_i \in \mathcal{T}$

RCPSP는 NP-난해 문제이며, 대규모 인스턴스에 대하여 정확한 최적해의 계산은 사실상 불가능하다. 이에 따라, 우선순위 규칙 기반 휴리스틱(priority-rule-based heuristic), 유전 알고리즘(genetic algorithm), 시뮬레이티드 어닐링(simulated annealing) 등의 근사적 방법이 활용된다.

5.2 에너지 인식 경로 계획

에너지 자원 제약을 경로 계획에 통합하면, 목표 지점을 방문하면서 에너지 제약을 만족하는 경로를 탐색하는 문제가 된다. 이는 용량 제약이 있는 차량 경로 문제(Capacitated Vehicle Routing Problem, CVRP)의 변형으로 정식화된다:

$\min \sum_{(i,j) \in \mathcal{E}} c_{ij} x_{ij}$

$\text{s.t.} \quad \sum_{j} E_{\text{move}}(w_i, w_j) x_{ij} \leq E_0 - E_{\text{reserve}}$

여기서 $x_{ij} \in \{0, 1\}$ 는 경유점 $w_i$ 에서 $w_j$ 로의 이동 여부를 나타내는 이진 변수이다.

5.3 자원 재충전 모델

충전소(charging station)에서의 에너지 보충이 가능한 경우, 자원 제약은 재충전 기회를 포함하여 모델링된다:

$E(t_k^+) = \min\left(E(t_k^-) + \Delta E_{\text{charge}}, E_{\max}\right)$

여기서 $t_k^-$ 와 $t_k^+$ 는 충전 이벤트 $k$ 의 전후 시점이고, $\Delta E_{\text{charge}}$ 는 충전량이다. 충전 시간과 충전 효율의 모델링이 추가적으로 요구된다.

6. 자원 제약의 완화와 트레이드오프

모든 자원 제약을 경성 제약으로 처리하면 실현 가능한 해가 존재하지 않는 과잉 제약 상황이 발생할 수 있다. 이 경우, 연성 제약으로의 완화가 고려된다:

$\min \left[ f(\mathbf{x}) + \sum_k \lambda_k \cdot \max\left(0, \sum_{i \in \mathcal{T}_{\text{active}}(t)} r_{ik} - R_k\right) \right]$

여기서 $\lambda_k$ 는 자원 $k$ 의 초과에 대한 페널티 계수이다.

자원 간 트레이드오프(trade-off)의 분석도 중요하다. 속도를 높이면 시간 제약은 완화되나 에너지 소비가 증가하며, 센서 해상도를 높이면 임무 품질은 향상되나 처리 시간과 에너지가 증가한다. 이러한 트레이드오프는 파레토 최적화(Pareto optimization)를 통하여 분석된다:

$\min_{\mathbf{x}} \left[ f_{\text{time}}(\mathbf{x}), f_{\text{energy}}(\mathbf{x}), f_{\text{quality}}(\mathbf{x}) \right]$

7. 참고문헌

Brucker, P., Drexl, A., Möhring, R., Neumann, K., and Pesch, E. (1999). “Resource-Constrained Project Scheduling: Notation, Classification, Models, and Methods.” European Journal of Operational Research, 112(1), 3–41.
Toth, P. and Vigo, D. (2014). Vehicle Routing: Problems, Methods, and Applications. 2nd Edition, SIAM.
Mei, Y., Lu, Y.H., Hu, Y.C., and Lee, C.S.G. (2006). “Energy-Efficient Motion Planning for Mobile Robots.” Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), 2006.
Sundar, K. and 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.
Laborie, P. (2003). “Algorithms for Propagating Resource Constraints in AI Planning and Scheduling.” Artificial Intelligence, 143(2), 151–188.

본 절은 로봇공학 서적 Volume 9, Part 53, Chapter 396의 일부로 작성되었다. 버전: 2026-03-23 v1.0