397.71 임무 계획의 성능 평가 지표

1. 서론

임무 계획(Mission Planning) 알고리즘의 실용적 가치를 객관적으로 판단하기 위해서는 정량적이고 체계적인 성능 평가 지표(Performance Evaluation Metrics)가 필수적이다. 임무 계획 문제는 본질적으로 다목적 최적화(Multi-Objective Optimization) 문제의 특성을 가지며, 계획 품질(Plan Quality), 계산 효율성(Computational Efficiency), 실행 가능성(Executability), 그리고 강건성(Robustness) 등 다양한 측면에서 동시에 평가되어야 한다. 본 절에서는 임무 계획 알고리즘의 성능을 평가하기 위한 핵심 지표들을 체계적으로 분류하고, 각 지표의 수학적 정의와 적용 맥락을 상세히 기술한다.

2. 성능 평가 지표의 분류 체계

임무 계획의 성능 평가 지표는 크게 다음의 네 가지 범주로 분류할 수 있다.

2.1 계획 생성 효율성 지표

계획 생성 효율성(Planning Generation Efficiency) 지표는 임무 계획 알고리즘이 해를 도출하는 데 소요되는 계산 자원을 정량화한다.

2.1.1 계획 소요 시간 (Planning Time)

계획 소요 시간 $T_{\text{plan}}$ 은 임무 계획 알고리즘이 입력 사양(Specification)을 수신한 시점부터 실행 가능한 계획(Feasible Plan)을 출력하기까지 경과된 벽시계 시간(Wall-Clock Time)으로 정의된다.

$T_{\text{plan}} = t_{\text{output}} - t_{\text{input}}$

여기서 $t_{\text{input}}$ 은 임무 명세 입력 시각, $t_{\text{output}}$ 은 계획 출력 시각이다. 실시간 임무 재계획(Replanning) 시나리오에서는 $T_{\text{plan}}$ 이 시스템의 제어 주기(Control Period) $\Delta t_c$ 보다 작아야 한다는 제약 $T_{\text{plan}} < \Delta t_c$ 가 부과된다.

실시간 시스템에서 특히 중요한 파생 지표로서, 첫 번째 해 도달 시간(Time to First Solution, TTFS)이 있다. 이는 최적화 기반 계획기가 임의의 실행 가능 해를 최초로 발견하는 데 걸리는 시간을 측정하며, 에니타임(Anytime) 알고리즘의 평가에서 핵심적으로 활용된다.

2.1.2 노드 확장 수 (Node Expansion Count)

탐색 기반 계획 알고리즘에서 노드 확장 수 $N_{\text{exp}}$ 는 알고리즘이 해를 찾기까지 확장(Expand)한 탐색 노드의 총 수를 나타낸다. 이 지표는 알고리즘의 탐색 효율성을 하드웨어 독립적으로 비교할 수 있게 한다. A* 알고리즘의 경우, 휴리스틱 함수 $h(n)$ 의 품질이 $N_{\text{exp}}$ 에 직접적인 영향을 미친다. 허용 가능(Admissible)하고 일관성(Consistent) 있는 휴리스틱일수록 $N_{\text{exp}}$ 가 감소한다.

2.1.3 메모리 사용량 (Memory Consumption)

메모리 사용량 $M_{\text{peak}}$ 은 계획 수립 과정에서 소비되는 최대 메모리(Peak Memory)를 바이트 단위로 측정한다. 특히 상태 공간(State Space)이 기하급수적으로 확장되는 대규모 임무 계획 문제에서 메모리 제약은 알고리즘 적용 가능성을 결정짓는 핵심 요소이다. BDD(Binary Decision Diagram) 기반 심볼릭 탐색(Symbolic Search) 기법은 명시적 상태 열거 방식 대비 메모리 사용량을 크게 절감할 수 있다.

2.2 계획 품질 지표

계획 품질(Plan Quality) 지표는 생성된 임무 계획의 우수성을 다양한 관점에서 정량화한다.

2.2.1 총 임무 비용 (Total Mission Cost)

