1316.15 뮤텍스 관계의 추출과 활용

1. 뮤텍스의 정의

뮤텍스(mutex, mutual exclusion)는 플래닝 그래프에서 두 요소(액션 쌍 또는 명제 쌍)가 동일한 시간 단위에 동시에 존재할 수 없음을 나타내는 관계이다. 이 관계는 탐색 공간을 축소하고 휴리스틱 정보를 제공하는 핵심 메커니즘이다(Blum & Furst, 1997).

2. 액션 간 뮤텍스의 유형

2.1 비일관적 효과(Inconsistent Effects)

한 액션의 추가 효과가 다른 액션의 삭제 효과와 동일한 명제를 대상으로 하거나, 한 액션의 추가 효과가 다른 액션의 추가 효과와 모순되는 경우이다:

$\text{mutex}(a_1, a_2) \leftarrow \exists p: (p \in \text{eff}^+(a_1) \wedge p \in \text{eff}^-(a_2)) \vee (p \in \text{eff}^-(a_1) \wedge p \in \text{eff}^+(a_2))$

예시: move(r1, wp1, wp2)와 no-op(robot_at r1 wp1) — move가 (robot_at r1 wp1)을 삭제하는 반면 no-op은 이를 유지하므로 비일관적이다.

2.2 간섭(Interference)

한 액션의 효과(추가 또는 삭제)가 다른 액션의 전제 조건과 충돌하는 경우이다:

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

예시: move(r1, wp1, wp2)가 (robot_at r1 wp1)을 삭제하고, pick(r1, box1, wp1)이 (robot_at r1 wp1)을 전제 조건으로 요구하면 간섭 관계이다.

2.3 경쟁적 요구(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)$

이 유형은 이전 수준의 명제 뮤텍스에서 전파(propagation)된다.

3. 명제 간 뮤텍스

두 명제 $p$ 와 $q$ 가 수준 $i+1$ 에서 뮤텍스인 조건:

$\text{mutex}(p, q, i+1) \iff \forall a_p \in \text{achievers}(p, i), \forall a_q \in \text{achievers}(q, i): \text{mutex}(a_p, a_q, i)$

여기서 $\text{achievers}(p, i)$ 는 수준 $i$ 에서 명제 $p$ 를 효과로 생산하는 모든 액션의 집합이다. $p$ 를 달성하는 모든 방법이 $q$ 를 달성하는 모든 방법과 뮤텍스이면, $p$ 와 $q$ 도 뮤텍스이다.

4. 뮤텍스 추출 알고리즘

COMPUTE_MUTEXES(level_i):
    ;; 액션 뮤텍스
    FOR EACH pair (a1, a2) in A_i:
        IF inconsistent_effects(a1, a2) OR
           interference(a1, a2) OR
           competing_needs(a1, a2, mutex_props[i]):
            mark mutex(a1, a2, i)

    ;; 명제 뮤텍스
    FOR EACH pair (p, q) in P_{i+1}:
        IF all_achiever_pairs_mutex(p, q, mutex_actions[i]):
            mark mutex(p, q, i+1)

5. 뮤텍스의 단조적 감소

플래닝 그래프가 확장됨에 따라 뮤텍스 관계의 수는 단조적으로 감소(또는 유지)한다:

$\text{mutex\_count}(i+1) \leq \text{mutex\_count}(i)$

이는 새로운 수준에서 추가적인 액션(달성 방법)이 등장하면, 명제 간 뮤텍스 조건이 완화되기 때문이다.

6. 뮤텍스의 활용

6.1 솔루션 추출에서의 가지치기

솔루션 추출 단계에서 뮤텍스 관계를 확인하여 비호환 액션 조합을 사전에 배제한다. 이는 역방향 탐색의 분기 요인을 크게 줄인다.

6.2 휴리스틱 정보 제공

뮤텍스 관계는 플래닝 그래프 기반 휴리스틱에서 목표 달성의 난이도를 추정하는 데 활용된다. 목표 리터럴 간의 뮤텍스가 해소되는 최소 수준이 휴리스틱 값의 기반이 된다.

6.3 도달 불가능성 판정

목표 조건의 리터럴 쌍이 그래프 수렴 후에도 뮤텍스를 유지하면, 해당 목표는 달성 불가능하다고 판정할 수 있다.

6.4 현대 플래너에서의 간접 활용

FF 플래너의 $h^{\text{FF}}$ 휴리스틱은 플래닝 그래프의 뮤텍스를 무시한 완화된 버전을 사용하여 빠른 휴리스틱 계산을 달성한다. 뮤텍스 정보를 포함하면 정보성이 높아지지만 계산 비용이 증가한다.

7. 로봇 도메인에서의 뮤텍스 예시

;; 공간적 뮤텍스
(robot_at r1 wp1)과 (robot_at r1 wp2)는 항상 mutex
;; 로봇은 동시에 두 위치에 있을 수 없음

;; 자원 뮤텍스  
(gripper_free r1)과 (holding r1 box1)은 항상 mutex
;; 그리퍼가 비어 있으면서 물체를 잡고 있을 수 없음

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.
Hoffmann, J. & Nebel, B. (2001). “The FF Planning System: Fast Plan Generation Through Heuristic Search.” Journal of Artificial Intelligence Research, 14, 253–302.