완화 문제를 이용한 휴리스틱 추정 (Heuristic Estimation Using Relaxed Problems)

1. 개요

완화 문제(relaxed problem)는 원래 계획 문제의 제약을 일부 제거하여 더 쉽게 풀 수 있는 문제로, 이 완화된 문제의 해 비용이 원래 문제의 휴리스틱으로 사용된다. 삭제 완화(delete relaxation)가 가장 널리 사용되는 완화 기법이며, FF 계획기의 핵심이다.

2. 삭제 완화 (Delete Relaxation)

2.1 원리

행동의 삭제 효과(delete effects)를 무시하여 문제를 완화한다. 삭제 효과가 없으면 한 번 참이 된 명제는 영원히 참으로 유지되므로, 명제의 달성이 누적되어 계획 생성이 훨씬 쉬워진다.

2.2 형식적 정의

완화된 행동 a^+:
\text{Pre}(a^+) = \text{Pre}(a), \quad \text{Add}(a^+) = \text{Add}(a), \quad \text{Del}(a^+) = \emptyset

완화된 전이 함수:
\gamma^+(s, a) = s \cup \text{Add}(a) \quad \text{if } \text{Pre}(a) \subseteq s

2.3 최적 삭제 완화 해 (h^+)

h^+(s) = \text{완화된 문제의 최적 해 길이}

h^+는 허용 가능(admissible)하나 계산이 NP-hard이므로, 다항 시간 근사가 사용된다.

FF 휴리스틱 (h_{\text{FF}})

FF 계획기의 휴리스틱은 h^+의 다항 시간 근사이다.

계산 과정

1. 완화된 계획 그래프 구성: 삭제 효과를 무시하고 플래닝 그래프를 확장한다.
2. 역추적: 목표에서 시작하여 각 명제를 최초로 달성하는 행동을 선택한다.
3. 완화된 계획 추출: 선택된 행동의 집합이 완화된 계획이다.
4. 휴리스틱 값: 완화된 계획의 행동 수 = h_{\text{FF}}(s)

도움 행동 (Helpful Actions)

h_{\text{FF}} 계산 과정에서 첫 번째 계층에 포함된 행동은 현재 상태에서 목표를 향해 진전을 이루는 행동(helpful actions)으로 식별된다. FF는 이 도움 행동만을 탐색 후보로 제한하여 효율을 높인다.

h_{\max}와 h_{\text{add}}의 도출

플래닝 그래프의 명제 계층에서 각 명제가 처음 등장하는 계층의 인덱스를 비용으로 사용한다.

• h_{\max}(s) = \max_{g \in G} \text{level}(g)
• h_{\text{add}}(s) = \sum_{g \in G} \text{level}(g)

참고 문헌

• Hoffmann, J., & Nebel, B. (2001). “The FF Planning System: Fast Plan Generation Through Heuristic Search.” JAIR, 14, 253-302.
• Ghallab, M., Nau, D., & Traverso, P. (2016). Automated Planning and Acting. Cambridge University Press.