397.72 계획 소요 시간, 달성 확률, 자원 소모 평가

1. 서론

임무 계획 알고리즘의 실질적 성능을 결정짓는 세 가지 핵심 평가 축은 계획 소요 시간(Planning Time), 임무 달성 확률(Mission Achievement Probability), 그리고 자원 소모(Resource Consumption)이다. 이 세 지표는 서로 상충 관계(Trade-off)를 형성하는 경우가 빈번하며, 특정 도메인의 운용 요구 사항에 따라 각 지표의 상대적 중요도가 달라진다. 본 절에서는 이 세 가지 핵심 평가 축의 수학적 정의, 측정 방법론, 그리고 상호 관계를 상세히 기술한다.

2. 계획 소요 시간의 정밀 평가

2.1 계획 소요 시간의 구성 요소 분해

계획 소요 시간 T_{\text{plan}}은 단일 수치로 표현되지만, 내부적으로 여러 구성 요소의 합으로 분해될 수 있다. 일반적인 임무 계획 파이프라인에서 전체 계획 소요 시간은 다음과 같이 분해된다.

T_{\text{plan}} = T_{\text{parse}} + T_{\text{ground}} + T_{\text{search}} + T_{\text{post}}

여기서 각 항의 의미는 다음과 같다.

대부분의 경우 T_{\text{search}}가 지배적(Dominant) 요소이나, 대규모 도메인에서는 T_{\text{ground}}가 전체 시간의 상당 부분을 차지할 수 있다. 이러한 시간 분해 분석은 알고리즘의 병목(Bottleneck) 지점을 식별하는 데 유용하다.

2.2 시간 복잡도와 실측 시간의 관계

이론적 시간 복잡도(Time Complexity)는 최악의 경우(Worst-Case) 분석에 기반하므로, 실제 벤치마크에서의 실측 시간과 괴리가 발생할 수 있다. 따라서 계획 소요 시간의 평가에서는 이론적 복잡도와 더불어 실험적 성능 프로파일(Performance Profile)을 병행하여 분석해야 한다.

실험적 성능 프로파일의 대표적 방법으로서 누적 분포 함수(Cumulative Distribution Function, CDF) 기반 분석이 있다. 벤치마크 인스턴스 집합 \mathcal{I}에 대해 계획기 p의 성능 비율(Performance Ratio)을 다음과 같이 정의한다.

r_p(i) = \frac{T_p(i)}{\min_{p' \in \mathcal{P}} T_{p'}(i)}

여기서 \mathcal{P}는 비교 대상 계획기 집합이다. 성능 프로파일 \rho_p(\tau)는 성능 비율이 \tau 이하인 인스턴스의 비율로 정의된다.

\rho_p(\tau) = \frac{|\{i \in \mathcal{I} : r_p(i) \leq \tau\}|}{|\mathcal{I}|}

\rho_p(1)은 계획기 p가 최고 성능을 달성한 인스턴스의 비율을, \lim_{\tau \to \infty} \rho_p(\tau)는 해결 가능한 인스턴스의 총 비율(커버리지)을 나타낸다 (Dolan and Moré, 2002).

2.3 에니타임 성능 프로파일

에니타임(Anytime) 계획 알고리즘은 시간이 경과함에 따라 점진적으로 해의 품질을 개선한다. 이러한 알고리즘의 평가에는 **에니타임 성능 곡선(Anytime Performance Curve)**이 활용된다.

에니타임 성능은 시간 t에서의 현재 최선의 해 비용 C_{\text{best}}(t)를 시간의 함수로 표현한다.

C_{\text{best}}(t) = \min_{0 \leq t' \leq t} C(\pi_{t'})