총 임무 비용 $C_{\text{total}}$ 은 계획에 포함된 모든 행동(Action)의 비용 합으로 정의된다. 임무 계획 $\pi = \langle a_1, a_2, \ldots, a_n \rangle$ 에 대하여

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

로 표현된다. 여기서 $c(a_i, s_i)$ 는 상태 $s_i$ 에서 행동 $a_i$ 를 실행할 때의 비용이다. 비용 함수 $c(\cdot)$ 는 도메인에 따라 이동 거리, 에너지 소모량, 시간, 또는 이들의 가중 결합으로 정의될 수 있다.

2.2.2 최적성 비율 (Optimality Ratio)

최적성 비율 $\rho_{\text{opt}}$ 는 생성된 계획의 비용이 최적 해(Optimal Solution)의 비용에 대한 비율로 정의된다.

$\rho_{\text{opt}} = \frac{C_{\text{total}}(\pi)}{C_{\text{total}}(\pi^*)}$

여기서 $\pi^*$ 는 최적 계획이다. $\rho_{\text{opt}} = 1$ 이면 최적 해이며, $\rho_{\text{opt}} > 1$ 이면 차선 해(Sub-optimal Solution)이다. 근사 알고리즘의 경우 이론적 최적성 보장 비율(Approximation Ratio)이 $\rho_{\text{opt}} \leq \alpha$ 의 형태로 제시되기도 한다.

2.2.3 최적성 갭 (Optimality Gap)

최적성 갭(Optimality Gap)은 현재 해와 이론적 최적 해 사이의 절대적 또는 상대적 차이를 나타내며, 다음과 같이 정의된다.

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

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

최적 해를 직접 구할 수 없는 대규모 문제에서는 하한(Lower Bound) $\underline{C}$ 를 활용하여 $\Delta_{\text{opt}}^{\%} \leq \frac{C_{\text{total}}(\pi) - \underline{C}}{\underline{C}} \times 100\%$ 로 상한을 추정한다.

2.2.4 메이크스팬 (Makespan)

메이크스팬(Makespan) $T_{\text{makespan}}$ 은 임무 계획의 전체 실행 완료까지 소요되는 총 시간으로 정의되며, 특히 병렬 행동 실행이 가능한 다중 로봇 시스템에서 핵심적인 지표이다.

$T_{\text{makespan}} = \max_{j \in \mathcal{R}} T_j^{\text{completion}}$

여기서 $\mathcal{R}$ 은 로봇 집합이고, $T_j^{\text{completion}}$ 은 로봇 $j$ 의 할당된 모든 과업 완료 시각이다. 메이크스팬의 최소화는 NP-난해(NP-hard) 문제임이 알려져 있다 (Lenstra, Rinnooy Kan, and Brucker, 1977).

2.2.5 계획 길이 (Plan Length)

계획 길이(Plan Length) $L_{\text{plan}}$ 은 계획에 포함된 행동의 총 수를 나타낸다.

$L_{\text{plan}} = |\pi| = n$

계획 길이는 계획의 복잡도(Complexity)를 간접적으로 반영하며, 짧은 계획이 일반적으로 실행 오류 확률이 낮고 해석 가능성(Interpretability)이 높다.

2.3 실행 품질 지표

실행 품질(Execution Quality) 지표는 계획된 임무가 실제 로봇 시스템에서 실행될 때의 성능을 평가한다. 계획 단계에서의 이론적 품질과 실제 실행 결과 사이의 괴리(Reality Gap)를 정량화하는 데 핵심적으로 활용된다.

2.3.1 임무 성공률 (Mission Success Rate)

임무 성공률 $P_{\text{success}}$ 는 $N$ 회의 독립 시행(Trial)에서 임무 목표를 성공적으로 달성한 횟수 $N_{\text{success}}$ 의 비율로 정의된다.

$P_{\text{success}} = \frac{N_{\text{success}}}{N}$

