397.62 페이로드 제약 반영 임무 계획

1. 개요

자율 로봇이 수행하는 임무의 상당수는 물체의 운반, 센서 장비의 탑재, 도구의 이동 등 **페이로드(payload)**를 수반한다. 로봇의 물리적 적재 용량, 중량 한계, 부피 제약 등은 동시에 수행 가능한 임무의 범위를 제한하며, 이러한 제약을 무시한 임무 계획은 실행 불가능한 시퀀스를 생성할 수 있다. 페이로드 제약 반영 임무 계획은 로봇의 물리적 적재 능력을 명시적으로 고려하여 최적의 임무 시퀀스를 결정하는 기법이다.

본 절에서는 페이로드 제약의 유형과 수학적 모델링, 제약이 포함된 최적화 문제의 정식화, 그리고 해법 알고리즘을 다룬다.

2. 페이로드 제약의 유형과 모델링

2.1 페이로드 제약의 분류

로봇 시스템에서의 페이로드 제약은 다음과 같이 분류된다.

중량 제약(Weight Constraint): 로봇이 동시에 운반할 수 있는 최대 중량 $W_{\max}$ 에 의한 제한이다. 각 임무 $\tau_i$ 에 연관된 화물의 중량을 $w_i$ 라 할 때, 임의 시점에서 로봇에 적재된 화물의 총중량이 한계를 초과해서는 안 된다.

$\sum_{i \in \mathcal{L}(t)} w_i \leq W_{\max}, \quad \forall t$

여기서 $\mathcal{L}(t)$ 는 시간 $t$ 에서 로봇에 적재되어 있는 화물의 집합이다.

부피 제약(Volume Constraint): 로봇의 적재 공간의 부피 $V_{\max}$ 에 의한 제한이다. 각 화물의 부피를 $v_i$ 라 하면 다음이 성립해야 한다.

$\sum_{i \in \mathcal{L}(t)} v_i \leq V_{\max}, \quad \forall t$

품목 수 제약(Item Count Constraint): 동시에 운반 가능한 물품의 개수 $N_{\max}$ 에 의한 제약이다.

$|\mathcal{L}(t)| \leq N_{\max}, \quad \forall t$

호환성 제약(Compatibility Constraint): 특정 화물 유형 간의 동시 적재가 금지되는 경우이다. 예를 들어, 위험 물질과 일반 화물의 동시 운반이 불가능한 경우가 해당한다. 호환 불가 쌍의 집합을 $\mathcal{C} = \{(i, j) \mid \tau_i \text{와 } \tau_j \text{는 동시 적재 불가}\}$ 로 정의한다.

$\forall (i, j) \in \mathcal{C}: \lnot (i \in \mathcal{L}(t) \land j \in \mathcal{L}(t)), \quad \forall t$

2.2 동적 페이로드 변화 모델

임무 수행 과정에서 페이로드는 동적으로 변화한다. 배달 임무에서는 화물을 적재(pickup)하고 하역(delivery)하며, 수집 임무에서는 샘플을 순차적으로 누적한다.

배달 임무에서의 적재량 변화를 형식화하면 다음과 같다.

$\mathcal{L}(t_k) = \mathcal{L}(t_{k-1}) \cup \text{pickup}(\tau_{\sigma_k}) \setminus \text{delivery}(\tau_{\sigma_k})$

여기서 $\text{pickup}(\tau_i)$ 는 임무 $\tau_i$ 에서 적재하는 화물 집합, $\text{delivery}(\tau_i)$ 는 하역하는 화물 집합이다.

총 적재 중량의 시간적 변화는 다음과 같이 추적된다.

$W(t_k) = W(t_{k-1}) + \sum_{i \in \text{pickup}(\tau_{\sigma_k})} w_i - \sum_{j \in \text{delivery}(\tau_{\sigma_k})} w_j$

3. 페이로드 제약 포함 최적화 문제의 정식화

