부분 순서 계획과 완전 순서 계획의 비교 (Comparison of Partial-Order and Total-Order Plans)
1. 개요
계획에서 행동의 순서를 얼마나 결정하느냐에 따라 완전 순서(total-order) 계획과 부분 순서(partial-order) 계획으로 구분된다. 두 표현의 장단점과 적합한 응용 분야를 비교한다.
2. 비교
| 특성 | 완전 순서 계획 | 부분 순서 계획 |
|---|---|---|
| 행동 순서 | a_1 < a_2 < a_3 < \ldots | 필요한 순서만 지정 |
| 표현 | 선형 시퀀스 | 방향 비순환 그래프 (DAG) |
| 유연성 | 고정된 단일 실행 순서 | 복수의 유효 실행 순서 |
| 병렬 행동 | 명시적으로 표현 불가 | 자연스럽게 식별 |
| 탐색 공간 | O(n!) 순열 | 순서 독립 부분 축소 |
| 실행 적응성 | 고정 순서만 가능 | 실행 시 순서 조정 가능 |
| 대표 계획기 | FF, Fast Downward | POPF, UCPOP |
3. 부분 순서의 이점: 최소 약속 (Least Commitment)
부분 순서 플래닝은 최소 약속(least commitment) 원칙을 따른다. 필요하지 않은 순서 결정을 미루어, 탐색 중 불필요한 선택에 의한 백트래킹을 줄인다.
4. 완전 순서의 이점: 단순한 휴리스틱
현대의 고성능 휴리스틱은 전방 탐색 기반 완전 순서 계획기에서 더 효과적으로 동작한다. FF, Fast Downward 등의 최고 성능 계획기가 완전 순서를 채택한 이유이다.
5. 시간적 계획에서의 부분 순서
시간적 계획(temporal planning)에서는 부분 순서가 필수적이다. 병렬 실행 가능한 행동을 식별하여 총 실행 시간을 최소화한다. POPF 계획기가 시간적 부분 순서 계획을 지원한다.
6. 로봇 공학에서의 선택
| 상황 | 권장 |
|---|---|
| 단순 순차 임무 | 완전 순서 |
| 병렬 실행 필요 | 부분 순서 |
| 시간 제약 | 부분 순서 (POPF) |
| 최고 성능 요구 | 완전 순서 (FF, LAMA) |
7. 참고 문헌
- Penberthy, J., & Weld, D. (1992). “UCPOP: A Sound, Complete, Partial Order Planner for ADL.” KR 1992.
- Coles, A., et al. (2010). “Forward-Chaining Partial-Order Planning.” ICAPS 2010.
- Ghallab, M., Nau, D., & Traverso, P. (2016). Automated Planning and Acting. Cambridge University Press.
| 버전 | 날짜 | 변경 사항 |
|---|---|---|
| v0.1 | 2026-04-05 | 초안 작성 |