임무 성공 여부의 판정 기준은 도메인에 따라 달라지며, 시간 제한 내 목표 지점 도달, 페이로드(Payload) 배송 완료, 탐색 영역의 일정 비율 이상 커버리지(Coverage) 달성 등이 대표적인 기준이 된다. 확률적 환경에서의 임무 성공률은 다수의 몬테카를로(Monte Carlo) 시뮬레이션을 통해 통계적으로 추정된다.

2.3.2 임무 달성 확률 (Mission Completion Probability)

임무 달성 확률 $P_{\text{comp}}$ 는 확률론적 모델에 기반한 분석적 계산으로 도출되는 지표이다. MDP 또는 POMDP 기반 계획에서 최적 정책 $\pi^*$ 하에서의 목표 상태 $s_g$ 도달 확률로 정의된다.

$P_{\text{comp}}(\pi^*) = \Pr\left[\exists t \geq 0 : s_t \in S_{\text{goal}} \mid \pi^*, s_0\right]$

여기서 $S_{\text{goal}}$ 은 목표 상태 집합, $s_0$ 는 초기 상태이다. 이 지표는 불확실성이 내재된 환경에서의 계획 신뢰도(Reliability)를 평가하는 데 활용된다.

2.3.3 임무 달성도 (Mission Completeness)

부분적 달성(Partial Completion)이 의미 있는 임무에서는, 임무 달성도 $\eta_{\text{comp}}$ 를 정의하여 전체 임무 목표 중 달성된 부분의 비율을 측정한다.

$\eta_{\text{comp}} = \frac{\sum_{i=1}^{m} w_i \cdot \mathbb{1}[g_i \text{ achieved}]}{\sum_{i=1}^{m} w_i}$

여기서 $g_i$ 는 $i$ 번째 하위 목표(Sub-goal), $w_i$ 는 해당 목표의 가중치, $\mathbb{1}[\cdot]$ 은 지시 함수(Indicator Function)이다. 수색 및 구조(SAR) 임무에서 탐색 영역 커버리지(Coverage Ratio)는 이 지표의 대표적인 적용 사례이다.

2.3.4 실행 시간 편차 (Execution Time Deviation)

실행 시간 편차 $\delta_T$ 는 계획된 임무 실행 시간 $T_{\text{planned}}$ 과 실제 실행 시간 $T_{\text{actual}}$ 사이의 차이를 정량화한다.

$\delta_T = \frac{|T_{\text{actual}} - T_{\text{planned}}|}{T_{\text{planned}}} \times 100\%$

이 지표가 클수록 계획 모델이 실제 환경의 동적 특성을 충분히 반영하지 못하고 있음을 의미한다. 낮은 $\delta_T$ 값은 환경 모델의 정확성과 불확실성 처리 능력의 우수성을 간접적으로 시사한다.

2.4 강건성 및 적응성 지표

강건성(Robustness) 및 적응성(Adaptability) 지표는 환경 변화, 센서 노이즈, 시스템 고장 등의 교란(Perturbation) 하에서 임무 계획의 성능 유지 또는 회복 능력을 평가한다.

2.4.1 강건성 지표 (Robustness Metric)

강건성 지표 $R(\pi)$ 는 환경 파라미터의 섭동(Perturbation)에 대한 계획 성능의 민감도를 정량화한다. 환경 파라미터 벡터 $\theta$ 에 대하여 다음과 같이 정의될 수 있다.

$R(\pi) = \min_{\|\delta\theta\| \leq \epsilon} J(\pi, \theta + \delta\theta)$

여기서 $J(\pi, \theta)$ 는 파라미터 $\theta$ 하에서 계획 $\pi$ 의 성능 함수이고, $\epsilon$ 은 허용 섭동 범위이다. 이 지표는 최악 상황(Worst-Case) 분석에 해당하며, 높은 $R(\pi)$ 값은 해당 계획이 파라미터 변동에 대해 강건함을 의미한다.

확률적 관점에서는 조건부 가치 위험(Conditional Value at Risk, CVaR) 기반 강건성 지표가 활용되기도 한다.

