397.52 다목적 임무 계획(Multi-Objective Mission Planning)

1. 개요

다목적 임무 계획(multi-objective mission planning)은 로봇이 수행해야 할 임무에 내재된 복수의 상충하는 목적 함수를 동시에 고려하여 최적의 행동 계획을 수립하는 방법론이다. 실제 로봇 운용에서는 임무 완수 시간의 최소화, 에너지 소모의 절감, 경로 안전성의 극대화, 서비스 품질의 보장 등 다수의 성능 기준이 동시에 요구되며, 이들 기준은 일반적으로 상호 상충(trade-off) 관계에 있다.

단일 목적 최적화(single-objective optimization)에서는 유일한 최적해가 존재하는 것이 일반적이나, 다목적 최적화에서는 목적 함수 간의 상충으로 인해 단일 최적해 대신 파레토 최적 해 집합(Pareto-optimal solution set)이 도출된다. 다목적 임무 계획의 과제는 이러한 파레토 해 집합을 효율적으로 탐색하고, 의사 결정자(운영자)가 임무 상황에 적합한 해를 선택할 수 있도록 지원하는 것이다.

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_k(\mathbf{x}) \right]^T

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

\quad h_l(\mathbf{x}) = 0, \quad l = 1, \ldots, p

여기서 \mathbf{x}는 결정 변수 벡터(임무 계획의 경우 행동 시퀀스, 경로, 자원 할당 등), \mathcal{X}는 실행 가능 영역, f_i는 i번째 목적 함수, g_j는 부등식 제약, h_l은 등식 제약이다.

2.2 지배 관계

두 실행 가능 해 \mathbf{x}_1, \mathbf{x}_2 \in \mathcal{X}에 대해, \mathbf{x}_1이 \mathbf{x}_2를 지배(dominate)한다 함은 다음 조건이 성립함을 의미한다:

\mathbf{x}_1 \prec \mathbf{x}_2 \iff \forall i : f_i(\mathbf{x}_1) \leq f_i(\mathbf{x}_2) \wedge \exists j : f_j(\mathbf{x}_1) < f_j(\mathbf{x}_2)

즉, 모든 목적에서 \mathbf{x}_1이 \mathbf{x}_2 이상의 성능을 보이면서, 적어도 하나의 목적에서 엄격히 우수해야 한다.

2.3 파레토 최적성

해 \mathbf{x}^* \in \mathcal{X}가 파레토 최적(Pareto-optimal)이라 함은, \mathbf{x}^*를 지배하는 다른 실행 가능 해가 존재하지 않음을 의미한다:

\nexists \mathbf{x} \in \mathcal{X} : \mathbf{x} \prec \mathbf{x}^*

파레토 최적 해의 집합을 파레토 전선(Pareto front)이라 하며, 이는 목적 공간(objective space)에서 비열등 해(non-dominated solution)들의 경계면을 형성한다.

2.4 파레토 전선의 기하학적 해석

k개의 목적 함수에 대한 파레토 전선은 k-차원 목적 공간의 (k-1)-차원 초곡면(hypersurface)으로 표현된다. 2-목적 문제에서 파레토 전선은 평면 위의 곡선으로, 3-목적 문제에서는 3차원 공간의 곡면으로 나타난다. 파레토 전선의 형상(볼록, 비볼록, 불연속 등)은 문제의 특성에 따라 달라지며, 알고리즘 선택에 영향을 미친다.

3. 로봇 임무 계획에서의 목적 함수

3.1 대표적 목적 함수

로봇 임무 계획에서 흔히 고려되는 목적 함수는 다음과 같다:

1. 임무 완수 시간(Makespan): 모든 임무 과업이 완료되기까지 소요되는 총 시간을 최소화한다.

f_{\text{time}} = \max_{i} T_{\text{completion}}^{(i)}

2. 총 이동 거리(Total travel distance): 로봇이 이동하는 총 경로 거리를 최소화한다.

f_{\text{dist}} = \sum_{t=0}^{T-1} d(s_t, s_{t+1})

3. 에너지 소모(Energy consumption): 이동, 작업, 통신 등에 소비되는 총 에너지를 최소화한다.

f_{\text{energy}} = \sum_{t=0}^{T-1} E(a_t, s_t)

4. 위험 노출(Risk exposure): 위험 영역 통과 빈도 또는 불확실한 환경에서의 임무 실패 확률을 최소화한다.

f_{\text{risk}} = \sum_{t=0}^{T-1} r(s_t)

5. 서비스 품질(Quality of Service): 임무 요청에 대한 응답 지연, 서비스 커버리지 등 품질 지표를 최대화(또는 품질 결손을 최소화)한다.

6. 통신 연결성(Communication connectivity): 다중 로봇 환경에서 로봇 간 통신 네트워크의 연결성을 유지한다.

3.2 목적 간 상충 관계

임무 완수 시간과 에너지 소모는 전형적 상충 관계에 있다. 빠른 임무 수행을 위해 고속 이동하면 에너지 소모가 증가하고, 에너지 절약을 위해 저속 이동하면 임무 시간이 연장된다. 유사하게, 안전 경로(위험 회피)는 통상 최단 경로보다 길어지므로 이동 거리와 안전성 사이에도 상충이 존재한다.

