플래닝 문제의 계산 복잡도 (Computational Complexity of Planning Problems)
1. 개요
플래닝 문제의 계산 복잡도는 문제의 표현력(expressiveness)에 따라 다양한 수준에 걸친다. 이는 계획기 알고리즘의 이론적 한계를 결정하며, 실용적 계획기의 설계 전략에 직접적인 영향을 미친다.
2. 복잡도 분류
| 플래닝 유형 | 계획 존재 판정 | 최적 계획 |
|---|---|---|
| STRIPS (명제적) | PSPACE-complete | \text{FP}^{\text{NP}[\log n]} |
| ADL | PSPACE-complete | PSPACE-hard |
| 시간적 | PSPACE-complete | PSPACE-hard |
| 수치적 (일반) | 결정 불가능 | 결정 불가능 |
| 확률적 (MDP) | P (다항) | P |
| POMDP | EXPTIME-complete | EXPTIME |
| HTN (일반) | 결정 불가능 | - |
| HTN (제한) | NEXPTIME | - |
3. 실용적 함의
이론적 최악 복잡도에도 불구하고, 구조적 특성(도메인 특화 휴리스틱, 뮤텍스, 도달 가능성)을 활용하면 많은 실용적 문제를 효율적으로 해결할 수 있다.
4. 참고 문헌
- Bylander, T. (1994). “The Computational Complexity of Propositional STRIPS Planning.” AI, 69, 165-204.
- Ghallab, M., Nau, D., & Traverso, P. (2016). Automated Planning and Acting. Cambridge University Press.
| 버전 | 날짜 | 변경 사항 |
|---|---|---|
| v0.1 | 2026-04-05 | 초안 작성 |