$\text{CVaR}_\alpha[J(\pi, \theta)] = \mathbb{E}[J(\pi, \theta) \mid J(\pi, \theta) \leq F_J^{-1}(\alpha)]$

여기서 $\alpha$ 는 신뢰 수준, $F_J^{-1}(\alpha)$ 는 $J$ 의 $\alpha$ -분위수(Quantile)이다.

2.4.2 재계획 빈도 (Replanning Frequency)

재계획 빈도 $f_{\text{replan}}$ 은 단위 임무 시간당 재계획이 발생한 횟수를 나타낸다.

$f_{\text{replan}} = \frac{N_{\text{replan}}}{T_{\text{mission}}}$

여기서 $N_{\text{replan}}$ 은 재계획 발생 횟수, $T_{\text{mission}}$ 은 총 임무 수행 시간이다. 높은 재계획 빈도는 초기 계획의 강건성이 부족하거나 환경의 동적 변화가 심함을 시사한다. 반면, 적절한 재계획은 임무 성공률에 긍정적 기여를 할 수 있으므로, 이 지표는 다른 지표와 함께 종합적으로 해석되어야 한다.

2.4.3 재계획 소요 시간 (Replanning Time)

재계획 소요 시간 $T_{\text{replan}}$ 은 환경 변화 감지 시점부터 갱신된 계획 산출 시점까지의 시간이다. 실시간 시스템에서는 $T_{\text{replan}}$ 이 시스템의 반응 시간 요구 사항을 충족해야 하며, 다음의 제약이 부과된다.

$T_{\text{replan}} \leq T_{\text{deadline}} - T_{\text{detect}}$

여기서 $T_{\text{deadline}}$ 은 응답 마감 시한, $T_{\text{detect}}$ 는 변화 감지에 소요된 시간이다.

2.4.4 적응성 지수 (Adaptability Index)

적응성 지수 $A(\pi)$ 는 환경 변화 발생 시 계획을 수정하여 임무 목표를 달성하는 능력을 종합적으로 평가하는 복합 지표이다.

$A(\pi) = \frac{P_{\text{success}}^{\text{perturbed}}}{P_{\text{success}}^{\text{nominal}}} \times \frac{T_{\text{plan}}^{\text{nominal}}}{T_{\text{replan}}^{\text{avg}}}$

여기서 $P_{\text{success}}^{\text{perturbed}}$ 는 교란 환경에서의 임무 성공률, $P_{\text{success}}^{\text{nominal}}$ 은 공칭(Nominal) 환경에서의 성공률, $T_{\text{plan}}^{\text{nominal}}$ 은 초기 계획 수립 시간, $T_{\text{replan}}^{\text{avg}}$ 는 평균 재계획 소요 시간이다. $A(\pi) \geq 1$ 이면 적응성이 양호한 것으로 판단된다.

3. 자원 효율성 관련 지표

자원 제약이 중요한 로봇 임무에서는 자원 효율성(Resource Efficiency) 관련 지표가 특별히 중요하다.

3.1 에너지 소모 효율 (Energy Consumption Efficiency)

에너지 소모 효율 $\eta_E$ 는 임무 달성에 소비된 에너지의 실제 사용 비율을 나타낸다.

$\eta_E = \frac{E_{\text{useful}}}{E_{\text{total}}}$

여기서 $E_{\text{useful}}$ 은 임무 수행에 직접 기여한 유효 에너지, $E_{\text{total}}$ 은 총 소비 에너지이다. 배터리 기반 이동 로봇이나 무인 항공기(UAV)에서 이 지표는 임무의 실현 가능성(Feasibility)을 직접적으로 결정한다.

3.2 자원 활용도 (Resource Utilization Rate)

다중 로봇 시스템에서 자원 활용도 $U_R$ 은 전체 시스템 자원 대비 실제 임무 수행에 투입된 자원의 비율로 정의된다.

$U_R = \frac{1}{|\mathcal{R}|} \sum_{j \in \mathcal{R}} \frac{T_j^{\text{active}}}{T_{\text{mission}}}$

