1316.14 플래닝 그래프의 확장 절차

1. 확장 절차의 개요

플래닝 그래프의 확장(expansion)은 현재 명제 계층에서 적용 가능한 액션을 식별하고, 해당 액션의 효과로 다음 명제 계층을 생성하며, 상호 배제(mutex) 관계를 계산하는 과정이다. 이 과정은 단조적(monotonic)이어서, 각 수준에서 명제와 액션의 수가 이전 수준 이상으로 증가하거나 유지된다(Blum & Furst, 1997).

2. 확장의 단계별 절차

2.1 단계: 명제 계층 $P_i$ 에서 적용 가능 액션 식별

현재 명제 계층 $P_i$ 의 명제들 중에서, 전제 조건이 모두 $P_i$ 에 포함되고 전제 조건 간에 mutex가 없는 액션을 식별한다:

$A_i = \{a \in \mathcal{A}_{\text{ground}} \mid \text{pre}(a) \subseteq P_i \wedge \nexists p, q \in \text{pre}(a): \text{mutex}(p, q, i)\}$

2.2 단계: 무행동 액션(No-op) 추가

각 명제 $p \in P_i$ 에 대해, $p$ 를 이전 수준에서 다음 수준으로 전파하는 무행동(persistence) 액션을 추가한다:

$\text{no-op}_p: \text{pre} = \{p\}, \text{eff}^+ = \{p\}, \text{eff}^- = \emptyset$

무행동 액션은 “해당 명제가 변하지 않고 유지된다“는 프레임 가정을 명시적으로 표현한다.

2.3 단계: 다음 명제 계층 $P_{i+1}$ 생성

$A_i$ 의 모든 액션(무행동 포함)의 추가 효과를 합산하여 다음 명제 계층을 생성한다:

$P_{i+1} = \bigcup_{a \in A_i} \text{eff}^+(a)$

2.4 단계: 액션 간 mutex 계산

$A_i$ 의 액션 쌍에 대해 상호 배제 관계를 계산한다:

비일관적 효과(Inconsistent Effects):
$\text{mutex}(a_1, a_2) \leftarrow \exists p: p \in \text{eff}^+(a_1) \wedge p \in \text{eff}^-(a_2)$

간섭(Interference):
$\text{mutex}(a_1, a_2) \leftarrow \exists p: p \in \text{eff}^-(a_1) \wedge p \in \text{pre}(a_2)$

경쟁적 요구(Competing Needs):
$\text{mutex}(a_1, a_2) \leftarrow \exists p \in \text{pre}(a_1), q \in \text{pre}(a_2): \text{mutex}(p, q, i)$

2.5 단계: 명제 간 mutex 계산

$P_{i+1}$ 의 명제 쌍에 대해 상호 배제 관계를 계산한다:

$\text{mutex}(p, q, i+1) \leftarrow \forall a_p, a_q: (p \in \text{eff}^+(a_p) \wedge q \in \text{eff}^+(a_q)) \Rightarrow \text{mutex}(a_p, a_q, i)$

즉, $p$ 를 달성하는 모든 액션이 $q$ 를 달성하는 모든 액션과 mutex일 때, $p$ 와 $q$ 는 mutex이다.

3. 확장의 예시

초기 상태: $P_0 = \{(\text{robot\_at} \ r1 \ wp1), (\text{connected} \ wp1 \ wp2), (\text{gripper\_free} \ r1)\}$

수준 0 → 수준 1 확장:

$A_0$ 에 포함되는 액션: move(r1, wp1, wp2) (전제 조건이 $P_0$ 에 포함)
무행동: no-op(robot_at r1 wp1), no-op(connected wp1 wp2), no-op(gripper_free r1)

$P_1 = P_0 \cup \{(\text{robot\_at} \ r1 \ wp2)\}$

mutex: move(r1, wp1, wp2)와 no-op(robot_at r1 wp1)은 mutex (간섭: move가 robot_at r1 wp1을 삭제)

4. 그래프의 단조적 성장과 수렴

플래닝 그래프는 다음의 단조적 성질을 가진다:

$P_i \subseteq P_{i+1}, \quad A_i \subseteq A_{i+1}$

$\text{mutex}(p, q, i+1) \Rightarrow \text{mutex}(p, q, i) \text{ 는 반드시 성립하지는 않지만, mutex 수는 비증가}$

유한한 명제 집합에서 명제와 액션의 수가 단조 증가하고 mutex의 수가 단조 감소하므로, 유한한 수준에서 그래프가 수렴(level off)한다:

$\exists k: P_k = P_{k+1} \wedge \text{mutex}_k = \text{mutex}_{k+1}$

수렴 후에도 솔루션이 추출되지 않으면, 문제에 해가 없다고 판정한다.

5. 확장의 계산 비용

각 수준의 확장 비용은 다항 시간이다:

적용 가능 액션 식별: $O(\lvert\mathcal{A}\rvert \cdot k)$ (여기서 $k$ 는 평균 전제 조건 크기)
Mutex 계산: $O(\lvert A_i\rvert^2)$
총 비용: 도메인 크기에 대해 다항 시간

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.