여기서 \pi_{t'}는 시각 t'에서 발견된 계획이다. 에니타임 비율(Anytime Ratio)은 특정 시간 한도 T에서의 해 품질과 충분한 시간이 주어졌을 때의 최종 해 품질의 비율로 정의된다.

\text{AR}(T) = \frac{C_{\text{best}}(T)}{C_{\text{best}}(\infty)}

\text{AR}(T)가 1에 가까울수록 해당 시간 한도 내에서 최종 해에 근접한 품질의 계획을 신속하게 도출함을 의미한다.

2.4 실시간 제약 하에서의 시간 예산 관리

실시간 로봇 시스템에서는 계획 소요 시간이 엄격한 상한(Deadline)을 준수해야 한다. 시간 예산(Time Budget) T_{\text{budget}}이 주어질 때, 계획기의 시간 준수율(Deadline Compliance Rate)은 다음과 같이 정의된다.

\text{DCR} = \frac{|\{i \in \mathcal{I} : T_p(i) \leq T_{\text{budget}}\}|}{|\mathcal{I}|}

높은 DCR은 계획기가 실시간 운용에 적합함을 나타낸다. 실시간 시스템에서는 평균 계획 시간보다 최악의 경우 계획 시간(Worst-Case Execution Time, WCET)이 더 중요한 지표가 된다.

3. 임무 달성 확률의 체계적 평가

3.1 결정론적 환경에서의 달성 확률

결정론적(Deterministic) 환경에서 임무 달성 확률은 이론적으로 0 또는 1의 이진값을 가진다. 그러나 실제 시스템에서는 모델링되지 않은 불확실성, 센서 오류, 액추에이터 오차 등으로 인해 확률적 특성이 나타난다. 이 경우, 몬테카를로(Monte Carlo) 시뮬레이션을 통해 임무 달성 확률을 경험적으로 추정한다.

N회의 독립 시행에서 k회 성공 시, 달성 확률의 점 추정치(Point Estimate)와 (1-\alpha) 신뢰 구간(Confidence Interval)은 다음과 같다.

\hat{P} = \frac{k}{N}

\text{CI}_{1-\alpha} = \hat{P} \pm z_{\alpha/2} \sqrt{\frac{\hat{P}(1-\hat{P})}{N}}

여기서 z_{\alpha/2}는 표준 정규 분포의 \alpha/2 분위수이다. 통계적으로 유의미한 추정을 위해서는 충분한 시행 횟수 N이 필요하며, 일반적으로 N \geq 30이 요구된다.

3.2 확률론적 환경에서의 달성 확률

확률론적 환경에서는 MDP 또는 POMDP 프레임워크를 통해 임무 달성 확률을 분석적으로 계산할 수 있다.

3.2.1 MDP 기반 달성 확률 계산

MDP \mathcal{M} = \langle S, A, T, R, \gamma \rangle 하에서 정책 \pi의 임무 달성 확률은 다음의 벨만 방정식(Bellman Equation)으로 계산된다.

P_{\pi}(s) = \begin{cases} 1, & \text{if } s \in S_{\text{goal}} \\ 0, & \text{if } s \in S_{\text{fail}} \\ \sum_{s' \in S} T(s' \mid s, \pi(s)) \cdot P_{\pi}(s'), & \text{otherwise} \end{cases}

여기서 S_{\text{goal}}은 목표 상태 집합, S_{\text{fail}}은 실패 상태 집합, T(s' \mid s, a)는 전이 확률 함수이다. 이 재귀 방정식은 선형 연립 방정식(Linear System of Equations)으로 변환되어 효율적으로 풀 수 있다.

3.2.2 POMDP 기반 달성 확률 계산

POMDP에서는 직접적인 상태 관측이 불가능하므로, 신뢰 상태(Belief State) b \in \Delta(S) 공간에서의 달성 확률을 계산해야 한다.

P_{\pi}(b) = \sum_{s \in S_{\text{goal}}} b(s) + \sum_{s \notin S_{\text{goal}} \cup S_{\text{fail}}} b(s) \cdot \sum_{o \in O} \Pr(o \mid b, \pi(b)) \cdot P_{\pi}(b')

여기서 b'는 행동 \pi(b)와 관측 o에 의해 갱신된 신뢰 상태이다. POMDP에서의 정확한 달성 확률 계산은 일반적으로 계산적으로 난해(Intractable)하므로, 점 기반 근사(Point-Based Approximation) 또는 입자 필터(Particle Filter) 기반 시뮬레이션으로 추정한다.

3.3 다중 목표 달성 확률

복수의 하위 목표 \{g_1, g_2, \ldots, g_m\}를 포함하는 복합 임무에서는 개별 목표 달성 확률과 전체 임무 달성 확률 사이의 관계를 분석해야 한다.

3.3.1 독립 목표의 경우

하위 목표들이 확률적으로 독립(Independent)일 때, 전체 임무 달성 확률은 다음과 같다.

P_{\text{mission}} = \prod_{i=1}^{m} P(g_i)

이 경우 개별 목표 달성 확률이 높더라도 목표 수가 증가하면 전체 달성 확률이 급격히 감소하는 확률적 쇄도(Probability Cascade) 현상이 발생한다.

3.3.2 종속 목표의 경우

하위 목표들이 선후 관계(Precedence Relation)나 자원 공유 관계를 통해 종속(Dependent)될 때, 조건부 확률을 활용한다.

P_{\text{mission}} = P(g_1) \cdot P(g_2 \mid g_1) \cdot P(g_3 \mid g_1, g_2) \cdots P(g_m \mid g_1, \ldots, g_{m-1})

실제 시스템에서는 이러한 조건부 확률의 정확한 추정이 어려우므로, 베이지안 네트워크(Bayesian Network) 또는 동적 결함 트리(Dynamic Fault Tree) 분석을 활용한다 (Kabir et al., 2018).

3.4 위험 가중 달성 확률

임무 실패의 결과가 심각한 도메인(예: 군사 작전, 핵시설 점검)에서는 단순 달성 확률 외에 위험 가중(Risk-Weighted) 지표가 요구된다.

R_{\text{weighted}} = P_{\text{success}} \cdot V_{\text{success}} - (1 - P_{\text{success}}) \cdot V_{\text{failure}}

여기서 V_{\text{success}}는 임무 성공의 가치, V_{\text{failure}}는 임무 실패로 인한 손실이다. 이 지표는 기대 효용(Expected Utility) 이론에 기반하며, 의사 결정자의 위험 선호도(Risk Preference)를 반영할 수 있다.

4. 자원 소모 평가의 다차원 프레임워크

4.1 에너지 소모 평가

4.1.1 이동 에너지 모델

지상 이동 로봇의 이동 에너지 소모 E_{\text{move}}는 경로 \mathcal{P}를 따른 적분으로 계산된다.

E_{\text{move}} = \int_{\mathcal{P}} \left( F_{\text{roll}} + F_{\text{aero}} + F_{\text{grade}} + F_{\text{accel}} \right) \, ds

여기서 F_{\text{roll}}은 구름 저항력, F_{\text{aero}}는 공기 저항력, F_{\text{grade}}는 경사 저항력, F_{\text{accel}}은 가속 저항력이다.

무인 항공기(UAV)의 경우 비행 에너지 모델은 더욱 복잡하며, 회전익(Rotary-Wing) UAV의 호버링 에너지 P_{\text{hover}}와 전진 비행 에너지 P_{\text{forward}}를 구분하여 모델링한다.

P_{\text{hover}} = \frac{W^{3/2}}{\sqrt{2\rho A}}

여기서 W는 기체 중량, \rho는 공기 밀도, A는 로터 디스크 면적이다 (Shi et al., 2019).

4.1.2 배터리 충전 상태(SoC) 추적

배터리 기반 로봇의 에너지 소모는 충전 상태(State of Charge, SoC) 변화로 추적된다.

\text{SoC}(t) = \text{SoC}(t_0) - \frac{1}{Q_{\text{nom}}} \int_{t_0}^{t} I(\tau) \, d\tau

여기서 Q_{\text{nom}}은 배터리의 공칭 용량(Nominal Capacity), I(\tau)는 시각 \tau에서의 방전 전류이다. 임무 계획에서는 SoC가 안전 하한(Safety Threshold) \text{SoC}_{\min} 이하로 떨어지지 않아야 한다는 제약이 필수적이다.

\text{SoC}(t) \geq \text{SoC}_{\min}, \quad \forall t \in [t_0, t_f]

4.2 시간 자원 소모 평가

4.2.1 총 임무 시간

총 임무 시간 T_{\text{mission}}은 임무 시작부터 완료까지의 전체 경과 시간이다. 이는 다음의 구성 요소로 분해된다.

T_{\text{mission}} = T_{\text{travel}} + T_{\text{task}} + T_{\text{wait}} + T_{\text{comm}}

효율적인 임무 계획은 T_{\text{wait}}와 T_{\text{comm}}의 최소화를 통해 전체 임무 시간을 단축하도록 설계되어야 한다.

4.2.2 시간 여유도 (Temporal Slack)

시간 여유도(Temporal Slack) \sigma_i는 각 과업 i에 할당된 시간 윈도우(Time Window)와 실제 소요 시간 사이의 차이를 나타낸다.

\sigma_i = (d_i - r_i) - p_i

여기서 d_i는 과업의 마감 시한(Deadline), r_i는 준비 시각(Release Time), p_i는 처리 시간(Processing Time)이다. \sigma_i > 0이면 해당 과업에 시간 여유가 존재하며, \sigma_i = 0이면 임계 과업(Critical Task)이 된다.

4.3 통신 자원 소모 평가

다중 로봇 임무에서 통신 자원 소모는 계획의 실행 가능성에 직접적인 영향을 미친다.

4.3.1 통신 대역폭 소모

통신 대역폭 소모 B_{\text{total}}은 임무 수행 중 교환되는 총 데이터 양으로 측정된다.

B_{\text{total}} = \sum_{t=0}^{T_{\text{mission}}} \sum_{(i,j) \in \mathcal{E}(t)} b_{ij}(t)

여기서 \mathcal{E}(t)는 시각 t에서의 활성 통신 링크 집합, b_{ij}(t)는 로봇 i와 j 사이의 데이터 전송량이다. 대역폭 제약이 있는 환경에서는 b_{ij}(t) \leq B_{\max}의 조건이 부과된다.

4.3.2 통신 빈도와 오버헤드

통신 빈도(Communication Frequency) f_{\text{comm}}은 로봇 간 메시지 교환의 단위 시간당 횟수를 나타낸다. 분산형(Decentralized) 계획의 경우 통신 빈도가 높아지므로, 통신 오버헤드와 계획 품질 사이의 균형이 중요하다.

4.4 계산 자원 소모 평가

온보드(Onboard) 컴퓨터의 계산 자원 제약은 임무 계획 알고리즘 선택에 직접적인 영향을 미친다.

4.4.1 CPU 사용률

계획 수립 및 실행 중의 CPU 사용률 U_{\text{CPU}}는 다음과 같이 측정된다.

U_{\text{CPU}} = \frac{T_{\text{CPU}}^{\text{plan}}}{T_{\text{wall}}}

여기서 T_{\text{CPU}}^{\text{plan}}은 계획 관련 CPU 시간, T_{\text{wall}}은 벽시계 시간이다. 실시간 시스템에서는 계획 알고리즘의 CPU 사용이 제어 루프(Control Loop), 인식(Perception) 모듈 등과 경합하지 않도록 관리되어야 한다.

5. 세 지표 간의 상충 관계 분석

5.1 시간-품질 상충 관계

계획 소요 시간과 계획 품질(비용 최적성, 달성 확률) 사이에는 근본적인 상충 관계가 존재한다. 더 많은 시간을 투입할수록 보다 넓은 상태 공간을 탐색할 수 있어 더 나은 해를 발견할 가능성이 높지만, 실시간 운용 제약이 이를 제한한다. 이 상충 관계는 다음의 에니타임 품질 함수로 표현된다.

Q(t) = Q^* - \Delta Q \cdot e^{-\lambda t}

여기서 Q^*는 최적 품질, \Delta Q는 초기 품질 차이, \lambda는 수렴 속도 상수이다.

5.2 달성 확률-자원 소모 상충 관계

높은 임무 달성 확률을 보장하기 위해서는 추가적인 자원(에너지, 시간, 예비 로봇)의 투입이 필요하다. 예를 들어, 보수적(Conservative) 계획은 안전 마진(Safety Margin)을 확보하기 위해 더 많은 에너지와 시간을 소모한다.

E_{\text{conservative}} = E_{\text{nominal}} \cdot (1 + \alpha_{\text{margin}})

여기서 \alpha_{\text{margin}}은 안전 마진 계수이다. 도메인 요구 사항에 따라 적절한 마진 수준을 결정해야 한다.

5.3 파레토 프론티어 기반 통합 분석

세 지표 간의 상충 관계를 종합적으로 분석하기 위해, 3차원 파레토 프론티어(Pareto Frontier) 분석이 활용된다. 각 계획 대안 \pi_k에 대해 3차원 벡터 (T_{\text{plan}}(\pi_k), 1 - P_{\text{success}}(\pi_k), E_{\text{total}}(\pi_k))를 구성하고, 파레토 비지배(Pareto Non-dominated) 해 집합을 식별한다. 의사 결정자는 파레토 프론티어 위의 해들 중에서 도메인 요구 사항과 운용 우선순위에 따라 최종 계획을 선택한다.

6. 평가 실험 설계 지침

6.1 벤치마크 인스턴스 선정

세 지표의 평가를 위한 실험 설계 시, 벤치마크 인스턴스는 다음의 기준에 따라 선정되어야 한다.

1. 규모 다양성(Scale Diversity): 소규모에서 대규모까지 다양한 문제 크기를 포함해야 한다.
2. 구조 다양성(Structural Diversity): 선형, 분기, 순환 등 다양한 과업 구조를 포함해야 한다.
3. 불확실성 수준(Uncertainty Level): 결정론적 환경부터 고불확실성 환경까지의 스펙트럼을 포괄해야 한다.
4. 자원 제약 강도(Resource Constraint Intensity): 느슨한 제약부터 긴박한 제약까지의 범위를 다루어야 한다.

6.2 통계적 유의성 확보

확률적 알고리즘 또는 확률적 환경에서의 실험 결과는 통계적 검정(Statistical Testing)을 통해 유의성을 검증해야 한다. 윌콕슨 순위합 검정(Wilcoxon Rank-Sum Test) 또는 크루스칼-왈리스 검정(Kruskal-Wallis Test) 등의 비모수 검정(Nonparametric Test)이 일반적으로 사용된다. 실험 결과의 보고 시 평균(Mean)뿐 아니라 중앙값(Median), 사분위 범위(Interquartile Range), 그리고 극단값(Extreme Values)을 함께 제시하는 것이 권장된다 (Arcuri and Briand, 2014).

6.3 공정한 비교를 위한 실험 조건 통제

알고리즘 간 공정한 비교를 위해서는 다음의 실험 조건이 통제되어야 한다.

• 동일 하드웨어: 모든 알고리즘은 동일한 하드웨어 플랫폼에서 실행되어야 한다.
• 동일 시간 한도: 동일한 계획 시간 한도(Time Limit)와 메모리 한도가 부여되어야 한다.
• 동일 난수 시드(Random Seed): 확률적 알고리즘의 경우, 복수의 난수 시드에 대한 결과를 보고해야 한다.
• 동일 환경 모델: 자원 소모 평가 시 동일한 물리 모델(에너지 소모 모델, 이동 모델)이 사용되어야 한다.

7. 요약

계획 소요 시간, 임무 달성 확률, 자원 소모는 임무 계획 알고리즘의 성능을 결정짓는 세 가지 핵심 축이다. 각 지표는 독립적으로 정의된 수학적 모델과 측정 방법론을 가지며, 동시에 상호 간 복잡한 상충 관계를 형성한다. 효과적인 성능 평가를 위해서는 이 세 지표를 개별적으로 정밀하게 측정하는 동시에, 파레토 분석 등의 다목적 평가 프레임워크를 통해 종합적으로 비교하여야 한다. 또한, 통계적으로 유의미한 실험 설계와 공정한 비교 조건의 확보가 평가 결과의 신뢰성을 보장하는 데 필수적이다.

참고 문헌

• Arcuri, A. and Briand, L. (2014). “A Hitchhiker’s Guide to Statistical Tests for Assessing Randomized Algorithms in Software Engineering.” Software Testing, Verification and Reliability, 24(3), 219–250.
• Dolan, E. D. and Moré, J. J. (2002). “Benchmarking optimization software with performance profiles.” Mathematical Programming, 91(2), 201–213.
• Kabir, S., Walker, M., Papadopoulos, Y., Rüde, E., and Securius, P. (2018). “An overview of fault tree analysis and its application in model based dependability analysis.” Expert Systems with Applications, 77, 114–135.
• Shi, W., Zhou, H., Li, J., Xu, W., Zhang, N., and Shen, X. (2019). “Drone assisted vehicular networks: Architecture, challenges and opportunities.” IEEE Network, 32(3), 130–137.

version: 1.0