여기서 $T_j^{\text{active}}$ 는 로봇 $j$ 가 임무 수행에 실제 활동한 시간이다. $U_R$ 이 1에 가까울수록 로봇 자원이 효율적으로 활용되고 있음을 의미한다. 낮은 $U_R$ 값은 과잉 자원 할당(Over-provisioning) 또는 비효율적 과업 분배를 시사한다.

4. 확장성 지표

4.1 계산 확장성 (Computational Scalability)

계산 확장성은 문제 규모(Problem Size) $n$ 의 증가에 따른 계획 소요 시간 및 메모리의 증가 양상을 분석하여 평가한다. 알고리즘의 시간 복잡도(Time Complexity) $O(f(n))$ 과 공간 복잡도(Space Complexity) $O(g(n))$ 가 기본 지표가 되며, 실험적으로는 문제 크기를 체계적으로 변화시키면서 실측된 성능을 로그-로그(Log-Log) 스케일로 분석하여 경험적 확장성 지수(Empirical Scaling Exponent) $\beta$ 를 추정한다.

$T_{\text{plan}}(n) \propto n^\beta$

$\beta$ 값이 작을수록 확장성이 우수하다.

4.2 로봇 수 확장성 (Agent Scalability)

다중 로봇 임무 계획에서 로봇 수 $|\mathcal{R}|$ 의 증가에 따른 성능 변화를 평가한다. 이상적으로는 로봇 수에 대해 선형적(Linear) 성능 향상이 기대되나, 통신 오버헤드, 조율 비용(Coordination Cost), 자원 경합 등으로 인해 실제 성능은 이에 미치지 못한다. 속도 향상 비율(Speedup Ratio)을 다음과 같이 정의한다.

$S(|\mathcal{R}|) = \frac{T_{\text{makespan}}(1)}{T_{\text{makespan}}(|\mathcal{R}|)}$

이상적 확장성은 $S(|\mathcal{R}|) = |\mathcal{R}|$ 이며, 암달의 법칙(Amdahl’s Law)에 의해 실제 확장성의 상한이 결정된다.

5. 벤치마크 및 표준화 동향

임무 계획 성능의 객관적 비교를 위해 표준화된 벤치마크(Benchmark)와 경진 대회(Competition)가 활용된다.

5.1 IPC (International Planning Competition)

국제 계획 경진 대회(International Planning Competition, IPC)는 PDDL 기반 계획 알고리즘의 성능을 표준 벤치마크 도메인에서 비교하는 학술 행사이다. IPC에서 주로 채택하는 성능 지표는 다음과 같다.

IPC 품질 점수(Quality Score): 벤치마크 인스턴스 $i$ 에 대해 계획기 $p$ 가 생성한 계획 비용을 $C_p(i)$ , 모든 참가 계획기 중 최소 비용을 $C^*(i)$ 라 할 때, 품질 점수는 $Q_p(i) = C^*(i) / C_p(i)$ 로 정의된다.
커버리지(Coverage): 주어진 시간 및 메모리 한도 내에서 해를 찾은 벤치마크 인스턴스 수의 비율이다.
PAR-k 점수: 미해결 인스턴스에 대해 시간 한도의 $k$ 배를 패널티로 부여하는 방식으로, 해결 능력과 속도를 동시에 평가한다.

5.2 로봇 도메인 벤치마크

로봇 임무 계획의 고유한 특성을 반영한 벤치마크로는 다음이 있다.

ROSPlan 벤치마크: ROS 통합 환경에서의 임무 계획 시나리오를 제공한다 (Cashmore et al., 2015).
Multi-Robot Task Allocation (MRTA) 벤치마크: 다중 로봇 과업 할당 문제의 표준 인스턴스를 제공하며, 메이크스팬, 총 이동 거리, 자원 활용도 등의 지표로 평가한다 (Korsah, Stentz, and Dias, 2013).
PlanBench: 대규모 언어 모델(LLM) 기반 계획 능력을 평가하기 위한 벤치마크로, 기존 PDDL 도메인을 자연어 임무 기술로 변환하여 사용한다 (Valmeekam et al., 2023).

