397.45 임무 달성 가능성(Feasibility) 검사

임무 계획이 수립된 후, 그 계획이 실제로 실행 가능한지를 사전에 검증하는 것은 자율 로봇 시스템의 안전성과 신뢰성을 확보하기 위한 필수적 단계이다. 임무 달성 가능성(feasibility) 검사는 수립된 계획이 로봇의 물리적 능력, 환경 제약, 자원 한계 등을 모두 만족하면서 목표를 달성할 수 있는지를 형식적으로 판별하는 과정이다.

1. 달성 가능성의 정의

1.1 형식적 정의

계획 $\pi = \langle a_1, a_2, \ldots, a_n \rangle$ 의 달성 가능성은 다음 조건의 동시 만족으로 정의된다.

논리적 달성 가능성(Logical Feasibility): 계획의 모든 행동이 순차적으로 실행될 때, 각 행동의 전제 조건이 실행 시점의 상태에서 성립하며, 최종 상태가 목표 조건을 만족한다.

$\text{logically\_feasible}(\pi) \iff \forall i \in \{1, \ldots, n\}: \text{pre}(a_i) \subseteq s_{i-1} \quad \wedge \quad G \subseteq s_n$

여기서 $s_i = \gamma(s_{i-1}, a_i)$ 는 행동 $a_i$ 실행 후의 결과 상태이며, $G$ 는 목표 조건의 집합이다.

물리적 달성 가능성(Physical Feasibility): 계획에서 요구하는 모든 행동이 로봇의 물리적 능력(운동학적 제약, 동역학적 한계, 센서 범위 등) 내에서 수행 가능하다.

자원 달성 가능성(Resource Feasibility): 계획의 실행에 필요한 모든 자원(에너지, 시간, 적재 용량, 통신 대역폭 등)이 가용 한도 내에 있다.

시간 달성 가능성(Temporal Feasibility): 계획의 모든 시간 제약(마감 시한, 시간 창, 동기화 시점)이 충족된다.

1.2 통합 달성 가능성 조건

통합 달성 가능성은 위의 모든 조건이 동시에 만족될 때 성립한다.

$\text{feasible}(\pi) \iff \text{logically\_feasible}(\pi) \wedge \text{physically\_feasible}(\pi) \wedge \text{resource\_feasible}(\pi) \wedge \text{temporally\_feasible}(\pi)$

2. 논리적 달성 가능성 검사

2.1 계획 검증(Plan Validation)

논리적 달성 가능성은 계획의 **시뮬레이션 실행(simulated execution)**을 통해 검증된다. 초기 상태 $s_0$ 에서 출발하여 계획의 각 행동을 순차적으로 적용하면서 다음을 확인한다.

알고리즘: Logical Feasibility Check
입력: 계획 π = ⟨a₁, a₂, ..., aₙ⟩, 초기 상태 s₀, 목표 G
출력: feasible 또는 (infeasible, 실패_원인)

1. s ← s₀
2. for i = 1 to n do
3.     if pre(aᵢ) ⊄ s then
4.         return (infeasible, "행동 aᵢ의 전제 조건 미충족", i)
5.     s ← γ(s, aᵢ)
6. end for
7. if G ⊄ s then
8.     return (infeasible, "목표 조건 미달성")
9. return feasible

2.2 VAL 계획 검증 도구

Howey 등(2004)이 개발한 **VAL(Plan Validation)**은 PDDL 기반 계획의 달성 가능성을 자동으로 검증하는 표준 도구이다. VAL은 다음을 검사한다.

각 행동의 전제 조건이 적용 시점에 성립하는지
지속적 행동(durative action)의 경우, at start, over all, at end 조건이 적절한 시점에 성립하는지
동시에 실행되는 행동들 사이에 불일치가 없는지
최종 상태가 목표 조건을 만족하는지

3. 자원 달성 가능성 검사

3.1 에너지 달성 가능성

로봇의 배터리 잔량이 계획의 완수에 충분한지를 검사한다. 각 행동 $a_i$ 의 에너지 소비량 $e(a_i)$ 에 대해 다음 조건이 모든 시점에서 성립해야 한다.

$E_0 - \sum_{j=1}^{i} e(a_j) \geq E_{\min} \quad \forall i \in \{1, \ldots, n\}$

여기서 $E_0$ 는 초기 에너지, $E_{\min}$ 은 안전 복귀에 필요한 최소 에너지 예비량이다. 이 조건을 **에너지 불변조건(energy invariant)**이라 하며, 이를 위반하는 계획은 에너지 비달성 가능으로 판정된다.

