1316.24 인과 링크와 위협 해소 메커니즘
1. 인과 링크의 구조와 역할
인과 링크(causal link)는 부분 순서 계획에서 두 액션 간의 인과적 의존 관계를 명시하는 구조이다. 인과 링크 a_p \xrightarrow{c} a_c는 다음의 세 가지 의미를 동시에 갖는다:
- 생산자(producer) a_p가 조건 c를 효과로 생산한다
- 소비자(consumer) a_c가 조건 c를 전제 조건으로 요구한다
- 보호 구간: a_p에서 a_c 사이에 c를 삭제하는 액션이 실행되지 않아야 한다
인과 링크는 계획의 정당성을 구조적으로 보장하는 메커니즘이며, “이 전제 조건이 왜 충족되는지“의 인과적 설명(causal explanation)을 제공한다.
2. 위협의 형식적 정의
위협(threat)은 인과 링크의 보호 구간을 침범하는 액션이다. 형식적으로, 인과 링크 a_p \xrightarrow{c} a_c��� 대해 액션 a_t가 위협이 되는 조건:
\text{threat}(a_t, a_p \xrightarrow{c} a_c) \iff c \in \text{eff}^-(a_t) \wedge \text{possibly}(a_p \prec a_t \prec a_c)
여기서 \text{possibly}(a_p \prec a_t \prec a_c)는 현재의 순서 제약 하에서 a_t가 a_p와 a_c 사이에 배치될 수 있음을 의미한다.
3. 위협 해소 전략
3.1 승격(Promotion)
위협 액션 a_t를 생산자 a_p 이전으로 순서를 강제한다:
O \leftarrow O \cup \{a_t \prec a_p\}
이에 의해 a_t는 c가 생산되기 전에 실행되므로, 인과 링크가 보호된다.
3.2 강등(Demotion)
위협 액션 a_t를 소비자 a_c 이후로 순서를 강제한다:
O \leftarrow O \cup \{a_c \prec a_t\}
이에 의해 a_t는 c가 소비된 이후에 실행되므로, 인과 링크가 보호된다.
3.3 분리(Separation)
리프팅된(비그라운딩된) 계획에서 변수 바인딩을 조정하여, a_t의 삭제 효과가 c와 통일(unification)되지 않도록 한다. 이는 ADL 수준의 POCL 플래너에서 사용되는 기법이다.
4. 해소 전략의 선택
| 상황 | 승격 가능 | 강등 가능 | 대응 |
|---|---|---|---|
| 양쪽 모두 가능 | 예 | 예 | 비결정적 선택 (역추적 대비) |
| 승격만 가능 | 예 | 아니오 | 승격 적용 |
| 강등만 가능 | 아니오 | 예 | 강등 적용 |
| 둘 다 불가 | 아니오 | 아니오 | 역추적 |
양쪽 모두 가능한 경우, 하나를 선택하고 다른 하나를 역추적 지점으로 기록한다.
5. 위협 해소의 예시
계획 상황:
- 인과 링크:
move(r1, wp1, wp2) →(robot_at r1 wp2)→ pick(r1, box1, wp2) - 위협 액션:
move(r1, wp2, wp3)(robot_at r1 wp2를 삭제)
해소:
- 승격:
move(r1, wp2, wp3)≺move(r1, wp1, wp2)— 이는 move가 wp2에서 시작하므로 전제 조건 불일치 가능 → 불가능할 수 있음 - 강등:
pick(r1, box1, wp2)≺move(r1, wp2, wp3)— pick이 먼저 실행 후 이동 → 유효
6. 다중 위협의 처리
하나의 새 액션이 여러 인과 링크를 동시에 위협할 수 있다. 각 위협은 독립적으로 해소해야 하며, 하나의 해소가 다른 위협의 해소와 충돌하면 역추적이 필요하다.
7. 인과 링크의 현대적 활용
인과 링크의 개념은 현대 전방 탐색 플래너에서도 간접적으로 활용된다:
- 랜드마크(Landmark): 모든 유효한 계획에서 반드시 달성되어야 하는 사실로, 인과적 의존 분석에서 도출된다.
- 인과 그래프(Causal Graph): Fast Downward의 SAS+ 표현에서 변수 간의 인과적 의존 관계를 그래프로 표현한다.
- 도움 행동(Helpful Actions): FF 플래너에서 현재 상태의 완화된 계획으로부터 인과적으로 유용한 액션을 식별한다.
8. 참고 문헌
- McAllester, D. & Rosenblitt, D. (1991). “Systematic Nonlinear Planning.” Proceedings of AAAI, 634–639.
- Weld, D. S. (1994). “An Introduction to Least Commitment Planning.” AI Magazine, 15(4), 27–61.
- Ghallab, M., Nau, D., & Traverso, P. (2004). Automated Planning: Theory and Practice. Morgan Kaufmann.