396.14 임무 재계획(Mission Replanning) 기능
1. 임무 재계획의 정의
임무 재계획(Mission Replanning)은 임무 수행 중에 환경 변화, 시스템 고장, 목표 변경 등의 사유로 기존 계획이 더 이상 유효하지 않거나 최적이 아니게 되었을 때, 현재 상태를 기반으로 계획을 수정하거나 새롭게 수립하는 과정이다.
형식적으로, 재계획 문제는 다음과 같이 정의된다:
\mathcal{F}_{\text{replan}}: \Pi_{\text{old}} \times \mathcal{S}_{\text{current}} \times \Delta\mathcal{E} \rightarrow \Pi_{\text{new}}
여기서 \Pi_{\text{old}}는 기존 계획, \mathcal{S}_{\text{current}}는 현재 시스템 상태, \Delta\mathcal{E}는 감지된 환경 변화이다.
2. 재계획 트리거 분류
재계획을 촉발하는 이벤트(Trigger)는 그 원인에 따라 다음과 같이 분류된다:
2.1 외부 트리거
| 트리거 유형 | 설명 | 긴급도 |
|---|---|---|
| 목표 변경 | 운용자에 의한 임무 목표 수정 | 높음 |
| 환경 변화 | 새로운 장애물, 기상 변화 | 중~높음 |
| 위협 감지 | 적대적 행동, 안전 위협 | 최상 |
| 기회 발견 | 예상치 못한 유리한 조건 | 낮음 |
2.2 내부 트리거
| 트리거 유형 | 설명 | 긴급도 |
|---|---|---|
| 과업 실패 | 특정 과업의 실행 실패 | 높음 |
| 하드웨어 고장 | 센서, 액추에이터 등의 고장 | 높음 |
| 에너지 부족 | 예상보다 빠른 에너지 소모 | 높음 |
| 시간 초과 | 계획 대비 지연 누적 | 중간 |
3. 재계획 전략
3.1 완전 재계획 (Complete Replanning)
기존 계획을 완전히 폐기하고 현재 상태에서 새로운 계획을 처음부터 수립하는 전략이다:
\Pi_{\text{new}} = \text{Plan}(\mathcal{S}_{\text{current}}, \mathcal{G}, \mathcal{O}, \mathcal{C}_{\text{updated}})
장점: 변경된 조건을 완전히 반영한 전역 최적 계획을 생성할 수 있다.
단점: 계산 비용이 높으며, 계획 수립 동안 로봇의 행동이 중단될 수 있다.
3.2 증분 재계획 (Incremental Replanning)
기존 계획의 변경이 필요한 부분만 국소적으로 수정하는 전략이다:
\Pi_{\text{new}} = \text{Patch}(\Pi_{\text{old}}, \delta_{\text{change}})
여기서 \delta_{\text{change}}는 감지된 변화에 의해 영향을 받는 계획의 부분이다.
경로 재계획의 예: D* Lite 알고리즘은 그래프의 간선 비용이 변경되었을 때, 이전 탐색 정보를 재활용하여 효율적으로 최단 경로를 갱신한다(Koenig and Likhachev, 2002):
\text{rhs}(s) = \begin{cases} 0 & \text{if } s = s_{\text{goal}} \\ \min_{s' \in \text{Succ}(s)} [c(s, s') + g(s')] & \text{otherwise} \end{cases}
3.3 임기응변 재계획 (Anytime Replanning)
시간이 허용하는 한 계속 계획을 개선하는 전략이다. 초기에 빠르게 실행 가능한 계획을 생성하고, 남은 시간 동안 점진적으로 품질을 향상시킨다:
J(\Pi_{\text{new}}^{(k+1)}) \leq J(\Pi_{\text{new}}^{(k)}), \quad \forall k
ARA*(Anytime Repairing A*)는 대표적인 임기응변 계획 알고리즘으로, 가중 A*의 가중치를 점진적으로 감소시켜 최종적으로 최적해에 수렴한다(Likhachev et al., 2003).
4. 재계획의 범위 결정
재계획의 효율성은 변경 범위(Scope of Replanning)의 적절한 결정에 의존한다. 변경 범위는 변화의 영향 분석(Impact Analysis)을 통해 결정된다:
\text{Scope}(\delta) = \{t_i \in \Pi_{\text{old}} \mid \text{affected}(t_i, \delta) = \text{True}\}
영향 분석의 기준:
- 인과 관계(Causal Dependency): 변화가 영향을 미치는 과업의 전제 조건이 변경되었는가
- 자원 의존(Resource Dependency): 자원 가용성 변화가 과업 실행에 영향을 미치는가
- 시간 의존(Temporal Dependency): 시간 제약의 변경이 후속 과업에 영향을 미치는가
5. 재계획의 안정성
과도한 재계획은 시스템의 안정성을 저해할 수 있다. 재계획 안정성(Replanning Stability)을 보장하기 위한 메커니즘은 다음과 같다:
5.1 재계획 억제 (Replanning Suppression)
동일한 원인에 의한 반복적 재계획을 방지하기 위해 최소 재계획 간격(Minimum Replanning Interval)을 설정한다:
t_{\text{replan}}^{(k+1)} - t_{\text{replan}}^{(k)} \geq \Delta T_{\text{min}}
5.2 계획 안정성 메트릭 (Plan Stability Metric)
기존 계획과 새 계획 간의 유사도를 측정하여, 과도한 변경을 억제한다:
\text{Stability}(\Pi_{\text{old}}, \Pi_{\text{new}}) = 1 - \frac{|\Pi_{\text{old}} \triangle \Pi_{\text{new}}|}{|\Pi_{\text{old}} \cup \Pi_{\text{new}}|}
여기서 \triangle은 대칭 차집합(Symmetric Difference)이다. 안정성이 임계값 이하로 하락하면 재계획의 필요성을 재평가한다.
5.3 히스테리시스 (Hysteresis)
재계획 트리거 임계값에 히스테리시스를 도입하여 경계 조건 근처에서의 진동(Oscillation)을 방지한다:
\text{Trigger ON}: \quad \Delta > \theta_{\text{upper}}
\text{Trigger OFF}: \quad \Delta < \theta_{\text{lower}}, \quad \theta_{\text{lower}} < \theta_{\text{upper}}
6. 실시간 재계획의 기술적 과제
- 계산 시간 제약: 재계획 동안에도 로봇은 안전한 행동을 유지해야 하므로, 재계획의 최대 허용 시간이 존재한다.
- 정보의 불완전성: 재계획 시점에서 환경의 완전한 정보를 확보하기 어렵다.
- 중단/재개 관리: 재계획에 의해 현재 수행 중인 과업이 중단될 때, 안전한 중단과 원활한 재개를 보장해야 한다.
- 계획 일관성: 재계획된 계획이 현재까지의 수행 결과와 일관되어야 한다.
7. 참고 문헌
- Koenig, S., and Likhachev, M. (2002). “D* Lite.” Proceedings of the AAAI Conference on Artificial Intelligence, 476-483.
- Likhachev, M., Gordon, G. J., and Thrun, S. (2003). “ARA*: Anytime A* with Provable Bounds on Sub-Optimality.” Advances in Neural Information Processing Systems (NIPS), 767-774.
- Nebel, B., and Koehler, J. (1995). “Plan Reuse versus Plan Generation: A Theoretical and Empirical Analysis.” Artificial Intelligence, 76(1-2), 427-454.
Version: v1.0 (2026-03-23)