396.75 다중 목적 최적화 기반 임무 스코어링 체계

396.75 다중 목적 최적화 기반 임무 스코어링 체계

1. 개요

로봇 임무 관리에서 임무 스코어링(Mission Scoring)은 다수의 후보 임무 또는 임무 계획 중 가장 적절한 것을 선택하기 위해 각 후보에 정량적 점수를 부여하는 체계적 평가 과정이다. 현실의 로봇 임무는 완수 시간, 에너지 소비, 안전성, 탐색 범위, 위험도 등 복수의 상충하는 목적(objectives)을 동시에 고려해야 하므로, 단일 목적 함수로는 임무의 적합성을 충분히 표현할 수 없다. 다중 목적 최적화(Multi-Objective Optimization, MOO)에 기반한 임무 스코어링 체계는 이러한 복수의 목적을 체계적으로 통합하여, 의사 결정자에게 합리적 선택 기반을 제공한다. 본 절에서는 다중 목적 최적화의 이론적 기초, 임무 스코어링 함수 설계, 파레토 최적해 분석, 그리고 실용적 구현 전략을 다룬다.

2. 다중 목적 최적화의 이론적 기초

2.1 다중 목적 최적화 문제의 정식화

다중 목적 최적화 문제(Multi-Objective Optimization Problem, MOOP)는 다음과 같이 정식화된다.

\min_{\mathbf{x} \in \mathcal{X}} \; \mathbf{F}(\mathbf{x}) = \left[ f_1(\mathbf{x}), \; f_2(\mathbf{x}), \; \ldots, \; f_p(\mathbf{x}) \right]^T

\text{subject to:} \quad g_j(\mathbf{x}) \leq 0, \quad j = 1, \ldots, m

h_k(\mathbf{x}) = 0, \quad k = 1, \ldots, q

여기서 \mathbf{x} \in \mathcal{X} \subseteq \mathbb{R}^n은 결정 변수 벡터(임무 계획의 파라미터), \mathbf{F}: \mathbb{R}^n \rightarrow \mathbb{R}^p는 p개의 목적 함수 벡터, g_j(\mathbf{x})는 부등식 제약, h_k(\mathbf{x})는 등식 제약이다.

2.2 파레토 우위와 파레토 최적해

두 해 \mathbf{x}^a와 \mathbf{x}^b에 대해, \mathbf{x}^a가 \mathbf{x}^b를 파레토 지배(Pareto dominate)한다는 것은 다음을 의미한다.

\mathbf{x}^a \preceq \mathbf{x}^b \iff \forall i \in \{1, \ldots, p\}: f_i(\mathbf{x}^a) \leq f_i(\mathbf{x}^b) \;\; \wedge \;\; \exists j \in \{1, \ldots, p\}: f_j(\mathbf{x}^a) < f_j(\mathbf{x}^b)

어떠한 다른 해에 의해서도 파레토 지배되지 않는 해를 파레토 최적해(Pareto optimal solution)라 하며, 모든 파레토 최적해의 집합을 파레토 전선(Pareto front) \mathcal{P}^*라 한다.

\mathcal{P}^* = \{ \mathbf{x}^* \in \mathcal{X} \mid \nexists \; \mathbf{x} \in \mathcal{X}: \mathbf{x} \preceq \mathbf{x}^* \}

파레토 전선 위의 해들은 목적 함수 간의 트레이드오프를 나타내며, 어느 하나가 절대적으로 우수하다고 판단할 수 없다.

2.3 이상점과 나디르점

다중 목적 공간에서의 참조점(reference point)은 해의 품질을 상대적으로 평가하는 데 활용된다.

이상점(Ideal Point) \mathbf{z}^{\text{ideal}}는 각 목적 함수가 독립적으로 최적화될 때의 값이다.

z_i^{\text{ideal}} = \min_{\mathbf{x} \in \mathcal{X}} f_i(\mathbf{x}), \quad i = 1, \ldots, p

나디르점(Nadir Point) \mathbf{z}^{\text{nadir}}는 파레토 전선 위에서 각 목적 함수의 최악 값이다.

z_i^{\text{nadir}} = \max_{\mathbf{x} \in \mathcal{P}^*} f_i(\mathbf{x}), \quad i = 1, \ldots, p

이상점과 나디르점은 목적 함수의 정규화(normalization)에 필수적이다.

3. 임무 스코어링 함수 설계

3.1 목적 함수의 식별

로봇 임무 관리에서 스코어링에 활용되는 대표적 목적 함수는 다음과 같다.

