397.73 계획 품질과 최적성 갭 분석

1. 서론

임무 계획(Mission Planning) 알고리즘이 생성한 계획의 품질(Plan Quality)을 평가하는 것은 알고리즘의 실용적 가치를 판단하는 데 핵심적인 과정이다. 특히 대규모 임무 계획 문제에서는 최적 해(Optimal Solution)를 도출하는 것이 계산적으로 난해(Intractable)하므로, 근사 해(Approximate Solution)의 품질을 최적 해와의 차이, 즉 최적성 갭(Optimality Gap)을 통해 정량적으로 분석하는 것이 필수적이다. 본 절에서는 계획 품질의 다양한 정의와 측정 방법론, 최적성 갭의 수학적 형식화, 그리고 갭 축소를 위한 알고리즘적 전략을 상세히 기술한다.

2. 계획 품질의 다차원적 정의

2.1 비용 기반 품질 (Cost-Based Quality)

계획 품질의 가장 기본적인 정의는 비용 함수(Cost Function)에 기반한다. 임무 계획 \pi = \langle a_1, a_2, \ldots, a_n \rangle에 대해 비용 기반 품질은 다음과 같이 정의된다.

Q_{\text{cost}}(\pi) = C_{\text{total}}(\pi) = \sum_{i=1}^{n} c(a_i, s_i)

비용 함수 c(a_i, s_i)는 도메인에 따라 다양한 형태를 취하며, 대표적인 비용 모델은 다음과 같다.

비용이 낮을수록 계획 품질이 높은 것으로 판정되며, 최소 비용 계획 \pi^*는 다음을 만족한다.

\pi^* = \arg\min_{\pi \in \Pi_{\text{valid}}} C_{\text{total}}(\pi)

여기서 \Pi_{\text{valid}}는 모든 유효한(Valid) 계획의 집합이다.

2.2 다기준 품질 (Multi-Criteria Quality)

실제 임무 계획에서는 단일 비용 지표만으로 품질을 평가하는 것이 불충분하다. 다기준 품질 평가에서는 복수의 품질 요소를 벡터로 표현한다.

\mathbf{Q}(\pi) = \left( Q_1(\pi), Q_2(\pi), \ldots, Q_k(\pi) \right)

각 Q_i는 독립적인 품질 차원(Quality Dimension)을 나타내며, 대표적으로 다음의 요소가 포함된다.

• 비용 효율성(Cost Efficiency): 총 임무 비용의 최소화 정도
• 시간 효율성(Time Efficiency): 메이크스팬(Makespan)의 최소화 정도
• 안전성(Safety): 위험 영역 회피의 정도
• 강건성(Robustness): 환경 섭동에 대한 성능 유지 능력
• 공정성(Fairness): 다중 로봇 간 과업 분배의 균형 정도

다기준 품질에서는 모든 차원을 동시에 최적화할 수 없는 경우가 일반적이며, 파레토 최적(Pareto Optimal) 해 집합의 식별이 중요하다.

2.3 IPC 품질 점수 (IPC Quality Score)

국제 계획 경진 대회(IPC)에서 채택하는 표준화된 품질 점수는 다음과 같이 정의된다.

Q_{\text{IPC}}(p, i) = \frac{C^*(i)}{C_p(i)}

여기서 C_p(i)는 계획기 p가 인스턴스 i에 대해 생성한 계획의 비용, C^*(i)는 해당 인스턴스에 대한 모든 참가 계획기 중 최소 비용이다. Q_{\text{IPC}} = 1이면 최고 품질이며, 0 < Q_{\text{IPC}} < 1이면 상대적으로 품질이 낮음을 나타낸다. 인스턴스를 해결하지 못한 경우 Q_{\text{IPC}} = 0이다.

계획기의 전체 품질 점수는 벤치마크 인스턴스 집합 \mathcal{I}에 대한 합으로 산출된다.

Q_{\text{IPC}}^{\text{total}}(p) = \sum_{i \in \mathcal{I}} Q_{\text{IPC}}(p, i)

3. 최적성 갭의 수학적 형식화

