397.54 가중합 기반 다목적 임무 최적화

1. 개요

가중합 기반 다목적 임무 최적화(weighted sum-based multi-objective mission optimization)는 복수의 목적 함수를 단일 스칼라 목적 함수로 결합하여, 기존의 단일 목적 최적화 알고리즘을 직접 활용할 수 있도록 하는 가장 고전적이고 직관적인 스칼라화(scalarization) 기법이다. 각 목적 함수에 비음(non-negative) 가중치를 부여하고 이를 선형 결합하여 합산 비용을 최소화하는 방식으로 작동한다.

로봇 임무 계획에서 가중합 방법은 이동 시간, 에너지 소모, 위험 노출 등 상충하는 다수의 성능 지표를 운영자의 선호(preference)에 따라 하나의 비용 함수로 통합함으로써, Dijkstra 알고리즘, A* 알고리즘, 가치 반복(value iteration) 등의 표준 최적화 기법을 그대로 적용할 수 있는 편의성을 제공한다.

2. 수학적 정식화

2.1 기본 형태

$k$ 개의 목적 함수 $f_1(\mathbf{x}), f_2(\mathbf{x}), \ldots, f_k(\mathbf{x})$ 를 동시에 최소화하는 다목적 문제에 대해, 가중합 스칼라화는 다음과 같이 정식화된다:

$\min_{\mathbf{x} \in \mathcal{X}} F(\mathbf{x}) = \sum_{i=1}^{k} w_i f_i(\mathbf{x})$

여기서 $w_i \geq 0$ 은 $i$ 번째 목적 함수에 대한 가중치이며, 관례적으로 다음의 정규화 조건을 부과한다:

$\sum_{i=1}^{k} w_i = 1$

가중치 벡터 $\mathbf{w} = (w_1, w_2, \ldots, w_k)^T$ 는 운영자의 선호를 수량적으로 반영한다. $w_i$ 가 클수록 $i$ 번째 목적이 상대적으로 더 중요하게 고려된다.

2.2 정규화된 가중합

목적 함수 간 스케일 차이가 존재하는 경우, 정규화(normalization)를 통해 공정한 비교가 가능하도록 한다. 정규화된 가중합 목적 함수는 다음과 같다:

$\min_{\mathbf{x} \in \mathcal{X}} F_{\text{norm}}(\mathbf{x}) = \sum_{i=1}^{k} w_i \cdot \frac{f_i(\mathbf{x}) - f_i^{\min}}{f_i^{\max} - f_i^{\min}}$

여기서 $f_i^{\min}$ 과 $f_i^{\max}$ 는 각각 $i$ 번째 목적 함수의 최소값과 최대값(또는 이상점과 나디르점의 해당 성분)이다. 정규화를 통해 각 목적의 값이 $[0, 1]$ 범위로 조정되어, 가중치의 의미가 명확해진다.

3. 이론적 성질

3.1 파레토 최적해 보장 정리

가중합 방법의 핵심적 이론적 성질은 다음과 같다.

정리 1 (충분 조건): 가중치 $w_i > 0$ ( $\forall i$ )에 대해, 가중합 문제의 최적해 $\mathbf{x}^*$ 는 원래 다목적 문제의 파레토 최적해이다.