목적 함수기호정의최적화 방향
임무 완수 시간f_{\text{time}}임무 시작부터 완료까지의 총 시간최소화
에너지 소비f_{\text{energy}}임무 수행에 소비되는 총 에너지최소화
안전 위험도f_{\text{risk}}충돌, 장애물 접근 등의 위험 지표최소화
임무 커버리지f_{\text{cover}}탐색/감시 영역의 커버율최대화
정보 획득량f_{\text{info}}센서를 통해 획득한 정보량(엔트로피 감소)최대화
자원 잔여율f_{\text{res}}임무 완료 후 잔여 배터리/연료 비율최대화

최대화 목적함수는 부호를 반전하여 최소화 문제로 통일한다.

\min f_i' = -f_i, \quad \text{if } f_i \text{ is to be maximized}

3.2 목적 함수의 정규화

서로 다른 단위와 척도를 갖는 목적 함수를 통합하기 위해서는 정규화가 필수적이다. 이상점-나디르점 기반 정규화(Ideal-Nadir Normalization)는 다음과 같이 수행된다.

\hat{f}_i(\mathbf{x}) = \frac{f_i(\mathbf{x}) - z_i^{\text{ideal}}}{z_i^{\text{nadir}} - z_i^{\text{ideal}}}, \quad i = 1, \ldots, p

정규화된 목적 함수 \hat{f}_i \in [0, 1]은 0이 이상 값, 1이 파레토 전선 내 최악 값에 대응한다.

3.3 가중 합 스코어링(Weighted Sum Scoring)

가장 단순한 스코어링 방법은 가중 합(Weighted Sum) 방식이다.

S(\mathbf{x}) = \sum_{i=1}^{p} w_i \cdot \hat{f}_i(\mathbf{x}), \quad \sum_{i=1}^{p} w_i = 1, \quad w_i \geq 0

여기서 w_i는 i번째 목적에 대한 가중치이다. 이 방법은 구현이 단순하고 직관적이나, 비볼록(non-convex) 파레토 전선의 해를 탐색하지 못하는 본질적 한계가 있다(Das & Dennis, 1997).

3.4 체비셰프 스코어링(Tchebycheff Scoring)

가중 체비셰프(Weighted Tchebycheff) 방법은 비볼록 파레토 전선도 탐색할 수 있다.

S_{\infty}(\mathbf{x}) = \max_{i \in \{1, \ldots, p\}} \; w_i \cdot \left\vert \hat{f}_i(\mathbf{x}) - z_i^{\text{ref}} \right\vert

여기서 \mathbf{z}^{\text{ref}}는 참조점(reference point)으로, 보통 이상점을 사용한다. 이 방법은 모든 파레토 최적해를 원리적으로 빠짐없이 탐색할 수 있음이 증명되어 있다(Miettinen, 1999).

3.5 성취 함수 기반 스코어링(Achievement Scalarizing Function)

성취 함수(Wierzbicki, 1982)는 의사 결정자의 희망 수준(aspiration level) \mathbf{z}^{\text{asp}}를 반영한 스코어링을 제공한다.

S_{\text{ASF}}(\mathbf{x}) = \max_{i \in \{1, \ldots, p\}} \; \frac{\hat{f}_i(\mathbf{x}) - z_i^{\text{asp}}}{w_i} + \rho \sum_{i=1}^{p} \hat{f}_i(\mathbf{x})

여기서 \rho > 0은 미소 보정 파라미터이다. 이 함수는 의사 결정자가 원하는 목표 수준에 가장 가까운 파레토 최적해를 탐색하는 데 유용하다.

4. 다중 목적 최적화 알고리즘

4.1 진화 알고리즘 기반 접근

다중 목적 진화 알고리즘(Multi-Objective Evolutionary Algorithm, MOEA)은 개체군(population) 기반 탐색을 통해 파레토 전선을 근사한다.

NSGA-II(Non-dominated Sorting Genetic Algorithm II): Deb et al.(2002)이 제안한 대표적 MOEA로, 비지배 정렬(non-dominated sorting)과 혼잡 거리(crowding distance)를 결합하여 다양하고 잘 분포된 파레토 전선을 산출한다. 시간 복잡도는 O(p \cdot N^2)이며, 여기서 N은 개체군 크기이다.

MOEA/D(Multi-Objective Evolutionary Algorithm based on Decomposition): Zhang & Li(2007)가 제안한 분해 기반 알고리즘으로, MOOP를 다수의 스칼라 최적화 부분 문제(subproblem)로 분해하고, 이웃하는 부분 문제 간 정보를 공유하여 효율적으로 탐색한다.