특히, UAV 임무에서의 에너지 달성 가능성은 풍속, 고도, 적재 중량에 따른 변동 에너지 소비를 고려하여 보수적으로 평가된다.

$E_{\text{required}}(\pi) = \sum_{i=1}^{n} e(a_i) + E_{\text{margin}} + E_{\text{return}}$

여기서 $E_{\text{margin}}$ 은 불확실성에 대한 에너지 여유분, $E_{\text{return}}$ 은 현재 위치에서 기지까지의 복귀 에너지이다.

3.2 적재 용량 달성 가능성

물류 로봇의 적재 임무에서는 로봇의 적재 용량 $W_{\max}$ 를 초과하지 않는지를 검사한다. 계획 실행 중 적재 상태 $W(i)$ 는 다음과 같이 추적된다.

$W(i) = W(i-1) + \Delta w(a_i)$

여기서 $\Delta w(a_i)$ 는 행동 $a_i$ 에 의한 적재량 변화이다 (적재 시 양수, 하역 시 음수). 달성 가능성 조건은 다음과 같다.

$0 \leq W(i) \leq W_{\max} \quad \forall i$

3.3 통신 달성 가능성

로봇이 기지국과의 통신을 유지해야 하는 임무에서는, 계획의 모든 시점에서 로봇의 위치가 통신 가능 영역 내에 있는지를 검사한다.

$\text{pos}(r, t_i) \in \mathcal{C}_{\text{coverage}} \quad \forall t_i \in [0, T]$

여기서 $\mathcal{C}_{\text{coverage}}$ 는 통신 커버리지 영역이다.

4. 시간 달성 가능성 검사

4.1 시간 창 호환성 검사

각 과업 $t_j$ 에 시간 창 $[e_j, l_j]$ 가 부여된 경우, 스케줄링된 실행 시점 $s_j$ 가 시간 창 내에 있는지를 검사한다.

$e_j \leq s_j \quad \wedge \quad s_j + \text{dur}(t_j) \leq l_j \quad \forall j$

4.2 선행 제약 일관성 검사

선행 제약 $(t_j, t_k) \in \text{prec}$ 이 스케줄에서 만족되는지를 검사한다.

$s_j + \text{dur}(t_j) \leq s_k \quad \forall (t_j, t_k) \in \text{prec}$

이 조건은 **임계 경로법(Critical Path Method, CPM)**에 의해 효율적으로 검사된다. 선행 제약 그래프의 최장 경로가 전체 가용 시간을 초과하면 시간적으로 비달성 가능(temporally infeasible)하다.

4.3 동기화 시점 일관성

협력 과업의 참여 로봇 간 동기화 시점이 서로 양립 가능한지를 검사한다. 로봇 $r_i$ 의 과업 $t_k$ 도착 시점 $\text{arr}(r_i, t_k)$ 가 다음을 만족해야 한다.

$\max_{r_i \in \mathcal{F}(t_k)} \text{arr}(r_i, t_k) \leq l_k - \text{dur}(t_k)$

즉, 모든 참여 로봇이 마감 시한 이전에 도착하여 과업을 완수할 수 있어야 한다.

5. 물리적 달성 가능성 검사

5.1 운동학적 달성 가능성

로봇의 운동학적 제약(최대 속도, 최대 가속도, 최소 회전 반경 등)을 고려하여, 계획된 경로가 실제로 추종 가능한지를 검사한다.

지상 로봇의 비홀로노믹(nonholonomic) 제약 하에서의 달성 가능성은 다음 조건으로 판별된다.

$\kappa(s) \leq \kappa_{\max} \quad \forall s \in \text{path}$

여기서 $\kappa(s)$ 는 경로 상 위치 $s$ 에서의 곡률(curvature), $\kappa_{\max} = 1/r_{\min}$ 은 최소 회전 반경 $r_{\min}$ 에 의해 결정되는 최대 허용 곡률이다.

5.2 동역학적 달성 가능성

로봇의 동역학적 한계(최대 추력, 토크 한계, 관절 속도 한계 등)를 고려하여, 계획된 궤적이 물리적으로 실행 가능한지를 검사한다.

매니퓰레이터 로봇의 경우, 역동역학(inverse dynamics)을 통해 궤적 추종에 필요한 관절 토크를 계산하고, 이것이 모터의 토크 한계를 초과하지 않는지를 확인한다.

$|\tau_i(t)| \leq \tau_{i,\max} \quad \forall i,\ \forall t$

6. 달성 가능성 검사의 계산 복잡도