3.1 절대 최적성 갭 (Absolute Optimality Gap)

절대 최적성 갭 \Delta_{\text{abs}}는 현재 해의 비용과 최적 해의 비용 사이의 절대적 차이로 정의된다.

\Delta_{\text{abs}}(\pi) = C_{\text{total}}(\pi) - C_{\text{total}}(\pi^*)

\Delta_{\text{abs}} = 0이면 최적 해이며, \Delta_{\text{abs}} > 0이면 차선 해(Sub-optimal Solution)이다. 이 지표는 비용의 절대적 크기에 의존하므로, 상이한 규모의 문제 간 비교에는 적합하지 않다.

3.2 상대 최적성 갭 (Relative Optimality Gap)

상대 최적성 갭 \Delta_{\text{rel}}은 절대 갭을 최적 해의 비용으로 정규화한 것이다.

\Delta_{\text{rel}}(\pi) = \frac{C_{\text{total}}(\pi) - C_{\text{total}}(\pi^*)}{C_{\text{total}}(\pi^*)} \times 100\%

이 지표는 문제 규모에 독립적이므로, 상이한 인스턴스 간 갭의 비교가 가능하다.

3.3 하한 기반 최적성 갭 (Lower Bound Based Gap)

대규모 조합 최적화 문제에서는 최적 해 \pi^*를 직접 구하는 것이 불가능한 경우가 많다. 이 경우 최적 비용의 하한(Lower Bound) \underline{C}를 활용하여 최적성 갭의 상한을 추정한다.

\Delta_{\text{UB}}(\pi) = \frac{C_{\text{total}}(\pi) - \underline{C}}{\underline{C}} \times 100\%

하한 \underline{C}는 문제의 완화(Relaxation)를 통해 도출할 수 있다. 주요 완화 기법은 다음과 같다.

3.3.1 LP 완화 (Linear Programming Relaxation)

정수 계획(Integer Programming) 문제의 정수 제약을 완화하여 선형 계획(LP) 문제로 변환한다. LP 완화의 최적 해 값은 원 문제의 하한이 된다.

\underline{C}_{\text{LP}} = \min \{ \mathbf{c}^\top \mathbf{x} : A\mathbf{x} \leq \mathbf{b}, \mathbf{x} \geq \mathbf{0} \}

3.3.2 라그랑주 완화 (Lagrangian Relaxation)

난해한 제약 조건을 목적 함수에 페널티 항으로 흡수하여 문제를 단순화한다. 라그랑주 승수(Lagrange Multiplier) \boldsymbol{\lambda} \geq \mathbf{0}에 대해 다음과 같이 정의된다.

L(\boldsymbol{\lambda}) = \min_{\mathbf{x} \in X} \left\{ \mathbf{c}^\top \mathbf{x} + \boldsymbol{\lambda}^\top (\mathbf{A}\mathbf{x} - \mathbf{b}) \right\}

라그랑주 이중(Lagrangian Dual) 문제 \max_{\boldsymbol{\lambda} \geq \mathbf{0}} L(\boldsymbol{\lambda})의 최적 값은 LP 완화보다 더 강건한(Tighter) 하한을 제공하거나 동일한 하한을 제공한다 (Fisher, 2004).

3.3.3 휴리스틱 기반 하한

도메인 특화 휴리스틱을 활용하여 하한을 도출할 수 있다. 예를 들어, 순회 외판원 문제(Traveling Salesman Problem, TSP) 기반 임무 계획에서 최소 신장 트리(Minimum Spanning Tree, MST) 비용은 TSP 최적 비용의 하한이 된다.

\underline{C}_{\text{MST}} \leq C_{\text{TSP}}^*

3.4 이중 갭 (Duality Gap)

수리 최적화에서 이중 갭(Duality Gap)은 원 문제(Primal Problem)의 현재 상한(Upper Bound)과 이중 문제(Dual Problem)의 현재 하한 사이의 차이로 정의된다.

\Delta_{\text{dual}} = C_{\text{UB}} - C_{\text{LB}}

