패턴 데이터베이스 휴리스틱 (Pattern Database Heuristics)

1. 개요

패턴 데이터베이스(Pattern Database, PDB) 휴리스틱은 원래 문제의 일부 변수만을 고려하는 추상화된(abstracted) 부분 문제를 완전히 풀어, 그 해 비용을 원래 문제의 휴리스틱으로 사용하는 기법이다. Culberson과 Schaeffer(1998)가 퍼즐 문제에서 도입한 이후, AI 플래닝에서도 효과적으로 활용된다.

2. 원리

2.1 추상화 (Abstraction)

원래 문제에서 일부 변수를 무시(project)하여 더 작은 부분 문제를 생성한다.

\mathcal{P}_{\text{abs}} = \text{project}(\mathcal{P}, \text{pattern})

패턴(pattern)은 주목하는 변수의 부분 집합이다.

사전 계산

추상화된 부분 문제의 모든 상태에 대한 최적 비용을 사전에 계산하여 테이블에 저장한다.

\text{PDB}[s_{\text{abs}}] = h^*(s_{\text{abs}}, G_{\text{abs}})

2.2 휴리스틱 조회

실제 탐색 중 현재 상태를 추상화하고, PDB에서 비용을 조회한다.

h_{\text{PDB}}(s) = \text{PDB}[\text{project}(s)]

허용 가능성

PDB 휴리스틱은 허용 가능(admissible)하다. 추상화된 문제의 최적 비용은 원래 문제의 최적 비용 이하이기 때문이다.

h_{\text{PDB}}(s) \leq h^*(s)

3. 다중 패턴의 결합

여러 패턴의 PDB를 결합하여 더 정보적인 휴리스틱을 구성한다.

3.1 최대값 결합

h(s) = \max_i h_{\text{PDB}_i}(s)

허용 가능하다.

가산 결합 (Additive)

패턴이 서로 독립적(disjoint)이면 합산이 허용 가능하다.

h(s) = \sum_i h_{\text{PDB}_i}(s) \quad \text{(패턴이 disjoint인 경우)}

4. Fast Downward에서의 PDB

Fast Downward 계획기의 SAS+ 표현에서 PDB가 효과적으로 활용된다. 인과 그래프(causal graph) 분석을 통해 의미 있는 패턴을 자동으로 선택한다.

5. 참고 문헌

• Culberson, J., & Schaeffer, J. (1998). “Pattern Databases.” Computational Intelligence, 14(3), 318-334.
• Helmert, M. (2006). “The Fast Downward Planning System.” JAIR, 26, 191-246.
• Ghallab, M., Nau, D., & Traverso, P. (2016). Automated Planning and Acting. Cambridge University Press.