4. 스칼라화 기법

4.1 가중합 방법(Weighted Sum Method)

가중합 방법은 다목적 문제를 단일 목적 문제로 변환하는 가장 기본적 방법이다. 각 목적 함수에 가중치 w_i \geq 0을 부여하여 합산된 스칼라 목적 함수를 최소화한다:

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

가중합 방법의 장점은 단일 목적 최적화 알고리즘을 직접 적용할 수 있다는 것이다. 그러나 비볼록(non-convex) 파레토 전선의 경우, 가중치 조합에 관계없이 도달할 수 없는 파레토 최적 해가 존재할 수 있다는 근본적 한계가 있다.

4.2 ε-제약법(ε-Constraint Method)

ε-제약법은 하나의 목적 함수를 주 목적으로 선택하고, 나머지 목적 함수를 상한 제약으로 변환하는 방법이다:

\min_{\mathbf{x} \in \mathcal{X}} f_1(\mathbf{x})

\text{subject to} \quad f_i(\mathbf{x}) \leq \epsilon_i, \quad i = 2, \ldots, k

\epsilon_i의 체계적 변동을 통해 파레토 전선의 다양한 지점을 탐색할 수 있으며, 비볼록 파레토 전선에도 적용 가능하다는 장점이 있다.

4.3 체비셰프 방법(Tchebycheff Method)

체비셰프 방법은 이상점(utopia point) \mathbf{z}^* = (z_1^*, z_2^*, \ldots, z_k^*)로부터의 체비셰프 거리(가중 무한대 노름)를 최소화한다:

\min_{\mathbf{x} \in \mathcal{X}} \max_{i=1,\ldots,k} w_i \lvert f_i(\mathbf{x}) - z_i^* \rvert

여기서 z_i^* = \min_{\mathbf{x} \in \mathcal{X}} f_i(\mathbf{x})는 i번째 목적의 개별 최적값이다. 이 방법은 볼록 및 비볼록 파레토 전선 모두에 적용 가능하다.

5. 진화 기반 다목적 최적화

5.1 NSGA-II

NSGA-II(Non-dominated Sorting Genetic Algorithm II)는 Deb, Pratap, Agarwal, Meyarivan(2002)이 제안한 대표적 다목적 진화 알고리즘이다. 이 알고리즘은 다음의 핵심 메커니즘을 포함한다:

1. 비지배 정렬(Non-dominated sorting): 해 집단(population)을 비지배 수준(front)에 따라 계층적으로 분류한다. 제1전선(first front)의 해들은 집단 내에서 비지배적이며, 제2전선의 해들은 제1전선의 해만 지배하는 식이다.

2. 군집 거리(Crowding distance): 동일 비지배 전선 내에서 해들의 다양성을 유지하기 위해, 각 해의 주변 밀도를 측정한다. 군집 거리가 큰 해가 선호되어 파레토 전선의 균일한 분포가 촉진된다.

3. 토너먼트 선택(Tournament selection): 비지배 수준이 낮은(좋은) 해를 우선 선택하고, 동일 수준 내에서는 군집 거리가 큰 해를 선택한다.

5.2 MOEA/D

MOEA/D(Multi-Objective Evolutionary Algorithm based on Decomposition)는 Zhang, Li(2007)가 제안한 분해 기반 다목적 진화 알고리즘이다. 다목적 문제를 다수의 단일 목적 부분 문제(subproblem)로 분해하고, 각 부분 문제를 이웃 부분 문제와의 협력을 통해 동시에 최적화한다.

분해 방법으로는 체비셰프 분해, 경계 교차법(boundary intersection), 벌칙 기반 경계 교차법(PBI: Penalty-Based Boundary Intersection) 등이 사용된다.

5.3 로봇 임무 계획에의 적용

진화 기반 다목적 최적화를 로봇 임무 계획에 적용하는 경우, 개체(individual)의 인코딩은 임무의 특성에 따라 달라진다:

• 순서 인코딩(Permutation encoding): 방문 순서를 결정하는 문제(예: 순찰 경로 최적화)에서 사용된다.
• 분할 인코딩(Partition encoding): 다중 로봇에 대한 과업 할당 문제에서 사용된다.
• 이진 인코딩(Binary encoding): 과업 선택/비선택 결정 문제에서 사용된다.

교차(crossover) 및 돌연변이(mutation) 연산자는 임무 계획의 실행 가능성 제약을 준수하도록 설계되어야 한다.

6. 형식 명세와 다목적 최적화의 결합

6.1 LTL 명세 하의 다목적 경로 최적화

형식 임무 명세(LTL)를 만족하면서 복수의 비용 기준을 최적화하는 문제를 고려하자. 이 문제는 다음과 같이 정식화된다:

\min_{\rho \in \mathcal{L}(\mathcal{P})} \left[ J_1(\rho), J_2(\rho), \ldots, J_k(\rho) \right]^T