여기서 C_{\text{UB}}는 현재 실행 가능 해의 비용(상한), C_{\text{LB}}는 이중 문제로부터 도출된 하한이다. 최적 해에서는 강한 이중성(Strong Duality) 조건 하에서 \Delta_{\text{dual}} = 0이 성립한다.

이중 갭의 상대적 비율은 다음과 같이 정의된다.

\Delta_{\text{dual}}^{\%} = \frac{C_{\text{UB}} - C_{\text{LB}}}{C_{\text{LB}}} \times 100\%

이 지표는 분기 한정법(Branch and Bound) 등의 정확한 해법(Exact Method)에서 탐색 종료 기준으로 활용된다. 예를 들어, \Delta_{\text{dual}}^{\%} \leq \epsilon이면 현재 해가 \epsilon-최적(Epsilon-Optimal)임을 보장하고 탐색을 종료한다.

4. 최적성 갭의 이론적 보장

4.1 근사 비율 (Approximation Ratio)

근사 알고리즘(Approximation Algorithm)은 최적 해에 대한 성능 비율의 이론적 보장을 제공한다. \alpha-근사 알고리즘은 다음을 만족한다.

C_{\text{total}}(\pi) \leq \alpha \cdot C_{\text{total}}(\pi^*), \quad \alpha \geq 1

\alpha를 근사 비율(Approximation Ratio) 또는 성능 보장(Performance Guarantee)이라 한다. \alpha가 1에 가까울수록 알고리즘의 품질 보장이 강력하다.

대표적인 임무 계획 관련 근사 비율은 다음과 같다.

4.2 확률적 근사 보장 (Probabilistic Approximation Guarantee)

확률적 알고리즘(예: 시뮬레이티드 어닐링, 유전 알고리즘)의 경우 결정론적 근사 비율 대신 확률적 근사 보장이 제공되기도 한다.

\Pr\left[ C_{\text{total}}(\pi) \leq (1 + \epsilon) \cdot C_{\text{total}}(\pi^*) \right] \geq 1 - \delta

여기서 \epsilon은 허용 오차, \delta는 실패 확률이다. 이러한 보장은 확률적 근사 체계(Probabilistic Approximation Scheme, PAS)로 분류된다.

4.3 경쟁 비율 (Competitive Ratio)

온라인 임무 계획(Online Mission Planning)에서는 미래 정보 없이 순차적으로 결정을 내려야 하므로, 오프라인 최적 해에 대한 경쟁 비율(Competitive Ratio)로 성능을 평가한다.

\text{CR} = \sup_{\sigma \in \Sigma} \frac{C_{\text{online}}(\sigma)}{C_{\text{offline}}^*(\sigma)}

여기서 \sigma는 입력 시퀀스, \Sigma는 가능한 모든 입력 시퀀스의 집합이다. \text{CR}이 1에 가까울수록 온라인 알고리즘의 성능이 오프라인 최적 해에 근접함을 의미한다 (Borodin and El-Yaniv, 1998).

5. 최적성 갭 축소 전략

5.1 에니타임 탐색 전략

에니타임(Anytime) 탐색 알고리즘은 시간이 경과함에 따라 점진적으로 최적성 갭을 축소한다. 대표적인 에니타임 탐색 전략은 다음과 같다.

5.1.1 가중 A* (Weighted A*)

가중 A* 알고리즘은 표준 A*의 평가 함수를 다음과 같이 변형한다.

f(n) = g(n) + w \cdot h(n), \quad w \geq 1

여기서 w는 가중치(Weight) 파라미터이다. w > 1일 때 해를 신속하게 발견하지만, 최적성 갭은 (\Delta_{\text{rel}} \leq (w-1) \times 100\%)로 상한이 주어진다. 초기에 큰 w 값으로 시작하여 점진적으로 w \to 1로 감소시키면 에니타임 성능을 달성할 수 있다 (Likhachev, Gordon, and Thrun, 2003).

5.1.2 ARA* (Anytime Repairing A*)

ARA* 알고리즘은 가중 A*의 가중치 w를 점진적으로 감소시키면서 이전 탐색 결과를 재활용(Reuse)한다. 각 반복에서 w-최적 해가 보장되며, 충분한 시간이 주어지면 정확한 최적 해에 수렴한다.