3.1 용량 제약 차량 경로 배정 문제와의 관계

페이로드 제약이 포함된 임무 계획 문제는 조합 최적화 분야의 **용량 제약 차량 경로 배정 문제(Capacitated Vehicle Routing Problem, CVRP)**와 밀접한 관련이 있다. CVRP는 정해진 적재 용량을 가진 차량이 전체 고객을 방문하면서 총 이동 비용을 최소화하는 문제이다.

로봇 임무 계획에서의 CVRP 정식화는 다음과 같다.

$\begin{aligned} \min \quad & \sum_{(i,j) \in E} c_{ij} x_{ij} \\ \text{s.t.} \quad & \sum_{j} x_{ij} = 1, \quad \forall i \in T \quad \text{(각 임무 정확히 한 번 방문)} \\ & \sum_{i \in S} \sum_{j \notin S} x_{ij} \geq \lceil d(S) / W_{\max} \rceil, \quad \forall S \subseteq T \\ & x_{ij} \in \{0, 1\} \end{aligned}$

여기서 $c_{ij}$ 는 임무 $i$ 에서 $j$ 로의 이동 비용, $d(S) = \sum_{i \in S} w_i$ 는 집합 $S$ 의 총 수요량이다. 두 번째 제약은 용량 초과를 방지하기 위한 절단 제약(capacity cut)이다.

3.2 픽업-배달 문제

픽업과 배달이 쌍을 이루는 임무의 경우, **픽업-배달 문제(Pickup and Delivery Problem, PDP)**로 정식화된다. 각 요청 $r_k = (p_k, d_k, w_k)$ 는 픽업 지점 $p_k$ , 배달 지점 $d_k$ , 화물 중량 $w_k$ 로 구성된다.

추가 제약 조건은 다음과 같다.

선후 관계: 각 요청에 대해 픽업이 배달보다 먼저 수행되어야 한다. $\sigma(p_k) < \sigma(d_k)$
동일 차량 제약: 동일 요청의 픽업과 배달은 동일 로봇이 처리해야 한다.
적재 제약: 임의 시점에서 적재량이 용량을 초과할 수 없다.

$0 \leq W(t) \leq W_{\max}, \quad \forall t$

3.3 다차원 페이로드 제약

현실적인 로봇 시스템에서는 중량과 부피가 동시에 제약되는 경우가 일반적이다. 다차원 페이로드 제약은 $d$ -차원 자원 벡터로 모델링된다.

$\mathbf{c}_i = [w_i, v_i, n_i, \ldots]^T \in \mathbb{R}^d$

제약 조건은 다음과 같이 일반화된다.

$\sum_{i \in \mathcal{L}(t)} \mathbf{c}_i \leq \mathbf{C}_{\max}, \quad \forall t$

여기서 $\mathbf{C}_{\max} = [W_{\max}, V_{\max}, N_{\max}, \ldots]^T$ 는 각 차원의 최대 허용량 벡터이며, 비교 연산은 원소별로 수행된다.

4. 해법 알고리즘

4.1 정확해 알고리즘

분지 한정법(Branch and Bound): 탐색 트리를 체계적으로 탐색하면서, 하한(lower bound) 추정을 통해 최적 해가 아닌 분지를 조기에 제거한다. 페이로드 제약은 각 노드에서의 적합성 검사로 반영된다.

분지 절단법(Branch and Cut): 선형 계획 완화(LP relaxation)를 풀고, 유효 부등식(valid inequality)을 동적으로 추가하여 정수해에 수렴한다. 용량 절단(capacity cut), 라운딩 절단(rounding cut) 등이 적용된다.

열 생성법(Column Generation): 대규모 문제에 대해 집합 분할 정식화(set partitioning formulation)를 채택하고, 가격 책정 하위 문제(pricing subproblem)를 통해 유망한 경로를 동적으로 생성한다. 하위 문제는 자원 제약 최단 경로 문제(Resource-Constrained Shortest Path Problem, RCSPP)로 정식화된다.

