1316.17 GraphPlan의 복잡도와 성능 특성
1. 계산 복잡도 분석
1.1 그래프 확장의 복잡도
플래닝 그래프의 단일 수준 확장은 다항 시간(polynomial time)에 수행된다:
- 액션 식별: O(\lvert\mathcal{A}_{\text{ground}}\rvert \cdot k_{\text{pre}}), 여기서 k_{\text{pre}}는 평균 전제 조건 크기
- 뮤텍스 계산: O(\lvert A_i\rvert^2 + \lvert P_{i+1}\rvert^2)
- 전체 수준 확장: 도메인 크기에 대해 다항식
그래프의 최대 수준 수는 O(n) (n: 명제 수)에 의해 제한되므로, 전체 그래프 확장의 복잡도는 다항식이다.
1.2 솔루션 추출의 복잡도
솔루션 추출은 최악의 경우 NP-완전이다. 각 수준에서 목표 리터럴에 대한 비뮤텍스 액션 집합을 선택하는 문제가 CSP(제약 충족 문제)로 환원되기 때문이다.
그러나 메모이제이션에 의해 동일한 (목표 집합, 수준) 쌍이 재평가되지 않으므로, 실제 성능은 대부분의 벤치마크 도메인에서 합리적이다.
1.3 전체 복잡도
T_{\text{total}} = \sum_{i=0}^{L} (T_{\text{expand}}(i) + T_{\text{extract}}(i))
여기서 L은 최종 그래프 수준, T_{\text{expand}}는 확장 비용, T_{\text{extract}}는 추출 비용이다. 확장은 다항식이지만 추출은 NP-완전이므로, 전체 최악 복잡도는 지수적이다.
2. 그래프 수렴과 종료 보장
플래닝 그래프는 다음의 단조적 성질에 의해 유한 시간에 수렴한다:
- P_i \subseteq P_{i+1} (명제 수 비감소)
- A_i \subseteq A_{i+1} (액션 수 비감소)
- 뮤텍스 수 비증가
유한한 명제 집합에서 이 세 성질이 동시에 성립하므로, 유한한 수준 k에서 P_k = P_{k+1}이고 뮤텍스도 변하지 않는 수렴 상태에 도달한다.
수렴 후에도 솔루션이 추출되지 않으면, 메모이제이션 테이블의 수렴을 추가로 확인하여 “해 없음“을 판정한다.
3. 성능 특성
3.1 IPC 벤치마크에서의 성능
GraphPlan은 1990년대 후반 IPC에서 우수한 성능을 보였으나, 2000년대 이후 휴리스틱 탐색 플래너(FF, Fast Downward)에 의해 성능이 초월되었다. 특히 대규모 도메인에서 솔루션 추출의 NP-완전 특성이 병목이 된다.
3.2 강점 도메인
- 병렬 계획이 필요한 도메인: GraphPlan은 각 수준에서 병렬 실행 가능한 액션 집합을 자연스럽게 생성한다.
- 뮤텍스 분석이 효과적인 도메인: 뮤텍스 관계가 탐색 공간을 크게 줄이는 도메인에서 효과적이다.
- 소규모 도메인: 명제와 액션 수가 적은 도메인에서 빠르게 최적 병렬 계획을 생성한다.
3.3 약점 도메인
- 장거리 목표 도메인: 최적 계획의 길이가 긴 도메인에서 그래프 수준 수가 증가하여 솔루션 추출 비용이 급증한다.
- 대규모 상태 공간: 명제 수가 많으면 각 수준의 확장과 뮤텍스 계산 비용이 증가한다.
- 숫자 변수 도메인: GraphPlan은 순수 명제 수준에서 동작하므로 수치 플루언트를 직접 처리하지 못한다.
4. GraphPlan과 현대 플래너의 비교
| 특성 | GraphPlan | FF | Fast Downward |
|---|---|---|---|
| 탐색 전략 | 그래프 확장 + 역방향 추출 | 전방 휴리스틱 탐색 | 전방 휴리스틱 탐색 |
| 계획 형태 | 병렬 (수준 기반) | 순차적 | 순차적 |
| 휴리스틱 | 뮤텍스 기반 가지치기 | 삭제 완화 (h^{\text{FF}}) | 다양 (h^{\text{LM}}, h^{\text{FF}} 등) |
| 수치 플래닝 | 미지원 | Metric-FF로 지원 | 지원 |
| 최적성 | 최소 병렬 수준 | 비보장 (만족) | 설정에 따라 |
| 대규모 도메인 | 제한적 | 우수 | 우수 |
5. GraphPlan의 현대적 의의
GraphPlan 자체는 현대 플래닝에서 직접 사용되지 않지만, 그 핵심 아이디어는 다음에서 계속 활용된다:
- h^{\text{max}} 휴리스틱: 플래닝 그래프의 수준 수에 대응하는 휴리스틱
- h^{\text{FF}} 휴리스틱: 플래닝 그래프에서의 완화된 계획 추출
- 뮤텍스 기반 가지치기: 다양한 플래너의 전처리 및 탐색 가지치기
- 도달 가능성 분석: 그래프 확장을 통한 명제 도달 가능성 추정
6. 참고 문헌
- Blum, A. L. & Furst, M. L. (1997). “Fast Planning Through Planning Graph Analysis.” Artificial Intelligence, 90(1–2), 281–300.
- Ghallab, M., Nau, D., & Traverso, P. (2004). Automated Planning: Theory and Practice. Morgan Kaufmann.
- Hoffmann, J. & Nebel, B. (2001). “The FF Planning System: Fast Plan Generation Through Heuristic Search.” Journal of Artificial Intelligence Research, 14, 253–302.