GraphPlan 알고리즘의 동작 원리 (Operating Principles of the GraphPlan Algorithm)

1. 개요

GraphPlan은 Blum과 Furst(1997)가 개발한 플래닝 알고리즘으로, 플래닝 그래프를 확장한 후 역방향 추출(backward extraction)을 통해 계획을 생성한다. 확장과 추출의 두 단계를 반복하며, 계획이 존재하지 않는 경우도 효율적으로 감지한다.

2. 알고리즘의 두 단계

2.1 단계: 그래프 확장 (Graph Expansion)

초기 상태 P_0에서 시작하여 명제 계층과 행동 계층을 교대로 확장한다. 목표 조건 G의 모든 명제가 뮤텍스 없이 동일 계층에 포함될 때까지 확장을 계속한다.

2.2 단계: 해 추출 (Solution Extraction)

목표 조건이 포함된 마지막 명제 계층에서 시작하여, 역방향으로 각 계층에서 목표를 달성하는 행동을 선택한다. 이 과정은 역방향 탐색의 일종이며, 뮤텍스 관계를 이용하여 가지치기를 수행한다.

3. 알고리즘 요약

function GraphPlan(P):
    PlanGraph = initialize(s₀)
    loop:
        if G ⊆ last_prop_layer AND no mutex among G:
            plan = extract(PlanGraph, G)
            if plan ≠ FAILURE:
                return plan
        if PlanGraph has leveled off:
            return FAILURE
        extend(PlanGraph)  // 한 계층 확장

4. 해 추��의 역추적

각 명제 계층에서 목표 명제를 달성하는 행동 집합을 ��택하고, 선택된 행동의 전제 조건이 이전 계층의 새로운 ���위 목표가 된다.

계층 k: 목표 {g₁, g₂} → 행동 {a₁(g₁을 달성), a₂(g₂를 달성)} 선택
         a₁과 a₂가 뮤텍스가 아님�� 확인
계층 k-1: 새 하위 목표 = Pre(a₁) ∪ Pre(a₂)
...
계층 0: 하위 목표 ⊆ s₀ 이면 계획 완성

5. GraphPlan의 특성

6. 안정화 (Level-Off) 조건

플래닝 그래프가 더 이상 새로운 명제를 추가하지 않고, 뮤텍스도 변하지 않는 상태에 도달하면 안정화(level-off)된 것이다. 이 상태에서도 계획을 추출할 수 없다면, 유효한 계획이 존재하지 않는다.

7. 현대 플래닝에서의 위치

GraphPlan 자체��� 현대 계획기에서 직접 사용되지 않으나, 플래닝 그래프 구조는 휴리스틱 계산(h_{\max}, h_{\text{add}}, h_{\text{FF}})의 기반으로 여전히 활용된다.

8. 참고 문헌

• Blum, A., & Furst, M. (1997). “Fast Planning Through Planning Graph Analysis.” Artificial Intelligence, 90(1-2), 281-300.
• Ghallab, M., Nau, D., & Traverso, P. (2016). Automated Planning and Acting. Cambridge University Press.