4.2 구성적 휴리스틱

용량 인식 최근접 이웃 삽입(Capacity-Aware Nearest Neighbor Insertion): 현재 적재량을 감안하여 적재 가능한 임무 중 가장 가까운 임무를 순차적으로 삽입한다.

알고리즘: CapacityAwareNearestNeighor

입력: 임무 집합 T, 로봇 용량 W_max
출력: 적재 가능한 임무 시퀀스

1.  현재 위치 ← 기지, 현재 적재량 W ← 0
2.  while 미방문 임무 존재 do:
      후보 ← {τ ∈ 미방문 | W + w_τ ≤ W_max}
      if 후보 = ∅ then:
          기지로 귀환, W ← 0 (하역 후 재출발)
      else:
          τ* ← arg min_{τ ∈ 후보} distance(현재 위치, location(τ))
          시퀀스에 τ* 추가
          W ← W + w_{τ*}
3.  기지로 귀환

클러스터 우선-경로 후 전략(Cluster-First, Route-Second): 먼저 임무를 용량 제약 내의 클러스터로 분할하고, 각 클러스터 내에서 최적 순회 경로를 구한다. 클러스터링에는 $k$ -means, 스위프(sweep) 알고리즘 등이 사용된다.

4.3 메타휴리스틱 기반 접근

적응형 대규모 이웃 탐색(Adaptive Large Neighborhood Search, ALNS): Ropke & Pisinger(2006)가 제안한 ALNS는 다양한 파괴(destroy) 및 수리(repair) 연산자를 적응적으로 선택하여 해를 개선한다. 페이로드 제약 위반은 수리 연산자에서 검증되며, 위반 해는 패널티를 부과하여 탐색 범위 내에 유지하거나 즉시 폐기한다.

대표적인 파괴 연산자는 다음과 같다.

무작위 제거(Random Removal): 임의의 임무를 시퀀스에서 제거한다.
최악 제거(Worst Removal): 목적 함수에 가장 부정적 영향을 미치는 임무를 제거한다.
관련 제거(Related Removal): 지리적으로 인접하거나 속성이 유사한 임무들을 함께 제거한다.

수리 연산자는 다음을 포함한다.

탐욕적 삽입(Greedy Insertion): 제거된 임무를 비용 증가가 최소인 위치에 삽입한다.
후회 삽입(Regret Insertion): 차선 위치와의 비용 차이가 가장 큰 임무부터 우선 삽입한다.

타부 탐색(Tabu Search): 최근 방문한 해를 금기 목록(tabu list)에 등록하여 순환 탐색을 방지하면서 이웃 해를 탐색한다. 이동 연산으로는 임무 재배치(relocate), 교환(swap), 2-opt 등이 사용된다.

5. 페이로드 제약과 에너지 소비의 연계

페이로드는 로봇의 에너지 소비에 직접적인 영향을 미친다. 적재 중량이 증가하면 이동에 필요한 에너지가 증가하므로, 페이로드 제약과 에너지 제약은 상호 연계되어 고려해야 한다.

적재 중량 $W(t)$ 에 따른 이동 에너지 소비 모델은 다음과 같이 확장된다.

$P_{\text{loco}}(v, W) = \left[ (m_{\text{robot}} + W) g \mu + \frac{1}{2} C_d \rho A v^2 \right] v + P_{\text{idle}}$

멀티로터 드론의 경우, 호버링 전력은 총중량의 제곱근에 비례한다.

$P_{\text{hover}}(W) = \sqrt{\frac{\left[(m_{\text{drone}} + W) g\right]^3}{2 \rho A_{\text{rotor}}}}$