여기서 \mathcal{P}는 제품 오토마톤, \mathcal{L}(\mathcal{P})는 \mathcal{P}의 수락 실행 집합, J_i(\rho)는 실행 \rho에 대한 i번째 비용 함수이다.

Smith, Tumova, Belta, Rus(2011)는 래소(lasso) 형태의 수락 경로에 대해 접두사 비용과 주기 비용을 벡터 값으로 확장하는 다목적 최적 경로 탐색 알고리즘을 개발하였다.

6.2 다목적 MDP

확률적 환경에서의 다목적 임무 계획은 다목적 마르코프 결정 과정(MOMDP: Multi-Objective Markov Decision Process)으로 모델링된다:

\mathcal{M} = (S, A, P, s_0, \mathbf{r})

여기서 \mathbf{r}: S \times A \rightarrow \mathbb{R}^k는 벡터 값 보상 함수이다. 다목적 MDP에서는 파레토 최적 정책(Pareto-optimal policy)의 집합을 탐색하는 것이 목표이다.

Roijers, Vamplew, Whiteson, Dazeley(2013)의 조사 연구에서는 다목적 순차 의사 결정(multi-objective sequential decision making)의 이론과 알고리즘을 체계적으로 정리하였다.

7. 다중 로봇 환경에서의 다목적 임무 계획

7.1 과업 할당과 경로 계획의 동시 최적화

다중 로봇 다목적 임무 계획에서는 과업 할당(task allocation)과 경로 계획(path planning)을 동시에 최적화해야 한다. 이는 다음과 같은 2-수준 다목적 문제로 구성된다:

• 상위 수준: 각 로봇에 대한 과업 집합의 최적 할당
• 하위 수준: 각 로봇의 할당된 과업에 대한 최적 방문 순서와 경로

이 문제는 다목적 차량 경로 문제(MO-VRP: Multi-Objective Vehicle Routing Problem)의 변형으로서, NP-난해(NP-hard) 문제 클래스에 속한다.

7.2 이질적 로봇 팀의 다목적 계획

이질적(heterogeneous) 로봇 팀에서는 각 로봇의 능력(센서 유형, 적재 용량, 이동 속도, 내구성 등)이 상이하므로, 과업-로봇 적합성(task-robot fitness)이 추가적인 목적 또는 제약으로 반영된다. 이 경우 목적 함수 공간이 확장되어 파레토 전선의 차원이 증가하고, 해 탐색의 계산 복잡도가 심화된다.

8. 의사 결정 지원

8.1 파레토 해 시각화

2-목적 문제에서의 파레토 전선은 2차원 산점도(scatter plot)로 직접 시각화 가능하다. 3-목적 이상의 문제에서는 평행 좌표 플롯(parallel coordinate plot), 방사형 시각화(radar chart), 또는 차원 축소 기법(예: PCA)을 통한 투영이 사용된다.

8.2 선호 통합(Preference Integration)

운영자의 선호(preference)를 다목적 최적화에 통합하는 방법은 세 가지로 분류된다:

1. 사전적 선호 통합(A priori): 최적화 전에 목적 함수의 가중치나 선호 순서를 지정한다. 가중합 방법, 목표 계획법(goal programming) 등이 이에 해당한다.

2. 사후적 선호 통합(A posteriori): 전체 파레토 전선을 먼저 도출한 후, 운영자가 적합한 해를 선택한다. NSGA-II, MOEA/D 등의 진화 알고리즘이 이 접근법에 적합하다.

3. 상호작용적 선호 통합(Interactive): 최적화 과정 중 운영자가 점진적으로 선호를 표명하여 탐색 방향을 유도한다. 인간-로봇 상호작용(HRI) 환경에서의 실시간 임무 계획에 적합하다.

9. 계산 복잡도와 확장성

다목적 임무 계획의 계산 복잡도는 단일 목적 문제에 비해 현저히 증가한다:

확장성 향상을 위한 대표적 기법으로는 참조점 기반 분해(reference point decomposition), 대리 모델(surrogate model) 기반 최적화, 계층적 분해(hierarchical decomposition) 등이 있다.

10. 참고 문헌

• 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), pp. 182–197.
• Zhang, Q., Li, H. (2007). “MOEA/D: A Multiobjective Evolutionary Algorithm Based on Decomposition.” IEEE Transactions on Evolutionary Computation, 11(6), pp. 712–731.
• Smith, S.L., Tumova, J., Belta, C., Rus, D. (2011). “Optimal Path Planning for Surveillance with Temporal-Logic Constraints.” The International Journal of Robotics Research, 30(14), pp. 1695–1708.
• Roijers, D.M., Vamplew, P., Whiteson, S., Dazeley, R. (2013). “A Survey of Multi-Objective Sequential Decision-Making.” Journal of Artificial Intelligence Research, 48, pp. 67–113.
• Miettinen, K. (1999). Nonlinear Multiobjective Optimization. Springer.
• Ehrgott, M. (2005). Multicriteria Optimization. Springer, 2nd edition.

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