6. 다중 지표 종합 평가 방법론

단일 지표만으로는 임무 계획 알고리즘의 성능을 종합적으로 평가하기 어렵다. 따라서 다중 지표를 통합하는 체계적 방법론이 요구된다.

6.1 가중 합산 방법 (Weighted Sum Method)

다수의 성능 지표 $\{m_1, m_2, \ldots, m_k\}$ 를 정규화(Normalization)한 후 가중합으로 종합 점수 $S_{\text{overall}}$ 을 산출한다.

$S_{\text{overall}} = \sum_{i=1}^{k} w_i \cdot \hat{m}_i$

여기서 $\hat{m}_i$ 는 $i$ 번째 지표의 정규화된 값, $w_i$ 는 해당 지표의 가중치( $\sum w_i = 1$ )이다. 가중치 설정은 도메인 전문가의 판단 또는 AHP(Analytic Hierarchy Process) 등의 체계적 방법론을 통해 결정된다.

6.2 레이더 차트 (Radar Chart) 기반 다차원 비교

정량적 종합이 어렵거나 지표 간 상충 관계(Trade-off)를 시각적으로 파악해야 할 경우, 레이더 차트(Radar Chart) 또는 키비아트 차트(Kiviat Chart)를 활용하여 다차원 성능 프로파일을 시각화한다. 각 축은 개별 성능 지표를 나타내며, 알고리즘 간 성능 프로파일의 형태적 차이를 직관적으로 비교할 수 있다.

6.3 파레토 지배 분석 (Pareto Dominance Analysis)

다목적 최적화의 관점에서, 계획 알고리즘 $A$ 가 알고리즘 $B$ 를 파레토 지배(Pareto Dominate)한다는 것은 모든 지표에서 $A$ 가 $B$ 이상이며 적어도 하나의 지표에서 엄격히 우월함을 의미한다. 파레토 비지배 집합(Pareto Non-dominated Set)에 속한 알고리즘들을 식별함으로써 성능 비교의 공정성과 객관성을 확보할 수 있다.

7. 요약

임무 계획의 성능 평가 지표는 계획 생성 효율성, 계획 품질, 실행 품질, 강건성 및 적응성, 자원 효율성, 확장성의 다층적 관점에서 체계적으로 구성되어야 한다. 각 지표는 고유한 의미와 적용 맥락을 가지며, 단일 지표에 의존한 평가는 편향된 결론을 초래할 수 있다. 따라서 도메인 특성과 임무 요구 사항에 부합하는 적절한 지표 집합의 선정과 다중 지표 종합 평가 방법론의 적용이 필수적이다. IPC, MRTA 벤치마크 등 표준화된 평가 체계를 활용하면 알고리즘 간 공정하고 재현 가능한(Reproducible) 성능 비교가 가능하다.

참고 문헌

Cashmore, M., Fox, M., Long, D., Magazzeni, D., Ridder, B., Carrera, A., Palomeras, N., Hurtos, N., and Carreras, M. (2015). “ROSPlan: Planning in the Robot Operating System.” Proceedings of the International Conference on Automated Planning and Scheduling (ICAPS).
Korsah, G. A., Stentz, A., and Dias, M. B. (2013). “A comprehensive taxonomy for multi-robot task allocation.” International Journal of Robotics Research, 32(12), 1495–1512.
Lenstra, J. K., Rinnooy Kan, A. H. G., and Brucker, P. (1977). “Complexity of machine scheduling problems.” Annals of Discrete Mathematics, 1, 343–362.
Valmeekam, K., Marquez, M., Sreedharan, S., and Kambhampati, S. (2023). “PlanBench: An Extensible Benchmark for Evaluating Large Language Models on Planning and Reasoning about Change.” Proceedings of the Conference on Neural Information Processing Systems (NeurIPS).

version: 1.0