w_k = w_0 - k \cdot \Delta w, \quad k = 0, 1, 2, \ldots

여기서 w_0는 초기 가중치, \Delta w는 가중치 감소량이다. 가중치 w_k에서의 최적성 갭 보장은 \Delta_{\text{rel}} \leq (w_k - 1) \times 100\%이다.

5.2 분기 한정법 기반 갭 축소

분기 한정법(Branch and Bound)은 체계적 탐색을 통해 최적성 갭을 정확히 제어하는 방법이다. 알고리즘 실행 중 상한 C_{\text{UB}}와 하한 C_{\text{LB}}가 동시에 갱신되며, 이들 사이의 갭이 허용 오차 이하가 되면 탐색을 종료한다.

분기 한정법의 효율성은 다음 요소에 의해 결정된다.

1. 분기 전략(Branching Strategy): 탐색 트리의 분기 방식으로, 최대 분수 분기(Most Fractional Branching), 강한 분기(Strong Branching) 등이 있다.
2. 하한 품질(Lower Bound Quality): 강건한 하한은 더 많은 노드를 가지치기(Pruning)하여 탐색 효율을 높인다.
3. 상한 갱신(Upper Bound Update): 좋은 실행 가능 해를 조기에 발견할수록 가지치기 효과가 증대된다.

5.3 대규모 이웃 탐색 (Large Neighborhood Search)

대규모 이웃 탐색(Large Neighborhood Search, LNS)은 현재 해의 일부를 파괴(Destroy)하고 재구성(Repair)하는 과정을 반복하여 최적성 갭을 축소하는 메타휴리스틱 기법이다 (Ropke and Pisinger, 2006).

\pi_{k+1} = \text{Repair}(\text{Destroy}(\pi_k))

적응형 대규모 이웃 탐색(Adaptive Large Neighborhood Search, ALNS)은 복수의 파괴-재구성 연산자 쌍을 유지하고, 과거 성능에 기반하여 연산자 선택 확률을 적응적으로 조절한다.

w_j^{k+1} = (1 - \rho) \cdot w_j^k + \rho \cdot \frac{\pi_j^k}{n_j^k}

여기서 w_j^k는 연산자 j의 k번째 세그먼트에서의 가중치, \pi_j^k는 획득 점수, n_j^k는 사용 횟수, \rho는 학습률이다.

6. 갭 분석의 시각화 기법

6.1 수렴 곡선 (Convergence Curve)

에니타임 알고리즘의 갭 축소 과정을 시각화하기 위해 수렴 곡선(Convergence Curve)을 활용한다. 수렴 곡선은 시간 t에 대한 현재 최선의 해 비용 C_{\text{best}}(t)와 하한 \underline{C}(t)를 동시에 도시하여, 갭의 시간적 변화를 관찰할 수 있게 한다.

\Delta(t) = \frac{C_{\text{best}}(t) - \underline{C}(t)}{\underline{C}(t)} \times 100\%

수렴 곡선의 기울기가 완만해지는 지점은 알고리즘이 수확 체감(Diminishing Returns) 구간에 진입함을 나타내며, 이 지점에서 탐색 종료를 결정할 수 있다.

6.2 갭 분포 히스토그램

벤치마크 인스턴스 집합에 대한 최적성 갭의 분포를 히스토그램으로 표현함으로써, 알고리즘의 전반적 품질 프로파일을 파악할 수 있다. 갭 분포의 분석에서 주요 통계량은 다음과 같다.

• 평균 갭(Mean Gap): 전체 인스턴스에 대한 평균 최적성 갭
• 최대 갭(Maximum Gap): 최악의 경우 최적성 갭
• 갭 표준 편차(Gap Standard Deviation): 갭의 변동성
• 갭 백분위수(Gap Percentile): 특정 비율의 인스턴스가 달성하는 갭 수준

6.3 성능 프로파일 (Performance Profile)

복수의 알고리즘 간 갭 비교를 위해 성능 프로파일(Performance Profile)이 활용된다. 알고리즘 p의 성능 프로파일은 다음과 같이 정의된다.