검사 유형	계산 복잡도	비고
논리적 달성 가능성	$O(n \cdot \vert S \vert)$	계획 길이 $n$ 에 비례
에너지 달성 가능성	$O(n)$	누적 합 계산
시간 창 호환성	$O(n)$	개별 검사
선행 제약 일관성	$O(n + m)$	CPM, DAG 최장 경로
운동학적 달성 가능성	$O(n \cdot p)$	경로 점 수 $p$
전체 통합 검사	$O(n \cdot (p + \vert S \vert))$	모든 검사 합산

7. 비달성 가능 계획의 처리

달성 가능성 검사에서 비달성 가능(infeasible)으로 판정된 계획에 대해서는 다음과 같은 후속 처리가 필요하다.

7.1 진단 정보 생성

비달성 가능의 **원인(cause)**을 정확하게 식별하는 것이 재계획의 효율성을 좌우한다. 진단 정보는 다음을 포함한다.

위반된 제약의 유형 (에너지, 시간, 운동학 등)
위반이 발생한 계획 내 위치 (행동 인덱스, 시점)
위반의 정도 (여유분 대비 초과량)

7.2 이완 기반 수정(Relaxation-Based Repair)

비달성 가능 계획을 최소한의 수정으로 달성 가능하게 변환하는 전략이다. 이완의 방향은 다음과 같다.

시간 이완: 마감 시한의 완화 또는 실행 속도의 조정
자원 이완: 추가 자원(예: 충전, 자원 보급) 행동의 삽입
목표 이완: 일부 목표의 포기 또는 대체 목표로의 전환
경로 이완: 대안 경로의 탐색

7.3 재계획(Replanning)

이완으로 해결이 불가능한 경우, 비달성 가능 원인을 반영하여 새로운 계획을 수립하는 **재계획(replanning)**이 수행된다. 재계획은 전체 계획의 재생성(full replanning) 또는 비달성 가능 부분만의 국소적 재계획(local replanning)으로 수행될 수 있다.

8. 확률적 달성 가능성 평가

결정론적 달성 가능성 검사는 모든 매개변수가 정확히 알려져 있다고 가정하지만, 실제로는 행동 소요 시간, 에너지 소비, 센서 관측 등에 불확실성이 존재한다. **확률적 달성 가능성(probabilistic feasibility)**은 계획이 성공적으로 완수될 확률을 평가한다.

$P_{\text{feasible}}(\pi) = P\left(\bigcap_{i=1}^{n} \text{constraint}_i \text{ satisfied}\right)$

Monte Carlo 시뮬레이션을 통해 다수의 시나리오에서 계획을 실행하고, 성공 비율을 달성 가능 확률의 추정치로 사용하는 방법이 실용적으로 활용된다.

$\hat{P}_{\text{feasible}} = \frac{1}{N} \sum_{k=1}^{N} \mathbb{1}[\text{scenario}_k \text{ succeeds}]$

여기서 $N$ 은 시뮬레이션 횟수, $\mathbb{1}[\cdot]$ 은 지시 함수(indicator function)이다.

9. 요약

임무 달성 가능성 검사는 논리적, 물리적, 자원적, 시간적 측면에서의 종합적 평가를 수행하여, 수립된 계획이 실제로 실행 가능한지를 사전에 판별하는 핵심 과정이다. VAL 등의 자동 검증 도구, 임계 경로법에 의한 시간 일관성 검사, 에너지 불변조건에 의한 자원 검사 등이 체계적으로 적용된다. 비달성 가능 계획에 대해서는 진단 정보의 생성, 이완 기반 수정, 재계획이 수행되며, 불확실 환경에서는 확률적 달성 가능성 평가를 통해 계획의 강건성을 정량적으로 평가할 수 있다.

10. 참고 문헌

Howey, R., Long, D., & Fox, M. (2004). “VAL: Automatic plan validation, continuous effects and mixed initiative planning using PDDL.” Proceedings of the IEEE International Conference on Tools with Artificial Intelligence (ICTAI), pp. 294–301.
Ghallab, M., Nau, D., & Traverso, P. (2004). Automated Planning: Theory and Practice. Morgan Kaufmann.
Fox, M., & Long, D. (2003). “PDDL2.1: An extension to PDDL for expressing temporal planning domains.” Journal of Artificial Intelligence Research, 20, pp. 61–124.
LaValle, S. M. (2006). Planning Algorithms. Cambridge University Press.
Bäckström, C., & Nebel, B. (1995). “Complexity results for SAS+ planning.” Computational Intelligence, 11(4), pp. 625–655.

v1.0 | 로봇공학 서적 – Volume 9, Part 53, Chapter 397, Section 45