계산 복잡도와 실시간 제약 (Computational Complexity and Real-Time Constraints)
1. 개요
자율 계획의 계산 복잡도는 실시간 로봇 시스템에서의 적용을 제한하는 핵심 요소이다. 계획 문제의 이론적 복잡도 분류, 실제 계획기의 성능, 실시간 제약 하에서의 대응 전략을 다룬다.
2. 이론적 복잡도
2.1 고전적 계획의 복잡도
| 문제 | 복잡도 |
|---|---|
| 계획 존재 판정 (plan existence) | PSPACE-complete |
| 최적 계획 (optimal planning) | \text{FP}^{\text{NP}[\log n]}-complete |
| 제한된 길이의 계획 | NP-complete |
2.2 확장된 계획의 복잡도
| 계획 유형 | 복잡도 |
|---|---|
| 시간적 계획 (temporal) | PSPACE-complete |
| 수치적 계획 (numeric) | 결정 불가능 (일반 경우) |
| 확률적 계획 | EXPTIME-complete |
| 조건부 계획 | 2-EXPTIME-complete |
3. 실제 계획기의 성능
이론적 최악 복잡도에도 불구하고, 현대 계획기는 휴리스틱 탐색을 통해 많은 실용적 문제를 효율적으로 해결한다.
3.1 벤치마크 성능
| 문제 규모 | 객체 수 | 행동 수 | 계획 생성 시간 |
|---|---|---|---|
| 소규모 | ~10 | ~5 | < 1초 |
| 중규모 | ~50 | ~10 | 1~10초 |
| 대규모 | ~200 | ~20 | 10초~수분 |
| 극대규모 | ~1000 | ~50 | 수분~타임아웃 |
4. 실시간 제약 하의 대응 전략
4.1 임의 시간 계획 (Anytime Planning)
지정된 시간 내에서 최선의 계획을 반환하고, 추가 시간이 주어지면 계획을 점진적으로 개선한다.
4.2 증분적 계획 (Incremental Planning)
이전 계획의 일부를 재사용하여, 변경된 부분만 재계획한다. 전체 재계획보다 빠르다.
4.3 계획 캐싱
자주 발생하는 목표에 대한 계획을 캐싱하여, 동일한 목표가 재요청될 때 즉시 반환한다.
4.4 계층적 분해 (HTN)
HTN 방식의 태스크 분해는 탐색 공간을 축소하여 계획 속도를 향상시킨다.
4.5 도메인 특화 휴리스틱
특정 로봇 도메인에 최적화된 휴리스틱을 설계하여 탐색 효율을 높인다.
5. 로봇 시스템에서의 시간 예산
| 시나리오 | 허용 계획 시간 | 적합한 전략 |
|---|---|---|
| 비상 대응 | < 100ms | 하드코딩 (계획 불가) |
| 내비게이션 재계획 | < 1초 | 증분적 계획 |
| 임무 초기 계획 | < 10초 | 일반 계획기 |
| 복잡 다단계 임무 | < 60초 | 최적 계획기 |
| 오프라인 임무 준비 | 제한 없음 | 최적 계획기 |
6. 참고 문헌
- Bylander, T. (1994). “The Computational Complexity of Propositional STRIPS Planning.” Artificial Intelligence, 69(1-2), 165-204.
- Ghallab, M., Nau, D., & Traverso, P. (2016). Automated Planning and Acting. Cambridge University Press.
| 버전 | 날짜 | 변경 사항 |
|---|---|---|
| v0.1 | 2026-04-05 | 초안 작성 |