플래닝 그래프의 개념과 구성 (Concept and Construction of Planning Graphs)

1. 개요

플래닝 그래프(planning graph)는 Blum과 Furst(1997)가 Graphplan 알고리즘을 위해 도입한 다층 데이터 구조로, 계획 문제에서 도달 가능한 명제와 행동을 계층적으로 확장하여 표��한다. 휴리스틱 계산, 상호 배제(mutex) 분석, 유효 계획 존재 여부의 빠른 판정에 활용된다.

2. 구조

플래닝 그래프는 교대하는 명제 계층(proposition layer)과 행동 계층(action layer)으로 구성된다.

P₀ → A₀ → P₁ → A₁ → P₂ → A₂ → ...

2.1 명제 계층 P_i

해당 시점에서 참일 수 있는 모든 명제의 집합이다. P_0 = s_0 (초기 상태)이다.

2.2 행동 계층 A_i

P_i에서 적용 가능한 모든 행동의 집합이다. 각 행동의 전제 조���이 P_i에 포함되어야 한다.

2.3 확장 규칙

1. P_{i+1}은 A_i의 모든 행동의 추가 효과와 P_i의 기존 명제(무행동, no-op)를 포함한다.
2. A_i는 P_i에서 전제 조건이 충족되는 모든 행동을 포함한다.

3. 구성 과정

1. P₀ = s₀ (초기 상태)
2. A₀ = {a ∈ A : Pre(a) ⊆ P₀} ∪ {no-op(p) : p ∈ P₀}
3. P₁ = P₀ ∪ {Add(a) : a ∈ A₀}
4. 뮤텍스 계산 (A₀, P₁)
5. 반복: Aᵢ, Pᵢ₊₁ 확장 및 뮤텍스 계산
6. 종료: Pᵢ₊₁ = Pᵢ (안정화) 또는 G ⊆ Pᵢ

4. 뮤텍스 관계

두 명제 또는 두 행동이 동시에 성립할 수 없는 관계이다.

4.1 행동 간 뮤텍스

4.2 명제 간 뮤텍스

��� 명��를 달성하는 모든 행동 쌍이 뮤텍스인 경우, 해당 두 명제도 뮤텍스이다.

5. 플래닝 그래프의 활용

6. 참고 문헌

• 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.