1316.13 GraphPlan 알고리즘의 구조

1316.13 GraphPlan 알고리즘의 구조

1. GraphPlan의 개요

GraphPlan은 Blum과 Furst(1995, 1997)가 제안한 플래닝 알고리즘으로, 플래닝 그래프(planning graph)라는 특수한 자료 구조를 구축하고 이를 분석하여 계획을 추출하는 방식으로 동작한다. GraphPlan은 1990년대 후반 플래닝 연구에 혁신을 가져왔으며, 이후 휴리스틱 탐색 플래너의 발전에 핵심적인 영감을 제공하였다.

2. 알고리즘의 두 단계

GraphPlan은 두 단계의 교대적 실행으로 구성된다:

  1. 그래프 확장(Graph Expansion): 플래닝 그래프를 한 수준(level)씩 확장하여 도달 가능한 명제와 적용 가능한 액션을 기록한다.
  2. 솔루션 추출(Solution Extraction): 확장된 그래프에서 역방향으로 탐색하여 유효한 계획을 추출한다.

이 두 단계를 목표 조건이 그래프에 도달할 때까지, 그리고 유효한 계획이 추출될 때까지 반복한다.

3. 플래닝 그래프의 구조

플래닝 그래프는 교대하는 두 종류의 계층(layer)으로 구성된다:

3.1 명제 계층(Proposition Layer)

각 수준 i에서 도달 가능한 명제(술어 인스턴스)의 집합 P_i이다. P_0 = s_0(초기 상태)으로 시작한다.

3.2 액션 계층(Action Layer)

각 수준 i에서 적용 가능한 액션의 집합 A_i이다. 전제 조건이 P_i에 포함되고 상호 배제(mutex)가 아닌 액션이 포함된다.

3.3 계층 간 연결

P_0 → A_0 → P_1 → A_1 → P_2 → A_2 → P_3 → ...
  • P_i의 명제가 A_i의 액션의 전제 조건으로 연결된다.
  • A_i의 액션의 효과가 P_{i+1}의 명제로 연결된다.
  • 각 명제 계층에는 “무행동(no-op)” 액션이 포함되어, 이전 수준의 명제를 다음 수준으로 전파한다.

4. 전체 알고리즘

GRAPHPLAN(initial_state, goal):
    graph ← initialize(initial_state)
    level ← 0

    LOOP:
        IF goal ⊆ P[level] AND no mutex among goal propositions:
            plan ← EXTRACT_SOLUTION(graph, goal, level)
            IF plan ≠ FAILURE:
                RETURN plan
        
        IF graph has leveled off (P[level] = P[level-1]):
            RETURN "No plan exists"
        
        EXPAND_GRAPH(graph, level)
        level ← level + 1

5. 상호 배제(Mutex) 관계

GraphPlan의 핵심 혁신 중 하나는 상호 배제(mutual exclusion, mutex) 관계의 추론이다:

5.1 액션 간 mutex

두 액션 a_1과 a_2가 같은 수준에서 mutex인 조건:

  1. 비일관적 효과: 한 액션의 효과가 다른 액션의 효과를 부정한다
  2. 간섭: 한 액션의 효과가 다른 액션의 전제 조건을 삭제한다
  3. 경쟁적 요구: 두 액션의 전제 조건이 이전 수준에서 mutex이다

5.2 명제 간 mutex

두 명제 p와 q가 같은 수준에서 mutex인 조건:

  • p를 달성하는 모든 액션이 q를 달성하는 모든 액션과 mutex이다

6. GraphPlan의 특성

6.1 완전성

GraphPlan은 완전하다. 해가 존재하면 반드시 찾으며, 그래프가 수렴(level off)하면 해가 없음을 판정할 수 있다.

6.2 최적성

GraphPlan은 최소 수준(최소 병렬 단계 수)의 계획을 찾는다. 이는 최소 순차 액션 수와는 다를 수 있다.

6.3 시간 복잡도

그래프 확장은 각 수준에서 다항 시간에 수행되지만, 솔루션 추출은 최악의 경우 NP-완전이다.

7. GraphPlan의 역사적 의의

GraphPlan 자체는 현대 플래너에서 직접 사용되지 않지만, 그 핵심 아이디어는 현대 플래닝의 기반을 형성한다:

  1. 삭제 완화 휴리스틱: 플래닝 그래프의 수준 수가 휴리스틱 추정으로 사용되며, FF 플래너의 h^{\text{FF}} 휴리스틱의 기초가 된다.
  2. 상호 배제 분석: mutex 관계의 추론이 다양한 플래너의 가지치기에 활용된다.
  3. 도달 가능성 분석: 플래닝 그래프가 명제의 도달 가능성을 효율적으로 추정한다.

8. 참고 문헌

  • 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.
  • Haslum, P., Lipovetzky, N., Magazzeni, D., & Muise, C. (2019). An Introduction to the Planning Domain Definition Language. Morgan & Claypool Publishers.