NSGA-III: 3개 이상의 목적 함수를 다루는 다목적(many-objective) 문제에 적합한 참조점 기반 선택 알고리즘이다(Deb & Jain, 2014).

4.2 수학적 프로그래밍 기반 접근

정확한 최적해가 필요하거나 목적 함수가 볼록인 경우, 수학적 프로그래밍 기법을 적용한다.

ε-제약법(ε-Constraint Method): 하나의 목적 함수만 최적화하고, 나머지 목적 함수를 제약 조건으로 변환한다.

\min_{\mathbf{x}} f_1(\mathbf{x}) \quad \text{subject to:} \quad f_i(\mathbf{x}) \leq \epsilon_i, \quad i = 2, \ldots, p

\epsilon_i 값을 체계적으로 변화시키면서 반복 풀이하면 파레토 전선의 근사를 얻는다.

목표 계획법(Goal Programming): 각 목적 함수에 대해 목표값 T_i를 설정하고, 목표로부터의 편차를 최소화한다.

\min_{\mathbf{x}} \sum_{i=1}^{p} \left( w_i^+ \cdot d_i^+ + w_i^- \cdot d_i^- \right)

\text{subject to:} \quad f_i(\mathbf{x}) - d_i^+ + d_i^- = T_i, \quad d_i^+, d_i^- \geq 0

여기서 d_i^+는 양의 편차(초과), d_i^-는 음의 편차(미달)이다.

5. 가중치 결정 기법

5.1 전문가 판단 기반 직접 할당

도메인 전문가가 각 목적의 상대적 중요도를 직접 수치로 지정하는 방법이다. 구현이 간편하나, 주관적 편향이 개입하며 목적 수가 증가하면 일관된 가중치 설정이 어려워진다.

5.2 계층 분석 과정(AHP)

Saaty(1980)가 제안한 계층 분석 과정(Analytic Hierarchy Process, AHP)은 목적 함수 쌍별 비교(pairwise comparison)를 통해 체계적으로 가중치를 도출한다. 비교 행렬 \mathbf{A} = [a_{ij}]를 구성하고, 최대 고유벡터를 산출하여 가중치로 변환한다.

\mathbf{A} \mathbf{w} = \lambda_{\max} \mathbf{w}

여기서 \lambda_{\max}는 최대 고유값, \mathbf{w}는 가중치 벡터이다. 일관성 비율(Consistency Ratio, CR)을 검증하여 쌍별 비교의 논리적 일관성을 확인한다.

\text{CR} = \frac{\text{CI}}{\text{RI}} = \frac{(\lambda_{\max} - p) / (p - 1)}{\text{RI}(p)}

일반적으로 \text{CR} < 0.1이면 일관성이 수용 가능한 것으로 판단한다.

5.3 적응적 가중치 조정

임무 실행 중 환경 변화에 따라 목적 함수의 상대적 중요도가 변할 수 있다. 예를 들어, 배터리 잔량이 저하되면 에너지 소비 목적의 가중치가 증가해야 한다. 이를 위한 적응적 가중치 조정 모델은 다음과 같다.

w_i(t) = \frac{\phi_i(s(t))}{\sum_{j=1}^{p} \phi_j(s(t))}

여기서 s(t)는 시간 t에서의 시스템 상태, \phi_i(s(t))는 상태에 따른 목적 i의 긴급도 함수이다.

6. 불확실성하의 임무 스코어링

6.1 확률적 목적 함수

실제 로봇 임무에서 목적 함수의 값은 센서 노이즈, 환경 변동, 모델 불확실성 등에 의해 확률적으로 변동한다. 확률적 목적 함수는 확률 변수로 모델링된다.

\tilde{f}_i(\mathbf{x}) = f_i(\mathbf{x}) + \varepsilon_i, \quad \varepsilon_i \sim \mathcal{N}(0, \sigma_i^2)

6.2 기대값-분산 스코어링

불확실성을 반영한 스코어링은 기대값과 분산을 동시에 고려한다.

S_{\text{EV}}(\mathbf{x}) = \sum_{i=1}^{p} w_i \cdot \left[ \mathbb{E}[\tilde{f}_i(\mathbf{x})] + \lambda \cdot \sqrt{\text{Var}[\tilde{f}_i(\mathbf{x})]} \right]

여기서 \lambda \geq 0은 위험 회피 계수(risk aversion coefficient)이다. \lambda가 클수록 분산이 큰(불확실성이 높은) 임무에 불이익을 부여한다.

6.3 CVaR(Conditional Value at Risk) 기반 스코어링

극단적 위험을 관리하기 위해 조건부 위험가치(CVaR)를 활용한 스코어링도 가능하다.

