뮤텍스 관계와 상호 배제 분석 (Mutex Relations and Mutual Exclusion Analysis)

1. 개요

뮤텍스(mutex, mutual exclusion) 관계는 플래닝 그래프에서 동시에 성립할 수 없는 두 행동 또는 두 명제 사이의 관계이다. 뮤텍스 분석은 무효한 행동 조합을 사전에 식별하여 탐색 공간을 축소하며, GraphPlan의 효율성과 현대 계획기의 휴리스틱 정확도의 핵심이다.

2. 행동 간 뮤텍스

두 행동 a_1과 a_2가 동일 계층에서 뮤텍스인 조건은 다음 세 가지이다.

2.1 불일치 효과 (Inconsistent Effects)

한 행동의 추가 효과가 다른 행동의 삭제 효과인 경우이다.

\text{Add}(a_1) \cap \text{Del}(a_2) \neq \emptyset \quad \text{or} \quad \text{Add}(a_2) \cap \text{Del}(a_1) \neq \emptyset

2. 간섭 (Interference)

한 행동의 삭제 효과가 다른 행동의 전제 조건인 경우이다.

\text{Del}(a_1) \cap \text{Pre}(a_2) \neq \emptyset \quad \text{or} \quad \text{Del}(a_2) \cap \text{Pre}(a_1) \neq \emptyset

2.2 경쟁 전제 (Competing Needs)

두 행동의 전제 조건 중 하나라도 상호 뮤텍스인 명제 쌍이 존재하는 경우이다.

\exists p_1 \in \text{Pre}(a_1), p_2 \in \text{Pre}(a_2) : \text{mutex}(p_1, p_2)

명제 간 뮤텍스

두 명제 p_1과 p_2가 동일 계층에서 뮤텍스인 조건은 다음과 같다.

불일치 지원 (Inconsistent Support): p_1과 p_2를 각각 달성하는 모든 행동 쌍이 뮤텍스인 경우이다.

\forall a_1 \in \text{achievers}(p_1), \forall a_2 \in \text{achievers}(p_2) : \text{mutex}(a_1, a_2)

3. 뮤텍스의 전파

플래닝 그래프의 확장 과정에서 뮤텍스 관계는 계층 간에 전파된다. 이전 계층의 뮤텍스 관계가 현재 계층의 행동 적용 가능성에 영향을 미친다.

4. 뮤텍스 분석의 활용

5. 예시

행동: move(robot, A, B)와 move(robot, A, C)
뮤텍스 이유: 불일치 효과
  - move(A,B)의 Add: at(robot,B)
  - move(A,C)의 Del: at(robot,A) (move(A,B)의 Pre)
  → 간섭에 의한 뮤텍스

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.