증명 개요: 귀류법으로, $\mathbf{x}^*$ 가 파레토 최적이 아니라면 $\mathbf{x}^*$ 를 지배하는 해 $\mathbf{x}'$ 가 존재하여 모든 $i$ 에 대해 $f_i(\mathbf{x}') \leq f_i(\mathbf{x}^*)$ 이고 적어도 하나의 $j$ 에 대해 $f_j(\mathbf{x}') < f_j(\mathbf{x}^*)$ 이다. 그러면 $F(\mathbf{x}') = \sum w_i f_i(\mathbf{x}') < \sum w_i f_i(\mathbf{x}^*) = F(\mathbf{x}^*)$ 이므로 $\mathbf{x}^*$ 의 최적성에 모순된다.

정리 2 (필요 조건의 한계): 볼록 문제에서 모든 파레토 최적해는 적절한 가중치 벡터에 의해 가중합 최적해로 도출 가능하다. 그러나 비볼록 문제에서는 가중치 변동으로 도달할 수 없는 파레토 최적해가 존재할 수 있다.

3.2 볼록 문제에서의 완전성

목적 함수 $f_1, \ldots, f_k$ 가 모두 볼록(convex)이고 실행 가능 영역 $\mathcal{X}$ 가 볼록 집합인 경우, 파레토 전선은 볼록 집합의 경계를 이루며, 가중합 방법으로 파레토 전선의 모든 점을 생성할 수 있다. 이는 볼록 최적화의 지지 초평면 정리(supporting hyperplane theorem)로부터 도출된다.

3.3 비볼록 문제에서의 한계

비볼록 파레토 전선에서는 함입 영역(concave region)에 위치하는 파레토 최적해를 가중합 방법으로 도출할 수 없다. 이는 가중합 목적 함수의 등위선(iso-cost line)이 항상 초평면이므로, 볼록 포락선(convex hull) 위에 놓이지 않는 파레토 해에는 접할 수 없기 때문이다.

이를 극복하기 위해 다음의 대안이 제안되었다:

적응적 가중합 방법(Adaptive Weighted Sum): Kim, de Weck(2006)이 제안한 방법으로, 이미 발견된 파레토 해를 기반으로 금지 영역(exclusion region)을 설정하고, 부등식 제약을 추가하여 비볼록 영역의 해를 탐색한다.
정규 경계 교차법(NBI: Normal Boundary Intersection): Das, Dennis(1998)가 제안한 방법으로, 볼록 포락선에 수직인 방향으로 탐색하여 비볼록 영역을 포함한 균일 분포의 파레토 해를 생성한다.

4. 로봇 임무 계획에의 적용

4.1 가중 경로 최적화

로봇의 임무 경로 계획에서 가중합 방법은 다음과 같이 적용된다. 이동 거리 $f_1$ 과 위험 노출 $f_2$ 를 동시에 최소화하는 2-목적 경로 문제를 고려하자:

$\min_{\pi} F(\pi) = w_1 \cdot \sum_{(u,v) \in \pi} d(u,v) + w_2 \cdot \sum_{v \in \pi} r(v)$

여기서 $\pi$ 는 경로, $d(u,v)$ 는 간선 $(u,v)$ 의 물리적 거리, $r(v)$ 는 노드 $v$ 의 위험도이다.

이 스칼라 목적 함수에 대해 Dijkstra 알고리즘을 적용하면 주어진 가중치 $\mathbf{w} = (w_1, w_2)$ 에 대한 최적 경로가 $O(\lvert E \rvert + \lvert V \rvert \log \lvert V \rvert)$ 시간 내에 도출된다. 가중치를 체계적으로 변동시키면 파레토 전선의 서로 다른 지점에 대응하는 경로들을 생성할 수 있다.

4.2 LTL 명세 하의 가중 래소 최적화

형식 임무 명세(LTL)를 만족하는 래소(lasso) 경로에 대한 가중합 최적화는 다음과 같이 수행된다. 접두사 비용 $c_{\text{prefix}}$ 와 주기 비용 $c_{\text{cycle}}$ 이 각각 벡터 값일 때, 가중합 스칼라 비용은:

$F(\rho) = \sum_{i=1}^{k} w_i \left[ c_{\text{prefix}}^{(i)}(\rho) + \alpha \cdot c_{\text{cycle}}^{(i)}(\rho) \right]$

이다. 여기서 $\alpha$ 는 접두사와 주기 간 상대적 가중 계수이다. 이 스칼라 비용에 대해 2-Dijkstra 알고리즘을 적용하여 최적 래소를 탐색한다.

4.3 다중 로봇 과업 할당에의 적용

다중 로봇 과업 할당(multi-robot task allocation) 문제에서, 방법 적 비용(makespan)과 총 이동 거리를 동시에 최소화하는 가중합 정식화는 다음과 같다:

$\min_{\mathbf{A}} F(\mathbf{A}) = w_1 \cdot \max_{r \in \mathcal{R}} T_r(\mathbf{A}) + w_2 \cdot \sum_{r \in \mathcal{R}} D_r(\mathbf{A})$

여기서 $\mathbf{A}$ 는 할당 행렬, $T_r$ 은 로봇 $r$ 의 임무 완수 시간, $D_r$ 은 로봇 $r$ 의 총 이동 거리이다.

5. 가중치 결정 방법

5.1 직접 지정

운영자가 경험과 직관에 기반하여 각 목적의 가중치를 직접 설정하는 방법이다. 간편하지만 주관성이 크고, 목적 함수의 스케일에 대한 이해가 필요하다.

5.2 AHP(Analytic Hierarchy Process)

Saaty(1980)의 AHP 방법을 통해, 운영자가 목적 함수 쌍에 대한 상대적 중요도를 쌍대 비교 행렬로 제시하면 고유벡터 분석을 통해 가중치를 도출한다. 일관성 비율(consistency ratio, CR)을 통해 비교의 논리적 일관성을 검증한다. $\text{CR} < 0.1$ 이면 일관성이 수용 가능한 것으로 판정된다.

5.3 엔트로피 가중법

Shannon 엔트로피에 기반하여 목적 함수의 분산 정보로부터 가중치를 객관적으로 도출하는 방법이다. 분산이 큰(정보량이 많은) 목적에 높은 가중치를 부여한다:

$w_i = \frac{1 - E_i}{\sum_{j=1}^{k} (1 - E_j)}$

여기서 $E_i$ 는 $i$ 번째 목적의 정규화된 엔트로피이다.

5.4 균등 분포 스캔

목적 함수의 수 $k$ 에 대해, 가중치 벡터의 심플렉스(simplex) $\Delta^{k-1} = \{\mathbf{w} \mid w_i \geq 0, \sum w_i = 1\}$ 위에서 균등하게 분포된 다수의 가중치 벡터를 생성하고, 각 벡터에 대해 단일 목적 최적화를 수행하여 파레토 전선의 근사를 구성하는 방법이다.

2-목적 문제에서 $N$ 개의 가중치 벡터를 생성하면:

$\mathbf{w}^{(j)} = \left( \frac{j}{N}, 1 - \frac{j}{N} \right), \quad j = 0, 1, \ldots, N$

각 가중치에 대해 단일 목적 최적화를 수행하여 파레토 전선 상의 $N+1$ 개의 비열등 해를 근사적으로 도출한다.

6. MDP 기반 가중합 임무 최적화

6.1 스칼라화된 MDP

다목적 MDP에서 벡터 보상 $\mathbf{r}(s, a) = (r_1(s,a), \ldots, r_k(s,a))^T$ 에 대해, 가중합 스칼라화는:

$r_w(s, a) = \sum_{i=1}^{k} w_i r_i(s, a) = \mathbf{w}^T \mathbf{r}(s, a)$

로 변환된 단일 보상 MDP를 생성한다. 이 스칼라화된 MDP에 대해 표준적 가치 반복 또는 정책 반복 알고리즘을 적용하여 최적 정책 $\pi^*_\mathbf{w}$ 를 계산한다.

주어진 가중치 $\mathbf{w}$ 에 대한 최적 정책에서의 기대 총 보상 벡터:

$\mathbf{V}^{\pi^*_\mathbf{w}}(s_0) = \left( V_1^{\pi^*_\mathbf{w}}(s_0), \ldots, V_k^{\pi^*_\mathbf{w}}(s_0) \right)^T$

는 파레토 전선의 한 점에 대응한다.

6.2 볼록 커버리지 집합

Roijers, Whiteson, Oliehoek(2015)는 가중합 스칼라화로 도달 가능한 최적 정책 집합, 즉 볼록 커버리지 집합(convex coverage set)을 효율적으로 계산하는 알고리즘을 제안하였다. 이 알고리즘은 가중치 공간을 재귀적으로 분할하며 새로운 비열등 정책을 탐색한다.

7. 민감도 분석

7.1 가중치 변동의 영향

가중치의 미소 변동이 최적해에 미치는 영향을 분석하는 민감도 분석(sensitivity analysis)은 가중합 방법의 견고성을 평가하는 데 중요하다.

가중치 $w_i$ 에 대한 최적 비용의 민감도는 다음의 편미분으로 계산된다:

$\frac{\partial F^*}{\partial w_i} = f_i(\mathbf{x}^*)$

이는 가중합 최적해에서의 $i$ 번째 목적 함수 값에 해당한다. 이 결과는 가중치 변동 시 비용 변화의 방향과 크기를 파악하는 데 활용된다.

7.2 안정성 영역(Stability Region)

특정 최적해 $\mathbf{x}^*$ 가 최적으로 유지되는 가중치 범위를 안정성 영역이라 한다. 선형 계획법 기반 임무 계획에서는 쌍대성(duality) 이론을 활용하여 안정성 영역을 해석적으로 도출할 수 있다.

8. 장점과 한계

8.1 장점

계산 효율성: 기존 단일 목적 최적화 알고리즘을 변형 없이 사용할 수 있다. Dijkstra, A*, 가치 반복 등의 표준 알고리즘이 그대로 적용된다.
직관성: 가중치가 각 목적의 상대적 중요도를 직접적으로 반영하므로, 운영자가 해석하기 용이하다.
단일 해 도출: 각 가중치 벡터에 대해 하나의 최적해가 도출되므로, 추가적 해 선택 과정이 불필요하다.
이론적 보장: 양의 가중치에 대해 파레토 최적성이 보장된다.

8.2 한계

비볼록 파레토 전선의 불완전 탐색: 비볼록 영역의 파레토 해에 도달할 수 없다.
가중치 사전 결정: 가중치를 최적화 이전에 결정해야 하므로, 문제에 대한 충분한 사전 지식이 필요하다.
비균일 분포: 가중치의 균일 분포가 파레토 전선 상의 균일한 해 분포를 보장하지 않는다.
스케일 의존성: 정규화 없이 사용 시 목적 함수 간 스케일 차이에 의해 결과가 왜곡될 수 있다.

9. 참고 문헌

Saaty, T.L. (1980). The Analytic Hierarchy Process. McGraw-Hill.
Zadeh, L.A. (1963). “Optimality and Non-Scalar-Valued Performance Criteria.” IEEE Transactions on Automatic Control, 8(1), pp. 59–60.
Das, I., Dennis, J.E. (1998). “Normal-Boundary Intersection: A New Method for Generating the Pareto Surface in Nonlinear Multicriteria Optimization Problems.” SIAM Journal on Optimization, 8(3), pp. 631–657.
Kim, I.Y., de Weck, O.L. (2006). “Adaptive Weighted-Sum Method for Multiobjective Optimization: A New Method for Pareto Front Generation.” Structural and Multidisciplinary Optimization, 31(2), pp. 105–116.
Roijers, D.M., Whiteson, S., Oliehoek, F.A. (2015). “Computing Convex Coverage Sets for Faster Multi-Objective Coordination.” Journal of Artificial Intelligence Research, 52, pp. 399–443.
Miettinen, K. (1999). Nonlinear Multiobjective Optimization. Springer.

버전: 2026-03-24
출처: Robotics Engineering 서적, Volume 9, Part 53, Chapter 397