\text{CVaR}_\alpha(f_i) = \mathbb{E}\left[ f_i \mid f_i \geq \text{VaR}_\alpha(f_i) \right]

여기서 \text{VaR}_\alpha는 신뢰 수준 \alpha에서의 위험가치(Value at Risk)이다. CVaR 기반 스코어링은 합리적 최악 시나리오(rational worst case)에서의 성능을 고려함으로써, 안전 필수(safety-critical) 임무에 적합하다.

7. 실용적 구현 고려 사항

7.1 실시간 스코어링의 계산 효율

임무 재계획이나 동적 임무 할당 시, 스코어링은 밀리초 단위의 실시간 요구를 만족해야 한다. 계산 효율을 확보하기 위한 전략은 다음과 같다.

  • 사전 계산 테이블(Look-Up Table): 대표적 임무 시나리오에 대한 스코어를 사전 계산하여 저장한다.
  • 대리 모델(Surrogate Model): 복잡한 목적 함수를 가우시안 프로세스(Gaussian Process)나 신경망으로 근사하여 평가 시간을 단축한다.
  • 점진적 정제(Progressive Refinement): 초기에는 저해상도 스코어링으로 빠르게 후보를 필터링하고, 상위 후보에 대해서만 정밀 평가를 수행한다.

7.2 의사 결정 지원 시각화

파레토 전선을 운영자에게 시각적으로 제시하여 최종 선택을 지원한다. 목적 함수가 2~3개인 경우 산점도나 3D 표면으로 직접 시각화할 수 있으며, 4개 이상인 경우 평행 좌표(parallel coordinates) 플롯이나 방사형 차트(radar chart)를 활용한다.

7.3 선호 학습(Preference Learning)

운영자의 반복적 선택 데이터를 축적하여, 암묵적 선호를 가중치로 학습하는 기법이다. 임무 스코어링 결과에 대한 운영자의 승인/거부 피드백을 수집하고, 이를 바탕으로 가중치 벡터를 베이지안 추론 또는 서포트 벡터 학습으로 갱신한다.

8. 한계와 연구 과제

다중 목적 최적화 기반 임무 스코어링 체계의 주요 한계와 과제는 다음과 같다.

  1. 목적 함수 간 상관관계: 임무 시간과 에너지 소비 등 강한 상관관계를 갖는 목적 함수가 존재할 때, 불필요한 차원 팽창이 발생한다. 주성분 분석(PCA) 등을 통한 목적 공간 축소가 필요하다.

  2. 다목적(Many-Objective) 문제의 확장성: 목적 함수 수가 4개 이상으로 증가하면, 파레토 전선의 차원이 급증하여 대부분의 해가 비지배 상태가 되고 선별력이 저하된다.

  3. 동적 목적 함수: 임무 실행 중 목적 함수 자체가 변화하는 경우(예: 새로운 위험 요소 출현), 스코어링 체계의 실시간 재구성이 필요하다.

  4. 주관적 가중치의 일관성: 운영자마다 상이한 선호를 가지므로, 일관되고 재현 가능한 가중치 설정 방법론의 확립이 과제이다.

9. 참고 문헌

  • Deb, K., Pratap, A., Agarwal, S., & Meyarivan, T. (2002). “A Fast and Elitist Multiobjective Genetic Algorithm: NSGA-II.” IEEE Transactions on Evolutionary Computation, 6(2), 182–197.
  • Deb, K., & Jain, H. (2014). “An Evolutionary Many-Objective Optimization Algorithm Using Reference-Point-Based Nondominated Sorting Approach, Part I.” IEEE Transactions on Evolutionary Computation, 18(4), 577–601.
  • Zhang, Q., & Li, H. (2007). “MOEA/D: A Multiobjective Evolutionary Algorithm Based on Decomposition.” IEEE Transactions on Evolutionary Computation, 11(6), 712–731.
  • Das, I., & Dennis, J. E. (1997). “A Closer Look at Drawbacks of Minimizing Weighted Sums of Objectives for Pareto Set Generation in Multicriteria Optimization Problems.” Structural Optimization, 14(1), 63–69.
  • Miettinen, K. (1999). Nonlinear Multiobjective Optimization. Springer.
  • Saaty, T. L. (1980). The Analytic Hierarchy Process. McGraw-Hill.
  • Wierzbicki, A. P. (1982). “A Mathematical Basis for Satisficing Decision Making.” Mathematical Modelling, 3(5), 391–405.

본 절은 로봇공학 서적 시리즈의 일부로서 버전 1.0(2026년 3월)에 해당한다.