따라서 최적 임무 시퀀싱에서는 하역 가능한 임무를 먼저 수행하여 적재 중량을 조기에 감소시킴으로써, 이후 이동 구간의 에너지 소비를 절감하는 전략이 유효하다. 이는 적재 순서에 따른 총 에너지 소비의 비대칭성을 활용하는 것이다.

$E_{\text{total}}(\sigma_1) \neq E_{\text{total}}(\sigma_2), \quad \sigma_1 \neq \sigma_2 \text{ (동일 임무, 상이한 순서)}$

6. 다중 로봇 환경에서의 페이로드 제약

6.1 이종 로봇의 이질적 적재 용량

다중 로봇 시스템에서 각 로봇은 상이한 적재 용량을 가질 수 있다. 로봇 $r_j$ 의 적재 용량을 $W_{\max}^{(j)}$ 라 할 때, 임무-로봇 할당 문제는 다음과 같이 확장된다.

$\begin{aligned} \min \quad & \sum_{j \in R} \sum_{(i,k) \in E} c_{ik} x_{ik}^{(j)} \\ \text{s.t.} \quad & W^{(j)}(t) \leq W_{\max}^{(j)}, \quad \forall j, \forall t \\ & \sum_{j \in R} y_i^{(j)} = 1, \quad \forall i \in T \quad \text{(각 임무 정확히 하나의 로봇에 할당)} \end{aligned}$

6.2 협력적 운반 임무

단일 로봇의 적재 용량을 초과하는 대형 화물의 경우, 복수의 로봇이 협력하여 운반하는 협력적 운반(cooperative transport) 임무가 필요하다. 이 경우 임무 계획에는 다음 추가 제약이 포함된다.

동기화 제약: 협력 운반에 참여하는 모든 로봇이 동시에 해당 임무에 도착해야 한다.
결합 용량 제약: 참여 로봇들의 용량 합이 화물 중량을 초과해야 한다.

$\sum_{j \in R_{\text{coop}}(\tau_i)} W_{\max}^{(j)} \geq w_i$

7. 산업 응용 사례

7.1 물류 창고 자율 이동 로봇

물류 창고의 AMR은 다수의 주문 물품을 동시에 적재하여 배송 지점으로 운반한다. 적재 용량(중량, 부피, 품목 수)이 제한되므로, 주문 배치(order batching)와 경로 최적화를 결합한 페이로드 인식 임무 계획이 필수적이다. 최적 배치 크기는 적재 용량, 주문의 공간 분포, 이동 거리 간의 트레이드오프에 의해 결정된다.

7.2 드론 배달 시스템

소형 드론의 적재 용량은 일반적으로 1–5 kg으로 제한된다. 다수의 배달 주문을 효율적으로 처리하기 위해, 페이로드 제약과 비행 거리(에너지) 제약을 동시에 고려한 경로 계획이 요구된다. 특히 적재 중량에 따른 비행 에너지 변화가 현저하므로, 배달 순서의 최적화가 총 에너지 소비에 직접적인 영향을 미친다.

7.3 농업 로봇의 수확물 수집

자율 농업 로봇은 수확물을 순차적으로 수집하면서 적재함의 용량이 가득 차면 하역 지점으로 이동해야 한다. 수확 지점의 공간 분포와 예상 수확량을 고려한 최적 수확 경로 계획은 작업 효율을 결정하는 핵심 요소이다.

8. 참고 문헌

Dantzig, G. B., & Ramser, J. H. (1959). “The Truck Dispatching Problem.” Management Science, 6(1), 80–91.
Laporte, G. (2007). “What You Should Know about the Vehicle Routing Problem.” Naval Research Logistics, 54(8), 811–819.
Ropke, S., & Pisinger, D. (2006). “An Adaptive Large Neighborhood Search Heuristic for the Pickup and Delivery Problem with Time Windows.” Transportation Science, 40(4), 455–472.
Toth, P., & Vigo, D. (Eds.). (2014). Vehicle Routing: Problems, Methods, and Applications (2nd ed.). SIAM.