\rho_p(\tau) = \frac{|\{i \in \mathcal{I} : \Delta_p(i) \leq \tau \cdot \min_{p'} \Delta_{p'}(i)\}|}{|\mathcal{I}|}

성능 프로파일은 다수의 알고리즘의 갭 분포를 하나의 차트에서 비교할 수 있게 하며, \rho_p(1) 값이 높을수록 해당 알고리즘이 가장 작은 갭을 달성하는 인스턴스의 비율이 높음을 의미한다.

7. 도메인별 갭 분석 사례

7.1 PDDL 기반 임무 계획

PDDL 기반 임무 계획에서는 IPC 벤치마크 도메인을 통해 갭 분석이 수행된다. 최적 계획기(예: A* 기반)와 만족형 계획기(Satisficing Planner, 예: LAMA)의 갭 비교가 대표적이다. Richter and Westphal (2010)은 LAMA 계획기가 IPC 벤치마크에서 평균 30% 이내의 갭으로 해를 신속하게 도출함을 보고하였다.

7.2 다중 로봇 과업 할당

다중 로봇 과업 할당(Multi-Robot Task Allocation, MRTA) 문제에서 최적성 갭은 메이크스팬 또는 총 비용에 대해 분석된다. 정확한 최적 해는 혼합 정수 선형 계획(MILP) 풀이를 통해 도출되며, 이를 기준으로 경매 기반(Auction-Based) 및 탐욕 기반(Greedy) 알고리즘의 갭이 평가된다.

7.3 무인 항공기 경로 계획

무인 항공기(UAV) 경로 계획에서는 에너지 제약을 포함한 순회 경로 문제가 핵심이며, TSP 또는 차량 경로 문제(VRP) 변형으로 모델링된다. 이 도메인에서의 갭 분석은 Christofides 알고리즘의 3/2 근사 비율 또는 LKH(Lin-Kernighan-Helsgott) 알고리즘의 경험적 갭을 기준으로 수행된다 (Helsgaun, 2017).

8. 요약

계획 품질의 평가는 비용 기반 단일 지표에서부터 다기준 벡터 평가에 이르기까지 다양한 수준에서 수행될 수 있다. 최적성 갭은 이러한 품질 평가에서 가장 정량적이고 객관적인 도구로서, 절대 갭, 상대 갭, 하한 기반 갭, 이중 갭 등의 형태로 형식화된다. 대규모 문제에서 최적 해를 직접 구할 수 없는 경우에도, LP 완화, 라그랑주 완화, 도메인 특화 하한 등을 통해 갭의 상한을 추정할 수 있다. 에니타임 탐색, 분기 한정법, 대규모 이웃 탐색 등의 전략은 갭을 체계적으로 축소하는 데 활용되며, 수렴 곡선과 성능 프로파일 등의 시각화 도구를 통해 갭 축소 과정과 알고리즘 간 비교가 효과적으로 수행된다.

참고 문헌

• Borodin, A. and El-Yaniv, R. (1998). Online Computation and Competitive Analysis. Cambridge University Press.
• Fisher, M. L. (2004). “The Lagrangian Relaxation Method for Solving Integer Programming Problems.” Management Science, 50(12), 1861–1871.
• Helsgaun, K. (2017). “An Extension of the Lin-Kernighan-Helsgott TSP Solver for Constrained Traveling Salesman and Vehicle Routing Problems.” Technical Report, Roskilde University.
• Likhachev, M., Gordon, G. J., and Thrun, S. (2003). “ARA*: Anytime A* with Provable Bounds on Sub-Optimality.” Proceedings of the Conference on Neural Information Processing Systems (NeurIPS).
• Richter, S. and Westphal, M. (2010). “The LAMA Planner: Guiding Cost-Based Anytime Planning with Landmarks.” Journal of Artificial Intelligence Research, 39, 127–177.
• Ropke, S. and Pisinger, D. (2006). “An Adaptive Large Neighborhood Search Heuristic for the Pickup and Delivery Problem with Time Windows.” Transportation Science, 40(4), 455–472.

version: 1.0